Memory Access Optimization FAQ & Answers

Pointer chasing (following pointers in linked structures) serializes memory access - each load depends on the previous result. Cost: full memory latency per node (100+ cycles) with no opportunity for parallelism or prefetching. Traversing a 1000-node linked list: ~100,000 cycles vs ~1,000 cycles for array scan. Hardware prefetchers cannot predict pointer targets. Mitigation: (1) Replace with arrays where possible. (2) Pool allocation keeps nodes physically close. (3) Prefetch next node while processing current: __builtin_prefetch(node->next). (4) Use B-trees instead of binary trees (multiple keys per node). (5) Linearize tree traversal order (van Emde Boas layout). Pointer-heavy code often runs at 0.1-0.3 IPC.

String processing optimization: (1) Use short string optimization (SSO) - strings under ~22 bytes stored inline, avoiding pointer chase. std::string in most implementations has SSO. (2) String interning - deduplicate identical strings, compare by pointer. (3) Rope data structure for long strings - avoid copying on concatenation. (4) Process strings in batches - load multiple strings into cache before processing. (5) Use SIMD for character scanning (strchr, strlen). (6) Avoid std::string copy - use string_view or const reference. (7) Pre-allocate with reserve() to avoid reallocations. Cache-friendly string table: store strings contiguously with length prefixes.

Database memory optimization: (1) Column stores (SoA) for analytical queries - scan only needed columns. (2) Buffer pool management - keep hot pages in memory, use clock/LRU eviction. (3) Huge pages for buffer pool - reduce TLB misses for random access. (4) NUMA-aware allocation - place data on local memory. (5) Compression (dictionary encoding) - more data in cache. (6) Index optimization - B+ trees sized to cache lines, prefetch during traversal. (7) Batch query execution - amortize cache misses. (8) Memory-mapped I/O with MAP_POPULATE for predictable loading. (9) Write-ahead log with non-temporal stores. Modern databases (DuckDB, ClickHouse) are designed cache-first.

Recursive algorithms can have excellent or terrible cache performance. Good: cache-oblivious divide-and-conquer (subproblems eventually fit in cache). Bad: deep recursion with large stack frames, random access across recursion levels. Optimization: (1) Tail recursion elimination - convert to iteration. (2) Switch to iterative at small sizes (base case). (3) Process multiple elements per recursive call. (4) Use explicit stack instead of call stack for better locality. (5) Ensure recursive subdivision creates cache-sized subproblems. Quicksort: good cache behavior due to sequential access. Tree traversal: poor cache behavior due to pointer chasing - consider linearized representation.

Cache-aware: algorithm explicitly tuned for known cache parameters (size, line size, associativity). Must be re-tuned for different hardware. Example: tiled matrix multiply with tile size chosen for L2 cache. Achieves best performance on target system but not portable. Cache-oblivious: algorithm achieves good cache performance without knowing cache parameters. Uses recursive divide-and-conquer to automatically adapt. Example: recursive matrix multiply divides until base case. Achieves theoretically optimal cache complexity on any cache hierarchy. Practical comparison: cache-aware is 10-30% faster on tuned system; cache-oblivious is simpler, portable, and automatically optimal for multi-level hierarchies.

TLB optimization strategies: (1) Use huge pages (2MB/1GB) - each TLB entry covers more memory. (2) Improve spatial locality - access data sequentially. (3) Reduce working set - smaller footprint means fewer pages. (4) Align frequently-accessed data to page boundaries. (5) Use memory pools to keep related data on same pages. (6) Avoid sparse access patterns across large arrays. (7) Consider data structure flattening - reduce pointer indirection. (8) Profile with perf stat -e dTLB-load-misses. With 4KB pages, 1GB working set needs 262,144 TLB entries; with 2MB pages, only 512. For databases and HPC, huge pages are essential.

THP benefits: automatic huge page promotion, no code changes needed, reduced TLB misses for large allocations. Drawbacks: (1) Khugepaged compaction causes latency spikes (up to seconds). (2) Memory fragmentation prevents promotion. (3) Memory waste - 2MB minimum allocation even for small requests. (4) Swap complexity - must split pages. (5) Copy-on-fork overhead - entire 2MB page copied. Many latency-sensitive applications (Redis, MongoDB, PostgreSQL) recommend disabling THP. For batch processing and HPC, THP often helps. Check status: cat /sys/kernel/mm/transparent_hugepage/enabled. Alternatives: explicit HugeTLBfs for controlled allocation, or madvise mode for per-region control.

Memory benchmarking best practices: (1) Disable CPU frequency scaling: cpupower frequency-set -g performance. (2) Disable turbo boost for consistent results. (3) Pin processes to specific cores: taskset -c 0 ./benchmark. (4) Use NUMA-aware allocation: numactl --membind=0 --cpunodebind=0. (5) Run multiple iterations, report median. (6) Ensure data is not cached from previous runs (flush caches or use new data). (7) Measure cold and warm cache separately. (8) Use high-resolution timers (clock_gettime CLOCK_MONOTONIC). (9) Account for memory allocation time separately. Tools: STREAM benchmark for bandwidth, Intel MLC for latency matrix, lmbench for microbenchmarks.

Key differences: Cache sizes: AMD Zen 4 has 32KB L1D/32KB L1I per core, 1MB L2, up to 96MB L3 (with 3D V-Cache). Intel 13th/14th gen has 48KB L1D, 2MB L2, up to 36MB L3. Cache line: both use 64 bytes. L3 architecture: AMD uses shared victim cache (L2 evictions go to L3); Intel uses inclusive hierarchy (older) or non-inclusive (newer). Prefetchers: Intel typically more aggressive, AMD more power-conscious. NUMA: AMD chiplet design has more NUMA nodes per socket. 3D V-Cache: AMD stacks additional L3 for gaming/latency-sensitive workloads. Optimization usually transfers between vendors, but benchmark on target hardware.

Intel DDIO allows network and storage I/O to read/write directly to L3 cache instead of main memory, reducing latency. Network packets arrive directly in cache, ready for CPU processing. Benefits: reduced memory bandwidth consumption, lower latency for I/O-intensive workloads. Available on Xeon E5/E7 and later. Considerations: (1) DDIO uses ~10% of L3 by default. (2) Heavy I/O can pollute cache. (3) Tune with DDIO-related MSRs if needed. (4) Works best with DPDK, SPDK for kernel-bypass I/O. (5) On servers with small L3 or heavy I/O, consider limiting DDIO allocation. Profile with PCM (Processor Counter Monitor) to see DDIO effectiveness.

malloc/free in tight loops causes: (1) Allocator overhead - thread synchronization, metadata management. (2) Memory fragmentation - scattered allocations have poor locality. (3) Cache pollution - allocator data structures compete for cache. (4) TLB pressure - many small allocations span pages. Performance impact: 10-100x slower than stack allocation. Solutions: (1) Pre-allocate arrays/vectors instead of per-element allocation. (2) Use arena/pool allocators for same-lifetime objects. (3) Reuse allocated buffers across iterations. (4) Use alloca() for small, fixed-size temporary buffers (stack allocation). (5) Use thread-local allocators (jemalloc, tcmalloc) for better multithread performance.

Loop fusion combines multiple loops that iterate over the same data into a single loop, improving temporal locality. Before: for(i) a[i]=b[i]+1; for(i) c[i]=a[i]*2; - array a loaded twice. After: for(i) { a[i]=b[i]+1; c[i]=a[i]*2; } - array a used immediately while in cache. Benefits: reduces memory traffic, improves instruction-level parallelism, reduces loop overhead. Conditions for fusion: same iteration bounds, no dependencies preventing reordering. Compilers may auto-fuse with optimization flags, but manual fusion often needed. Related: loop fission (splitting) can help when working set exceeds cache - process in chunks instead.

GCC/Clang flags: -O3 enables auto-vectorization, loop unrolling, inlining. -ffast-math allows reordering for better locality. -march=native uses CPU-specific optimizations. -funroll-loops explicit unrolling. -fprefetch-loop-arrays auto software prefetch. -ftree-vectorize auto SIMD. Intel ICC: -O3 -xHost -qopt-prefetch. For profile-guided optimization: compile with -fprofile-generate, run workload, recompile with -fprofile-use. Link-time optimization (-flto) enables cross-file optimization. Verify with -fopt-info-vec or -Rpass=loop-vectorize. Warning: aggressive optimization can hurt if assumptions wrong - always benchmark. Most cache optimizations require manual intervention.

GPU shared memory is organized into banks (typically 32 banks, 4 bytes each on NVIDIA). Bank conflicts occur when multiple threads in a warp access the same bank, serializing access. Optimization: (1) Access pattern should distribute across banks - stride of 1 or 33 is conflict-free. (2) Add padding to 2D shared arrays to avoid bank conflicts: shared float tile[32][33]; (extra column shifts each row). (3) Use 8-byte accesses (double/long) which access 2 consecutive banks. (4) Broadcast is free - all threads reading same address is one access. Profile with Nsight Compute for bank conflict metrics. Shared memory with bank conflicts can be slower than global memory.