Allow non-power-of-2 signature cache sizes #9533

pull sipa wants to merge 1 commits into bitcoin:master from sipa:anysigcachesize changing 1 files +11 −18

sipa commented at 6:21 PM on January 12, 2017: member

This uses the fast reduction from http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ instead of a modulus operator to quickly compute (nearly) uniformly distributed values within range.
Allow non-power-of-2 signature cache sizes 7482781347
JeremyRubin commented at 6:27 PM on January 12, 2017: contributor

Concept ACK. Great find!
fanquake added the label Refactoring on Jan 12, 2017
fanquake commented at 10:19 PM on January 12, 2017: member

Travis failure is in keypool.py, so seemingly unrelated.

in src/cuckoocache.h:None in 7482781347

 224 | +                 (uint32_t)((hash_function.template operator()<2>(e) * (uint64_t)size) >> 32),
 225 | +                 (uint32_t)((hash_function.template operator()<3>(e) * (uint64_t)size) >> 32),
 226 | +                 (uint32_t)((hash_function.template operator()<4>(e) * (uint64_t)size) >> 32),
 227 | +                 (uint32_t)((hash_function.template operator()<5>(e) * (uint64_t)size) >> 32),
 228 | +                 (uint32_t)((hash_function.template operator()<6>(e) * (uint64_t)size) >> 32),
 229 | +                 (uint32_t)((hash_function.template operator()<7>(e) * (uint64_t)size) >> 32)}};

dcousens commented at 4:33 AM on January 13, 2017:

maybe a small inline function/macro would be easier to read than this?

gmaxwell commented at 7:33 PM on January 21, 2017: contributor

utACK.
gmaxwell commented at 7:39 PM on January 21, 2017: contributor

someone should make sure to benchmark this change.
JeremyRubin commented at 8:37 PM on January 22, 2017: contributor

Just dropping a note here to assist other reviewers that you should also verify that InitSignatureCache makes no power-of-2 assumptions. I wrote it not to make such assumptions, and it doesn't, but it is aware that the cache may end up not using it's whole memory budget.
sipa commented at 6:44 PM on March 29, 2017: member

Anything needed here?
JeremyRubin commented at 7:49 PM on March 29, 2017: contributor

Maybe a benchmark?

I'd previously done a simulation on division v.s. masking and didn't see a difference, so I'm sure that this is fine...
sdaftuar commented at 2:36 PM on March 30, 2017: member

utACK
laanwj merged this on Apr 3, 2017
laanwj closed this on Apr 3, 2017
laanwj referenced this in commit cb598cfba1 on Apr 3, 2017
PastaPastaPasta referenced this in commit 7f111e100f on May 10, 2019
PastaPastaPasta referenced this in commit 8afe749302 on May 15, 2019
PastaPastaPasta referenced this in commit f471b75aec on May 20, 2019
PastaPastaPasta referenced this in commit 65aaa95265 on May 21, 2019
barrystyle referenced this in commit 9b32c0e0a0 on Jan 22, 2020
zkbot referenced this in commit bb6e5fad4c on Apr 20, 2021
DrahtBot locked this on Sep 8, 2021

Contributors

Labels