[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20230422220901.GA16721@openwall.com>
Date: Sun, 23 Apr 2023 00:09:01 +0200
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: Birthday paradox
On Tue, Apr 18, 2023 at 11:12:31PM +0200, Solar Designer wrote:
> On Tue, Apr 18, 2023 at 10:31:04PM +0200, magnum wrote:
> > Like we discussed recently, the modulo operations are compile-time
> > constants so should be fairly optimized - but perhaps they are still
> > relatively expensive?
>
> If optimized by the compiler, their latency is probably that of two
> consecutive integer multiplies plus a little more. We could help the
> compiler optimize further (removing that "a little more" part) by doing
> the reciprocals explicitly targeting the 31-bit range if/when it's
> sufficient for us. It costs a few more operations to support the full
> 32-bit range, as I figured out and explained on that recent GitHub PR
> comments. However, the performance difference is probably small.
>
> We could also verify whether the compiler optimizes this. One way would
> be to look at the ISA. Another would be to use a runtime variable for
> the divisor and see whether and how much slower it would be - in the
> full program or/and in an isolated test case.
>
> Oh! I just realized that we're dividing a 64-bit number here. My tests
> and reasoning above were for 32-bit to 32-bit (or to 31-bit). It should
> be most costly for 64-bit, although conceptually the same kind of
> optimizations would apply (needing 128-bit or maybe 96-bit temporarily,
> which is probably still faster than a division).
Correction: the optimizations for 31-bit applied to input range, not the
result, so we'd need to mask the hash value from 32 to 31 bits to use
them, which would cost an extra AND. The corresponding savings are one
32-bit subtraction and one 64-bit shift. So the net savings are in the
avoided shift operation.
I think it's similar for 64-bit vs. 63-bit.
Alexander
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.
