1-hour dive into things worth knowing about contemporary CPUs & memory

Dmitry Petrashko

Date matters

Source: https://people.eecs.berkeley.edu/~rcs/research/interactive_latency.html

Initially, in order to be fast, you wanted to make sure you remove branch mispredicts. A lot of techniques have been built to trade them with memory references. Only a couple years later, situation has changed. In ~2000, memory latency stopped improving. today, the biggest cost is memory references. This leads to a couple of interesting artifacts: 1. More and more, caching is becoming a thing that is not only not worth doing, but a thing that could make you slower. Caching trades computation for memory usage. Introducing cache in one place, evicts data of other places. 2. Benchmarking does not caputre this well: microbenchmarks normally work on small sets of data and thus don't see cache missess. Even if there's a lot of data, reproducing access patterns is very hard. SwissTable Similar things might happen to storage soon: it used to be the case that reading data from disk was slow, while reading it from server in same rack was faster. It used to take 0.5ms to do a round trim in datacenter, while 10ms to read best disks, now, it takes the same ammount of time to read from SSD.

Performance recipes do not age well.

What used to be good idea, may become a subpar approach soon.

Understanding hardware

Tenchiques used by hardware are tricky and change fast, but general ideas are simple and stay the same:

temporal bet;
spacial bet;
pattern bet.

Temporal bet

If you've used a resource, you'll use it again soon.

Temporal bet: illustration

first read of an integer from memory takes ~100ns;
second read of same integer that follows first one will take <1ns.

Spacial bet

If you've read some data, you'll soon read more data close to it.

Spacial bet: illustration


val a: Array[Array[Int]] = ...
val i = 0
while (i < n) {
 val j = 0
 while (j < n) {
  if(fast) {
    a[i][j] += a[i][j]
  } else { // slow
    a[j][i] += a[j][i]
  }
  j += 1
 }
 i += 1
}

Advice

getting performance is hard, needs a lot of exploration;
exploration needs to be repeated - old recipes don't age well;
loosing performance is easy, seemingly small changes can kill it;
tracking performance from start is crucial;
measure on an isolated machine with the same environment for all runs.

Thank you.

Q & A

Further read: