Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Tue, 25 Apr 2023 16:24:19 +0200
From: magnum <>
Subject: Re: Birthday paradox

On 2023-04-23 13:08, Solar Designer wrote:
> On Sun, Apr 23, 2023 at 12:28:27PM +0200, magnum wrote:
>> Oh, I see now I need longer tests because of the speed involved. At
>> 30Gp/s a nano-second timer indeed *is* low resolution. Still, the
>> difference is very small. I now bumped a 2.5 second test to 25 seconds
>> for the below.  Difference still is small and shows "steps" in reported
>> speed.
> Looks like the low resolution timer is what we use for the figures on
> the status line, and it has 1-second resolution in your tests.  (...) 
> I think we should switch to using floating-point inside that function so
> that we do not have to explicitly lower precision (...)
This (fixed now in bleeding) helped a lot.  Here's a few data points 
(this all on nvidia 2080ti):

- Probing the table directly is faster than, or about as fast as, using 
the bitmap - up to about 500 hashes.  For a single (1) hash, it's 4-5% 
faster than best seen with bitmap - even when the tables are in global 
memory (nearly same performance, caches doing their job).
At about 5K hashes, probing directly gets significantly slower than the 
bitmap, when the tables no longer fit in local memory.  Above that, the 
bitmap clearly wins, even where the bitmap no longer fits in local and 
even with poor parameter choices (high FP rates).

Even in the upper end of the spectrum (10M hashes in this case), the 
tables were largely outperformed by nearly any bitmap, even with 1/15 fp 
rate.  I'm a bit surprised by this, as probing directly is less work and 
fewer loads from global - the cache situation should be horrible in both 

- I've seen at least one case where k=3 is much better than the old 
bitmaps:  At 1.5M hashes I got 10891Mp/s with m=16777216 and k=3 whereas 
bleeding-jumbo produced 6686Mp/s using m=8388608 and k=1.
k=5 or 6 was tried but not better than others. k=7 or 8 was never picked 
by my (varying) algorithms so far.

- I have yet to see the old bitmap code outperform the new in any 
discouraging way.  It sometimes wins, but not by far and I'm nowhere 
near finishing my "algo".  Endless testing ahead.


Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.