Memory locality and performance

While memory is often thought of as a single, uniform pool of storage, its physical organization and the way the CPU accesses it have a profound impact on application performance. Understanding memory locality is key to writing high-performance code that makes efficient use of the CPU's cache hierarchy.

The CPU cache hierarchy

A modern mobile CPU is much faster than the system's main RAM (DRAM). To bridge this performance gap, CPUs use several levels of small, extremely fast memory called caches.

• L1 Cache (Level 1): The smallest and fastest (~1ns). On a 3GHz CPU, this is about 3 clock cycles.
• L2 Cache (Level 2): Larger and slightly slower (~3-5ns, or ~10-15 cycles).
• L3 Cache (Level 3): The largest cache (~10-20ns, or ~30-60 cycles).
• Main Memory (DRAM): The largest and slowest (~100ns+, or ~300+ cycles).

Contextualizing latency: the cost of a stall

To understand the impact of these numbers, consider a modern superscalar CPU that can retire 4 to 8 instructions per clock cycle.

If the CPU misses all caches and must wait 100ns (300 cycles) for a DRAM read:

• Cycles Lost: ~300 cycles.
• Instructions "Wasted": Between 1,200 and 2,400 instructions that could have been executed if the data were already in a local register or the L1 cache.

When your code has poor memory locality, the CPU isn't necessarily busy with complex math; it is frequently "stalled," sitting idle for thousands of instruction-equivalents while waiting for the memory subsystem.

Instructions per cycle (IPC)

A key metric for measuring this efficiency is Instructions Per Cycle (IPC). IPC represents how many instructions the CPU successfully "retires" (completes) on average during each clock cycle.

• High IPC (e.g., 3.0 - 5.0): The CPU is running at high efficiency, likely finding most of its data in L1/L2 caches or registers.
• Low IPC (e.g., < 0.5): The CPU is severely bottlenecked. Even if the CPU is at 100% "usage" in system monitors, it is actually spent mostly waiting for memory—a state known as a memory stall.

Memory locality is the primary factor that determines whether a data-intensive loop runs at high IPC or collapses into a series of stalls.

Cache lines

CPUs do not load single bytes from memory. Instead, they load fixed-size blocks called cache lines, which are typically 64 bytes. When you access a single variable, the CPU fetches the entire 64-byte chunk containing it into the cache.

TLB (translation lookaside buffer)

Android uses virtual memory. Every memory access requires translating a virtual address to a physical address. The TLB is a specialized cache that stores recent translations. A TLB miss requires the kernel to walk page tables in main memory, which is a relatively expensive operation compared to a TLB hit.

Hardware profile: Pixel 10 Pro Fold

For the following exercises, we used a Pixel 10 Pro Fold hardware device. This device features a Google Tensor G5 SoC.

Interrogating the hardware

To understand the memory subsystem, we first examine the CPU configuration and cache parameters.

# Check CPU architecture and core parts
adb shell cat /proc/cpuinfo | grep 'CPU part' | sort -u
# Output:
# CPU part  : 0xd8b
# CPU part  : 0xd8c
# CPU part  : 0xd90

# Check cache line size
adb shell getconf -a | grep CACHE_LINESIZE
# Output:
# LEVEL1_ICACHE_LINESIZE             64
# LEVEL1_DCACHE_LINESIZE             64

Decoding CPU parts

The CPU part values in /proc/cpuinfo are hexadecimal identifiers for ARM CPU cores. For the Laguna SoC found in the Pixel 10 Pro Fold, these map to:

• 0xd8b: ARM Cortex-A520 (Efficiency cores)
• 0xd90: ARM Cortex-A720 (Performance cores)
• 0xd8c: ARM Cortex-X4 (Prime core)

This 4+3+1 configuration is common in modern mobile SoCs, where different clusters may have different cache sizes and latencies.

Types of locality

Efficient software design relies on two main types of locality:

1. Spatial Locality: If a memory location is accessed, nearby memory locations are likely to be accessed soon. Sequential array traversal is the classic example. Because the CPU loads an entire cache line, accessing the next element in an array is almost "free" if it's already in the cache line.
2. Temporal Locality: If a memory location is accessed, the same location is likely to be accessed again soon. Good algorithms reuse data while it is still "hot" in the cache.

Hands-on exercise: measuring locality with simpleperf

In this exercise, we will use simpleperf to monitor hardware performance counters while running two different traversals of a 256MB matrix.

1. Row-major Traversal: Accesses the matrix elements in the order they are stored in memory. This is cache-friendly and exploits spatial locality.
2. Column-major Traversal: Jumps across memory to access elements by column. This frequently misses the cache and the TLB, forcing the CPU to stall.

1. Run with Simpleperf

Push the binary, ensure it is executable, and use simpleperf stat to measure cache and TLB events. We use the :u suffix to measure events in userspace. These commands require adb root to access hardware PMU counters on most devices.

adb root
adb shell "chmod +x /data/local/tmp/LocalityLab"

Profile Row-major:

adb shell "simpleperf stat -e cpu-cycles:u,instructions:u,cache-misses:u,L1-dcache-load-misses:u,dTLB-load-misses:u /data/local/tmp/LocalityLab row"

Profile Column-major:

adb shell "simpleperf stat -e cpu-cycles:u,instructions:u,cache-misses:u,L1-dcache-load-misses:u,dTLB-load-misses:u /data/local/tmp/LocalityLab col"

2. Sample measurements (Pixel 10 Pro Fold)

The following results were measured on a Pixel 10 Pro Fold hardware device:

3. Analysis of results

• The IPC Crash: In the row-major test, the CPU achieves an IPC of 4.40, indicating it is efficiently executing multiple instructions per cycle. In the column-major test, IPC drops to 0.16. This means the CPU is stalled 96% of the time, waiting for data to arrive from DRAM.
• The TLB Bottleneck: The most dramatic difference is in dTLB-load-misses. Sequential access (row-major) stays within the same memory pages, resulting in very few TLB misses. Jumping across columns (column-major) causes the CPU to constantly reference new pages, overwhelming the TLB and forcing expensive page table walks.
• Cache Efficiency: The column-major traversal generates 16x more L1 cache misses, forcing the CPU to fetch data from much slower L3 or DRAM constantly.

Observation: Even though both traversals performed the same logical operation on the same data, the column-major traversal was over 80 times slower. This massive difference is entirely due to how the access pattern interacts with the physical reality of the CPU's memory subsystem.

Pointer chasing in Java and Kotlin data structures

While the 2D matrix benchmark demonstrates spatial locality in contiguous native arrays, most Android application and framework code is written in Java and Kotlin. In managed languages, object variables and collection elements don't store objects inline; they store references (pointers) to heap-allocated objects scattered across the ART heap.

The cost of nested reference graphs

Consider a common pattern in Android apps and system services: traversing nested collections such as an ArrayList of state objects, each containing an ArrayMap or ArraySet of listeners or connections, each pointing to another state record.

Even though ArrayList, ArrayMap, and ArraySet store their internal Object[] arrays contiguously, each element in that Object[] is still a heap reference. Dereferencing a chain such as process.services.valueAt(i).connections.valueAt(j).client requires five sequential dependent memory loads:

1. Load the Object[] backing services.
2. Load the ServiceRecord object header and fields.
3. Load the Object[] backing connections.
4. Load the ConnectionRecord object.
5. Load the target ProcessRecord field.

Because each load's memory address depends on the value returned by the previous load, the CPU's out-of-order execution engine and hardware prefetcher can't overlap them. If those objects were allocated at different times or moved to different regions during garbage collection, each hop risks an L1 or L2 cache miss.

Boxed primitives (ArrayList<Integer>, HashMap<Long, Boolean>) and generic lambdas compound this overhead: every element lookup requires an extra pointer dereference to unbox the value, and generic Consumer<T> callbacks insert runtime type-check (CheckCast) stubs that add instruction cache (L1-icache) pressure.

Diagnosing pointer chasing with simpleperf

In real-world Java and Kotlin workloads (such as system_server's OomAdjuster traversing process, service, and provider reference graphs), pointer chasing rarely drops IPC all the way to 0.16 like a synthetic 256 MB column-major scan, because part of the working set fits in L2 or L3 cache. Instead, look for this characteristic signature in simpleperf:

• Depressed IPC (around 0.6 to 0.9): Well below the CPU's superscalar retire width.
• High backend memory stalls (raw-stall-backend-mem): Often 35% to 45% of all CPU cycles are spent waiting on data cache fills.
• Elevated L1-dcache-load-misses and L1-icache-load-misses: High data cache miss rates paired with instruction cache misses when hot traversal loops jump across virtual methods and generic lambda stubs.

You can measure these counters on a running process using simpleperf stat:

adb shell simpleperf stat \
  -e cpu-cycles:u,instructions:u,raw-stall-backend-mem:u,L1-dcache-load-misses:u,L1-icache-load-misses:u \
  -p $(pidof system_server) --duration 10

Improving locality in managed code

• Replace boxed collections with primitive arrays or AndroidX collections: Use IntArray, LongArray, SparseIntArray, or androidx.collection primitives (IntList, LongLongMap, ScatterMap) to eliminate wrapper objects and keep values contiguous inside a single array allocation.
• Flatten hot traversal paths: If a hot loop repeatedly walks three or four hops across an object graph to read a single boolean or integer flag, hoist or cache that state into a flat array or bitmask indexed by a dense ID.
• Avoid capturing or generic lambdas in tight inner loops: Use standard indexed for loops over RandomAccess lists instead of forEach or iterator chains to avoid iterator allocations, megamorphic dispatch, and runtime type-check overhead.

← Threads | ↑ Up | Service bindings →