When the Working Set No Longer Fits in Cache

Investigation · Part 16 of 20 · When the benchmark lies

1.4 nanoseconds, and 114 nanoseconds. It is the same loop, the same instruction, one step of i = a[i]. The only difference is the size of the array: 32 KiB the first time, 128 MiB the second time.

Every benchmark has a working set, the memory it touches again and again. Until now in this series it was small, and I did not think about it. In this part I measure what happens when it grows, step by step, from 4 KiB to 256 MiB, because a benchmark that runs on a small input measures one level of the memory, and the real program may live in another one.

A loop that can not be helped

The loop is a pointer chase:

for _ in 0..STEPS {
    i = a[i];
}

The array contains a random permutation that is one single cycle, made with Sattolo's algorithm. So the next position is random, and the loop visits every element before it comes back to the start. Each step needs the result of the previous load to know the address of the next one. The processor can not start the next load early, and the prefetcher can not guess the next address. This is a dependency chain of the purest kind, the same problem that a DFA with one lookup per byte has, but here every link of the chain is a memory access. So the time per step is the latency of the memory level that holds the array.

The program measures 4,000,000 steps three times for each size and keeps the median, for 33 sizes between 4 KiB and 256 MiB, each size 1.41 times the previous one. It also measures a sequential sum of the same array, to compare.

The caches of the two kinds of cores, from /sys:

cpu2: L1 Data cache 48K, shared by cpus 2-3
cpu2: L2 Unified cache 1280K, shared by cpus 2-3
cpu2: L3 Unified cache 18432K, shared by cpus 0-15
cpu10: L1 Data cache 32K, shared by cpus 10
cpu10: L2 Unified cache 2048K, shared by cpus 8-11
cpu10: L3 Unified cache 18432K, shared by cpus 0-15

The steps

Because the DRAM part of this measurement is sensitive to what other programs do (the ranges below show how much: for the same size, one run can be twice slower than another), run.sh makes three rounds, and in each round it runs the P-core (CPU 2), the E-core (CPU 10), and the P-core again with huge pages disabled. The table shows the median of the three runs and the range:

      size                     P-core                     E-core               P-core,nothp
...
    32 KiB     1.44 [   1.39-   2.93]     1.29 [   1.21-   1.45]     1.41 [   1.31-   3.07]
    45 KiB     1.43 [   1.42-   2.18]     3.02 [   2.83-   3.33]     2.33 [   1.30-   3.12]
    64 KiB     2.24 [   2.23-   4.53]     4.30 [   3.99-   4.45]     2.86 [   2.02-   4.75]
    91 KiB     2.96 [   2.85-   5.09]     4.93 [   4.62-   5.08]     2.91 [   2.70-   6.16]
...
   1.0 MiB     6.55 [   6.38-  12.08]     9.08 [   8.52-   9.20]     5.57 [   5.00-  12.06]
   1.4 MiB     8.91 [   8.65-  15.19]    10.00 [   9.03-  10.18]     7.67 [   7.10-  18.61]
   2.0 MiB    12.29 [  11.22-  20.00]    11.43 [  11.01-  12.27]    10.59 [   9.63-  25.09]
   2.8 MiB    14.02 [  13.50-  24.63]    13.30 [  13.29-  13.56]    13.88 [  11.83-  33.26]
   4.0 MiB    16.67 [  14.36-  31.44]    18.25 [  15.88-  18.53]    18.33 [  14.45-  66.98]
   5.7 MiB    35.12 [  21.04-  46.90]    19.46 [  16.19-  19.97]    39.80 [  22.95- 107.36]
   8.0 MiB    32.97 [  26.96-  35.57]    21.62 [  17.95-  24.35]    59.11 [  27.60- 151.31]
  11.3 MiB    49.95 [  46.51-  81.81]    31.43 [  30.96-  41.45]    95.72 [  58.65- 182.49]
  16.0 MiB    85.23 [  78.23-  85.76]    48.27 [  36.81-  61.91]   100.08 [  72.18- 179.37]
  22.6 MiB    94.98 [  89.59- 104.73]    86.38 [  84.42-  91.28]   123.51 [  89.92- 201.22]
  32.0 MiB   105.85 [ 105.45- 107.30]    86.44 [  80.98-  90.26]   119.29 [ 100.73- 208.10]
...
 128.0 MiB   113.96 [ 111.76- 117.77]   124.09 [ 123.05- 142.12]   117.13 [ 107.11- 217.84]
...
 256.0 MiB   118.62 [ 115.66- 119.67]   137.01 [ 135.17- 142.23]   115.59 [ 113.88- 232.74]

The first step is very clear, and it is different for the two cores. On the P-core, the chase costs about 1.4 ns up to 45 KiB and 2.24 ns at 64 KiB: the step is between 45 and 64 KiB, around its L1 data cache of 48 KiB. On the E-core, it is 1.29 ns at 32 KiB and 3.02 ns at 45 KiB: the step comes earlier, around its L1 of 32 KiB.

Then the L2 region. It is not flat: the time grows slowly with the size, on the P-core from 2.2 ns at 64 KiB to 6.6 ns at 1 MiB, before its L2 ends at 1.25 MiB. The E-core has a bigger L2, 2 MiB, and its L2 region goes further, to about 11 ns at 2 MiB.

After that, the L3 and then the memory. With 22.6 MiB and more, both cores are at 86 to 137 ns per step: the array is in DRAM. The transition starts before the 18 MiB of the L3. The L3 is shared by all 16 CPUs, and the other programs of this laptop use a part of it too, so my array can not have all of it.

The E-core was faster

This one I can not explain. Between 5.7 and 16 MiB, the E-core was faster than the P-core, in all three rounds: at 8 MiB, 21.6 ns against 33.0 ns. And the numbers of the P-core have a problem. Just before the run, the snapshot that every result file has since the first part shows CPU 2 itself 41 percent busy with a program that was not mine, and in this run the P-core was slower than the E-core even in the L1 cache (1.44 against 1.29 ns at 32 KiB). A busy sibling can not be the whole answer: from 5.7 MiB the array does not fit in the L1 or the L2 of any core. And the P-core and E-core runs of a round are about 20 seconds apart, always with the sizes in the same order, the one-direction scan that part 14 warned about.

When I ran this part a second time, on a quieter laptop, the P-core was faster again in the L1 cache and at 5.7 and 8 MiB (14.0 and 17.1 ns, against 17.1 and 20.1 on the E-core), but the E-core was still faster from 16 to 22.6 MiB (p16-working-set.txt). So I do not know why the E-core won there.

The same data, read in order

The sequential sum reads the same arrays, from the first element to the last:

      size       P-core       E-core P-core,nothp
...
    32 KiB        0.092        0.162        0.089
...
   1.0 MiB        0.125        0.207        0.099
...
   8.0 MiB        0.150        0.220        0.161
...
  16.0 MiB        0.288        0.538        0.394
...
  32.0 MiB        0.437        0.576        0.502
...
 128.0 MiB        0.481        0.580        0.462
...
 256.0 MiB        0.468        0.569        0.472

On the P-core: 0.09 ns per element when the array is in L1 or L2, about 0.15 in L3, 0.47 in memory. At 128 MiB, the chase needs 114 ns per step and the sequential read 0.48 ns per element: 237 times less, for the same bytes.

Two things explain it. One cache line of 64 bytes contains 8 elements, so the sequential read uses each line 8 times, and the chase only once. And the order is predictable: the hardware prefetcher sees that the lines are read one after the other and loads the next lines before the loop needs them, and the loads do not depend on each other. Even in memory, the sequential read waits for almost nothing; the chase waits for every single access.

So the same array is very fast or very slow depending only on the order of the accesses. A benchmark that reads its data in order says almost nothing about a program that follows pointers through the same data.

Huge pages: I could not show it

Huge pages could be another factor. Each access to a new page needs its address translation in the TLB, a small cache of translations, and with 4 KiB pages a big random working set needs far more translations than the TLB can hold. With 2 MiB pages, it needs 512 times fewer. That is why the third run of each round disables transparent huge pages for the process.

But I can not show a clear effect. The table above has the P-core without huge pages slower in some sizes, but its ranges are the widest of the three, up to 233 ns for the same size that took 114 ns in another round. And with huge pages allowed, the kernel gave very few:

AnonHugePages of the process at the largest size, kB, per run:
  P-core: 10240, 6144, 2048
  E-core: 10240, 6144, 0
  P-core,nothp: 0, 0, 0

At most 10 MiB of huge pages for a 256 MiB array. The memory of the laptop was fragmented, and the kernel could not find free blocks of 2 MiB. Another series on this site found exactly the same thing: huge pages set to always, and almost every attempt falls back to small pages. So the "with" and "without" of my experiment were almost the same thing, and I would not claim a TLB effect from these numbers.

Two questions about every input

The working set of a benchmark decides which part of the hardware it measures. With 32 KiB of data it measures the L1 cache, with 100 MiB of random accesses it measures DRAM latency, and between them there is a factor of 80. So I ask two questions about every benchmark input: how big is it, compared to the caches of the core that runs it, and how big is the data of the real program? If the answers are in different rows of the table above, the benchmark measures a different machine than the program uses.

And I look at the order of the accesses, because the same working set can cost 0.5 or 114 ns per element. The next parts look at two more ways the data can change the speed of the same code: the values themselves, and the allocator.

The program, the nine runs and the summary are in the fixture, in p16-working-set.txt.