4 ms·

There are a lot of interesting algorithms, but as the author points out, he had to move the data to a RAM drive to avoid the disk access being the limiting fact

by HWR_14 5y ago

There are a lot of interesting algorithms, but as the author points out, he had to move the data to a RAM drive to avoid the disk access being the limiting factor. For a lot of use cases, it's not the CPU that is going to limit you. I did love the anecdote about adding gzip moving the bottleneck to the cpu from the network, and actually slowing down the whole system.

jiggawatts 5y ago
Storage is the limit until it isn't. 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 ))))); Even if forced to use that sequence because of a legacy format, ideally that sequence should be distributed between CPU cores so that one core is responsible for zip decode while another core is doing the low-level parsing, and the third core is building the object model. 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.
- adgjlsfhk1 5y ago
  Note that there are totally valid reason to not saturate NVME read speeds. Given the read vs write speeds of modern SSDs, if you have an algorithm that makes your reads 2x slower, but reduces the number of random writes, that can be a major win overall.
- thesz 5y ago
  Your comment kind of support notion "I/O is slow" you seemingly oppose - the I/O that is needed by real world programs may be different from I/O that is fast in benchmarks. 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.
  - nine_k 5y ago
    I/O hardware is fact. The algorithms did not adapt, so I/O in software is slow. Exactly what the author complaints about. 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.
    - thesz 5y ago
      Oh, those pesky algorithms, they did not adapt to the good, good hardware that is so fast. 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-instructions-on-the-apple-m1-processor/ 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.
jandrewrogers 5y ago
Storage is rarely the bottleneck in modern systems, a lot of software is just written as if it was. It is completely ordinary these days to have 4-12+ GB/sec of sustained storage bandwidth available, and that is available to the application if you write the code correctly. 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.
- jolynch 5y ago
  Agree with everything you say except that the post didn't mention non-cryptographic hashing algos that can be driven that hard. xxHash[1] (and especially XXH3) is almost always the fastest hashing choice, as it both is fast and has wide language support. 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 https://github.com/Cyan4973/xxHash [2] https://github.com/google/cityhash https://github.com/google/cityhash

by HWR_14 5y ago

jiggawatts 5y ago

Storage is the limit until it isn't. 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 ))))); Even if forced to use that sequence because of a legacy format, ideally that sequence should be distributed between CPU cores so that one core is responsible for zip decode while another core is doing the low-level parsing, and the third core is building the object model. 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.

adgjlsfhk1 5y ago
Note that there are totally valid reason to not saturate NVME read speeds. Given the read vs write speeds of modern SSDs, if you have an algorithm that makes your reads 2x slower, but reduces the number of random writes, that can be a major win overall.
thesz 5y ago
Your comment kind of support notion "I/O is slow" you seemingly oppose - the I/O that is needed by real world programs may be different from I/O that is fast in benchmarks. 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.
- nine_k 5y ago
  I/O hardware is fact. The algorithms did not adapt, so I/O in software is slow. Exactly what the author complaints about. 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.
  - thesz 5y ago
    Oh, those pesky algorithms, they did not adapt to the good, good hardware that is so fast. 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-instructions-on-the-apple-m1-processor/ 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.

jandrewrogers 5y ago

Storage is rarely the bottleneck in modern systems, a lot of software is just written as if it was. It is completely ordinary these days to have 4-12+ GB/sec of sustained storage bandwidth available, and that is available to the application if you write the code correctly. 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.

jolynch 5y ago
Agree with everything you say except that the post didn't mention non-cryptographic hashing algos that can be driven that hard. xxHash[1] (and especially XXH3) is almost always the fastest hashing choice, as it both is fast and has wide language support. 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 https://github.com/Cyan4973/xxHash [2] https://github.com/google/cityhash https://github.com/google/cityhash