… premature optimization is the root of all evil. […]
- Donald Knuth
There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.
- Donald Knuth
Optimization Makes Your Code Worst
Your first version should usually strive to be clean and simple
Any optimizations you do will take you away from the ideal
There’s no lower bound on code complexity and readability!
You need A GOOD REASON to optimize You need to know WHEN TO STOP
99% of optimizations happen at the design stage
If you do things well, micro-optimizations should be rare
Addresses mis-alignment between your program and the system it’s running on
Performance is mesured on:
Latency: How long something takes
Throughput: How much we can process per second
They are NOT linearily corelated to each other!
Increasing THROUGHPUT may increase or decrease LATENCY
Reducing LATENCY may decrease or increase THROUGHPUT
Set latency and throughput targets
BEFORE YOU START designing or optimizing code
Glamourized by war stories which fall in 2 categories:
- Brenden Gregg style bottleneck hunting
- Cool micro-optimizations stories, usually from the 80s
This will rarely match your reality
A hot-code path are performance sensitives areas of the code
A bottleneck is a where your hot-code path is spending all its time
hot-code paths: macro, doesn’t change as you optimize
bottlenecks: micro, changes as you optimize
hot-code paths: identified by understanding how your program is used
bottlenecks: identified through profiling and mesurements
Not everything is a CPU bottleneck
In fact, on modern CPUs, it’s RARELY the bottleneck
[remi@lga-gateway-1 ~]$ sudo perf stat --timeout 1000 -p $(pgrep beam) \
-e instructions -e cycles
Performance counter stats for process id '30736':
70,599,271,342 instructions # 0.64 insn per cycle
110,772,021,019 cycles
1.001732423 seconds time elapsedModern CPU can get up to 4 instructions per cycle
[remi@lga-gateway-1 ~]$ sudo perf stat --timeout 1000 -p $(pgrep beam) \
-e L1-dcache-loads -e L1-dcache-load-misses \
-e L1-icache-loads -e L1-icache-load-misses \
-e LLC-loads -e LLC-load-misses
Performance counter stats for process id '30736':
17,821,301,588 L1-dcache-loads (80.00%)
1,348,210,582 L1-dcache-load-misses # 7.57% of all L1-dcache hits (79.99%)
<not supported> L1-icache-loads
1,255,680,990 L1-icache-load-misses (80.01%)
542,559,694 LLC-loads (80.04%)
54,481,642 LLC-load-misses # 10.04% of all LL-cache hits (80.08%)
1.004556160 seconds time elapsedA miss takes about one order of magnitude more time then a hit
[remi@lga-gateway-1 ~]$ sudo perf stat --timeout 1000 -p $(pgrep beam) \
-e iTLB-loads -e iTLB-load-misses \
-e dTLB-loads -e dTLB-load-misses
Performance counter stats for process id '30736':
104,464,755 iTLB-loads
52,767,144 iTLB-load-misses # 50.51% of all iTLB cache hits
16,912,403,505 dTLB-loads
135,281,339 dTLB-load-misses # 0.80% of all dTLB cache hits
1.003465899 seconds time elapsedMemory is your most-likely bottleneck
Design your code to be memory friendly
Network bottlenecks
You can’t optimize the speed of light
Disk bottlenecks
Not all datasets fit in memory sadly.
Off-CPU time
Profilers tend to not mesure when your code isn’t running
Contention
Locks and other form of synchronization mechanism
My personal favourite :)
Essential.
If you’re not mesuring, you’re not optimizing.
WHAT and HOW you mesure are both important and non-trivial
start = now();
bob_the_function();
delta = now() - start;What are we mesuring here?
- bob_the_function()
- time()
- context switches
- interpreters
- JITs
- cache misses
- TLB misses
- page faults
- cpu migrations
- hardware interrupts
- system suspended events
- processes sharing physical core (hyper-thread)
- …
Confounding Factors: external variables that influences your mesurements
Confounding factors need to be controled or eliminated
You want consistency and reproducibility in your mesurements
Compare apples to apples
Degrees matter
If bob_the_function() takes 2 hours Then hardware interrupts unlikely to matter
If bob_the_function() takes 100ms Then context switches could lead to high variance in your results
Caches are everywhere and controlling them is super important
general recommendation for dealing with caches
- pin your process to a cpu
- remove all other processes from the pysical cpu and/or node
- prime your caches before mesuring
- size your dataset according to your cache sizes
Types of caches to control for:
- memory: L1, L2, LLC, I$ D$, TLB
- file system: buffer cache
- kernel caches and queues: networking buffers
- JIT/interpreters
- application caches
Throughput: number of events per second Latency: how long an event takes
Both have a time component so knowing how to mesure time is crucial
clock_gettime()
- CLOCK_REALTIME
- CLOCK_REALTIME_ALARM
- CLOCK_REALTIME_COARSE
- CLOCK_TAI
- CLOCK_MONOTONIC
- CLOCK_MONOTONIC_COARSE
- CLOCK_MONOTONIC_RAW
- CLOCK_BOOTTIME
- CLOCK_BOOTTIME_ALARM
- CLOCK_PROCESS_CPUTIME_ID
- CLOCK_THREAD_CPUTIME_ID
[CLOCK_REALTIME] is affected by discontinuous jumps in the system time (e.g., if the system administrator manually changes the clock), and by the incremental adjustments performed by adjtime(3) and NTP.
– man 2 clock_gettime
The CLOCK_MONOTONIC clock is not affected by discontinuous jumps in the system time (e.g., if the system administrator manually changes the clock), but is affected by the incremental adjustments performed by adjtime(3) and NTP. This clock does not count time that the system is suspended. All CLOCK_MONOTONIC variants guarantee that the time returned by consecutive calls will not go backwards, but successive calls may—depending on the architecture—return identical (not-increased) time values.
– man 2 clock_gettime
CLOCK_MONOTONIC: nanosecond resolution CLOCK_MONOTONIC_COARSE: second level resolution CLOCK_MONOTONIC_RAW: ~ cycle counter
The “vDSO” (virtual dynamic shared object) is a small shared library that the kernel automatically maps into the address space of all userspace applications. Applications usually do not need to concern themselves with these details as the vDSO is most commonly called by the C library. This way you can code in the normal way using standard functions and the C library will take care of using any functionality that is available via the vDSO.
– man vdso
To avoid variance of system calls, use vDSO based clocks
CLOCK_REALTIME CLOCK_MONOTONIC CLOCK_MONOTONIC_COARSE CLOCK_MONOTONIC_RAW
(been a while, need to double check)
Hardware Timestamp Counters If calling clock_gettime() is more expensive then code being timed
#define RDTSC_START(cycles) \
register uint32_t cyc_high, cyc_low; \
__asm volatile("cpuid\n\t" \
"rdtsc\n\t" \
"mov %%edx, %0\n\t" \
"mov %%eax, %1\n\t" \
: "=r"(cyc_high), "=r"(cyc_low)::"%rax", "%rbx", "%rcx", \
"%rdx"); \Use with great care.
- cpuid used to flush the caches
- rax, rbx, rcx rdx registers marked for clobering
- etc.
Plethora of other tools to mesure and visualize perf information:
- perf: hardware performance counters
- ss: network monitoring tool
- iostat: disk monitoring tool
- language specific profilers
- …
The more you know your system and your tools
The easier it will be to know WHAT to mesure and HOW to mesure it
THERE IS NO SHORTCUTS
99% of optimizations happen at the design stage
How you structure your program and data
More important then any micro optimization you could ever make
This happens before you sit down to write any code
Always keep in mind your hot code paths!
Your goal is to minimize the amount of work you do in these code paths.
The main role of code is to process data
How you organize your data is crucial!
Data-structures are the foundation of everything you do. Learn them and use them!
When designing, always have a good understanding of:
- what your data looks like
- how your data is structured
- what operations you need to perform on your data
- what are the performance requirements for each operations
Death by a thousand-cuts is a real thing
Usually caused by inneficient use of the language
Can be hard to detect as it’s evenly spread out everywhere
Micro-optimization: do less work
When working at this level, methodology is important:
- Mesure to form a baseline
- Attempt an optimization
- Mesure the outcome
- If slower then throw away what you did in the garbage
Don’t over invest or get attached to experimental code!
Look at your compiler output!
DON’T waste your time on optimizations that compilers can do trivially.
DO give the compiler a hand when it’s struggling.
godbolt.org is your bestest of friend.
Don’t compute the same thing twice
Leverage your cold paths to speed up your hot paths
Pre-compute things: lookup-tables, indexes, function calls, etc.
You can try to optimize memcpy
Or you could make less copies
Avoid over focusing on a tiny slither of code
Always keep in mind the system as a whole
Good way to make latency and throughput tradeoffs
Can enable things like vectorization and parallelization
And that’s it…
You probably feel cheated or that I’m hiding my magical voodoo secrets
I’m not.
Micro-optimization is very situation dependent and requires creativity
But it always boils down to doing less work