|
Microbenchmarks are fun but silly. I tried to write a similar one for Lua, but LuaJIT ultimately recognized the program was useless and boiled it down to a 3 instruction loop: loop:
add ebp, 1
cmp ebp, 10000000
jle loop
Anyway, in regards to your results, I could be wrong, but I think I read somewhere that LuaJIT uses linear search for tiny tables for this reason. Dunno what the threshold is, if there is one. The performance then would be similar to an alist, but saving a few bytes and cycles by not needing to deal with the extra list pointers and indirection.> Also, just to clarify, alist and property lists have a different behavior than hash-tables, namely that the sequential access allows you to shadow values from another list: if you write (cons (cons 'a b) older-alist), you have a new list where the value for key 'a is b, and where values for other keys are those found in older-list (even though older-list also contains key 'a). Oh yes, doesn't emacs make good use of this trick for its configuration variables? You can get the same effect with Lua's metatables, however, with a little elbow grease: parent = { a = "beep", b = "boop" }
print(parent.a) --> beep
print(parent.b) --> boop
child = { a = "poing" }
print(child.a) --> poing
print(child.b) --> nil
mt = { __index = parent }
setmetatable(child, mt)
print(child.a) --> poing
print(child.b) --> boop
Not quite as easy as "cons", but very flexible; __index can be another table to searched if the lookup on the child fails (which in turn can have its own parent and so on), but it can also be a "metamethod" that is called whenever a lookup fails and can then do arbitrary things. A neat example off the top of my head: OpenGL has the peculiarity that you do not know the address of any of its functions until runtime, requiring a program to call a lookup function for each function to get a usable pointer. Declaring FFI function prototypes for many OpenGL functions is not such a big deal, but looking up hundreds of functions that you will never use can add significantly to startup time. So someone (possibly an HN user?) wrote an OpenGL FFI library that uses the __index metamethod in a clever way; the first time a function like "GL.CreateShader" is called, the lookup fails, and the __index metamethod mangles the index name a bit and in turn calls (on Windows) the C function wglGetProcAddress to look up its address, which it then stores in the original table. Using this library, you can write code that uses GL functions willy-nilly, and their addresses will automatically be looked up at runtime the first time they are used.Sure, you can do the same thing in any language with macros or a preprocessor, but is that cool or what? |
The loop itself is quite useless, why wasn't it also removed ? (Just kidding)
I don't have anything agains Lua or hash tables in principle. And of course tables are used in practice in CL code, but they aren't the primary data-structure.
> __index can be another table to searched if the lookup on the child fails (which in turn can have its own parent and so on)
> the first time a function like "GL.CreateShader" is called, the lookup fails, and the __index metamethod mangles the index name a bit and in turn calls (on Windows) the C function wglGetProcAddress to look up its address, which it then stores in the original table. Using this library, you can write code that uses GL functions willy-nilly, and their addresses will automatically be looked up at runtime the first time they are used.
So, it is an association list implemented using tables, where links are given by the __index property, using a metatable.
So maybe it is convenient after all to have a very simple data-structure like cons in a language and let more complex data be implemented with it, instead of the opposite.