4 ms·

In the final program `mmuniq` I did a couple of, I think, interesting hacks. https://github.com/cloudflare/cloudflare-blog/blob/master/2020-02-mmuniq/mmuniq.c

by majke 7y ago

In the final program `mmuniq` I did a couple of, I think, interesting hacks. https://github.com/cloudflare/cloudflare-blog/blob/master/2020-02-mmuniq/mmuniq.c https://github.com/cloudflare/cloudflare-blog/blob/master/20... First, I used a hash function using aesni (aesenc) instruction set. See this: https://gist.github.com/majek/96dd615ed6c8aa64f60aac14e3f6ab5a https://gist.github.com/majek/96dd615ed6c8aa64f60aac14e3f6ab... While I have little proof it's a good hash, it seems enough, and is _slightly_ (5-10%?) faster than siphash24 in this context. Then I mixed counting hash with finding new lines \n. This allows me to do only one user-data load into XMM registers. Most importantly, to offset the RAM latency cost, I'm doing 64 prefetches as I parse the input, and only after this I actually touch the hash table. The memory latency is still the biggest time sync, but at least this seem to speed up the program 2x or more. Hash table without this batching+prefetch is 6-8 seconds. With batching goes down below 3s. I suspect linear probing / open addressing of the hash table may have some penalty. While it plays nicely with the cache prefetch, it generally leads to longer chains. This means we need to keep the hash table sparse, not loaded above 0.6-0.75. See this https://en.wikipedia.org/wiki/File:Hash_table_average_insertion_time.png https://en.wikipedia.org/wiki/File:Hash_table_average_insert... from https://en.wikipedia.org/wiki/Hash_table https://en.wikipedia.org/wiki/Hash_table

rurban 7y ago
I'll check your new aesni hash, but would recommend to try a simple fast 32bit hash instead, like the builtin crc32c. It needs half as much space and the cache misses will kill you essentially. Twice lesser cache misses. And a simple linear hash table instead of cookoo will also help in less cache misses. There are no deletions. Should be 20% faster, I think. Or even gperf.
- rurban 7y ago
  So I tested your aesnihash with smhasher. It's really bad. A much better 64bit aesni variant would be falkhash, which is 4x faster, supports a seed and passes most tests. https://github.com/gamozolabs/falkhash https://github.com/gamozolabs/falkhash nasm -f elf64 -o falkhash-elf64.o falkhash.asm
  - telendram 7y ago
    Even falkhash is not that great, and feature an abnormal amount of collisions as the nb of hashes increase. Basically, all "naive" AES implementations share this design weakness.
  - majke 7y ago
    <update> Crap. That gist contained some draft version of aesnihash. SORRY. See updated version https://gist.github.com/majek/96dd615ed6c8aa64f60aac14e3f6ab5a https://gist.github.com/majek/96dd615ed6c8aa64f60aac14e3f6ab... </update> Thanks for spending time on this. I would like to understand what "really bad" and "fails most of the tests" means. For the record, the commit: https://github.com/rurban/smhasher/commit/10f56385f3e9abb018eef7196c51a1a6fb4e1258 https://github.com/rurban/smhasher/commit/10f56385f3e9abb018... The main point of this hash, in this context, is to do streaming hash and find \n at in one loop. The intention is to reduce data loads _mm_loadu_si128 (I already have user data in xmm0, so why not do some aesni already?). Because it's streaming I can't for example derive the initial seed based on the chunk length, since it's unknown at the time of calling hash. See: https://github.com/cloudflare/cloudflare-blog/blob/master/2020-02-mmuniq/mmuniq.c#L176-L232 https://github.com/cloudflare/cloudflare-blog/blob/master/20... I don't need full aes hash, but maybe that could be an option as well. In other words, in my case I don't care just about hash() speed. I care about memchr() + hash() speed. I would like to understand/measure the hash quality itself. Maybe adding another aesenc round would be sufficient to fix it.
willvarfar 7y ago
I'm a bit confused, you are now storing the IPv4 addresses in a hash table using a 64-bit hash? Why not just use the 32-bit address as a key, and grow the 'blocks' so if two addresses are just a couple of digits apart, promote it to a /24 block etc.
- majke 7y ago
  Apologies, maybe I oversimplified the original problem. I'm dealing with IP's (both v4 and v6), subnets, ranges (which may or may not align to subnets). These map to one or more datacenter numbers. I could indeed define data model, parse the data thoroughly, optimize in-memory data structure, and so on. That requires rigid data structure, knowing access pattern and understanding the problem space. I'm not there yet. Instead, I created this generic tool which works with any text files, and fell into a rabbit hole of over-optimizing it. That's it.
  - taywrobel 7y ago
    FWIW, you should be able to represent individual IPs, ranges, and subsets all in CIDR notation, tho for ranges you may need multiple CIRD entries to reflect the whole range. CIDR for ipv4 consists of the 32 bit address and a 32 bit mask, so with some bit packing you can uniquely represent them in 64 bits without hashing. The problem you’ll run into there is doing a “contains” check on an origin IP for a list of CIDRs, but you’ll need to do that currently since you’re dealing with subnets, I assume.
    - jsn 7y ago
      32 bit mask is way too generous, you only need 5 bit masklen. It all doesn't matter though since they have v6 addresses and ranges.
      - willvarfar 7y ago
        Would save a lot of space to just have separate lists for each mask length etc.
heartbeats 7y ago
What about rewriting one of these[0] hash functions for SIMD? 0: https://nullprogram.com/blog/2018/07/31/ https://nullprogram.com/blog/2018/07/31/
ignoramous 7y ago
Thanks for the excellent write-up. Probably not as cache-friendly, but did you, at any point, evaluate Radix Tree [0] or Patricia Trie / CritBit Tree [1][2] as an underlying data-structure for the hash-table? These also compact nicely into one of the many succinct data-structures [3][4]. Radix Tree, in particular, seems to work really well for IPs from what I've read [5]. --- [0] https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-linux https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-lin... [1] https://news.ycombinator.com/item?id=6920862 https://news.ycombinator.com/item?id=6920862 [2] https://news.ycombinator.com/item?id=3015246 https://news.ycombinator.com/item?id=3015246 [3] https://news.ycombinator.com/item?id=2348619 https://news.ycombinator.com/item?id=2348619 [4] https://news.ycombinator.com/item?id=3650657 https://news.ycombinator.com/item?id=3650657 [5] https://news.ycombinator.com/item?id=18921058 https://news.ycombinator.com/item?id=18921058
vthriller 7y ago
May I suggest you to have a look at Swiss Tables? There's a good talk from CppCon [0] that explains its design decisions, and implementations available as part of Abseil [1] and Rust stdlib [2]. [0] https://www.youtube.com/watch?v=ncHmEUmJZf4 https://www.youtube.com/watch?v=ncHmEUmJZf4 [1] https://github.com/abseil/abseil-cpp https://github.com/abseil/abseil-cpp [2] https://github.com/rust-lang/hashbrown https://github.com/rust-lang/hashbrown
wolf550e 7y ago
Have you looked at XXH64 from https://cyan4973.github.io/xxHash/ https://cyan4973.github.io/xxHash/ ? For denser hash table, you need Robin Hood hashing.
trentnelson 7y ago
Do you have the source data available? Or can you make an anonymou version available?

by majke 7y ago

rurban 7y ago

I'll check your new aesni hash, but would recommend to try a simple fast 32bit hash instead, like the builtin crc32c. It needs half as much space and the cache misses will kill you essentially. Twice lesser cache misses. And a simple linear hash table instead of cookoo will also help in less cache misses. There are no deletions. Should be 20% faster, I think. Or even gperf.

rurban 7y ago
So I tested your aesnihash with smhasher. It's really bad. A much better 64bit aesni variant would be falkhash, which is 4x faster, supports a seed and passes most tests. https://github.com/gamozolabs/falkhash https://github.com/gamozolabs/falkhash nasm -f elf64 -o falkhash-elf64.o falkhash.asm
- telendram 7y ago
  Even falkhash is not that great, and feature an abnormal amount of collisions as the nb of hashes increase. Basically, all "naive" AES implementations share this design weakness.
- majke 7y ago
  <update> Crap. That gist contained some draft version of aesnihash. SORRY. See updated version https://gist.github.com/majek/96dd615ed6c8aa64f60aac14e3f6ab5a https://gist.github.com/majek/96dd615ed6c8aa64f60aac14e3f6ab... </update> Thanks for spending time on this. I would like to understand what "really bad" and "fails most of the tests" means. For the record, the commit: https://github.com/rurban/smhasher/commit/10f56385f3e9abb018eef7196c51a1a6fb4e1258 https://github.com/rurban/smhasher/commit/10f56385f3e9abb018... The main point of this hash, in this context, is to do streaming hash and find \n at in one loop. The intention is to reduce data loads _mm_loadu_si128 (I already have user data in xmm0, so why not do some aesni already?). Because it's streaming I can't for example derive the initial seed based on the chunk length, since it's unknown at the time of calling hash. See: https://github.com/cloudflare/cloudflare-blog/blob/master/2020-02-mmuniq/mmuniq.c#L176-L232 https://github.com/cloudflare/cloudflare-blog/blob/master/20... I don't need full aes hash, but maybe that could be an option as well. In other words, in my case I don't care just about hash() speed. I care about memchr() + hash() speed. I would like to understand/measure the hash quality itself. Maybe adding another aesenc round would be sufficient to fix it.

willvarfar 7y ago

I'm a bit confused, you are now storing the IPv4 addresses in a hash table using a 64-bit hash? Why not just use the 32-bit address as a key, and grow the 'blocks' so if two addresses are just a couple of digits apart, promote it to a /24 block etc.

majke 7y ago
Apologies, maybe I oversimplified the original problem. I'm dealing with IP's (both v4 and v6), subnets, ranges (which may or may not align to subnets). These map to one or more datacenter numbers. I could indeed define data model, parse the data thoroughly, optimize in-memory data structure, and so on. That requires rigid data structure, knowing access pattern and understanding the problem space. I'm not there yet. Instead, I created this generic tool which works with any text files, and fell into a rabbit hole of over-optimizing it. That's it.
- taywrobel 7y ago
  FWIW, you should be able to represent individual IPs, ranges, and subsets all in CIDR notation, tho for ranges you may need multiple CIRD entries to reflect the whole range. CIDR for ipv4 consists of the 32 bit address and a 32 bit mask, so with some bit packing you can uniquely represent them in 64 bits without hashing. The problem you’ll run into there is doing a “contains” check on an origin IP for a list of CIDRs, but you’ll need to do that currently since you’re dealing with subnets, I assume.
  - jsn 7y ago
    32 bit mask is way too generous, you only need 5 bit masklen. It all doesn't matter though since they have v6 addresses and ranges.
    - willvarfar 7y ago
      Would save a lot of space to just have separate lists for each mask length etc.

heartbeats 7y ago

What about rewriting one of these[0] hash functions for SIMD? 0: https://nullprogram.com/blog/2018/07/31/ https://nullprogram.com/blog/2018/07/31/

ignoramous 7y ago

Thanks for the excellent write-up. Probably not as cache-friendly, but did you, at any point, evaluate Radix Tree [0] or Patricia Trie / CritBit Tree [1][2] as an underlying data-structure for the hash-table? These also compact nicely into one of the many succinct data-structures [3][4]. Radix Tree, in particular, seems to work really well for IPs from what I've read [5]. --- [0] https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-linux https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-lin... [1] https://news.ycombinator.com/item?id=6920862 https://news.ycombinator.com/item?id=6920862 [2] https://news.ycombinator.com/item?id=3015246 https://news.ycombinator.com/item?id=3015246 [3] https://news.ycombinator.com/item?id=2348619 https://news.ycombinator.com/item?id=2348619 [4] https://news.ycombinator.com/item?id=3650657 https://news.ycombinator.com/item?id=3650657 [5] https://news.ycombinator.com/item?id=18921058 https://news.ycombinator.com/item?id=18921058

vthriller 7y ago

May I suggest you to have a look at Swiss Tables? There's a good talk from CppCon [0] that explains its design decisions, and implementations available as part of Abseil [1] and Rust stdlib [2]. [0] https://www.youtube.com/watch?v=ncHmEUmJZf4 https://www.youtube.com/watch?v=ncHmEUmJZf4 [1] https://github.com/abseil/abseil-cpp https://github.com/abseil/abseil-cpp [2] https://github.com/rust-lang/hashbrown https://github.com/rust-lang/hashbrown

wolf550e 7y ago

Have you looked at XXH64 from https://cyan4973.github.io/xxHash/ https://cyan4973.github.io/xxHash/ ? For denser hash table, you need Robin Hood hashing.

trentnelson 7y ago

Do you have the source data available? Or can you make an anonymou version available?