[Design] Cache friendly design, CPU/Memory level

Reference:
What do you mean by "Cache Friendly"? - Björn Fahller
What Every Programmer Should Know About Memory

Simplistic model of cache behaviour

Includes

• The cache is small
• and consists of fixed size lines
• and is very very fast when hit
• and missing is very slow

Excludes

• Multiple levels of caches
• Associativity
• Threading

All models are wrong, but some are useful

$ valgrind --tool=callgrind --cache-sim=yes --dump-instr=yes --branch-sim=yes
$ perf stat -e cycles,instructions,L1-dcache-loads,L1-dcache-Load-misses --call-graph=dwarf
$ perf record -e cycles,instructions,L1-dcache-loads,L1-dcache-Load-misses --call-graph=dwarf
$ pert report
$ hotspot perf.data

macos:

$ samply

Rule of thumb

follow/chasing pointer -> cache miss.

So,

Get rid of pointers.

Use std::vector (contiguous memory) vs. prev/next pointers.

std::vector be aware of memmove/memcpy.

memmove cause cache miss; if possible, memcpy.

Thus try to move less data.

binary tree/search still chasing pointer, 

can we get Log(n) lookup/insert without chasing pointers?

Heap. Use contiguous memory(e.g. std::vector) to implement.

But the heap is not searchable. Need extra contiguous memory to store the elements in order;

and the element holds the index to the contigous memory. Thus when the smallest heap

is processed, use the index to the contiguous memory and process that chunk.

Trade off: extra memory usage for speed and less cache miss.

Can we make it better?

B-Heap(binary heap implemented to keep subtrees in a single page); smaller heap fit into cache-line.

(not really better, depends on use case. i.e. if within a loop, the cache is hot, good.

otherwise, not worth the extra instructions due to cache is flushed anyways.)

Linear search is good iff the data set is small. (cpu prefetch within the cache size)

If data set is large, big O still dominates.

Rules of thumb

• Folling a pointer is a cache miss, unless have information to the contrary.
• Smaller working data set is better.
• Use as much of a cache entry as we can.
• Sequential memory accesses can be very fast due to prefetching.
• Fewer eviceted cache lines means more data in hot cache for the rest of the program.
• Mispredicted branches can evict cache entries (spectre/meltdown)
• Linear access in contigous memory rules for small data sets.
• Measure measure measure. (intuition can be wrong.)

Reference:

https://community.intel.com/t5/Intel-Moderncode-for-Parallel/Multidimensional-Transpose-Prefetching/m-p/1050948#M6795

Important things to know:

• The hardware prefetchers only work for streams within 4KiB pages.
  (There is a page-crossing L1 prefetcher in Ivy bridge, but it does not seem to make a lot of difference in my tests.)
• The L2 hardware prefetchers can only track a limited number of pages (16 to 32, depending on the processor model).
• Hardware prefetchers tend to be much more aggressive at fetching read streams than at fetching write streams.
• Transpose operations have to deal with non-contiguous accesses over some large area -- it helps if that area is small enough to be mapped by the TLBs.
  For Ivy Bridge, this is 4KiB * 512 entries = 2 MiB when using the default page size.
• Strided accesses in transpositions can very easily cause pathological cache conflicts.
• If the stride is a multiple of 4KiB, the L1 Data Cache will only hold 8 entries before beginning to overflow.
• Memory bandwidth performance in Intel processors is strongly degraded if a store maps to the same congruence class in the L1 cache as a preceding load.
  This will happen whenever a store maps to the same location in its 4KiB page as a recently preceding load.

From these principles, it is pretty easy to come up with tuning guidelines that work well for transpositions.

1. Pad arrays to avoid power-of-two strides (or offsets) whenever possible.
   Unrolling loops by 8 is usually a very good strategy.
2. This minimizes cache conflicts, so you (typically) get to read all the elements in a cache line before it gets evicted.
3. The number is small enough that the compiler does not typically get terribly confused about register scheduling.
4. When working in higher dimensions, make sure that the sub-blocks resulting from the unrolling don't cover more space than the TLB can cover.
5. This may mean unrolling by less than 8 for some or all of the loops.
6. Analysis from first principles is challenging for 2D transpositions, and is probably not practical for higher than 3D.
7. Favor contiguous reads over contiguous stores, but remember that there is minimal benefit to contiguous reads longer than 4 KiB.
8. If using streaming stores, remember to construct the code to store 64 contiguous bytes all at once, then store to the next block.
   This will maximize the number of full write-combining buffers that get used and will minimize the read/modify/write cycles at the DRAM (which are required if a partially full write-combining buffer gets flushed).

Unrolling and blocking are required to get good performance -- especially with arrays that have large power-of-two dimensions.

Hardware CPU Prefetching, Cache Friendliness, and Big-O Complexity

1. How CPU Prefetching Works on std::vector

Hardware CPU prefetchers actually work better on large std::vectors than small ones, and function seamlessly regardless of how large the vector grows (up to the physical limits of RAM).

In fact, CPU hardware prefetchers rely on streaming through large blocks of memory to function effectively.

Mechanics of Hardware Prefetching

std::vector stores its elements in a single, contiguous block of dynamically allocated memory. When iterating through a vector linearly, memory accesses occur at sequential byte addresses ($A, A+64, A+128, \dots$).

1. Pattern Detection: Modern CPU cores feature dedicated Stream Prefetchers and Spatial Prefetchers (L1/L2 data prefetchers). When the CPU detects sequential cache misses (typically 2 to 4 consecutive cache line accesses in the same direction), it identifies a linear stream.
2. Ahead-of-Time Fetching: Once a stream is detected, the prefetcher speculatively issues memory reads for upcoming cache lines ($N+2, N+3, \dots$) into L2 or L1 cache before execution requests them.
3. Pipelining Latency: As long as scanning continues sequentially, memory fetch latency is completely hidden behind instruction execution.

Impact of Dataset Size

• Small Vectors (< 1 KB / ~16 Cache Lines): The vector fits entirely within the L1 or L2 CPU cache after the first access anyway. Furthermore, by the time the hardware prefetcher detects the sequential pattern (after 2–3 misses), the iteration may already be near the end of the vector.
• Large / "Unlimited" Vectors (Gigabytes): The vector exceeds CPU cache capacity, meaning every element must be fetched from main RAM. Because the access pattern is perfectly predictable and long-running, the hardware prefetcher stays active at full throughput, streaming cache lines continuously from RAM with minimal cache-miss stalls.

Caveats: When Prefetching Breaks Down

While the size of std::vector does not limit the hardware prefetcher, the access pattern and data layout do:

• Non-Sequential Access: Accessing elements randomly (vec[rand()]) or via pointer chasing (e.g., storing raw pointers inside std::vector<T*>) prevents the prefetcher from predicting the next address.
• Page Boundaries (TLB Misses): Every 4 KB (or 2 MB) OS memory page boundary forces the prefetcher to pause until the CPU translates the next virtual page address via the Translation Lookaside Buffer (TLB).
• Page Faults / Virtual Memory: If a massive vector spills out of RAM into swap disk space, page faults will stall the CPU regardless of prefetching.
• Cache Pollution & Bandwidth Saturation: Iterating over a multi-gigabyte vector with minimal compute per element turns the execution into a memory-bandwidth-bound bottleneck.

---

2. Linear Search vs. Binary Search: Hardware Cache vs. Big-O Complexity

The assertion that "Linear search is good iff the data set is small (cpu prefetch within the cache size). If data set is large, big O still dominates" highlights a fundamental crossover point in systems programming: hardware cache efficiency vs. asymptotic algorithmic complexity ($Big-O$).

Why Linear Search Wins for Small Data Sets ($N$ is Small)

Actual execution time is modeled by:

$$T(N) = C \cdot f(N)$$

where $C$ is the constant factor determined by memory layout and hardware overhead, and $f(N)$ is the algorithmic growth function.

For small data sets (e.g., $N < 64$ elements):

$$C{\text{linear}} \cdot N < C{\text{binary}} \cdot \log_2 N$$

Structural Reasons for a Smaller $C_{\text{linear}}$:

1. Hardware Prefetching & Spatial Locality: Linear search scans contiguous memory (std::vector/array). As soon as element 0 is accessed, the CPU cache line (64 bytes) automatically pulls in adjacent elements. The CPU stream prefetcher speculatively fetches subsequent cache lines directly into L1/L2 cache before execution reaches them.
2. Zero Pointer Chasing: Operating on contiguous memory incurs L1 cache latency ($\sim 1\text{ ns}$) rather than random memory node jumps ($\sim 50\text{--}100\text{ ns}$ DRAM latency).
3. Branch Predictability: A simple sequential loop is trivial for the CPU's branch predictor to handle, minimizing pipeline stalls and flushes.

At small $N$, the data set fits entirely within L1/L2 cache, making memory access essentially instantaneous. The structural overhead of binary search (midpoint calculation, branches, non-sequential jumps) outweighs the cost of scanning a few adjacent cache lines sequentially.

---

Why Big-O Dominates as Data Grows ($N$ is Large)

As $N$ grows large (e.g., $N = 1,000,000$), hardware prefetching cannot overcome mathematical growth rate differences.

Metric	Linear Search $O(N)$	Binary Search $O(\log_2 N)$
Operations for $N = 1,000,000$	$\sim 500,000$ comparisons (avg)	$\sim 20$ comparisons
Memory Access Pattern	Sequential / Prefetched	Non-sequential / Cache line jumps
Primary Bottleneck	Memory Bandwidth & Total Operations	Cache Latency

Why Hardware Prefetching Fails to Save Linear Search at Scale:

1. Arithmetic Overwhelms Prefetching: Even if hardware prefetching streams data from main RAM at maximum bus bandwidth ($\sim 50\text{--}100\text{ GB/s}$), scanning $10^6$ elements still requires visiting half a million items on average.
2. Memory Bandwidth Saturation: Once the data set exceeds cache capacity (L3/RAM), linear search becomes entirely memory-bandwidth bound. Prefetching keeps the CPU pipeline fed, but the bus can only transport data so fast.
3. Logarithmic Superiority: In Binary Search, even if every single step of the 20 comparisons incurs a full DRAM cache miss ($\sim 70\text{ ns}$ each):

$$20 \text{ misses} \times 70\text{ ns} = 1.4 \;\mu\text{s}$$

Scanning megabytes of data sequentially via Linear Search takes hundreds of microseconds, making Binary Search orders of magnitude faster despite poor prefetch alignment.

---

Summary: The Crossover Point

Time (ns)
   ^
   |       /  Linear Search O(N) [Small C, bad growth]
   |      /
   |     /    <--- Crossover Point (N ≈ 32 - 128 elements)
   |    /___________ Binary Search O(log N) [Large C, excellent growth]
   |   /
   +-------------------------------------> N (Data Size)

• Small $N$ ($N \lesssim 64$): Constant factor $C$ dominates. The cache-friendliness, vectorization potential, and prefetching of linear search make $O(N)$ faster than $O(\log N)$ or $O(1)$.
• Large $N$ ($N \gg 1000$): Algorithmic growth $f(N)$ dominates. The exponential reduction in operations from $O(\log N)$ or $O(1)$ easily beats reading gigabytes of prefetched memory linearly.