6 ms·
A fast alternative to the modulo reduction (2016)
- wizzwizz4 5y ago> I also suspect that in many cases, given a list of IDs you can get reasonable results by doing just ID % . In this case, you can get away without applying a hashing transformation. With your trick, you do need this. Reverse the bits before applying the trick.
- thxg 5y agoYes, although the trick is used in the first place in order to replace a 6-cycle division by a 1-cycle multiplication (on x86_64, assuming no CPU stalls). Roughly, in order to still make it a net positive, we have a 4-cycles budget for additional operations. That's very tight for reversing the bits of a uint32_t.
- nullc 5y ago> used in the first place in order to replace a 6-cycle division by a 1-cycle multiplication Look a generation or two back and you'll see that the division is a LOT slower than 6 cycles, too. But it should be noted that if the modulus is a compile time constant the compiler will turn the % into a multiply and add. The riscv bitmanip instruction set has permutes that can reverse the bits in a word (along with other useful permutations). ... still doesn't exist in an actual asic yet. Maybe some time in my life we'll get it on common platforms.
- timdaub 5y agoI recently discovered a problem in this domain of modulo reduction. I'm looking for a way to create a smaller index for Ethereum accounts that are in the range of 0 to 2^160 [1]. It's mainly to reduce gas storage cost [3]. Most folks I asked about it, ended up concluding that I'll end up with this pidgeon hole effect where it'll become likely that an index is suggested multiple times [2]. It may not be super cryptographically-sophisticated: But what I want is a hash function that's (at least) somewhat aware of collisions without using too much storage. Bloomfilters were recommended - but it seems they need to much storage too. I need to be able to map Ethereum accounts to a smaller sized domain e.g. 0 to 2^32 to safe storage costs in smart contracts. Since I asked on Stackexchange, the problem has become kind of stale and I stopped working on it. But it's fascinating and I should continue to dive deeper... Interesting article! Thanks - 1: https://crypto.stackexchange.com/questions/91742/can-there-be-an-injective-function-that-maps-a-large-set-of-integers-to-a-smalle https://crypto.stackexchange.com/questions/91742/can-there-b... - 2: https://en.wikipedia.org/wiki/Pigeonhole_principle https://en.wikipedia.org/wiki/Pigeonhole_principle - 3: https://github.com/rugpullindex/honeybatcher https://github.com/rugpullindex/honeybatcher
- FreakLegion 5y agoThere are smaller alternatives to Bloom filters, if size is the only issue. A few examples: - https://github.com/0xcb/Golomb-coded-map https://github.com/0xcb/Golomb-coded-map - https://github.com/efficient/cuckoofilter https://github.com/efficient/cuckoofilter - https://github.com/FastFilter/xor_singleheader/ https://github.com/FastFilter/xor_singleheader/
- timdaub 5y agoThanks, helpful links. I've looked into them and found them a great fit for my awesome-ethereum-rollups list [1]. - 1 https://github.com/rugpullindex/awesome-ethereum-rollups#membership-proof-data-structures https://github.com/rugpullindex/awesome-ethereum-rollups#mem...
- deepsun 5y agoWhat about type conversion? The values were `uint32_t`, but converted to `uint64_t`, doesn't that consume cycles as well, or for one operation, optimizer compiles that away?
- wizzwizz4 5y agoSome CPUs have a single instruction for “multiply but get the high word”.
- flohofwoe 5y agoMultiplying two 32-bit numbers yields a 64-bit result down on the CPU instruction level, so the type conversion is basically built in, details may differ by CPU, but here's the vanilla x86 multiply which spreads the results over two registers: https://c9x.me/x86/html/file_module_x86_id_210.html https://c9x.me/x86/html/file_module_x86_id_210.html ...so the compiler could even drop the right-shift and instead just use the register where the upper half of the result is stored.
- deepsun 5y agoInteresting, thank you. But the type conversion is on the results, not input. Is it guaranteed that we're always multiplying two 32-bit numbers and not two 64-bit numbers in "(uint64_t) x * (uint64_t) N"? Because looking at the code, it's more natural to think we're multiplying 64-bit integers, so we may need some CPU cycles to make "x" occupy 64 bits first, same for "N", and then do multiplication on them.
- pwuille 5y agoThe conversion is free, at least on x86-like platforms, because there are no separate 32-bit and 64-bit registers. Instead, there is a fixed shared set of registers, and the instructions signal whether they operate on the 32-bit or 64-bit value on it. When assigning to a register in 32-bit mode the top 32 bits are cleared, so if x and n were loaded into 32-bit registers, a 64-bit multiplication can be applied to it directly, without any conversion instructions.
- bbojan 5y agoThis technique is not new. E.g. I remember it described in ARM system developer's guide published back in 2004. It shows how to use unsigned 64-bit multiplication to restrict a range of a 32-bit random number generator to 0..N. No shifts are needed, as the result is in the upper 32-bit register.
- thomasmg 5y agoYes it is not new; I read the multiplication trick was described even in 1986, in "The Metafont book" (Donald E. Knuth). (I don't have the book however). But it does look like the technique was forgotten, or at least not used very often in the past.
- eternalban 5y agoKenneth A. Ross mentions it in passing in his 2006 IBM research report (a great paper btw): "We can interpret a 32-bit hash value v as a binary fraction, i.e., the representation of a number between zero and one whose digits after the (binary) decimal point are given by v. Given a hash table size s, we can obtain a slot number by multiplying s and v and shifting right 32-bits. This way, arbitrary table sizes are possible without using expensive division or modulus operations. Computing s∗v can be performed with one 32-bit multiplication (generating a 64- bit result). If s is a 16-bit number, as might be expected for a small hash table, then two 16-bit multiplications, a shift, and a 32-bit addition suffice." Kenneth A. Ross, Efficient Hash Probes on Modern Processors, IBM Research Report RC24100 (W0611-039) November 8, 2006 https://dominoweb.draco.res.ibm.com/reports/rc24100.pdf https://dominoweb.draco.res.ibm.com/reports/rc24100.pdf
- adrian_b 5y agoIt is much older than that. If you interpret a random n-bit integer as random fraction >= 0 and < 1, it is obvious that if you multiply it by K you will have a random number >= 0 and < K. If you take the integer part and discard the fractional part, i.e. you keep just the upper word from multiplication, you get a random integer >= 0 and <= (K-1). This was well known since the oldest times when pseudo-random numbers began to be used, i.e. immediately after WW2. At that time, before the introduction of the floating-point numbers, interpreting the binary numbers as fractions instead of integers was much more frequent. Using modulo became popular only in higher level languages, where it was more complex to write a double word multiplication, but it is clearly an inferior solution compared to using a multiplication for the same job. Moreover, the multiplicative method ensures that all the integer values possible for the result have the same probabilities, while with the modulo K method it is possible that the last value (K-1) has a lower probability (corresponding to fewer possible values of the input number), which is not what is normally desired. For ancient congruential PRNGs, the modulo method was even worse, because those PRNGs had the lower bits less random than the upper bits.
- pwuille 5y agoI recently discovered a generalization of this approach, which allows mapping a single hash to multiple independent numbers, each in their own range, while maintaining various uniformity properties. A write-up is here, in case anyone is interested: https://github.com/sipa/writeups/tree/main/uniform-range-extraction https://github.com/sipa/writeups/tree/main/uniform-range-ext...
- kwillets 5y agoThis may save random bits, which are generally more costly than the range reduction.