Re: Question about accessing Lua tables and arrays faster

[Leo Romanoff <romixlev@...>]

----- Ursprüngliche Message -----

> Von: Steve Litt <slitt@troubleshooters.com>
> An: lua-l@lists.lua.org
> CC: Leo Romanoff <romixlev@yahoo.com>
> Gesendet: 17:20 Donnerstag, 25.Juli 2013
> Betreff: Re: Question about accessing Lua tables and arrays faster
> 
> On Thu, 25 Jul 2013 08:00:00 -0700 (PDT)
> Leo Romanoff <romixlev@yahoo.com> wrote:
>>  - 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. 
> 
> Hi Leo,
> 
> Comparing any interpreter to C is certain to yield disappointing
> results. A better test would have been to compare pure Lua to Perl
> arrays, Python lists, and whatever Ruby uses for arrays (I long since
> forgot). If *those* are faster than Lua in the algorithm you mention,
> then we have something to talk about.

Just out of curiosity I created versions of the same algorithm for Perl and Python as you suggested.

The outcome is: They are slightly faster by may be 5%-10% than Lua for this benchmark.

Then I also implemented a C library for Lua, which implements vectors of scalars (doubles).
Actually, I used the code from PIL (http://www.lua.org/pil/28.1.html). I expected a great speedup.
But here the results were much more interesting:

- Yes, C-based version consumes less memory. This is a win
- But using it from Lua results in a very slow execution! Namely:
1) The fastest results are produced by a simple non OOP version, without metatables. And it is about 5 times slower than pure Lua solution.
2) If I start using metatables, it becomes much, much slower due to usage luaL_checkudata. There were already problems reports about exactly this problem on this mailing list in 2012. There is also a workaround provided by LHF (http://lua-users.org/lists/lua-l/2011-12/msg00039.html). But even with this optimization it is almost 1.5 - 2 times slower than the version without metatables
3) And the version where __index and __newindex are overloaded in the metatable to use C-functions from the library is the slowest.

I was actually quite surprised that using a C library version turned out to be so slow. But this is most likely due to the fact that the overhead due to invocation of C functions is too high compared to the actual action performed (i.e. setting/getting a single element). 

But if C-based implementations are so slow when used in a "per element" way from Lua, then the only remaining option to get really fast arrays is probably to have a C library that performs iteration over elements on the C side. I.e. something like a "map" function. But here I expect another problem: if the argument function of "map" (i.e. a function to be applied to each element) is a Lua function, then the overhead of invoking it from C will probably also kill performance. And if both iteration and element transformation is implemented in C, then it probably gets faster, but you loose the possibility to use Lua for specifying what should be done with each element and hard-code it in your C library instead, which is not so good IMHO.

-Leo