Comment by majke | Hacker News Reader

Comment by majke | Hacker News Reader

Parent Full thread

In the final program `mmuniq` I did a couple of, I think, interesting hacks.

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/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_insert...

from https://en.wikipedia.org/wiki/Hash_table

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-lin...

[1] https://news.ycombinator.com/item?id=6920862

[2] https://news.ycombinator.com/item?id=3015246

[3] https://news.ycombinator.com/item?id=2348619

[4] https://news.ycombinator.com/item?id=3650657

[5] https://news.ycombinator.com/item?id=18921058

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.

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.

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.

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.

Would save a lot of space to just have separate lists for each mask length etc.

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 [1] https://github.com/abseil/abseil-cpp [2] https://github.com/rust-lang/hashbrown

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.

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 nasm -f elf64 -o falkhash-elf64.o falkhash.asm

<update> Crap. That gist contained some draft version of aesnihash. SORRY. See updated version 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/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/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.

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.

What about rewriting one of these[0] hash functions for SIMD?

0: https://nullprogram.com/blog/2018/07/31/

Have you looked at XXH64 from https://cyan4973.github.io/xxHash/ ?

For denser hash table, you need Robin Hood hashing.

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

Reply on news.ycombinator.com