[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Question about accessing Lua tables and arrays faster
- From: Leo Romanoff <romixlev@...>
- Date: Thu, 25 Jul 2013 08:00:00 -0700 (PDT)
Here comes a third part of my questions about using Lua as a target language/runtime for other dynamic and static langauges.
This time I'd like to discuss the peformance of accessing Lua tables from Lua when tables are used as maps or as arrays.
- Many static languages with a type system allow for definition of structural types (e.g. structs in C, classes in Java, etc). Access to the fields of such types is usually very cheap in those languages. If one maps such structural types to Lua tables (and this is the most obvious solution, I guess), then sematically everything is fine. But now every access to a field results in a table lookup, which introduces some overhead. It would be nice to have a faster way of accessing fields of tables.
- Many high-performance applications work intensively with arrays. Currently, Lua uses the same datatype, namely tables, for both arrays and maps. Accessing arrays from Lua is not extremely fast currently. (Lua interpreter does not use even those lua_rawseti/lua_rawgeti functions, IIRC. Only C libs for Lua can do it). It would be nice to have a faster way of operating on arrays in Lua.
BTW, I did some experiments where I create an array of 1000000 elements and then perform a 1000 iterations over it, touching each element and assigning a new value to it or incrementing its current value. I implemented the same algorithm in pure Lua, as a C library for Lua which uses lua_rawseti/lua_rawgeti, and as a C program. The outcome is that pure Lua solution is the slowest, the C library for Lua is roughly 1.5 times faster and C version is about 14.5 times faster than pure Lua solution.
Questions about arrays:
- Would it make sense to have an additional dedicated type for arrays as it is usually the case in most programming languages? Would it make things any faster, e.g. because it could use a more efficient internal representation? Or would it still be rather slow, because the problem is not the internal representation of arrays but Lua VM itself?
- Are there any well-known tricks besides what I used above in my experiments to process Lua arrays faster? And I don't mean here a purely FFI-based solutions, which most likely could be almost as efficient as C version. I mean Lua tricks.
Questions about tables used as maps:
- The interesting thing about structs/classes in static programming languages is that their structure is known in advance after their definition and it never changes. In Lua terms it would mean that a corresponding table has a predefined set of keys and this set of keys never changes. This is a very useful information which could be used for optimizations, I'd say.
So, my question is: could Lua make use of this fact to make access to such tables faster, e.g. by eliminating key lookups and replacing them by a more efficient indexed access (i.e. we know that field X is at offset 0, field Y at offset 4, etc) similar to what C compiler does or something like that? I think some JavaSctipt JITs and probably LuaJIT do something like this. But could Lua VM do a similar thing when it determines that a structure of the table never changes after a certain point in time?