It's an important distinction that many people forget:
* Hash tables need speed and uniformity
* Cryptographic hashes need irreversibility
back
1 comments
Cryptographic hashes also need speed and uniformity. They just need irreversibility significantly more.
GF(2) space is incredible for both speed and uniformity. IIRC, the fastest x86 hash-functions just use the AESENC instruction (Note: the AESENC instruction executes with 1-instruction per clock cycle on Intel, and 2-instructions per clock cycle on AMD. Its an incredibly fast primitive).
That's throughput you're citing, they still have 4-8 clock cycles of latency, according to https://software.intel.com/sites/landingpage/IntrinsicsGuide...
True, but in practice, throughput is what you should be thinking about as a low level performance programmer.
CPUs can execute many, many, many instructions in parallel. If all your data fits inside of L1 cache (4-clocks of latency), its actually pretty easy to achieve 2-instructions per clock or more !
Furthermore, modern CPUs are out-of-order processors. So the processor will automatically execute independent instructions to "fill up your latency", at least to some extent.
CPUs have enough space to even handle main memory fetches (over 200+ reorder buffers on Skylake, to handle the 200+ clocks of latency on a DDR4 memory read or write). As long as you have "enough independent work to do," its not too bad. Compilers usually figure out independent chunks of work as they unroll loops for example.
In my experience, the loop accounting (for int i=0; i<100; i++) will all execute inside of that latency in parallel to the work inside of the loop. So there's almost always work to do, at least at the ~5 clocks to 10-clocks worth of "misc" functions in any bit of code.
The hard part is coming up with work to do for ~50ns of latency (ex: DDR4 Reads or Writes).
Actually no, latency is usually a bottleneck before throughput is.
Edit: for example when accessing an hash table, the hash computation is in the critical path.
> Edit: for example when accessing an hash table, the hash computation is in the critical path.
Hmmm... I think I'm biased a bit because of something I'm writing recently where different iterations of a loop were independent.
In this case, you're right. The hash calculation is on the critical path and therefore is latency bound.
> Hmmm... I think I'm biased a bit because of something I'm writing recently where different iterations of a loop were independent.
That's a great place to be in :D.
BTW, I haven't tried to get implement an hash function in a while (I remember playing with carryless multiplication), but IIRC 6 clock cycles is not too bad.
> BTW, I haven't tried to get implement an hash function in a while
Multiply RAX, CONST1 / bswap RAX / XOR RAX, CONST2 / Multiply RAX, CONST3.
12 cycles of latency. CONST1 and CONST3 must be odd (bottom bit is 1). Pick CONST1, CONST2, and CONST3 out of /dev/urandom.
--------
BTW: This is exactly why latency didn't matter, because the 12-cycles of latency here are basically independent between loops. The next loop iteration would cut-the-dependency on RAX, allowing the next loop iteration's "RAX" to get a new register and execute independently.
--------
AESEnc is a good baseline, but you need 2 or 3 iterations of it to work well. AESEnc also works on 128-bit vector registers, but most people want something that works on the 64-bit registers.
If your data was already in XMM registers, AESEnc / AESDec will be great. Otherwise, 64-bit multiply is really good at shuffling those bits around. Take RAX (64-bit result), EAX (32-bit result), AX (16-bit result), or AL (8-bit result) as needed.