Systems performance book by B. Gregg

system-performance.md

Summary for Systems Performance book by Brendan Gregg

Book it sel on o'reilly

OS-related things

• Kernel -- software that manages the system by providing access to hardware and other resources (memory, network stack, scheduling cpu, etc). Runs in priveleged CPU mode -- kernel mode. It uses kernel-space stack.

• Process -- an OS abstraction for running programs. Runs in user mode with access to kernel mode via system calls. It consists of: memory address space, file descriptors, thread stacks, registers. Process uses user-space stacks. For example, syscalls use a s kernel exception stack associated with each thread.

• System call -- a protocol for user programs to request kernel to perform privileged operations

• Trap -- a signal sent to kernel to request a system routine (system calls, processor exceptions, interrups)

• Hardware interrupt -- a signal sent by devise to kernel, it is a type of trap

• Socket -- endpoints by which user-level aplications access the network

• Network interface -- physical device to connect to network

• IPIs -- inter-processor interrupt which is a way to coordinate processors in multiprocessor system

• SystemD -- service manager on Linux. Among features -- dependecy-aware service startup, analytics (systemd-analyze)

• KPTI -- kernel page table isolation patches to mitigate "meltdown" vulnerability. The cost is 0.1% - 6% depending on number of syscalls (context switch is more expensive)

CPU

• Functional unit CPU component does the following: fetch instruction, decode instruction, execute and (optionaly) memory access, register write-back.

• user-time/kernel-time ratio is high for computationally intensive applications and low for I/O bound (web server, etc).

• MMU -- memory managment unit. Performs virtual memory management. Memory is paged and the chache for pages translation is TLB (translation lookaside buffer). If there is tlb miss, MMU goes to Page tables (main memory).

Performance tools

Some tips and tricks

• futex -- fast user space mutex which is using atomic integer under the hood. Basic operations are WAIT(addr, val) (if *addr == val => current thread sleeps and WAKE(addr, num) (wakes up num threads waiting for the address addr.

• toplev -- tool to find bottleneck in software https://github.com/andikleen/pmu-tools/wiki/toplev-manual

ASM, control flow, etc

Watch all of these https://www.youtube.com/channel/UCmf3tLU4WzOnriEQXa638Bw

Procedure control flow

https://www.youtube.com/watch?v=XbZQ-EonR_I&t=354s

call label // push return address to stack, jump to label
ret // pop return address from stack, jump to address

instructions: conditional if, while, for... and unconditional (break, continue)

How conditional codes work?
There are the following code which store results for conditional operations:

• CF cary flag
• ZF zero flag
• SF sign flag
• OF overflow flag

These are set implicitly after add and other operations for example
And they are used as operands to some jump instructions:

• jmp lavel -- doesn't use codes
• je label -- uses ZF -- jumps if some variable was set to 0 before
• jl lable -- if less (uses SF^OF)

32bits for registers:
%esp -- stack pointer (data) (for register %rsp)
%eip -- instruction pointer
%eax -- used for returned value of the function
So e is for 32 and r is for 64.

some asm notes

movl dst, src (for x86-64)

operands types: (1) immediate (0x400), register (%eax), memory ( -4(%eax))
Cannot do mem-mem in one operation -- need to use intermediate register
Memory addressing modes:

• indirect: movl (%ecx), %eax
• displacement: movl 8(%ebp), %edx

Suffix l for mov means 4bytes, for 8bytes use q
For function call args 16 registers are used, all the other args are on stack

Different address manipulations. Assume that edx = 0xf000, ecx=0x100

• 0x8(%edx) = 0xf000 + 0x8
• (%edx, %exc) = 0xf000 + 0x100
• (%edx,%ecx, 4) = 0xf000 + 4 * 0x100

leal dst, src -- instruction which calculates the effective address (by doing this affine arithmetics) without accessing the memory

TODO https://web.stanford.edu/class/archive/cs/cs107/cs107.1222/assign1/ -- assignments on stanford

лекции чувака по потокам https://www.youtube.com/watch?v=36LMjAFbFfg&list=PL4_hYwCyhAvb7P8guwSTaaUS8EcOaWjxF&index=2

• если два потока и они не взаимодействуют между собой (каждый обрабатывает свой сокет например) -- какие shared variables они имеют? аллокация памяти -- она в юзер спейсе
• race condition -- когда поведение программы зависит от непредсказуемого порядка исполнения
• data race -- когда несколько потоков читают пишут в память которая не покрыта локами
• mutual exclusion -- mutex. между вызовами lock/unlock может находиться только один поток
• clang поддерживает аннотацию переменных GUARDED_BY(mutex name) и методов REQUIRES(mutex):

Mutex mu;
int bla GUARDED_BY(mu);

void withdraw(int amount) REQUIRES(mu) {}

• свойства мутекса:

1. liveness -- mutual exclusion
2. safety -- no mutual block

• deadlock -- нельзя выйти при любом поведении планировщика, livelock -- можно выйти если планировщик верно распланирует
• starvation -- вам долго не везет в плане планировщика
• atomics operations: store(write), fetch_add(read, modify, write), exchange(read, write), load(read)
• contention -- ситуация когда много потоков борятся за один ресурс. busy waiting -- использует ресурсы но ничего не делаем. можно решить на уровне CPU или OS. На уровне CPU PAUSE инструкция а на уровне OS -- sched yield -- отдаем сигнал планировщику что мы уступаем ядро
• futex -- очередь потоков в ядре ОС привязанный к ячейке памяти. FutexWait(addr, value) -- если *addr == value припарковать потом в очереди , FutexWake(addr, count) -- разбудить count потоков в очереди связанной с ячейкой по аддресу addr. В С++20 atomic::wait/wake

some note from модели памяти II

• program order -- partial order of data accesses in one thread (intrustions orders)
• sync with -- partial order of r/w in different threads (atomics for instace can give this )
  => happens-before -- transitive clouse of these two
  data race -- two data access which are not ordered by relation happens-before

So happens-before is out intuition about how the program should execute (sequentially).
For example if there are two threads

T1 -- x = 5 -- myatomic.store(tre)
T2 ---------- if (myatomic == true) -- print x ---

than x is ordered by happens before

Reader/Writer problem and it's solution

https://gclub.com/when-to-use-reader-writer

As shown above, the writer uses the atomic_store_explicit function with memory_order_release to set the guard variable. This ensures that the write to data completes before the write to guard variable completes while allowing for later memory operations to hoist above the barrier.

The reader uses the atomic_load_explicit function with memory_order_acquire to load the guard variable. This ensures that the load of the data starts only after the load of the guard variable completes while allowing for the earlier operations to sink below the barrier.

atomic_store_explicit and atomic_load_explicit functions ensure that the operations are atomic and enforce the required compiler barriers implicitly.

Concurrency models

Why: to reduce incidental complexity of the multi-threading code
How: by introducing handful abstractions

This article introduces 4 models:

1. Parallel workers (use mutex)
2. Assembly line (channels or actors)
3. Functional parallelism (stateless)

Another introduces 4

1. Synchronization primitives for sharing memory (e.g., sync.Mutex)
2. Synchronization via communicating (e.g., channels)
3. Immutable data
4. Data protected by confinement

here they just claim two:

1. shared state (mutex)
2. no shared state (channels)

This talk

1. cas (atomics and so on -- lock-free data structures)
2. agents (like channels)
3. STM (MVCC) persitent data structures and functional programming
4. locks

Disruptor pattern

https://www.infoq.com/presentations/LMAX/
Fowlers description https://martinfowler.com/articles/lmax.html

• important to model the problem

Basically, the idea is to avoid locks, use only sometimes CAS but mostly memory barrier. They achieve this by using their ring buffer

ABA problem in CAS https://youtu.be/_qaKkHuHYE0?t=1623
In this talk they used lock-free ring buffer but lost to mutex :'-)

Alternative way of proceeding mgeier/rtrb#39

but as of the moment crossbeam-queue is as efficient as his SPSC