Chapter 1 - My program is too slow

Oct 20, 2023

Intro to Part 1:

Our overall goal is to understand the root causes of variance in transaction latency - the apparently random unexpectedly long repsonse times in comlex software

This part also introduces the important practice of estimating within a factor of 10 how long pieces of code should take

Chapter 1

Definitions:

The median (or similar average) latency is a particularly ill-suited description of a skewed or multi-peak distribution because it rarely is near many of the actual values and it tells us nothing about the shape and size of the long tail - our topic of interest

Expectations───────────┐ │ │ ┌─────────┐ │ ┌─────────┐ │ System │ ┌─────▼──────┐ ┌─────────┐ ┌────┐ │ Offered ├─────► Under ├───────►Observations├───────►Reasoning├────►Fix │ │ load │ │ Test │ └────────────┘ └─────────┘ └────┘ └─────────┘ └─────────┘

Order-of-Magnitude Estimates

Numbers every programmer should know

Action Time O(n)
L1 cache reference .5 nsec O(1) nsec
Branch mispredict 5 nsec O(10) nsec
L2 cache reference 7 nsec O(10) nsec
Mutext lock/unlock 25 nsec O(10) nsec
Main memory reference 100 nsec O(100) nsec
Compress 1k bytes with zippy 3000 nsec O(1) usec
Send 2k bytes over 1Gbps network 20,000 nsec O(10) usec
Read 1mb sequentially from memory 250,000 nsec O(100) usec
Round trip within same datacenter 500,000 nsec O(1) msec
Disk seek 10,000,000 nsec O(10) msec
Read 1mb sequentially from disk 20,000,000 nsec O(10) msec
Send packet CA -> Netherlands -> CA 150,000,000 nsec O(100) msec

Doing an order of magnitude estimate of expected times in various parts of a program makes it easy, when you get real measurements of those times, to spot ones that differ substantially from your expectations. This is where the learning is

The five fundamental resources

There are only four computer hardware resources shared between unrelated programs running on a single server:

If a program has multiple cooperating threads, there is a fifth fundamental resource:

↑ up