5 ms·

It looks suspicious at 25x. Even 2.5x would be suspicious unless reading very small records. I assume both cases have the file cached in RAM already fully, wit

It looks suspicious at 25x. Even 2.5x would be suspicious unless reading very small records. I assume both cases have the file cached in RAM already fully, with a tiny size of 100MB. But the file read based version actually copies the data into a given buffer, which involves cache misses to get data from RAM to L1 for copying. The mmap version just returns the slice and it's discarded immediately, the actual data is not touched at all. Each record is 2 cache lines and with random indices is not prefetched. For the CPU AMD Ryzen 7 9800X3D mentioned in the repo, just reading 100 bytes from RAM to L1 should take ~100 nanos. The benchmark compares actually getting data vs getting data location. Single digit nanos is the scale of good hash tables lookups with data in CPU caches, not actual IO. For fairness, both should use/touch the data, eg copy it.

Scaevolus 1y ago
Yeah, 3.3ns is about 12 CPU cycles. You can indeed create a pointer to a memory location that fast!
kragen 1y ago
> For the CPU AMD Ryzen 7 9800X3D mentioned in the repo, just reading 100 bytes from RAM to L1 should take ~100 nanos. I think this is the wrong order of magnitude. One core of my Ryzen 5 3500U seems to be able to run memcpy() at 10 gigabytes per second (0.1 nanoseconds per byte) and memset() at 31 gigabytes per second (0.03 nanoseconds per byte). I'd expect a sequential read of 100 bytes to take about 3 nanoseconds, not 100 nanoseconds. However, I think random accesses do take close to 100 nanoseconds to transmit the starting row and column address and open the row. I haven't measured this on this hardware because I don't have a test I'm confident in.
- bcrl 1y ago
  100 nanoseconds from RAM is correct. Latency != bandwidth. 3 nanoseconds would be from cache or so on a Ryzen. You ain't gonna get the benefits of prefetching on the first 100 bytes.
  - kragen 1y ago
    Yes, my comment clearly specified that I was talking about sequential reads, which do get the benefits of prefetching, and said, "I think random accesses do take close to 100 nanoseconds".
    - bcrl 1y ago
      If you're doing large amounts of sequential reads from a filesystem, it's probably not in cache. You only get latency that low if you're doing nothing else that stresses the memory subsystem, which is rather unlikely. Real applications have overhead, which is why microbenchmarks like this are useless. Microbenchmarks are not the best first order estimate for programmers to think of.
      - kragen 1y ago
        Yes, I went into more detail on those issues in https://news.ycombinator.com/item?id=45689464 https://news.ycombinator.com/item?id=45689464, but overhead is irrelevant to the issue we were discussing, which is about how long it takes to read 100 bytes from memory. Microbenchmarks are generally exactly the right way to answer that question. Memory subsystem bottlenecks are real, but even in real applications, it's common for the memory subsystem to not be the bottleneck. For example, in this case we're discussing system call overhead, which tends to move the system bottleneck inside the CPU (even though a significant part of that effect is due to L1I cache evictions). Moreover, even if the memory subsystem is the bottleneck, on the system I was measuring, it will not push the sequential memory access time anywhere close to 1 nanosecond per byte. I just don't have enough cores to oversubscribe the memory bus 30×. (1.5×, I think.) Having such a large ratio of processor speed to RAM interconnect bandwidth is in fact very unusual, because it tends to perform very poorly in some workloads. If microbenchmarks don't give you a pretty good first-order performance estimate, either you're doing the wrong microbenchmarks or you're completely mistaken about what your application's major bottlenecks are (plural, because in a sequential program you can have multiple "bottlenecks", colloquially, unlike in concurrent systens where you almost always havr exactly one bottleneck.) Both of these problems do happen often, but the good news is that they're fixable. But giving up on microbenchmarking will not fix them.
a-dub 1y ago
doing these sorts of benchmarks is actually quite tricky. you must clear the page cache by allocating >1x physical ram before each attempt. moreover, mmap by default will load lazy, where mmap with MAP_POPULATE will prefetch. in the former case, reporting average operation times is not valid because the access time distributions are not gaussian (they have a one time big hit at first touch). with MAP_POPULATE (linux only), there is long loading delay when mmap is first called, but then the average access times will be very low. when pages are released will be determined by the operating system page cache eviction policy. the data structure on top is best chosen based on desired runtime characteristics. if it's all going in ram, go ahead and use a standard randomized hash table. if it's too big to fit in ram, designing a structure that is aware of lru style page eviction semantics may make sense (ie, a hash table or other layout that preserves locality for things that are expected to be accessed in a temporally local fashion.)
- codedokode 1y ago
  > you must clear the page cache In Linux there is a /proc/sys/vm/drop_caches pseudo file that does this. Look how great Linux is compared to other OSes.
  - a-dub 1y ago
    that's super cool! live and learn. even better would be the capability to drop caches from a supplied point in the filesystem hierarchy.
    - ahoka 1y ago
      People would run it from cron to "free memory", believe it or not.
      - DoctorOW 1y ago
        Hence, https://www.linuxatemyram.com/ https://www.linuxatemyram.com/
hyc_symas 1y ago
That's such an obvious error in their benchmark code. In my benchmark code I make sure to touch the data so at least the 1st page is actually paged in from disk. https://github.com/LMDB/dbbench/blob/1281588b7fdf119bcba65ce5f19fe2133dd59f31/t_lmdb.c#L228 https://github.com/LMDB/dbbench/blob/1281588b7fdf119bcba65ce...
checker659 1y ago
Latency Numbers Every Programmer Should Know (originally by Jeff Dean / Peter Norvig) https://gist.github.com/jboner/2841832 https://gist.github.com/jboner/2841832
Tuna-Fish 1y ago
> For the CPU AMD Ryzen 7 9800X3D mentioned in the repo, just reading 100 bytes from RAM to L1 should take ~100 nanos. It's important to note that throughput is not just an inverse of latency, because modern OoO cpus with modern memory subsystems can have hundreds of requests in flight. If your code doesn't serialize accesses, latency numbers are irrelevant to throughput.

Scaevolus 1y ago

Yeah, 3.3ns is about 12 CPU cycles. You can indeed create a pointer to a memory location that fast!

kragen 1y ago

> For the CPU AMD Ryzen 7 9800X3D mentioned in the repo, just reading 100 bytes from RAM to L1 should take ~100 nanos. I think this is the wrong order of magnitude. One core of my Ryzen 5 3500U seems to be able to run memcpy() at 10 gigabytes per second (0.1 nanoseconds per byte) and memset() at 31 gigabytes per second (0.03 nanoseconds per byte). I'd expect a sequential read of 100 bytes to take about 3 nanoseconds, not 100 nanoseconds. However, I think random accesses do take close to 100 nanoseconds to transmit the starting row and column address and open the row. I haven't measured this on this hardware because I don't have a test I'm confident in.

bcrl 1y ago
100 nanoseconds from RAM is correct. Latency != bandwidth. 3 nanoseconds would be from cache or so on a Ryzen. You ain't gonna get the benefits of prefetching on the first 100 bytes.
- kragen 1y ago
  Yes, my comment clearly specified that I was talking about sequential reads, which do get the benefits of prefetching, and said, "I think random accesses do take close to 100 nanoseconds".
  - bcrl 1y ago
    If you're doing large amounts of sequential reads from a filesystem, it's probably not in cache. You only get latency that low if you're doing nothing else that stresses the memory subsystem, which is rather unlikely. Real applications have overhead, which is why microbenchmarks like this are useless. Microbenchmarks are not the best first order estimate for programmers to think of.
    - kragen 1y ago
      Yes, I went into more detail on those issues in https://news.ycombinator.com/item?id=45689464 https://news.ycombinator.com/item?id=45689464, but overhead is irrelevant to the issue we were discussing, which is about how long it takes to read 100 bytes from memory. Microbenchmarks are generally exactly the right way to answer that question. Memory subsystem bottlenecks are real, but even in real applications, it's common for the memory subsystem to not be the bottleneck. For example, in this case we're discussing system call overhead, which tends to move the system bottleneck inside the CPU (even though a significant part of that effect is due to L1I cache evictions). Moreover, even if the memory subsystem is the bottleneck, on the system I was measuring, it will not push the sequential memory access time anywhere close to 1 nanosecond per byte. I just don't have enough cores to oversubscribe the memory bus 30×. (1.5×, I think.) Having such a large ratio of processor speed to RAM interconnect bandwidth is in fact very unusual, because it tends to perform very poorly in some workloads. If microbenchmarks don't give you a pretty good first-order performance estimate, either you're doing the wrong microbenchmarks or you're completely mistaken about what your application's major bottlenecks are (plural, because in a sequential program you can have multiple "bottlenecks", colloquially, unlike in concurrent systens where you almost always havr exactly one bottleneck.) Both of these problems do happen often, but the good news is that they're fixable. But giving up on microbenchmarking will not fix them.

a-dub 1y ago

doing these sorts of benchmarks is actually quite tricky. you must clear the page cache by allocating >1x physical ram before each attempt. moreover, mmap by default will load lazy, where mmap with MAP_POPULATE will prefetch. in the former case, reporting average operation times is not valid because the access time distributions are not gaussian (they have a one time big hit at first touch). with MAP_POPULATE (linux only), there is long loading delay when mmap is first called, but then the average access times will be very low. when pages are released will be determined by the operating system page cache eviction policy. the data structure on top is best chosen based on desired runtime characteristics. if it's all going in ram, go ahead and use a standard randomized hash table. if it's too big to fit in ram, designing a structure that is aware of lru style page eviction semantics may make sense (ie, a hash table or other layout that preserves locality for things that are expected to be accessed in a temporally local fashion.)

codedokode 1y ago
> you must clear the page cache In Linux there is a /proc/sys/vm/drop_caches pseudo file that does this. Look how great Linux is compared to other OSes.
- a-dub 1y ago
  that's super cool! live and learn. even better would be the capability to drop caches from a supplied point in the filesystem hierarchy.
  - ahoka 1y ago
    People would run it from cron to "free memory", believe it or not.
    - DoctorOW 1y ago
      Hence, https://www.linuxatemyram.com/ https://www.linuxatemyram.com/

hyc_symas 1y ago

That's such an obvious error in their benchmark code. In my benchmark code I make sure to touch the data so at least the 1st page is actually paged in from disk. https://github.com/LMDB/dbbench/blob/1281588b7fdf119bcba65ce5f19fe2133dd59f31/t_lmdb.c#L228 https://github.com/LMDB/dbbench/blob/1281588b7fdf119bcba65ce...

checker659 1y ago

Latency Numbers Every Programmer Should Know (originally by Jeff Dean / Peter Norvig) https://gist.github.com/jboner/2841832 https://gist.github.com/jboner/2841832

Tuna-Fish 1y ago

> For the CPU AMD Ryzen 7 9800X3D mentioned in the repo, just reading 100 bytes from RAM to L1 should take ~100 nanos. It's important to note that throughput is not just an inverse of latency, because modern OoO cpus with modern memory subsystems can have hundreds of requests in flight. If your code doesn't serialize accesses, latency numbers are irrelevant to throughput.