Re: Fun with table rehash

[Francisco Olarte <folarte@...>]

Egor:

On Wed, Sep 30, 2020 at 6:38 PM Egor Skriptunoff
<egor.skriptunoff@gmail.com> wrote:
> On Wed, Sep 30, 2020 at 5:36 PM Francisco Olarte wrote:
>> I mean, no rehashing involved,
>> just a slower emptyness test.
> Rehashing is involved.
> In my original test uncommenting the "slow" line
> changes the time complexity from linear to quadratic.

Yep, I should have said "I think in my simplified test no rehashing is
involved.". Although the quadratic in your case puzzles me, IIRC
growing the array part is amortized-constant and the hash part should
be untouched by your test.

> Inserting nils into a table might be a very costly operation in Lua :-)

Well, deleting elements really. I'll try to put some finer timing
code, second resolution is bad for asserting quadratic growths, and
test mine, which does not seem to be but can be quadratic ( given my
huge repeat count I would think it is not )......

Yep, mi code shows slowdown, but constant, yours goes quadratic:
    hashonlyfast,    1000000 iter,   0.023440 secs
    hashonlyfast,   10000000 iter,   0.186644 secs
    hashonlyslow,    1000000 iter,   0.057289 secs
    hashonlyslow,   10000000 iter,   0.565756 secs
   hasharrayfast,       1000 iter,   0.000037 secs
   hasharrayfast,      10000 iter,   0.000364 secs
   hasharrayfast,     100000 iter,   0.003283 secs
   hasharrayslow,       1000 iter,   0.000288 secs
   hasharrayslow,      10000 iter,   0.022734 secs
   hasharrayslow,     100000 iter,   2.183576 secs
   hasharrayfast,    1000000 iter,   0.030115 secs
   hasharrayfast,   10000000 iter,   0.317326 secs

Iter counts much lower in your sample to save time.

Curious, maybe because yours needs to grow the array part the code
uses the hash part in some perverse way. The difference on the fast
versions are more or less the expected for a list growth.

Francisco Olarte. Test code, written without much care....

local c = os.clock

local function timeit(f, t,it)
   local s = c()
   f(it)
   local e = c()
   print(string.format("%16s, %10d iter, %10.6f secs", t, it, e-s))
end

local function mine1(it)
   local t = {}
   for i=1,it do t[-i]=nil end
end

local function mine2(it)
   local t = {}
   t.slow = 1
   for i=1,it do t[-i]=nil end
end

local function egor1(it)
   local t = {}
   for i=1,it do t[i],t[-i]=1,nil end
end
local function egor2(it)
   local t = {}
   t.slow = 1
   for i=1,it do t[i],t[-i]=1,nil end
end

timeit(mine1, "hashonlyfast", 1E6)
timeit(mine1, "hashonlyfast", 1E7)
timeit(mine2, "hashonlyslow", 1E6)
timeit(mine2, "hashonlyslow", 1E7)

timeit(egor1, "hasharrayfast", 1E3)
timeit(egor1, "hasharrayfast", 1E4)
timeit(egor1, "hasharrayfast", 1E5)
timeit(egor2, "hasharrayslow", 1E3)
timeit(egor2, "hasharrayslow", 1E4)
timeit(egor2, "hasharrayslow", 1E5)

timeit(egor1, "hasharrayfast", 1E6)
timeit(egor1, "hasharrayfast", 1E7)