Re: Performance problem with 0-based arrays

["John Logsdon" <j.logsdon@...>]

Interesting to compare 5.1.5, 5.2.4, 5.3.3 and luajit 2,1.0-beta3 with the
following modified program. Everything is moved to local within the
function and a loop is because (particularly with luajit) there is
substantial variablity.

lua5.1 and 5.2 show an average ratio of about 28 with 0-based the slower,
lua5.3 shows an average 16 while for luajit they are both essentially the
same but with much larger sd/avg. 5.3 is the most consistent.

I ran these with 100 loops of a 10000 size table (the default 100000 took
too long to run).

[code]
local loop = tonumber(arg[1]) or 1
local game_size = tonumber(arg[2]) or 1000000
local initialize_game_field
function initialize_game_field(base_index,game_size)
   local game_field={}
   for j = base_index, base_index + game_size - 1 do
      game_field[j] = "white"
   end
   for j = base_index + game_size, base_index + 2*game_size - 1 do
      game_field[j] = nil
   end
   for j = base_index + 2*game_size, base_index + 3*game_size - 1 do
      game_field[j] = "black"
   end
end
local sum,sum2,ds0,ds1,maxv,minv=0,0,0,0,-1e6,1e6
for i=1,loop do
   local t=os.clock()
   initialize_game_field(0,game_size)
   local dt0=os.clock()-t
   t=os.clock()
   initialize_game_field(1,game_size)
   local dt1=os.clock()-t
   local ratio=dt0/dt1
 --  print(i,"base 0",dt0,"base 1",dt1,"ratio base0/base1",ratio)
   sum=sum+ratio
   sum2=sum2+ratio^2
   maxv=math.max(maxv,ratio)
   minv=math.min(minv,ratio)
   ds0=ds0+dt0
   ds1=ds1+dt1
end
local avg=sum/loop
local sd=math.sqrt((sum2-loop*avg^2)/(loop-1))
local cv=sd/avg
ds0,ds1=ds0/loop,ds1/loop
local function dp4(x) return string.format("%.4g",x) end
print("Avg1",dp4(ds1),"avg0",dp4(ds0),"base0/base1 ratio:
mean",dp4(avg),"sd",dp4(sd),"cv",dp4(cv),"min",dp4(minv),"max",dp4(maxv),"range",dp4(maxv-minv))
[/code]

Results:

lua5.1 zero.lua 100 10000
Avg1    0.0009263       avg0    0.02546 base0/base1 ratio: mean 27.57   sd
     1.925   cv      0.06982 min     20.83   max     31.52   range   10.69

lua5.2 zero.lua 100 10000
Avg1    0.0009695       avg0    0.02757 base0/base1 ratio: mean 28.45   sd
     0.4203  cv      0.01478 min     26.39   max     29.12   range   2.729

lua5.3 zero.lua 100 10000
Avg1    0.0009923       avg0    0.01605 base0/base1 ratio: mean 16.18   sd
     0.2056  cv      0.01271 min     14.71   max     16.54   range   1.829

/usr/bin/luajit zero.lua 100 10000
Avg1    9.411e-05       avg0    9.223e-05       base0/base1 ratio: mean
1.022   sd      0.3146  cv      0.3077  min     0.4485  max     2.084  
range   1.636




> Hi!
>
> The "Programming in Lua" book says:
>> we can start the indices of an array with any number that pleases us
>
> These words seem to be very misleading.
> Sometimes Lua has a terrible performance problem with 0-based arrays.
> In the following simple example 0-based array is 1000+ times slower than
> 1-based array!
>
> $ cat program.lua
> local game_field = {}
> local game_size = 1000000
> local base_index = tonumber(arg[1])
> print("Array indices start with "..base_index)
>
> local function initialize_game_field()
>    for j = base_index, base_index + game_size - 1 do
>       game_field[j] = "white"
>    end
>    for j = base_index + game_size, base_index + 2*game_size - 1 do
>       game_field[j] = nil
>    end
>    for j = base_index + 2*game_size, base_index + 3*game_size - 1 do
>       game_field[j] = "black"
>    end
> end
>
> initialize_game_field()
>
> $ lua -v
> Lua 5.4.2  Copyright (C) 1994-2020 Lua.org, PUC-Rio
>
> $ time lua program.lua 1
> Array indices start with 1
>
> real    0m0.400s
> user    0m0.360s
> sys     0m0.036s
>
> $ time lua program.lua 0
> Array indices start with 0
>
> real    24m12.488s
> user    24m8.532s
> sys     0m2.376s
>
>
> Is it a bug that will be fixed in the next bugfix release of Lua?
> Or is it an inherent Lua feature every Lua programmer should be aware of?
>