Array Padding
Insert unused space between array elements or groups to control alignment and reduce interference.
Tag
Cache
11 notes
Array Tiling
Process multidimensional arrays in small rectangular regions to improve locality.
Array Blocking
Process an array in fixed-size blocks to improve cache locality and batch behavior.
Array Stride Access
Access array elements at regular intervals and understand the effect on locality.
Array Memory Layout
Understand how arrays are stored in memory and how layout affects performance.
12. Specialized Search and Sorted-Order Procedures
Cache-efficient and hardware-tuned search: branchless binary search, Eytzinger and vEB layouts, learned indexes, SIMD search, and galloping intersection.
10. External Memory, Cache, and Database Sorting
Sorting beyond main memory: external merge sort, polyphase merge, cache-oblivious techniques, LSM compaction, and database sort phases.
Cache Oblivious Sorting
Sorting techniques that achieve good cache behavior without explicitly knowing cache size or block size.
Cache Aware Sorting
Sorting techniques that explicitly use knowledge of cache size and block size to minimize memory hierarchy cost.
5.23 Cache-Aware Hashing
Design hash table layouts that minimize cache misses and align memory access patterns with hardware behavior.
5.17 Cache Behavior
Understand how memory hierarchy effects cause hash table performance to deviate from asymptotic expectations.