Adventures in efficiency and performance

Dmitry Petrashko


About me:

  • Defended PhD at EPFL on architecture and implementation of Dotty
  • previously worked on ScalaBlitz, that influenced design of new collections
  • started Dotty Linker & optimizer project
  • working on a not-yet-announced project at Stripe

Date matters

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 microseconds.

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
}

Advise

  • getting performance is hard, needs a lot of exploration;
  • explaration 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: