Re: Hash Table Collisions (n.runs-SA-2011.004)

[David Favro <lua@...>]

On 01/05/2012 12:33 AM, David Favro wrote:
> Summary of times:
> 
> N fields  Body size  Non-colliding  Colliding
>  30,840    1024k        11s            91s
>  61,500    2042k        39s           359s
> 123,000    4084k       149s           ???

This site turned out to be a bad example: I was suspicious of the
non-colliding times being so long -- O(1) vs. O(n^2) should show a more
marked difference, so I did a little tracing and found that I had left an
option to log all post-fields turned on; after turning it off, the
differences are much more stark:
N fields  Body size  Non-colliding  Colliding
 30,840    1024k        <1s            77s
 61,500    2042k        <1s           310s
123,000    4084k         1s           ???

-- David