5 ms·

why not rip out CRC32 and put in xxhash?

• gwern 11y ago
  Probably don't want to go back and rewrite all their past data.
  • alfiedotwtf 11y ago
    Pretty much this. From the post: "Because it produces different results, it would render all our stored checksums invalid, so we'd have to recalculate them all. That's a big job, so we'd need to do a lot of testing first to make sure that it's so much better that it's actually worth the effort."
  • jorangreef 11y ago
    xxHash is at least an order of magnitude faster so it might be worth upgrading.
    • robn_fastmail 11y ago
      My quick tests here (using the same methods outlined in the post) suggests its around 30% faster on 64-byte buffers. If we're ever shopping for a new hash function entirely, I'll make sure its considered. Right now its not worth it because as noted in the post, we're not actually under any particular stress and changing hash functions is a big job.
      • deleted 11y ago
        [deleted]
• jorangreef 11y ago
  More about xxhash here, it's by Yann Collet, the author of LZ4: http://fastcompression.blogspot.fr/2012/04/selecting-checksum-algorithm.html http://fastcompression.blogspot.fr/2012/04/selecting-checksu...
  • PeCaN 11y ago
    And (perhaps more interestingly) Finite State Entropy coding: http://fastcompression.blogspot.com/2013/12/finite-state-entropy-new-breed-of.html http://fastcompression.blogspot.com/2013/12/finite-state-ent...
• Ono-Sendai 11y ago
  xxhash is great, I recommend it.
• baudehlo 11y ago
  Last time I needed really fast hashing I used FNV. How does it compare to xxhash?
  • baudehlo 11y ago
    Never mind - it's covered in the other reply link here. Looks like xxhash is the goto hash algorithm now.
    • kzrdude 11y ago
      That's a misunderstanding. If you need a hash or checksum for very long data (megabytes, gigabytes), use xxhash. It's not the best for hash tables.
      • baudehlo 11y ago
        Good to know. I was using FNV to hash spam signatures which are typically small. Glad I chose well.
        • jorangreef 11y ago
          If your spam signatures are small (around 32 bytes) and fixed size, you might also want to look into a pure XOR tabulation hash. It's excellent for generating fixed-size keys for hash tables: http://www2.imm.dtu.dk/projects/thrash-workshop/slides/thorup.pdf http://www2.imm.dtu.dk/projects/thrash-workshop/slides/thoru... https://en.wikipedia.org/wiki/Tabulation_hashing https://en.wikipedia.org/wiki/Tabulation_hashing I use it all the time when I need a hash table index. It's simple to understand, safe and fast. Even though it can generate more assembly than other hashes, it's actually often faster because it has no multiply operation, only XOR. If the tables are small enough to fit into cache (i.e. small keys), it's brilliant. It has properties suitable for triangular probing, where other hashes sometimes don't have enough independence. And if you need a rolling hash, i.e. for Rabin Karp, it's also perfect.
  • kzrdude 11y ago
    Fnv is fast because the code is tiny and hashing a few bytes is fast. xxhash uses multiple parallel streams and has very high throughput. They are fast hashes, each in their end of the spectrum, Fnv for 1-16 byte keys and xxhash for long data. It's better to call xxhash a checksum, since that's its purpose.
• awalton 11y ago
  If you were going to rewrite your data, why wouldn't you go with something that's been standardized by every hardware implementers as the next generation CRC algorithm, CRC32c (the one the article explicitly throws out at the beginning, because the author did not want to rewrite the data)? Even ARM chips and network- and storage-focused microcontrollers have hardware acceleration for it these days...