Hacker News Reader

Comment by drewg123 | Hacker News Reader

I disagree. RAM is still a huge bottleneck. Even when there is sufficient bandwidth, latency is a performance killer.

I just spent most of the weekend trying to optimize a hash table lookup which is one of our biggest sources of cache misses (and CPU stalls). The CPI (cycles per instruction) in that function started as 13.9 and I have it down to 7.5 by re-ordering a few fields and cacheline-aligning the struct (so as to have 1 cache miss per iteration, rather than 2). Now I need to figure out what's wrong with the hash function, as the table should be big enough to hold everything without much pointer chasing on average, but I'm seeing we do at least one pointer deref on average before we find the entry we're looking for.

View on HN

SDRAM latency is definitely not keeping up with improvements in throughput: if you go back to the time of the PC100 SDRAM standard (late 90s?) it was not uncommon to see RAM with CAS latency of 2 clocks and overall timings compatible with a latency of around 20-25ns; now with DDR5-4800, CL 34 is standard and latencies have only come down to about 15ns.

This despite the number of MT/s increasing 48-fold.

Computer architects use the term 'memory wall' to refer to this latency problem. CPU microarchitectures are constantly improved to improve IPC, Die technology helps increase CPU frequency, but memory access latency is not keeping up with the CPU improvements.

Right - I think, at this point, that L1 cache latency is worse than main-memory latency on a 'per CPU clock' basis than it was in the late 1990s!

Makes sense for a larger cache to take longer to decode an address.

I've had a devil of a time looking this up. Perhaps you'd know:

Back in the Amiga days, 60ns SIMMs were common. Some CPU accelerator boards could run faster if you upgraded to 50ns SIMMs instead. What did those numbers refer to? Latency? Time to fetch a byte? Something else?

I'd be interested in an apples-to-apples comparison of the old hardware with the new.

Those times referred to the speed of the actual ICs on the PCB. A “60 ns” SRAM IC takes up to 60 nanoseconds from the (input) address lines going stable to the (output) data lines going stable. If you sampled the data bus during those 60 nanoseconds, you might get incomplete data. Swapping for 50 ns modules means the ICs were verified to take less time for the data bus to be valid.

It’s a bit like overclocking your memory nowadays. Basically, the 50 and 60 nanosecond parts might be the same silicon, but the 50 ns ones were validated to perform at that speed. Today, a 3200 MT/s DDR4 module doesn’t mean it won’t run at 3600 MT/s; just that it was only verified to run at the former.

---

The big difference between the two memory formats, however, is that DDR is pipelined. In the old days, you would present an address on the bus, hold it, and then wait for the data to come back. Only after sampling the data could you request a new address. DDR, being pipelined, allows you to request an address, and, before the data comes back, request a new address. After a while, the data from the first address would come back, followed by the data from the second.

That alone makes apples-to-apples comparisons hard.

With original DRAM you had the row strobe, the column strobe and then you could read out your data. You then had to precharge the row again before doing another access. Page mode DRAM improved on this by allowing you to keep the row open and read multiple columns, but you had to wait until the read completed before presenting the next column address. Enhanced-data-out (EDO) DRAM extends this by allowing you to pipeline accesses with the row.

So the ability to pipeline is much older than DDR. DDR SDRAM is an evolution on SDRAM, which is the first variety of DRAM that is actually clocked (and came after EDO); and the main innovation is transfer on both edges of the clock (falling as well as rising) - hence double-data-rate.

Ah, thank you for that! So you could fetch 1/(60ns) bytes per second synchronously, then (assuming the CPU could run in a loop that tightly)?

No; because after the read, you need to precharge the row again (due to the design of dynamic RAM).

ref. https://en.wikipedia.org/wiki/Dynamic_random-access_memory#M...

The quoted "50 ns" DRAM has a read-cycle time of 84 ns.

Oh, interesting. I’ll read up more on that.

Any chance you can switch the hash table to use probing rather than chaining? Probing is way better for locality because on collisions you will just look at the next element in ram.

This table is not well suited for that, but it did get me interested in re-structuring it. Thanks for the suggestion!

Hash function quality varies a lot. Especially if you are memory-limited, it can help to use a round-reduced cryptographic hash to rule out unnecessary collisions. Example: Speck (= add/rotate/xor), but just reducing the number of rounds. And if that is again too expensive on the CPU side, we can always vectorize by inserting or looking up batches of keys at a time.

Small tangent. Would you mind sharing how you calculate CPI? Do you just do timing and use some base clock rate? With the CPU frequency being so variable (with boost clocks) I imagine the correct way is with some fancy instrumentation.

Perhaps cachegrind or linux perf? CPU frequency being variable is not an issue because you can disable turbo boost and limit the frequency to something that the CPU will not throttle. You can also pin the core with taskset to avoid migration. cset shield can prevent the CPU from executing other tasks for latency measurement (although you will still experience some jitter due to interrupts).

Reply on news.ycombinator.com