Efficiency vs Performance

Efficiency = doing less work

either by using a better algorithm
or by not doing unnececary work

Performance = doing it faster

Using hardware more efficiently

Know your hadrware

Adventures begin!

Adventures make you question your assumptions.

Can inefficient algorithm be more performant?

InsertionSort vs QuickSort for small arrays

"Small" is up to 5000 elements

In many programs average length of array is <4 elements.

Why?

QuickSort is on average O(N log N)
InsertionSort is on average O(N * N)
both O hide constant multiplier
constant for Insertion sort is much smaller

Efficient
Performant
Fast

None of them imply the other

Can doing more work be faster than doing less?

Can 64-byte write be faster than 1-byte write

Yes, when it's aligned!

Why?

memory is always read and written in 64-byte lines
if you need to write 1 byte you
- read full 64-byte line
- replace 1 byte
- write full 64-byte line

Less instructions -> faster code?

See previous example :-)

Some instructions are "simple", some are "hard"

Sometimes cpu is simply wierd

Weird example:

Taken from Eli Bendersky: http://eli.thegreenplace.net/2013/12/03/intel-i7-loop-performance-anomaly/

const unsigned N = 400 * 1000 * 1000;
volatile unsigned long long counter = 0;
void foo() {}

void loop_with_extra_call() {
  unsigned j;
  for (j = 0; j < N; ++j) {
    // __asm__("call foo");
    counter += j;
  }
}

on Haswell: 0.686s without call, 0.602 with call

Likely cause: loop aligment

Can a single threaded program do work in parallel?

GC is a different thread: does not count.

Instruction level paralelism

def foo(a: Array[Int], idx: Int) = {
  val s = a[idx]
  return idx * idx + idx / 2 + idx * 6 + s;
}

CPU: superscalar

Issue Width in Haswell: 8.

Can failed CPU speculations be good?

"Good" failed speculations

def foo(a: Array[Int], idx: Int) = {
  val s = a[idx]
  if (s < 0) idx + idx
  else idx - idx
}

Both branches will be executed in parallel, only one of them will be retired

Failed speculations can be good!

Reasoning about performance

"Date" makes a difference

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
}

Pattern bet

Behaviour of your program has simple repeating patterns.

Pattern bet: illustration

val a: Array[Int] = Array.fill(1000000)(scala.util.Random.nextInt)
// a = a.sorted // speeds up the loop below by 6x

val i = 0
while (i < n) {
 if (a[i] > 0) 
  a[i] += 1
 i += 1
}

Made a change and your app became faster?

Be aware of layout changes:

layout of code can impact performance by ~5%.
even size of starting environment can! Includes folder name!

See Mytkowicz, Todd, et al. "Producing wrong data without doing anything obviously wrong!."

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:

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