Fun with table rehash

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Fun with table rehash

Egor Skriptunoff-2
Hi!

This program runs very fast:

local t = {}
-- t.slow = true
for j = 1, 1e6 do t[j], t[-j] = 0, nil end

But if you uncomment the line with the "slow" option...

Reply | Threaded
Open this post in threaded view
|

Re: EXT SENDER - Fun with table rehash

Chodera, Ian
No appreciable difference on my machine (Dell Precision i7 about 4 years old) running Lua 5.2 - both take about 1.078 seconds

Ian


From: Egor Skriptunoff <[hidden email]>
Sent: 30 September 2020 12:23
To: Lua mailing list <[hidden email]>
Subject: EXT SENDER - Fun with table rehash
 
Hi!

This program runs very fast:

local t = {}
-- t.slow = true
for j = 1, 1e6 do t[j], t[-j] = 0, nil end

But if you uncomment the line with the "slow" option...

Reply | Threaded
Open this post in threaded view
|

Re: EXT SENDER - Fun with table rehash

Roberto Ierusalimschy
> No appreciable difference on my machine (Dell Precision i7 about 4
> years old) running Lua 5.2 - both take about 1.078 seconds

For some strange reason, in Lua 5.2 it seems that you have to change
«t[j], t[-j] = 0, nil» to «t[j] = 0; t[-j] = nil».

-- Roberto
Reply | Threaded
Open this post in threaded view
|

Re: Fun with table rehash

Francisco Olarte
In reply to this post by Egor Skriptunoff-2
On Wed, Sep 30, 2020 at 3:14 PM Egor Skriptunoff
<[hidden email]> wrote:
> This program runs very fast:
> local t = {}
> -- t.slow = true
> for j = 1, 1e6 do t[j], t[-j] = 0, nil end
> But if you uncomment the line with the "slow" option...

Not too precise but in my case, with a simpler test:

> local s=os.time();local t={};t.a=1;for j=1,100000000 do t[-j]=nill end;print(os.time()-s)
6
> local s=os.time();local t={};for j=1,100000000 do t[-j]=nill end;print(os.time()-s)
2
> local s=os.time();local t={};t[0]=1;for j=1,100000000 do t[-j]=nill end;print(os.time()-s)
7
> local s=os.time();local t={};t[1]=1;for j=1,100000000 do t[-j]=nill end;print(os.time()-s)
3

given i and iii times are the same within the timing method error, as
are ii and iv, I will suspect that deleting an element when the hash
part is empty is very fast, as there is nothing to check, but when the
hash part is not the code needs at least to hash j and look it up,
which will dwarf the rest of the code. I mean, no rehashing involved,
just a slower emptyness test.


Francisco Olarte.
Reply | Threaded
Open this post in threaded view
|

Re: Fun with table rehash

Francisco Olarte
This is why I like mandatory declarations:

On Wed, Sep 30, 2020 at 4:35 PM Francisco Olarte <[hidden email]> wrote:
> > local s=os.time();local t={};t.a=1;for j=1,100000000 do t[-j]=nill end;print(os.time()-s)
> 6
> > local s=os.time();local t={};for j=1,100000000 do t[-j]=nill end;print(os.time()-s)
> 2
> > local s=os.time();local t={};t[0]=1;for j=1,100000000 do t[-j]=nill end;print(os.time()-s)
> 7
> > local s=os.time();local t={};t[1]=1;for j=1,100000000 do t[-j]=nill end;print(os.time()-s)
> 3

Of course on a just started interpreter nill==nil, anyway, I redid it
properly, similar results

> local s=os.time();local t={};for j=1,100000000 do t[-j]=nil end;print(os.time()-s)
2
> local s=os.time();local t={};t[0]=1;for j=1,100000000 do t[-j]=nil end;print(os.time()-s)
5
> local s=os.time();local t={};t[1]=1;for j=1,100000000 do t[-j]=nil end;print(os.time()-s)
2
> local s=os.time();local t={};t.a=1;for j=1,100000000 do t[-j]=nil end;print(os.time()-s)
6

Francisco "ChubbyFingers" Olarte.
Reply | Threaded
Open this post in threaded view
|

Re: Fun with table rehash

Egor Skriptunoff-2
In reply to this post by Francisco Olarte
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.

Inserting nils into a table might be a very costly operation in Lua :-)
Reply | Threaded
Open this post in threaded view
|

Re: Fun with table rehash

Francisco Olarte
Egor:

On Wed, Sep 30, 2020 at 6:38 PM Egor Skriptunoff
<[hidden email]> 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)
Reply | Threaded
Open this post in threaded view
|

Re: Fun with table rehash

Paul Ducklin
In reply to this post by Egor Skriptunoff-2
Lua 5.4.1 on slackware-current (64-bit libraries only, Linux kernel 5.4.69) with 16GB RAM, nothing else of significance going on.

With the non-integer key ‘slow’ in the table:

77.9 seconds

Without it:

33.8 seconds

That ratio of about 2.3-to-1 (78/34) shows up repeatedly.

(I upped the loop to “j=1,1e9” otherwise it ran too quickly to give useful measurements, though at “j=1.1e8” I got similar results with 7.6sec and 3.3 sec.)



> On 30 Sep 2020, at 14:14, Egor Skriptunoff <[hidden email]> wrote:
>
> Hi!
>
> This program runs very fast:
>
> local t = {}
> -- t.slow = true
> for j = 1, 1e6 do t[j], t[-j] = 0, nil end
>
> But if you uncomment the line with the "slow" option...
>