Add an explanation of quickly hashing onto a non-power of two range. #10577

gmaxwell commented at 11:46 PM on June 11, 2017: contributor

In Olaoluwa Osuntokun's recent protocol proposal they were using a mod in an inner loop. I wanted to suggest a normative protocol change to use the trick we use here, but to find an explanation of it I had to dig up the PR on github. After I posted about it several other developers commented that it was very interesting and they were unaware of it.

I think ideally the code should be self documenting and help educate other contributors about non-obvious techniques that we use. So I've written a description of the technique with citations for future reference.

fanquake added the label Docs and Output on Jun 12, 2017

laanwj commented at 7:36 AM on June 12, 2017: member

math-review-ACK https://github.com/bitcoin/bitcoin/pull/10577/commits/3dedf120f2fa51833e6587365d1ad94990189343, thanks for adding documentation.

in src/cuckoocache.h:210 in 3dedf120f2 outdated

 205 | @@ -206,6 +206,37 @@ class cache
 206 |      /** compute_hashes is convenience for not having to write out this
 207 |       * expression everywhere we use the hash values of an Element.
 208 |       *
 209 | +     * We need to map the 32-bit input hash onto a hash bucket in a range [0, size) in a
 210 | +     *  manner which preserves as much of the hashe's uniformity as possible.  Ideally

sipa commented at 10:27 PM on June 12, 2017:

typo: hashe's

in src/cuckoocache.h:211 in 3dedf120f2 outdated

 205 | @@ -206,6 +206,37 @@ class cache
 206 |      /** compute_hashes is convenience for not having to write out this
 207 |       * expression everywhere we use the hash values of an Element.
 208 |       *
 209 | +     * We need to map the 32-bit input hash onto a hash bucket in a range [0, size) in a
 210 | +     *  manner which preserves as much of the hashe's uniformity as possible.  Ideally
 211 | +     *  would bitmask but the size is usually not a power of two.

sipa commented at 10:27 PM on June 12, 2017:

typo: "Ideally would bitmask" is not grammatical

in src/cuckoocache.h:214 in 3dedf120f2 outdated

 205 | @@ -206,6 +206,37 @@ class cache
 206 |      /** compute_hashes is convenience for not having to write out this
 207 |       * expression everywhere we use the hash values of an Element.
 208 |       *
 209 | +     * We need to map the 32-bit input hash onto a hash bucket in a range [0, size) in a
 210 | +     *  manner which preserves as much of the hashe's uniformity as possible.  Ideally
 211 | +     *  would bitmask but the size is usually not a power of two.
 212 | +     *
 213 | +     * The naive approach would be to use a mod -- which isn't perfectly uniform but so
 214 | +     *  long as the hash is much larger than size its not that bad.  Unfortunately,

sipa commented at 10:27 PM on June 12, 2017:

typo: its

sipa commented at 10:29 PM on June 12, 2017: member

ACK, but some typos

Add an explanation of quickly hashing onto a non-power of two range.

In Olaoluwa Osuntokun's recent protocol proposal they were using a
 mod in an inner loop.  I wanted to suggest a normative protocol
 change to use the trick we use here, but to find an explanation
 of it I had to dig up the PR on github.  After I posted about it
 several other developers commented that it was very interesting
 and they were unaware of it.

I think ideally the code should be self documenting and help
 educate other contributors about non-obvious techniques that
 we use.  So I've written a description of the technique with
 citations for future reference.

dd869c60ca

laanwj approved

sipa commented at 5:57 PM on June 13, 2017: member

utACK dd869c60ca069fa3eea3dd1aab977b8a10e05f2f

MarcoFalke commented at 8:58 AM on June 18, 2017: member

utACK dd869c60ca069fa3eea3dd1aab977b8a10e05f2f

MarcoFalke assigned laanwj on Jun 24, 2017

laanwj merged this on Jun 24, 2017

laanwj closed this on Jun 24, 2017

laanwj referenced this in commit 232508fe0f on Jun 24, 2017

markblundeberg referenced this in commit f760e536af on Jun 21, 2019

jtoomim referenced this in commit 45ffdb9fb0 on Jun 29, 2019

PastaPastaPasta referenced this in commit fefa0faff7 on Jul 6, 2019

PastaPastaPasta referenced this in commit cc1c973e16 on Jul 8, 2019

PastaPastaPasta referenced this in commit 9ec0827670 on Jul 9, 2019

PastaPastaPasta referenced this in commit f4c0858b49 on Jul 11, 2019

barrystyle referenced this in commit 381a704079 on Jan 22, 2020

zkbot referenced this in commit bb6e5fad4c on Apr 20, 2021

DrahtBot locked this on Sep 8, 2021