I coulda been a contender!

Contemplating ways to further explore the cache characteristics of my M2, a philosophical question came to mind: How many threads can dance on the head of a cacheline? Answering this question proves to be both decidable and illuminating.

For a modestly quick introduction, I suggest you read ryg’s wonderful Cache Coherency Primer since it’ll provide to basic foundation I’m working from. Otherwise, I feel this ended up being more elegant than I initially expected, and most readers should be able to follow along without knowing too many of the lower level details.

We’re going to intentionally create some contention, and then use timing around that contention to understand where the various breakpoints are. My machine has 8 logical cores (4 Performance cores and 4 Efficiency cores), which means we can arrange for 8 threads to simultaneously contend over any in-memory arrangement we so desire. The mismatch in relative power will add some slop to our measurements, but we aren’t doing heavy computation so hopefully it won’t be too skewed.

I set up 5 different arrays of uint32_ts, aligned to 256 bytes to ensure we don’t accidentally split a smaller line unintentionally, and of varying sizes so that I can spread out or crowd the threads as desired. I use a crude mach_absolute_time()-based time delta, so only relative differences matter here - machine to machine number comparisons will be meaningless. I then start 8 threads pointing to various locations within each array, and have them atomically increment their location until it reaches 20,000,000, and see how long it takes. When the addresses are within a cache line, there will be contention and serialization, while when they’re isolated, they can operate concurrently. Changes in timing will help reveal how the cache is managed.

The 5 tests use a tightly packed array, another where they’re spread across 2 64-byte cache lines, one where each thread gets its own 64-byte cache line, one where each thread gets its own 128-byte cache line, and finally one where each thread gets its own 256-byte cache line.

Here’s the code:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <stdint.h>
#include <strings.h>
#include <locale.h>
// compile with clang thread.c -Os -o thread
extern uint64_t mach_absolute_time(void);
void *threadFunc(void *arg) {
    _Atomic(uint32_t) *value = (_Atomic(uint32_t)*)arg;
    while (*value < 20000000)
        ++*value;
    pthread_exit(NULL);
}
// this will fill a single 64-byte cache line
__attribute__((aligned(256))) _Atomic(uint32_t) values[16] = {0};
// this will fill 2 64-byte cache lines
__attribute__((aligned(256))) _Atomic(uint32_t) spreadValues[32] = {0};
// this will fill 8 64-byte cache lines (enough for each core to have its own 64-byte line)
__attribute__((aligned(256))) _Atomic(uint32_t) maximumSpread[128] = {0};
// this will fill 8 128-byte cache lines (enough for each core to have its own 128-byte line)
__attribute__((aligned(256))) _Atomic(uint32_t) idealSpread[256] = {0};
// this will fill 8 256-byte cache lines (enough for each core to have its own 256-byte line)
__attribute__((aligned(256))) _Atomic(uint32_t) superSpread[512] = {0};
int main()
{
    pthread_t threads[8];
    uint64_t now, then;
    // warm them up
    bzero(values, sizeof(values));
    bzero(spreadValues, sizeof(spreadValues));
    bzero(maximumSpread, sizeof(maximumSpread));
    bzero(idealSpread, sizeof(idealSpread));
    bzero(superSpread, sizeof(superSpread));
    setlocale(LC_NUMERIC, "");  // get comma-separation in printf
    printf("testing tightly-packed incrementing\n");
    then = mach_absolute_time();
    for (int i = 0; i < 8; ++i)
        pthread_create(&threads[i], NULL, threadFunc, &values[i]);
    for (int i = 0; i < 8; ++i)
        pthread_join(threads[i], NULL);
    now = mach_absolute_time();
    printf("elapsed: %'lld units\n", now - then);
    printf("testing splitting across 2 64-byte cache line incrementing\n");
    then = mach_absolute_time();
    for (int i = 0; i < 8; ++i)
        pthread_create(&threads[i], NULL, threadFunc, &spreadValues[i * 4]);
    for (int i = 0; i < 8; ++i)
        pthread_join(threads[i], NULL);
    now = mach_absolute_time();
    printf("elapsed: %'lld units\n", now - then);
    printf("testing individual 64-byte-cache line spaced incrementing\n");
    then = mach_absolute_time();
    for (int i = 0; i < 8; ++i)
        pthread_create(&threads[i], NULL, threadFunc, &maximumSpread[i * 16]);
    for (int i = 0; i < 8; ++i)
        pthread_join(threads[i], NULL);
    now = mach_absolute_time();
    printf("elapsed: %'lld units\n", now - then);
    printf("testing individual 128-byte-cache line spaced incrementing\n");
    then = mach_absolute_time();
    for (int i = 0; i < 8; ++i)
        pthread_create(&threads[i], NULL, threadFunc, &idealSpread[i * 32]);
    for (int i = 0; i < 8; ++i)
        pthread_join(threads[i], NULL);
    now = mach_absolute_time();
    printf("elapsed: %'lld units\n", now - then);
    printf("testing individual 256-byte-cache line spaced incrementing\n");
    then = mach_absolute_time();
    for (int i = 0; i < 8; ++i)
        pthread_create(&threads[i], NULL, threadFunc, &superSpread[i * 64]);
    for (int i = 0; i < 8; ++i)
        pthread_join(threads[i], NULL);
    now = mach_absolute_time();
    printf("elapsed: %'lld units\n", now - then);
    return 0;
}

This gives us some interesting results that aren’t entirely congruent with the previous 2 articles exploring the cache subsystem.

% ./threads
testing tightly-packed incrementing
elapsed: 155,543,991 units
testing splitting across 2 64-byte cache line incrementing
elapsed: 67,404,277 units
testing individual 64-byte-cache line spaced incrementing
elapsed: 8,404,528 units
testing individual 128-byte-cache line spaced incrementing
elapsed: 4,743,030 units
testing individual 256-byte-cache line spaced incrementing
elapsed: 4,646,876 units

Unsurprisingly, the tightly packed variant takes the longest. Every single core is fighting over the same cache line, continually. (This is one reason why the whole _Alignas/__attribute__((aligned(...))) thing was cooked up).

Spreading the workers across 2 64-byte cache lines improves performance - there are apparently now 2 logical cache lines to fight over, so at least 2 cores can make progress simultaneously. The improvement in performance is more than a factor of 2 though; This leads me to conclude that there’s at least some degree of finer grained cache control than the marketed 128 bytes, which gets my hopes up at blowing up the whole 128-byte cache line nonsense.

Spreading the workers across 8 64-byte cache lines improves performance dramatically, roughly by a factor of 8. This suggests that each thread is able to work independently. We’re now a whopping 18x faster than the original serialized version - this seems surprising since there are only 8 cores. Even assuming 2 atomic operations per iteration (a read and then a write), I’d expect it to cap out around 16x faster at best. This continues to validate my disdain for 128-byte cache line marketing.

Here’s where it gets really weird: Spreading the work across 8 128-byte cache lines roughly doubles performance again. Now we’re almost 33x faster than the original. I’m honestly not sure how to interpret this - there’s clearly something special about the larger 128-byte cache lines over the hypothetical 64-byte ones. Perhaps elsewhere lower in the cache subsystem it does operate on 128-byte lines, and it’s just the PE that has logical 64-byte lines laid atop larger L1 primitives? The entire data set should comfortably fit in L1 with room to spare, but with some additional working set tweaks we could possibly explore the L1/L2 boundary. Using fewer threads, paired with QoS settings to try and utilize just Performance cores, might show details when lines cross the P/E boundary? I have yet to cook up a satisfactory hypothesis that explains how this might work, alas. I must concede that cache lines are indeed larger than 64 bytes though, at least somewhere between memory and the processor.

To conclude our exploration, there’s no improvement moving the work to 256-byte lines - giving us an end point in potential cache line size exploration.

So, there you have it. There apparently are 128 byte cache lines, though the system appears to have some concessions to work with 64-byte lines, at a performance disadvantage. There’s still more to explore here (perhaps exploring GPU or NPU or AMX bits, though getting low-level access to those is rather tricky?), but at least I’ve finally uncovered some validity to the 128-byte cache line claims.