Efficient array lookup in C

I'm trying to write a simple language interpreter for a custom language in C. I want to use C over C++ due to C's simplicity.

The things I'm not sure how to do in C is, storing variables and variable lookups.

I was planning to store variables in an array, but I think I'd need a variable sized array.

I also don't know an efficient way to lookup variables from an array besides just looping through it.

So I'd like to know, what is an efficient way of creating a variable sized array? How does Python or Ruby or Go store and retrieve variables efficiently?

> How does Python or Ruby or Go store and retrieve variables efficiently?

Python and Ruby use hash-tables: the name of the variable is translated into an integer, and that integer is used as index into an array. It can always happen that several names collide (translate to the same integer), so that needs to be taken into account by allowing several bindings from name to value at the same slot, but there will only be a few to check for each name.

Go is compiled, so the variable is translated to an address (either static or an offset with respect to the stack—or frame—pointer) at compile-time.

> what is an efficient way of creating a variable sized array?

If you decided to do that, you would use malloc and realloc.

In the case of resizing the array of buckets of a hash-table, realloc is unfortunately not useful because all the keys in the old array of buckets need to be re-hashed one by one to find where they go in the new array. If you know the maximum size of programs that will be interpreted by your interpreter, you can allocate the hash-table directly at the size that works for the largest programs, and avoid writing the hash-table resizing function.

I think you can get really carried away when trying to implement a variable-storage yourself. I would recommend you use an existing hashmap like uthash just to see how it works out for you conceptually and encapsulate it as good as possible. If it turns out to be a bottleneck, you can come back and optimize later.

I am somewhat confident to say, that at that time, you will not pick a dynamically expanding array. You have to consider that you need to implement a string-based search to find a variable by name, so you will have a hard time doing better than a hashmap with a dynamically expanding array. Search on it would be O(n) if unsorted and O(log n) if sorted, whereas the hashmap has O(1) search complexity.