Re: Lua 5.4-work1 with first class arrays (implementation & benchmarks)

[pocomane <pocomane_7a@...>]

On Wed, Mar 28, 2018 at 6:04 PM, Petri Häkkinen <petrih3@gmail.com> wrote:
> I don't see your point about fairness. If we would be comparing pure Lua version of arrays (or tables with 'n' field), the speed difference vs. native array implemention would be much higher than my benchmarks show and in favor of arrays. Every array insertion/removal would need to update 'n' which would be much, much slower than with arrays or even regular unordered tables.

For what I know, # is O(log(n)) when the sequence has holes, while .n
should be accessed in a costant time. E.g. the following code:

```

local N = 1000000

local a = {}

-- Construct an array with an hole
for i = 1, N do
  if i < N/2 -1 or i > N/2 +1 then
    a[i] = i
    a.n = i
  end
end

-- Time wasted in the loop
local o = os.clock()
for i = 1, N do
  local x = 0
end
o = os.clock()-o

-- Length operator benchmark
local l = os.clock()
for i = 1, N do
  local x = #a
end
l = os.clock()-l

-- Table access benchmark
local k = os.clock()
for i = 1, N do
  local x = a.n
end
k = os.clock()-k

assert(l>k)
print(o,l-o,k-o)
```

on my machine prints: 0.013 0.043 0.011 (they are: time elapsed in
loop, time elapsed in length operator, time elapsed in table key
access). And, actually, the # operator take the same time also on a
table without holes (i.e. skipping the `if i<...`) ...