Hacker News Reader

Comment by memset | Hacker News Reader

Thank you for this! Here is my question, though. I have an example C program that uses mmap() to read data from a file. It can do this linearly or select random records. I'm running it on my M1 mac.

https://gist.github.com/poundifdef/e748c467d354662ed034b5f64...

The script runs orders of magnitude slower when I do random reads rather than linear. Theoretically this seems like it should not be the case since it is running on an SSD, but clearly there are other tricks the OS (or hardware?) is doing to optimize for the linear case.

I'm looking to better understand why I'm observing that performance difference and how I can better design software around it, even though (intuitively) it seems like it should not matter with non-mechanical disks.

View on HN

Disk-based and in-memory algorithms and data structures need similar techniques these days. The numbers are just different.

RAM latency is something like 100 ns, or maybe a bit less. Sequential read speed ranges from tens to hundreds of gigabytes per second. However, if you divide cache line size by latency, you are still orders of magnitude below that. If an algorithm accesses the memory randomly and waits for the results before continuing, it's often much slower than an algorithm that reads sequentially, even when the structs are conveniently the size of a cache line.

SSD read latency is around 100 µs, or three orders of magnitude higher. Sequential read speed is gigabytes per second, or 1-2 orders of magnitude lower. Again, if you divide page size by latency, you are nowhere near the peak throughput. Reading sequentially can be much faster, because the OS and the controller can guess your intent and read ahead.

As a sibling comment pointed out, this is about the page (or block) size. Both disks and SSDs share the property that reads are done in a block, 256KB or more. So even if you're reading a few bytes you are actually reading the entire block. In the linear (sequential) read case, you are using it all.

The block size is a parameter in the theoretical model for I/O-efficient computation.

Okay. Does this imply that I should see similar SSD read speeds when reading 10 blocks contiguously vs randomly?

If I can fit, say, 2k records into a single block, then I would expect reading the first 4k pieces of data to have similar SSD read performance compared to reading 2k from the first and 2k from the last? (Haven't coded the experiment yet, but that would be the prediction?)

And: to the point of using block size as a parameter, do you have suggestions on further reading for techniques people have used to incorporate that into the design of their structures? Or is it basically the same as efficient paging algorithms?

> Okay. Does this imply that I should see similar SSD read speeds when reading 10 blocks contiguously vs randomly?

Yes, with some caveats:

1. Not sure if you can read block-aligned data from high-level code.

2. There might be some read-ahead heuristics in the I/O stack.

> techniques people have used to incorporate that into the design of their structures?

I haven't kept up with the research. You can try searching on scholar.google.com for "I/O-efficient" algorithms and data structures. Also "cache-oblivious". There should be some good surveys now, since this is not a new research area.

Note that most of the algorithms that were optimized for disk reads did not typically take into consideration sequential vs random reads. The model simply assumed that reading a block of size B has a unit cost and the performance of algos/ds was expressed in terms of the number of these units.

You will like this https://ayende.com/blog/posts/series/195587-B/implementing-a... and https://www.reddit.com/r/databasedevelopment/ where it talks about this kind of stuff.

Someone did test exactly that:

https://panthema.net/2019/0322-nvme-batched-block-access-spe...

From my experience as long as you can do that access multithreaded you won't really be penalized for random reads. Single threaded access I've seen as much as read performance halved (used fio for testing), but that didn't translate into multithreaded benchmarks

Just to be a bit pedantic, what you really want is several concurrent IOs, doesn’t have to be multithreaded. For example, io_uring can kick off many concurrent IOs off a single (userspace) thread.

But yes, if you don’t have io_uring you need to use threads, and if you use a lot of them context switches can have a nontrivial overhead from my experience.

Pedantic and wrong, good fucking luck saturating whole SSD from single thread on anything else than pure benchmark code

SSDs generally read at the page level, so you can get full performance or close to it from much smaller reads than 256KB or more.

For example, you may be able get maximum performance from 4K or 8K byte reads. Of course, there are a few layers between you and the SSD so you have to make sure you have the SSD actually sees enough pending requests at all times for maximum performance. If you just read one 4K block before submitting the next one, you'll get terrible performance because at queue depth of 1 the SSD is utilized most of the time (i.e., the bandwidth delay product is much lager than 4096 bytes).

This effect can lead the erroneous conclusion that small block sizes are slow when queue depth is actually the confounding factor (large blocks effectively feed many page-sized read requests to the SSD at once, so you can get away with a lower queue depth).

Writes are different but you also don't need gigantic block sizes. For SSDs available as EC2 local storage, for example, a 4K random write load can extract full performance if you get the other parameters right.

That program's data set is only 0.8 GB, which is like $10 of RAM. The time difference you're measuring between random & sequential access is probably mostly due to CPU cache and TLB, not flash.

Whatever real-world application you have in mind, this probably isn't representative. It pays to have realistic benchmarks before spending much time optimizing.

Understood - it sounds like the idea of a “minimal working code example” will give misleading results. I’ll pay more attention to this when testing, I appreciate it.

Shouldn't matter as long as you do direct IO for benchmarking

Once you mmap() a file the OS will (probably) use the same algorithms for accessing data as it uses for virtual memory. So you probably want to read:

https://news.ycombinator.com/item?id=19302299

If you want to get good random read performance out of an SSD, you can't use mmap. A thread can only page fault on one address at a time, but full random IO performance requires giving the SSD many requests to work on in parallel.

This, you should open the fd in O_DIRECT, non-mmap'ed

You have a lot more control this way

In the random case you’re reading a whole page to get some tiny struct.

Reply on news.ycombinator.com