4 ms·
My experience with compiler development is that the incentives all align toward making the "default RNG that people go to" as fast as possible to the exclusion
by pcwalton 11y ago
My experience with compiler development is that the incentives all align toward making the "default RNG that people go to" as fast as possible to the exclusion of all else, including the quality of the generated numbers. That's because people frequently write benchmarks gated on the speed of random number generation, and those benchmarks usually don't care about the quality of the random numbers. Sometimes those benchmarks get popular, which encourages a race to the bottom in RNG quality.
(Similar incentives exist for hash functions, by the way.)
Popular RNG-bound benchmarks:
* "fasta" from the Benchmarks Game [1] (thankfully, this one mandates use of its own RNG, though it's vulnerable to fast-forwarding as demonstrated in [2])
* "Perlin noise" [3] (almost entirely RNG performance bound)
* From SunSpider (this one being particularly relevant to V8): string-validate-input [4], string-base64 [5]
[1]: http://benchmarksgame.alioth.debian.org/u64q/fasta-description.html#fasta http://benchmarksgame.alioth.debian.org/u64q/fasta-descripti...
[2]: https://github.com/TeXitoi/benchmarksgame-rs/blob/master/src/fasta.rs#L121 https://github.com/TeXitoi/benchmarksgame-rs/blob/master/src...
[3]: https://github.com/nsf/pnoise https://github.com/nsf/pnoise
[4]: https://www.webkit.org/perf/sunspider-0.9/string-validate-input.html https://www.webkit.org/perf/sunspider-0.9/string-validate-in...
[5]: https://www.webkit.org/perf/sunspider-0.9/string-base64.html https://www.webkit.org/perf/sunspider-0.9/string-base64.html
- hajile 11y agoThe author makes a reasonable point that there are algorithms that are both faster AND higher quality than the one v8 uses. I think not understanding random number generators and the resulting voodoo programming is the real culprit.
- im2w1l 11y agoFast hash functions can be really important for performance of hash sets and maps. In my experience high speed is more important than a low collision rate. That was for primitive types, it may well be different for types where comparison is more costly. And of course if you need protection from algorithmic complexity attacks, then you will need to take that into account.
- Gankro 11y agoAs long as your usecase isn't worried about hash-flooding [0]. Unfortunately too few people know this is even an attack, so it may be reasonable for languages to default to a stronger hash algorithm for safety, but this isn't the common case... language design is hard. [0]: https://www.youtube.com/watch?v=wGYj8fhhUVA https://www.youtube.com/watch?v=wGYj8fhhUVA
- jbapple 11y agoFortunately, there are very fast universal hash functions like Vhash that are resistant to hash-flooding.
- Gankro 11y agoI've literally never heard of Vhash, and I see no references to it outside of the 2007 paper. As far as I know, the state of the art for "fast and secure" is still SipHash 2-4 or 2-3. While SipHash perf is generally quite good, it's still not as fast as Fnv on small inputs or XxHash on large inputs. As in, 4x slower [0]. FarmHash has great perf if you can invoke it in the way it wants, but doesn't do well in a streaming context. [0]: http://cglab.ca/~abeinges/blah/hash-rs/ http://cglab.ca/~abeinges/blah/hash-rs/
- jbapple 11y ago> I've literally never heard of Vhash, and I see no references to it outside of the 2007 paper. It is intimately tied up with VMAC. The title of the 2006 paper that introduced them is "Message authentication on 64-bit architectures". Google scholar says it has been cited 32 times, while "SipHash: a fast short-input PRF" has been cited 43 times. > As far as I know, the state of the art for "fast and secure" is still SipHash 2-4 or 2-3. SipHash seems to me like a good choice. SipHash has some security properties that Vhash does not, although Vhash-based-VMAC has similar security properties to SipHash, I believe. However, for hash flooding attacks, if the hash values themselves are not directly exposed to the attackers and there is enough noise in the response latency that timing attacks are difficult, I do not know what benefits SipHash has. "Faster 64-bit universal hashing using carry-less multiplications" has some benchmarks that show Vhash as faster than SipHash, substantially so on long input. Speed-wise, an iterated string hash using Dietzfelbinger-style multiply-shift hashing is also substantially faster (3-10x) than SipHash on both large and small inputs in my testing, and it needs about 20 lines of code to implement. I haven't written any Rust in a while, but I'll try and send you a patch to the repo you linked. The benchmarks from the "Faster 64-bit ..." paper are available at https://github.com/lemire/StronglyUniversalStringHashing https://github.com/lemire/StronglyUniversalStringHashing. The iterated string hash I referenced is https://github.com/lemire/StronglyUniversalStringHashing/blob/3215c53a34699c8b573a4a6e57e7df248c0a82fc/include/bigendianuniversal.h#L43 https://github.com/lemire/StronglyUniversalStringHashing/blo....
- igouy 11y ago>> "fasta" from the Benchmarks Game [1] (thankfully, this one mandates use of its own RNG << Part of the inheritance ;-) http://web.archive.org/web/20010424150740/http://www.bagley.org/~doug/shootout/bench/random/ http://web.archive.org/web/20010424150740/http://www.bagley.... >> though it's vulnerable to fast-forwarding << Is that a vulnerability given the way it is used in the benchmarks game?