For SHA3, if I were to hash large files (> 1GB), would that operation be CPU or I/O bound?

Suppose I were to exploit parallelism and either use multicore/SIMD execution or generate a hash tree, would that also be constrained by the same resource?

  • $\begingroup$ you might want to have a look at KangarooTwelve: keccak.team/KangarooTwelve.pdf It is tree hashing over the Keccak-p permutation. $\endgroup$ – Biv Apr 10 '17 at 9:10

Clearly this depends a lot on your setup.

Looking at some numbers:

According to Wikipedia SHA-3 requires 12.5 cbp (cycles per byte) on a Core 2. Let's also assume this Core 2 has 2.4 GHz. So we get 2.4 GHz / 12.5 cbp = 192 MB/s for the hash calculation.

Let's say you have an SSD with 500 MB/s access speed which is plausible according to the Wikipedia article on SSD and this benchmarking website.

That means the SSD is faster and hashing is CPU constrained.

Additionally, there are faster SSDs and benchmarks usually don't consider only consecutive reads so that could widen the gap.

  • 2
    $\begingroup$ According to your figures the SSD faster, so how would something get worse if the CPU is sped up? Wouldn't the figures grow towards each other? 192 < 500 right, and both are in bytes, not bits? $\endgroup$ – Maarten Bodewes Apr 10 '17 at 9:21
  • $\begingroup$ I completely agree with the "depends" statement. That 500MB/s number is based off the DRAM cache reads on the SSD with PCI-E as a constraint. It's much slower if I need to pull from the FLASH. It's definitely IO constrained. The "best case" speed would be a read into memory, and then hash the whole thing. $\endgroup$ – b degnan Apr 11 '17 at 19:54
  • $\begingroup$ @bdegnan So do I understand correctly that the values reported in those benchmarks are actually the absolute best and will in practice be lower? $\endgroup$ – Elias Apr 12 '17 at 10:14
  • $\begingroup$ @Elias The actual ICs move only about 30MiB/sec. This is why cache is king. $\endgroup$ – b degnan Apr 12 '17 at 14:42
  • 1
    $\begingroup$ @Elias They are not flat out lies, but you have a MCU that does prediction to try to keep the cache full. For instance, if you try to pull a 4GiB file from a device with 2GiB cache, you'll notice. ICs in parallel will help, so there is an architecture component. I'd have to revisit the documents from Samsung and Micron to find the bit-widths on a per-IC basis. Most people will never notice, but it's worth knowing that something could happen on a HUGE file. $\endgroup$ – b degnan Apr 12 '17 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.