His dismissal of the argument Knuth makes regarding the hot loops could have been explored a bit better. I found it weird he didn’t mention the difference of types of programs of then vs now. Even today, in scientific code it is still absolutely the case a lot of the time that a huge chunk of the runtime comes from a single very very hot loop. It might be hidden in a library, but it’s there.
Instead he focuses only on “program size”.
Knuth samples where very small FORTRAN programs (compared to today’s standards). Today’s program are bigger but the fundamental number crunching primitive of “let’s compute stuff in a loop” remains. It’s just buried under a pile of extra cruft (data loading, parallelism, dispatching etc).
Now we just deal with a lot more programs that are of a whole different class compared to what they where doing with computers in the 70s. We have much more I/O involved. And hot loops don’t like being I/O bound.
Being I/O bound is usually a result of bad engineering practices though.
If you're I/O bound, that either means the problem doesn't require much computation - which is possible but fairly rare, or more likely that your code is so unoptimised that barely any computation gets carried out while your code is waiting on memory/disk/network.
"I can't do anything because my program is I/O-bound" is more of an excuse / mental justification of why your program is slow instead of an honest reason for so.
ETL processes are heavily I/O bound, especially when you're trying to shuttle data from one enterprise system to another enterprise system. It's also common when the culture of data exchange from the regulator all the way down to the companies doing the actual work is batch processing where large amounts of data are shared once a day as opposed to real time. Excel spreadsheets are the norm, not the exception. Requests for data to be sent over via XML or JSON are mainly because my employer wanted to make it easier to process the data ourselves, but the regulators actually expect spreadsheets.
Most of the stuff I work on is almost exclusively network I/O bound. I wouldn't say it's a _result_ of bad engineering practices, though. One group decided on a particular system that's also public-facing, and the group I actually support prefers a more internal-facing system. It also doesn't help that the budgets for both projects are completely separate and firewalled from each other by law. Growth opportunities don't apply here because I deal with a captive market with legally-forced customers.
No, I don't think the way you're characterizing this is accurate. I/O is inherently very slow compared to computation. And many programs genuinely don't have any useful computation to do while waiting for I/O - because the result of that I/O operation contains the information needed for the program to even make its next decision.
Such programs are not necessarily impossible to optimize. One common optimization is to use an event loop, allowing just a few threads to handle thousands of concurrent operations. Because while a thread is waiting for I/O in one request or unit of work, in the meantime it moves on to work on processing another request/unit. Another common optimization is batching/grouping of I/O calls.
> I/O is inherently very slow compared to computation
This isn't really true anymore. IO has bad latency, but modern SSD bandwidth is ~5-15GB/s. If your program is IO latency bound and processing less that 5GB/s you aren't IO bound, you aren't hiding your latency well enough.
> I/O is inherently very slow compared to computation.
Not anymore, no. Your SSD, before any caching, does gigabytes per second of sequential reads. For any bytewise processing, except the most trivial of tasks, you’ll struggle to get above a few hundred megabytes per second with scalar (native) code. To actually keep up with a modern SSD, you’ll virtually always have to hand-write SIMD loops, minimize the number of syscalls with tools like io_uring, or possibly be smart about distributing tasks across cores without ruining the access pattern.
For instance, simdjson is famously fast but I don’t believe it can keep up with say a high-end PCIe Gen 4 SSD like a Samsung 990 PRO, let alone the latest-and-greatest (and, literally, hottest) Gen 5 stuff. And I know of no Unicode normalizer that would be able to do a gigabyte per second on general inputs (not ASCII, not Latin-1) simply because the latency for dependent lookup table accesses is absolute murder.
Your analysis is correct if and only if the data is on the same machine as the calculations. If the data comes from another machine, it comes at network speed. If it comes from the internet, it comes at non-local network speed. That's very different from SSD speed.
No, you're comparing apples and oranges. All an SSD sequential read is doing is copying data from one place to another. So you should be comparing SSD bandwidth to memory bandwidth, not SSD bandwidth to (time it takes to execute some arbitrary algorithm). Or you should be comparing SSD bandwidth when performing millions of tiny random non-sequential reads and writes, to the algorithm time.
What your comment demonstrates is that it is possible in some cases for I/O to be fast enough to not be a performance bottleneck for certain kinds of programs. But not that I/O is not slow.
Muratori et al. like comparing speeds to (single-core) memory bandwidth (dozens of GB/s) and that’s a reasonable upper bound, but generally it seems to me that, unless you operate on huge elements and don’t do very much with them, you won’t get within an order of magnitude of it. Even if you think about RAM exclusively, the headline numbers are for sequential reads and things will slow down dramatically if you actually perform random accesses (IIRC, DDR5 is about as slow as DDR4 there in terms of physical time units, so much slower in terms of bus cycles). Meanwhile, in a real situation, you’re going to be bound by compute long before that.
And I think you’re being unfair labelling my couple of examples “some arbitrary algorithm[s]”: my choice was indeed arbitrary, but it’s also immaterial. The general setup would be that you’re processing elements in a loop and that your iterations are serialized (as they usually more or less are before you get around to optimization). A loop body of even three lines of C is likely to have a latency of 5–10 cycles or so, and you’re running on a core clocked somewhere from 5 GHz (desktop) to half that (server). So the best you should expect is ~500 MB/s if your elements are bytes, ~2 GB/s if they’re 32-bit integers, etc. For very simple tasks (that are also somehow not susceptible to vectorization), it is possible to not lose this order of magnitude and get down to almost 1 cycle/element in scalar code, but that requires heroic effort[1].
> If you're I/O bound, that either means the problem doesn't require much computation - which is possible but fairly rare
This is backwards. I bet that by count, many more programs are written in domains where they're necessarily IO bound than the inverse. Anything that uses the network for its core functionality, anything reliant on a datasource whose aggregate contents are O(memory)+ size, or anything reliant on slow peripherals (lots of embedded software) are in this class.
Scientific simulations, HFT algorithms, video games, LLMs, etc.--the stuff in the other class--aren't inconsequential, but they're dwarfed in number by the class of software that spends 99+% of its time waiting for IO. Hell, entire programming languages (node.js) have been created in response to that proportion.
That’s completely backwards by orders of magnitude. Modern CPUs outrun L1 cache speed by a lot, L1 cache speed is on order of 1000-5000 GB/s, a GB/s is real bits used, is 8x of Gbps, and network speeds include significant overhead bits for frame packing and other data unused for the actual payloads.
The computers at the time had very little ram. The IBM System/360 didn’t get 1MB until 1968. I suspect a lot of programs were I/O bound just to be able to work at all. Most modern engineers cannot conceive of doing anything useful with 64KB and I think it’s a mistake to project modern practices 50 years into the past.
Plenty of scientific simulations end up being IO or communications bound when at scale (e.g. 30k CPU cores). Can hide latency to a certain degree but basically any algorithm that uses timestepping must halt at some point to allow data to flow around the nodes, or to dump data to disk for visualisation or checkpointing.
In saying that there are some novel and very clever algorithms that continue on without seemingly necessary boundary data, that then self correct when the data comes through, thus completely hiding the latency at the cost (in both accuracy and time) of running a correction process.
His dismissal of the argument Knuth makes regarding the hot loops could have been explored a bit better. I found it weird he didn’t mention the difference of types of programs of then vs now. Even today, in scientific code it is still absolutely the case a lot of the time that a huge chunk of the runtime comes from a single very very hot loop. It might be hidden in a library, but it’s there. Instead he focuses only on “program size”. Knuth samples where very small FORTRAN programs (compared to today’s standards). Today’s program are bigger but the fundamental number crunching primitive of “let’s compute stuff in a loop” remains. It’s just buried under a pile of extra cruft (data loading, parallelism, dispatching etc).
Now we just deal with a lot more programs that are of a whole different class compared to what they where doing with computers in the 70s. We have much more I/O involved. And hot loops don’t like being I/O bound.