Row-Wise vs Column-Wise Array Reads, L1/L2 Caches, and the TLB

In a screen for a performance-focused developer role, the interviewer asked a sequence of short questions about how programs use memory. Answer each part as you would out loud, with enough depth to show that you understand the hardware behavior, not just the definitions. ### Clarifying Questions - By "horizontal read" versus "vertical read", does the interviewer mean traversing an in-memory two-dimensional array row by row versus column by column, or reading row-oriented versus column-oriented data layouts (a table stored record by record versus field by field)? - Which memory layout should be assumed: row-major (C, C++, and NumPy by default) or column-major (Fortran, MATLAB)? - Is a particular CPU family assumed, since cache sizes and latencies differ between designs? ### Part 1 — Horizontal read versus vertical read Consider a large two-dimensional array of 8-byte numbers stored in row-major order. Compare reading it horizontally (outer loop over rows, inner loop over columns) with reading it vertically (outer loop over columns, inner loop over rows). Which is faster, and why? When does the gap become large, and how would you fix code that needs to process the data column by column? ```hint Follow the addresses Write down the memory address touched by each successive read in both loop orders, and compare the distance between consecutive reads with the size of a cache line. ``` #### What This Part Should Cover - The address pattern of each traversal and how it interacts with cache lines and hardware prefetching - When the difference becomes significant: array size relative to the caches, and large strides - Concrete remedies such as loop interchange, blocking, transposing, or changing the layout ### Part 2 — L1/L2 cache versus main memory Explain what the L1 and L2 caches are and how they differ from main memory: where they sit, their approximate size and access latency, what is private to a core and what is shared, and what happens on a cache miss. ```hint Think in lines, not bytes Describe the unit of data that moves between levels of the hierarchy, and what that implies about reading one value versus reading its neighbors. ``` #### What This Part Should Cover - The memory hierarchy, with orders of magnitude for size and latency - Cache lines, locality, and the cost of a miss - Private versus shared levels, and what that means for multithreaded code ### Part 3 — The TLB What is the TLB, why does it exist, and what happens when a lookup misses? How can it affect the performance of a program such as the vertical traversal in Part 1? ```hint Addresses are virtual Start from the fact that programs use virtual addresses, and ask what has to happen before a load can be served from memory that is addressed physically. ``` #### What This Part Should Cover - Address translation through page tables, and the TLB as a cache of translations - The cost of a TLB miss and the idea of TLB reach - Remedies such as huge pages and access patterns that touch fewer pages ### What a Strong Answer Covers - One coherent model that connects the access pattern, cache lines, and address translation - Reasoning with orders of magnitude rather than definitions alone - Practical ways to measure these effects (for example, hardware performance counters) and to fix them ### Follow-up Questions - Two threads update different counters that sit next to each other in memory, and the program gets slower as threads are added. What is happening, and how do you fix it? - Why do most CPUs split L1 into separate instruction and data caches? - How would you use hardware performance counters to confirm that a slowdown comes from cache misses or TLB misses? - On a two-socket machine, how does NUMA affect where you should allocate memory for a latency-sensitive thread?