Why do arrays of different integer sizes have different performance?

Question

Why does a 32-bit system need 4 times more time to save 32-bit values than to save 8-bit values?

It doesn’t. But there are 3 different issues with your benchmark that are giving you those results.

You’re not pre-faulting the memory. So you’re page-faulting the arrays during the benchmark. These page faults along with the OS kernel interaction are a dominant factor in the time.
The compiler with -O3 is completely defeating your benchmark by converting all your loops into memset().
Your benchmark is memory-bound. So you’re measuring the speed of your memory instead of the core.

Problem 1: The Test Data is not Prefaulted

Your arrays are declared, but not used before the benchmark. Because of the way the kernel and memory allocation works, they are not mapped into memory yet. It’s only when you first touch them does this happen. And when it does, it incurs a very large penalty from the kernel to map the page.

This can be done by touching all the arrays before the benchmark.

No Pre-Faulting: http://coliru.stacked-crooked.com/a/1df1f3f9de420d18

g++ -O3 -Wall main.cpp && ./a.out
Time of processing int8 array:  28983us.
Time of processing int16 array: 57100us.
Time of processing int32 array: 113361us.
Time of processing int64 array: 224451us.

With Pre-Faulting: http://coliru.stacked-crooked.com/a/7e62b9c7ca19c128

g++ -O3 -Wall main.cpp && ./a.out
Time of processing int8 array:  6216us.
Time of processing int16 array: 12472us.
Time of processing int32 array: 24961us.
Time of processing int64 array: 49886us.

The times drop by roughly a factor of 4. In other words, your original benchmark was measuring more of the kernel than the actual code.

Problem 2: The Compiler is Defeating the Benchmark

The compiler is recognizing your pattern of writing zeros and is completely replacing all your loops with calls to memset(). So in effect, you’re measuring calls to memset() with different sizes.

  call std::chrono::_V2::system_clock::now()
  xor esi, esi
  mov edx, 67108864
  mov edi, OFFSET FLAT:int8Array
  mov r14, rax
  call memset
  call std::chrono::_V2::system_clock::now()
  xor esi, esi
  mov edx, 134217728
  mov edi, OFFSET FLAT:int16Array
  mov r13, rax
  call memset
  call std::chrono::_V2::system_clock::now()
  xor esi, esi
  mov edx, 268435456
  mov edi, OFFSET FLAT:int32Array
  mov r12, rax
  call memset
  call std::chrono::_V2::system_clock::now()
  xor esi, esi
  mov edx, 536870912
  mov edi, OFFSET FLAT:int64Array
  mov rbp, rax
  call memset
  call std::chrono::_V2::system_clock::now()

The optimization that’s doing this is -ftree-loop-distribute-patterns. Even if you turn that off, the vectorizer will give you a similar effect.

With -O2, vectorization and pattern recognition are both disabled. So the compiler gives you what you write.

.L4:
  mov BYTE PTR [rax], 0         ;; <<------ 1 byte at a time
  add rax, 1
  cmp rdx, rax
  jne .L4
  call std::chrono::_V2::system_clock::now()
  mov rbp, rax
  mov eax, OFFSET FLAT:int16Array
  lea rdx, [rax+134217728]
.L5:
  xor ecx, ecx
  add rax, 2
  mov WORD PTR [rax-2], cx      ;; <<------ 2 bytes at a time
  cmp rdx, rax
  jne .L5
  call std::chrono::_V2::system_clock::now()
  mov r12, rax
  mov eax, OFFSET FLAT:int32Array
  lea rdx, [rax+268435456]
.L6:
  mov DWORD PTR [rax], 0        ;; <<------ 4 bytes at a time
  add rax, 4
  cmp rax, rdx
  jne .L6
  call std::chrono::_V2::system_clock::now()
  mov r13, rax
  mov eax, OFFSET FLAT:int64Array
  lea rdx, [rax+536870912]
.L7:
  mov QWORD PTR [rax], 0        ;; <<------ 8 bytes at a time
  add rax, 8
  cmp rdx, rax
  jne .L7
  call std::chrono::_V2::system_clock::now()

With -O2: http://coliru.stacked-crooked.com/a/edfdfaaf7ec2882e

g++ -O2 -Wall main.cpp && ./a.out
Time of processing int8 array:  28414us.
Time of processing int16 array: 22617us.
Time of processing int32 array: 32551us.
Time of processing int64 array: 56591us.

Now it’s clear that the smaller word sizes are slower. But you would expect the times to be flat if all the word sizes were the same speed. And the reason they aren’t is because of memory bandwidth.

Problem 3: Memory Bandwidth

Because the benchmark (as written) is only writing zeros, it is easily saturating the memory bandwidth for the core/system. So the benchmark becomes affected by how much memory is touched.

To fix that, we need to shrink the dataset so that it fits into cache. To compensate for this, we loop over the same data multiple times.

std::array<std::int8_t, 512> int8Array;
std::array<std::int16_t, 512> int16Array;
std::array<std::int32_t, 512> int32Array;
std::array<std::int64_t, 512> int64Array;

...

auto point1 = std::chrono::high_resolution_clock::now();
for (int c = 0; c < 64 * 1024; c++) for (auto &v : int8Array) v = 0;
auto point2 = std::chrono::high_resolution_clock::now();
for (int c = 0; c < 64 * 1024; c++) for (auto &v : int16Array) v = 0;
auto point3 = std::chrono::high_resolution_clock::now();
for (int c = 0; c < 64 * 1024; c++) for (auto &v : int32Array) v = 0;
auto point4 = std::chrono::high_resolution_clock::now();
for (int c = 0; c < 64 * 1024; c++) for (auto &v : int64Array) v = 0;
auto point5 = std::chrono::high_resolution_clock::now();

Now we see timings that are a lot more flat for the different word-sizes:

http://coliru.stacked-crooked.com/a/f534f98f6d840c5c

g++ -O2 -Wall main.cpp && ./a.out
Time of processing int8 array:  20487us.
Time of processing int16 array: 21965us.
Time of processing int32 array: 32569us.
Time of processing int64 array: 26059us.

The reason why it isn’t completely flat is probably because there are numerous other factors involved with the compiler optimizations. You might need to resort to loop-unrolling to get any closer.

Leave a Comment Cancel reply