I am trying to understand the CPU cache performance in a single producer single consumer queue algorithm, but cannot pinpoint the cause of performance degradation in some cases. The following simplified test program runs with practically no L1 cache misses, but nevertheless it spends many cycles stalled in the CPU backend when its memory access pattern is somewhat sparser. What causes the CPU backend to stall in such cases, when there are practically no L1 misses? What should be measured to pinpoint the cause?
My CPU is AMD Ryzen 5 PRO 4650G, which is Zen 2 “Renoir” with 192KiB L1d cache. The memcpy test program:
// demo_memcpy_test_speed-gap.c
#include <stdio.h>
#include <stdint.h>
#include <time.h>
#include <cstring>
#define PACKET_SIZE 8 // 16 32 // <--- it is really the stride of the memcpy over the mem array
#define SIZE_TO_MEMCPY 8 // memcpy only the first 8 bytes of the "packet"
const static long long unsigned n_packets = 512; // use few packets, to fit in L2 etc
static long long unsigned repeat = 1000*1000 * 2 * 2; // repeat many times to get enough stats in perf
const static long long unsigned n_max_data_bytes = n_packets * PACKET_SIZE;
#define CACHE_LINE_SIZE 64 // align explicitly just in case
alignas(CACHE_LINE_SIZE) uint8_t data_in [n_max_data_bytes];
alignas(CACHE_LINE_SIZE) uint8_t data_out [n_packets][PACKET_SIZE];
int main(int argc, char* argv[])
{
printf("memcpy_test.c standard\n");
printf("PACKET_SIZE %d SIZE_TO_MEMCPY %d\n", PACKET_SIZE, SIZE_TO_MEMCPY);
//
// warmup the memory
// i.e. access the memory to make sure Linux has set up the virtual mem tables
...
{
printf("\nrun memcpy\n");
long long unsigned n_bytes_copied = 0;
long long unsigned memcpy_ops = 0;
start_setup = clock();
for (unsigned rep=0; rep<repeat; rep++) {
uint8_t* data_in_ptr = &data_in [0];
for (unsigned long long i_packet=0; i_packet<n_packets; i_packet++) {
// copy only SIZE_TO_MEMCPY of the in data array to the out
uint8_t* data_out_ptr = &(data_out [i_packet][0]);
memcpy(data_out_ptr, data_in_ptr, SIZE_TO_MEMCPY*sizeof(uint8_t));
memcpy_ops++;
n_bytes_copied += SIZE_TO_MEMCPY;
data_in_ptr += PACKET_SIZE;
}
}
end_setup = clock();
cpu_time_used_setup = ((double) (end_setup - start_setup)) / CLOCKS_PER_SEC;
printf("memcpy() took %f seconds to execute\n", cpu_time_used_setup);
printf("%f Mops\n", memcpy_ops/(1000000*cpu_time_used_setup));
printf("%llu bytes\n", n_bytes_copied);
printf("%f Mbytes/s\n", n_bytes_copied/(1000000*cpu_time_used_setup));
}
} // end of main
It’s built with -O1 to get a really efficient loop with memcpy:
g++ -g -O1 ./demo_memcpy_test_speed-gap.c
The instructions of the memcpy loop, as seen in perf record annotate option:
sudo perf record -F 999 -e stalled-cycles-backend -- ./a.out
sudo perf report
...select main
With PACKET_SIZE set to 8, the code is really efficient:
│ for (unsigned long long i_packet=0; i_packet<n_packets; i_packet++) {
│11b:┌─→mov %rbx,%rax
│ │memcpy():
│11e:│ mov (%rcx,%rax,8),%rdx
100.00 │ │ mov %rdx,(%rsi,%rax,8)
│ │main():
│ │ add $0x1,%rax
│ │ cmp $0x200,%rax
│ │↑ jne 11e
│ │for (unsigned rep=0; rep<repeat; rep++) {
│ │ sub $0x1,%edi
│ └──jne 11b
With PACKET_SIZE set to 1024, and the code is the same for 256, except add $0x100.. instead of 0x400:
│ lea _end,%rsi
│140:┌─→mov %rbp,%rdx
│ │
│ │ lea data_in,%rax
│ │
│ │__fortify_function void *
│ │__NTH (memcpy (void *__restrict __dest, const void *__restrict __src,
│ │size_t __len))
│ │{
│ │return __builtin___memcpy_chk (__dest, __src, __len,
│14a:│ mov (%rax),%rcx
│ │memcpy():
96.31 │ │ mov %rcx,(%rdx)
│ │
1.81 │ │ add $0x400,%rax
0.20 │ │ add $0x400,%rdx
1.12 │ │ cmp %rsi,%rax
0.57 │ │↑ jne 14a
│ │ sub $0x1,%edi
│ └──jne 140
I run it with PACKET_SIZE set to 8, 16, 32, and other values. The perf counts for 8 and 32:
sudo perf stat -e task-clock,instructions,cycles,stalled-cycles-frontend,stalled-cycles-backend \
-e L1-dcache-loads,L1-dcache-load-misses,L1-dcache-prefetches \
-e l2_cache_accesses_from_dc_misses,l2_cache_hits_from_dc_misses,l2_cache_misses_from_dc_misses \
-- ./a.out
PACKET_SIZE 8 SIZE_TO_MEMCPY 8
...
Performance counter stats for './a.out':
503.43 msec task-clock # 0.998 CPUs utilized
10,323,618,071 instructions # 4.79 insn per cycle
# 0.01 stalled cycles per insn (29.11%)
2,154,694,815 cycles # 4.280 GHz (29.91%)
5,148,993 stalled-cycles-frontend # 0.24% frontend cycles idle (30.70%)
55,922,538 stalled-cycles-backend # 2.60% backend cycles idle (30.99%)
4,091,862,625 L1-dcache-loads # 8.128 G/sec (30.99%)
24,211 L1-dcache-load-misses # 0.00% of all L1-dcache accesses (30.99%)
18,745 L1-dcache-prefetches # 37.234 K/sec (30.37%)
30,749 l2_cache_accesses_from_dc_misses # 61.079 K/sec (29.57%)
21,046 l2_cache_hits_from_dc_misses # 41.805 K/sec (28.78%)
9,095 l2_cache_misses_from_dc_misses # 18.066 K/sec (28.60%)
PACKET_SIZE 32 SIZE_TO_MEMCPY 8
...
Performance counter stats for './a.out':
832.83 msec task-clock # 0.999 CPUs utilized
12,289,501,297 instructions # 3.46 insn per cycle
# 0.11 stalled cycles per insn (29.42%)
3,549,297,932 cycles # 4.262 GHz (29.64%)
5,552,837 stalled-cycles-frontend # 0.16% frontend cycles idle (30.12%)
1,349,663,970 stalled-cycles-backend # 38.03% backend cycles idle (30.25%)
4,144,875,512 L1-dcache-loads # 4.977 G/sec (30.25%)
772,968 L1-dcache-load-misses # 0.02% of all L1-dcache accesses (30.24%)
539,481 L1-dcache-prefetches # 647.767 K/sec (30.25%)
532,879 l2_cache_accesses_from_dc_misses # 639.839 K/sec (30.24%)
461,131 l2_cache_hits_from_dc_misses # 553.690 K/sec (30.04%)
14,485 l2_cache_misses_from_dc_misses # 17.392 K/sec (29.55%)
There is a slight increase in L1 cache misses: from 0% at 8 bytes PACKET_SIZE up to 0.02% at 32 bytes. But can it justify why the backend stalls jumped from 2.6% to 38%? If no, then what else stalls the CPU backend?
I get that a larger stride means that the memcpy loop moves from one L1 cache line to another one sooner. But, if the lines are already in the cache, and there are practically no L1 miss events, as reported by perf, then why would an access to a different cache line stall the backend? Is it something about how the CPU issues the instructions in parallel? Maybe, it cannot issue instructions that access different cache lines simultaneously?
Runs with PACKET_SIZE up to 1024 bytes are shown on the following somewhat busy plot:
“Sorry, you cannot include links in your post” i. stack. imgur. com /98nRo.jpg
The number on the data points shows the PACKET_SIZE parameter of the run, i.e. the stride of the memcpy access pattern. The X axis is millions of operations per second (Mops), an “operation” = 1 memcpy. The Y axis contains the metrics from perf: the percent of L1 accesses that missed, and percent of cycles that are stalled in backend and frontend.
In all these runs, the L2 accesses practically do not miss, i.e. l2_cache_misses_from_dc_misses metric is always very low. Just for completeness, according to Ian Cutress on anandtech (“AMD Zen 2 Microarchitecture Analysis: Ryzen 3000 and EPYC Rome” amd-zen-2-microarchitecture-analysis-ryzen-3000-and-epyc-rome/11) Zen 2 architecture L1 latency is 4 cycles, L2 latency is 12 cycles.
I am not sure why the frontend gets stalled. But that’s what perf reports. And I believe it is real. Because the effect of the stalled frontend is different from backend. If you compare the runs with PACKET_SIZE 256 and 1024 on the plot: they have about the same L1 misses; 256 has about 77% cycles stalled in backend and 0% in frontend; 1024 is the opposite, 77% stalled in frontend and 0% in backend. Yet, 1024 is much slower, because it has much less instructions issued per cycle. It’s about 0.42 in the 1024 run, and 1.28 in the 256 run.
So, the CPU issues less instructions per cycle when it is stalled in frontend rather than in backend. I guess that’s just how the frontend and backend work, i.e. the backend can run more parallel. It would be well appreciated if someone could confirm or correct this guess. However, a more important question: why does the frontend get stalled? The frontend is supposed to just decode the instructions. The assembly does not really change with PACKET_SIZE set to 256 or 1024. Then, what makes the frontend to stall more at 1024 stride than at 256?
The plot of IPC per Mops for all the PACKET_SIZE runs:
“Sorry, you cannot include links in your post” i. stack. imgur. com / zy678.png
The run with PACKET_SIZE 8 is slightly off the line towards more Mops, i.e. faster than the trend of other values. That must be because of the more efficient instructions.