I have been playing with Lua lately and I have to say that I’m pretty amazed by the simplicity and efficiency of the language!

I am particularly amazed by the way they define data structures for example by treating everything as HashTables (tables in Lua). Until Lua 5.0, every data structures was literally a strict HashTable. Since 5.0, they introduced the new “hybrid” table with every table containing a hash part and an array part. The reason for that is in case you want to store a pair with an integer key, you do not really need the overload of the hashing process when an array would do the job and allow you to store and retrieve the value with a single lookup. However, for avoiding waste of memory, a pair with an integer key n is inserted to the array part of the tables only if at least half the slots between 1 and n are occupied. In that way, a table would not have to create a 1,000,000 empty slots array in case the first key that I am trying to insert is 1,000,000. It would be added to the hash part of the table and moved to the array part if needed later on since the size and structure of the table is recomputed every time the table needs to grow. This is obviously a low-level implementation completely transparent to the user (and even to the virtual machine). The only thing you actually see when using Lua are tables.

A summary of the features and implementation in Lua 5.0 can be found in this paper by the authors of the language.