Data Access Patterns That Makes Your CPU Angry

Data Access Patterns That Makes Your CPU Really Angry | weineng30% worse than a randomized access pattern.">30% worse than a randomized access pattern.">30% worse than a randomized access pattern.">Given an array of data, what is the slowest way to sum up the integers? Is it adding the numbers from left to right, adding them randomly, or doing something else? In this post, we are going to build a data access pattern from the ground up that sums numbers as slowly as possible by exploiting memory pitfalls. uint32_t* data = ...;

// sequential data[0] + data[1] + data[2] + ... // random data[67] + data[69420] + data[42] + ... // the slowest data[A] + data[B] + data[C] + ... Spoiler: You can do >30% worse than a randomized access pattern.

Some rules: Only consider the time taken to run the accumulation function. The time taken to create positions isn’t included. The accumulation function is fixed as follows, and data is filled randomly and we are only allowed to change the contents of positions: constexpr int ELEMENT_COUNT = (1 16) * (PAGE_SIZE / sizeof(uint32_t)); // 2^26

/* data contains integers that we want to sum up * positions is the access pattern that we use to sum up the integers * Overflow is expected, but we don’t really care about the actual sum, do we? */ uint32_t accumulator(uint32_t const* data, uint32_t const* positions) { uint32_t total = 0; for (uint32_t i = 0; i ELEMENT_COUNT; ++i) { uint32_t pos = positions[i]; total += data[pos]; return total; Measurements of accumulator durations are based on using rdtsc cycle count. Some additional notes: There are 2^26 integers: using 65536 pages, and each page contains 1024 integers. These numbers are chosen simply so it doesn’t take too long on my machine to run. Huge pages are disabled. All measurements are based on my machine: Reveal machine specs Hide code❯ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 42 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 8 On-line CPU(s) list: 0-7 Vendor ID: GenuineIntel Model name: Intel® Core™ Ultra 7 268V CPU family: 6 Model: 189 Thread(s) per core: 1 Core(s) per socket: 8 Socket(s): 1 Stepping: 1 CPU(s) scaling MHz: 50% CPU max MHz: 2200.0000 CPU min MHz: 400.0000 BogoMIPS: 6604.80 Flags: … Virtualization features: Virtualization: VT-x Caches (sum of all): L1d: 320 KiB (8 instances) L1i: 512 KiB (8 instances) L2: 14 MiB (5 instances) L3: 12 MiB (1 instance) NUMA: Vulnerabilities:

The full code can be found here, run with g++ -std=c++2a -O3 slowest.cc && taskset -c 3 sudo ./a.out. I highly recommend opening up slowest.cc and running the code. Our job is to find the permutation of positions that yields the slowest possible timing. Let’s begin with the simplest access pattern: void linear(uint32_t const* data, uint32_t* positions) { for (uint32_t i = 0; i ELEMENT_COUNT; ++i) { positions[i] = i; This is likely the fastest permutation, taking 133M (132752394) cycles. This is expected, since CPUs are heavily optimised for sequential accesses. On the other hand, we could randomise the permutation of positions. void fisher_yates_shuffle(uint32_t const* data, uint32_t* positions) { linear(data, positions); uint32_t remaining = ELEMENT_COUNT; for (uint32_t i = 0; i ELEMENT_COUNT; ++i) { uint32_t random = rand() % remaining; uint32_t tmp = positions[i]; positions[i] = positions[i + random]; positions[i + random] = tmp; --remaining; Now, the CPU cannot predict which data it will access next, so randomised access takes 1.57B (1572108618) cycles, which is over 10x worse than with linear access. Could we do worse? Of course. Let’s build up the worst permutation, starting with a simple regression. Start by setting positions such that every consecutive element accessed is always separated by a cache line, which is the unit of data that is stored in a cache: void separated_by_a_cacheline(uint32_t const* data, uint32_t* positions) { constexpr int element_count_per_cacheline = CACHELINE_SIZE / sizeof(uint32_t); constexpr int cacheline_count = ELEMENT_COUNT / element_count_per_cacheline; static_assert(ELEMENT_COUNT % element_count_per_cacheline == 0); int current = 0; for (int element_index = 0; element_index element_count_per_cacheline; ++element_index) { for (int cacheline_index = 0; cacheline_index cacheline_count; ++cacheline_index) { positions[current] = cacheline_index * element_count_per_cacheline + element_index; ++current; This pattern is terrible because each access uses one 4-byte integer from a 64-byte cache line before moving on. By the time we come back to the same cache line, the useful reuse cache would have been evicted. This culminates in a horrible performance with a cycle count of 719M (718804156), already taking 4x longer than a linear scan. When accessing elements separated by a cache line, the hardware prefetchers can still recognise a simple streaming pattern in data and start fetching future cache lines before the load requests them. However, many Intel...

Data Access Patterns That Makes Your CPU Angry

Related Articles

US Government directive to suspend access to Fable 5 and Mythos 5

Is AI ruining our skills? Early results are in – and they're not good

The Anatomy of an AI-Native Org

Apertus – Open Foundation Model for Sovereign AI

How to Earn a Billion Dollars