#memory-layout
Alignment
Array Alignment Array alignment controls where elements begin in memory. Many processors access aligned values more efficiently because the value fits cleanly inside one memory word, cache line, or vector register. You use it when low-level performance, SIMD instructions, or binary layout compatibility matters. Problem Given an array $A$ whose element type requires alignment $a$, ensure that every element address satisfies: $$ address(A[i]) \bmod a = 0 $$ for every...
Cache Aware Binary Search
Cache Aware Binary Search Cache aware binary search modifies ordinary binary search to account for the memory hierarchy. The algorithm still uses ordering and comparisons, but the data layout or search strategy is chosen with explicit knowledge of cache line size, block size, or page size. The goal is to reduce cache misses. On modern hardware, a comparison is cheap, while an unpredictable memory load can be expensive. Problem Given...
Index Mapping
Array Index Mapping Array index mapping converts a logical index into the physical position where the value is stored. The logical order seen by the algorithm may differ from the storage order used in memory. You use it when arrays are sliced, rotated, circular, strided, blocked, or stored in multidimensional layouts. Problem Given a logical index $i$, compute the physical index $p$ used to access the backing array. For a...
Multidimensional Array
Multidimensional Array A multidimensional array stores values using two or more indices. Although it is written as a grid, matrix, or tensor, memory is still linear. The indexing formula maps each logical position to one physical offset. You use it when data has natural row, column, plane, or tensor structure. Problem Given a two-dimensional array $A$ with $r$ rows and $c$ columns, support reading and writing an element at position...
Memory Layout
Array Memory Layout Array memory layout describes how elements are arranged in physical memory. The layout determines how efficiently the CPU can access data due to cache behavior and alignment. You use this knowledge to write code that is fast in practice, not only in asymptotic terms. Problem Given an array $A$ of length $n$, understand how its storage layout affects: access time cache utilization traversal performance Structure A standard...