Use fast data algorithms (2021)
jolynch.github.io
jolynch.github.io
I didn't know about that, that's neat.
These types of articles come up often, and it's good to proselytize about better algorithms. However the end of the article hints at an issue. Most of the hashing and compression in my life are done embedded in some system or protocol that I can't easily change. Yeah, Docker and Debian and Firefox should use zstd but there's not much I can do about it. I may reach for zstd when I'm moving a big file between systems, but I'd have to install it first and much of the time that's not worthwhile.
This is true, but there's also more to the story. Modern password hashes like Argon2 force attackers into a "time-memory tradeoff", to try to reduce the advantage that specialized hardware has over the general-purpose computers that human beings use. I find that a lot of folks have memorized a summary like "slow hashes are good", and that's doubly unfortunate, because 1) like the article says, fast hashes are good, and 2) slow hashes in and of themselves are no longer the best we can do for password security. I often wish that password hashes weren't even called "hashes", because it's just a very different problem that they're solving.
> or even just a high number of rounds of SHA-512
Please god no :)
PBKDF1 (which is just iterated hashing) has the same security as PBKDF2 when used with fixed length salts, and avoids the numerous pitfalls of the latter. Though it's still not as good as bcrypt, scrypt or argon2.
I agree! And same for crypto hash (as in collision-resistant function) vs. “mixer” hash (as in diffuse permutation)[0].
We should make “PBKDF” a more common name.
> Please god no :-)
Heh I didn't mean it as a recommendation per say, but I'm pretty sure Linux uses repeated SHA-512 on at least some common distros. At least on my Ubuntu Focal machine my /etc/shadow appears to be using SHA-512.
I did love the anecdote about adding gzip moving the bottleneck to the cpu from the network, and actually slowing down the whole system.
Mechanical disks stagnated in performance for so long that people just "internalised" the rule that storage is always vastly slower than compute, and that just about any compression algorithm is faster than nothing, literally always. Similarly, hashing overheads could be safely ignored.
Meanwhile, my current laptop (not server!) has a single NVMe SSD that can easily do 7 GB/s reads... but only in benchmarks.
Why benchmarks you ask? Because nearly 100% of software has been written with the "disk is slow anyway, don't bother optimising I/O" assumption.
I was recently trying to process some bulk data on my laptop, and there were practically no tools available that could ingest data that fast! The fastest I saw was about 2 GB/s.
Similarly, I could not find any way to accelerate I/O further using compression without multithreading. That is, even LZ4 can only decompress at around 5GB/s, which would slow down reads.
Algorithm choice -- while important -- doesn't even begin to approach the gains that can be made via data formats that enable parallelism. Chunking the data so that multiple CPU cores can process a stream is critical. Again, my laptop has 8 cores and 16 threads. Using only 1 core is throwing away at least 90% of the available performance.
So if your code looks like this you have made a mistake:
var doc = new Parser( new XmlParser( new Utf8Reader( new ZipStream( File.Open( filename )))));
In an ideal world, the on-disk format would be in ~1MB chunks so that decode could be parallelised to almost any degree. Unfortunately, this has to be done end-to-end. Even if, say, the compression is chunked, this won't help much if the file that is stored is a sequentially parsed format such as a huge JSON or XML file.
The industry needs a renaissance of serialization formats where the "serial" part is taken out.
E.g., B-tree reads need pretty much random access after many non-sequential data insertions. And we are talking about read-optimized data structures here.
BTW network is also fast; your typical server has at least a 10G interface, sometimes 40G or even 100G. Transfers within the same rack may be faster than your NVMe, and within the same DC, comparable.
I do not like that stance at all.
Consider CPUs, out-of-order ones. They can adapt to the algorithms being thrown at them and most of the time algorithm author is not even aware it can be done. Improvements in this area are steady, about two-to-five of percents per year. Apple's M1 is able to schedule almost 8 instructions per cycle, for example, in quite latency-sensitive task [1].
[1] https://lemire.me/blog/2021/03/24/counting-cycles-and-instru...
Storage systems development is unable to produce something that is similar to OoO CPUs. You can't throw algorithm at storage so that it'll adapt. Algorithms should be adapted to hardware.
Circling back to CPUs, situation with storage hardware is very much like situation with the IBM's Cell BE architecture: hardware is fast, but nobody knows how to make concrete algorithms fast on that hardware.
In my opinion, Cell BE is slow, just like contemporary storage systems are slow. They are fast only in benchmarks.
NVMe devices introduce caches made with fast SLC flash and even banks of battery-backed RAM. They expose the familiar disk-like intetface while keeping a log-based structure internally. They expose contiguous space and mostly hide the latency due to the internal reallocation of faulty cells. They queue and reorder operations sent to them (OoO executuon).
But sometimes divining the user intent is impossible, and they expose stuff like the truncation command.
Even with serious performance engineering, it is difficult to drive compression, parsers, codecs, etc with throughput comparable to modern storage. There are several non-cryptographic hashing algorithms that can be driven that hard, but none of them are mentioned in the article.
Sure there are some other fast ones out there like cityhash[2] but there aren't good Java/Python bindings I'm aware of and I wouldn't recommend using it in production given the lack of wide-spread use versus xxhash which is used by LZ4 internally and in databases all over the place.
[1] https://github.com/Cyan4973/xxHash [2] https://github.com/google/cityhash
A trick not mentioned here: for Python devs, import “orjson” instead of the json standard library; it is usually a drop-in replacement.
With orjson, encoding produces a bytes object instead of a string object, and when you're writing to a file that avoids a bunch of extra memory management overhead and a str.encode() when the text-file wrapper converts that string to a bytes behind the scenes. So that interface change is quite a big performance win over and above just having the faster JSON encoder.
They may be slow only in programs which do not check for hardware support and which do not use the dedicated hardware instructions (which is the case in many programs, because Intel Skylake derivatives have been the most popular CPUs during many years, and they were the only modern CPUs without hardware support for SHA-1/SHA2-256, so most developers did not bother to optimize their programs for the other CPUs).
OpenSSL is one of the few programs which use the hardware instructions when available. This makes, e.g., "openssl dgst -sha256" much faster than "sha256sum" on recent CPUs.
When using the hardware instructions, SHA-1 and SHA2-256 are faster than many non-cryptographic hashes and only 1 cryptographic hash is faster: BLAKE3.
However, it must be kept in mind that BLAKE3 is much faster than any other cryptographic hash only because it distributes the computation on all CPU cores. So the much higher speed is accompanied by a much higher CPU utilization.
If you have something else that should be done in parallel with the hash computation, using BLAKE3 does not necessarily reduce the total execution time for your entire application, even if the hash is computed much faster, because other concurrent activities may be stalled until the hash computation is completed.
Surprisingly, this is incorrect. Here are some single-threaded measurements on a CPU with SHA-NI: https://bench.cr.yp.to/results-hash.html#amd64-icelake. What you see there is that BLAKE3 can take better advantage of SIMD parallelism than other hashes, and the C and Rust library implementations do this by default. Multithreading isn't enabled by default in the library APIs, but if you do use it (and you have enough input to feed it) the benefits are multiplicative. The b3sum CLI does use multithreading by default.
> only 1 cryptographic hash is faster: BLAKE3
SIMD implementations of KangarooTwelve are also about as fast as BLAKE3, given enough input.
In my tests on AMD Zen 3, BLAKE3 is much faster only when multi-threaded and that should be true on any CPU where the SHA instructions are well implemented.
You are right that it is a little exaggerated to say that BLAKE3 is the only hash with these properties.
Using a similar construction with BLAKE3 to allow parallel computation, instead of using the traditional Merkle–Damgård iterated construction, like SHA-1, SHA-2 and many others, it is possible to design many other fast hash algorithms and there already are many such experimental hashes.
What I have meant was that BLAKE3 is, for now, the only one that has both a freely available and easy to install high-quality implementation, and it is based on a theory that has been studied long enough to have confidence in it.
There are many other hashes that are candidates for being useful fast cryptographic hashes, but it is likely that a few more years are needed to trust them enough.
BLAKE3 is not multithreaded by default.
First, I am not sure the data on most in-use hardware (e.g. EC2 m5/c5/i3en etc ...) supports your conclusions. xxHash is faster than crypto hashes always and BLAKE3 single threaded is faster on every Intel machine I've come across in wide deployment. I hear similar arguments around CRC-32 and to be frank it just isn't true on most computers most people run things on.
Second, many languages don't properly use the hardware instructions and if they do they often don't use them correctly. For example, Java 8 has bog slow SHA-1, AES-GCM and MD5 implementations, and switching to Amazon Coretto Crypto Provider (which is just using proper native crypto) was able to speed SHA/MD5 up by 50% and AES-GCM by ~90% on a reasonably large deployment (although the JDK wasn't using proper hardware instructions for AES-GCM until Java 9 I think it is still slower even after that).
That being said, like I disclaimed at the top of the benchmark your particular hardware and your particular language matters a lot.
[1] https://github.com/corretto/amazon-corretto-crypto-provider/...
It's not in the standard library, can't just import it and expect it to always be there
However, I often find myself in situations where I care neither about speed nor any other of the traditional performance metrics (memory consumption, latency, bandwidth, parallelizability, etc ...).
In these situations, what I actually care about is:
a) code size (as in: fits compiled in 512 bytes)
b) code simplicity (as in: fits in head, takes up around 20 C++ LOC)
Exceptions:
TEA : https://en.wikipedia.org/wiki/Tiny_Encryption_Algorithm
Speck: https://en.wikipedia.org/wiki/Speck_(cipher)
Both of these are ciphers, and both can be perverted into becoming hashes for various scenarios.
But, there aren't any compression or native crypto-hard hashing algorithms that I know of that are specifically designed to optimize along that particular dimension.
Blake3 or zstd are large pieces of code.
If you need bloom filters, then use split block bloom filters [1] which use SIMD to increase speed from 30%-450%.
If you need erasure coding, then use Cauchy Reed-Solomon instead of Reed-Solomon. Cauchy Reed-Solomon uses pure XOR so you can do erasure coding at the speed of per-core memory bandwidth.
Therefore these are very fast when using the hardware support, so they are a natural choice versus other algorithms that must be implemented in software, which may be slower even when they seem much simpler.
Unless you have gigabytes of user IDs to hash on a regular basis, it doesn't matter what hash you use aside from achieving the randomness you desire, which I imagine almost any function, even x%2==0, would achieve.