# Parallel Performance Optimization ## Concurrency vs Parallelism - **Concurrency**: Doing two things but not necessarily at the same time - **Parallelism**: Doing two things at the same time Use OS threads for parallelism - the OS provides it for free. Just solve the problem with threads and you get parallelism automatically. --- ## When NOT to Use Threads - **Sequential dependencies**: If one task must complete before another starts, threads won't help - **System design**: If entire system needs to be single-threaded (e.g., Python GIL) - **Non-blocking IO already works**: Kernel provides IO that doesn't block threads - **Single thread is fast enough**: Waking a thread takes ~5μs. If your task takes less time, threads add overhead ``` Example: Sorting 100 integers = 3-5μs. Thread wake = 5μs. Spawn = 25μs. → Don't use threads for small tasks ``` --- ## When to Use Threads - Need more CPU time (compute-bound work) - Need more IO throughput (many pending IO operations) - Need more compute to offset overhead (crypto, compression) --- ## Profiling First Before adding threads: 1. Profile the entire application to find CPU hotspots 2. Identify what can actually be parallelized 3. Measure baseline performance 4. Add threads and measure again Don't add threads blindly - they can make things slower. --- ## Use Existing Primitives Don't write your own threading code: - **Zig**: Thread pool - **C++**: Intel TBB - **Rust**: Rayon - **Go**: sync.WaitGroup, channels - **Mac**: Grand Central Dispatch - **Linux**: futex-based primitives --- ## Three Sins of Threading ### 1. Spinning (Busy-Wait) Don't do this: ```c // BAD: Burns CPU while (!ready) { } ``` Don't do this either: ```c // BAD: Yields to scheduler unnecessarily while (!ready) { thread_yield(); } ``` Don't do this: ```c // BAD: Same problem - may yield to wrong thread while (!ready) { sleep(0); } ``` **Do this instead**: Use signaling/queues ```c // GOOD: Wake up only when ready queue_push(&work_queue, task); thread_wake(receiver); ``` - Thundering herd: Wake one task, not all. That task wakes the next. - Chained waking scales better than broadcasting. ### 2. Dependencies Avoid collecting onto one shared resource: ```c // BAD: All threads block on one lock mutex_lock(&shared); do_work(); mutex_unlock(&shared); ``` **Do this instead**: Race to register ```c // GOOD: All do work, only one registers result Result r = do_work_local(); if (atomic_compare_exchange(&winner, NULL, &r)) { // This thread won } ``` **Minimize critical sections**: Keep locking code as short as possible. **Avoid deferred handoffs**: Don't pass lock directly to another thread - limits throughput. **Prefer channels over mutexes**: Channels make critical sections tiny (just send/receive). **Use wait groups instead of multiple joins**: ```c // BAD: N join calls for (int i = 0; i < N; i++) { thread_join(threads[i]); } // GOOD: One wait wait_group_wait(&wg); ``` **Prefer RW locks over mutexes**: Readers don't block readers, only writers block. Use read-copy-update (RCU) for very high read loads. ### 3. Contention Contention is the biggest killer of thread performance. Atomics colliding slow everything down. **Exponential backoff**: ```c // BAD: All threads spin on collision while (!atomic_compare_exchange(&val, &old, old + 1)) { } // GOOD: Back off on collision int backoff = 1; while (!atomic_compare_exchange(&val, &old, old + 1)) { sleep_ns(backoff); backoff *= 2; } ``` **Check before locking**: ```c // GOOD: Check length first (no atomic needed) if (queue_length(q) > 0) { mutex_lock(&q->lock); // ... pop } ``` **Batch operations**: ```c // BAD: Lock for each push for (item) { lock(); push(); unlock(); } // GOOD: Batch then lock once prepare_batch(items); lock(); push_batch(); unlock(); ``` **Shard data**: Split into separate queues/data structures to avoid shared contention. **Separate cache lines**: If data doesn't contend logically, still might contend physically. Pad to cache line size (64 bytes). ```c // Pad to avoid false sharing struct Foo { char padding[64]; atomic_int counter; }; ``` --- ## Quick Checklist - [ ] Profile first - know your hotspots - [ ] Optimize single-threaded before adding threads - [ ] Use thread pools/existing libraries - [ ] Don't spin - use signaling - [ ] Minimize critical sections - [ ] Avoid locks - use channels or sharding - [ ] Batch operations before synchronizing - [ ] Add backoff on atomic contention - [ ] Separate hot data to different cache lines - [ ] Measure after adding threads --- ## Summary **Saturate**: Make tasks fat enough to utilize cores, not so fat that you don't parallelize. **Cut communication**: Tasks should work independently, not constantly sync. **Consolidate**: Threading bugs are subtle. Use well-tested libraries.