Author lemburg
Recipients Arach, Arfrever, Huzaifa.Sidhpurwala, Jim.Jewett, Mark.Shannon, PaulMcMillan, Zhiping.Deng, alex, barry, benjamin.peterson, christian.heimes, dmalcolm, eric.snow, fx5, georg.brandl, grahamd, gregory.p.smith, gvanrossum, gz, haypo, jcea, lemburg, mark.dickinson, merwok, neologix, pitrou, skrah, terry.reedy, tim.peters, v+python, zbysz
Date 2012-01-19.15:11:54
SpamBayes Score 0.000883374
Marked as misclassified No
Message-id <4F1832B4.4040603@egenix.com>
In-reply-to <CAMpsgwbsVX0g9o40EvjXbXt2FBugdd35AkH7zFOPVf99VNqB8A@mail.gmail.com>
Content
STINNER Victor wrote:
> 
> I tried the collision counting with a low number of collisions:
> ... no false positives with a limit of 50 collisions ...

Thanks for running those tests. Looks like a limit lower than 1000
would already do just fine.

Some timings showing how long it would take to hit a limit:

# 100
python2.7 -m timeit -n 100 "dict((x*(2**64 - 1), 1) for x in xrange(1, 100))"
100 loops, best of 3: 297 usec per loop

# 250
python2.7 -m timeit -n 100 "dict((x*(2**64 - 1), 1) for x in xrange(1, 250))"
100 loops, best of 3: 1.46 msec per loop

# 500
python2.7 -m timeit -n 100 "dict((x*(2**64 - 1), 1) for x in xrange(1, 500))"
100 loops, best of 3: 5.73 msec per loop

# 750
python2.7 -m timeit -n 100 "dict((x*(2**64 - 1), 1) for x in xrange(1, 750))"
100 loops, best of 3: 12.7 msec per loop

# 1000
python2.7 -m timeit -n 100 "dict((x*(2**64 - 1), 1) for x in xrange(1, 1000))"
100 loops, best of 3: 22.4 msec per loop

These timings have to matched against the size of the payload
needed to trigger those limits.

In any case, the limit needs to be configurable like the hash seed
in the randomization patch.
History
Date User Action Args
2012-01-19 15:11:55lemburgsetrecipients: + lemburg, gvanrossum, tim.peters, barry, georg.brandl, terry.reedy, gregory.p.smith, jcea, mark.dickinson, pitrou, haypo, christian.heimes, benjamin.peterson, merwok, grahamd, Arfrever, v+python, alex, zbysz, skrah, dmalcolm, gz, neologix, Arach, Mark.Shannon, eric.snow, Zhiping.Deng, Huzaifa.Sidhpurwala, Jim.Jewett, PaulMcMillan, fx5
2012-01-19 15:11:54lemburglinkissue13703 messages
2012-01-19 15:11:54lemburgcreate