Software Design
Published in

Software Design

Auto-vectorize C and C++ code

Auto-vectorization of for loops results in significant performance improvement

Developers can take advantage of built-in auto-vectorization support in GCC. Let’s explore vectorization with the GCC 11.2 compiler with the following compiler options to enable auto-vectorization.

-O3 -march=skylake-avx512 -mno-vzeroupper

Vector operations with 8 iterations

Let’s start with the following code. We are performing vector operations where the compiler knows that the code will loop 8 times (VECLEN). Another thing to note is the use of the __restrict keyword. This keyword tells the compiler that the pointer c does not overlap with a and b. Thus, the compiler does not need to keep updating intermediate results.

typedef float vec;
#define VECLEN 8
void vector_op(vec *a , vec *b, vec * __restrict c) {
for (int i=0; i < VECLEN; i++) {
c[i] = a[i] * b[i];
}
}

The compiler generates no loop, and the 8 operations are performed with a single set of instructions.

vector_op(float*, float*, float*):
vmovups ymm0, YMMWORD PTR [rdi]
vmulps ymm0, ymm0, YMMWORD PTR [rsi]
vmovups YMMWORD PTR [rdx], ymm0
ret

Here the compiler is performing the following operations:

vmovups ymm0, YMMWORD PTR [rdi]

The processor has copied the entire array of 8 entries of a from memory into 8 packed floats stored in the ymm0 register. Note that rdi register points to the start of the a array.

vmulps ymm0, ymm0, YMMWORD PTR [rsi]

Here the processor is performing a vector multiplication for a (ymm0) and b (pointer to b is stored in the rsi register). The final result is saved in the ymm0 register.

vmovups YMMWORD PTR [rdx], ymm0

Now the processor is copying the results to the array c. (pointer to c is stored in the rdx register). This is the last step before ret returns from the function.

View in compiler explorer.

Vector operations with 16 iterations

When the code is changed to 16 iterations, the generated code simply repeats the block we saw with 8 iterations.

typedef float vec;
#define VECLEN 16
void vector_op(vec *a , vec *b, vec * __restrict c) {
for (int i=0; i < VECLEN; i++) {
c[i] = a[i] * b[i];
}
}

The generated code unrolls the loop.

vector_op(float*, float*, float*):
vmovups ymm1, YMMWORD PTR [rdi]
vmulps ymm0, ymm1, YMMWORD PTR [rsi]
vmovups YMMWORD PTR [rdx], ymm0
vmovups ymm0, YMMWORD PTR [rdi+32]
vmulps ymm0, ymm0, YMMWORD PTR [rsi+32]
vmovups YMMWORD PTR [rdx+32], ymm0
ret

View in compiler explorer.

Vector operations with 128 iterations

Even with VECLEN set to 128, there is still no loop in sight.

vector_op(float*, float*, float*):
vmovups ymm1, YMMWORD PTR [rdi]
vmovups ymm2, YMMWORD PTR [rdi+32]
vmulps ymm0, ymm1, YMMWORD PTR [rsi]
vmovups ymm3, YMMWORD PTR [rdi+64]
vmovups ymm4, YMMWORD PTR [rdi+96]
vmovups ymm5, YMMWORD PTR [rdi+128]
vmovups ymm6, YMMWORD PTR [rdi+160]
vmovups YMMWORD PTR [rdx], ymm0
vmulps ymm0, ymm2, YMMWORD PTR [rsi+32]
vmovups ymm7, YMMWORD PTR [rdi+192]
vmovups ymm1, YMMWORD PTR [rdi+224]
vmovups ymm2, YMMWORD PTR [rdi+256]
vmovups YMMWORD PTR [rdx+32], ymm0
vmulps ymm0, ymm3, YMMWORD PTR [rsi+64]
vmovups ymm3, YMMWORD PTR [rdi+288]
vmovups YMMWORD PTR [rdx+64], ymm0
vmulps ymm0, ymm4, YMMWORD PTR [rsi+96]
vmovups ymm4, YMMWORD PTR [rdi+320]
vmovups YMMWORD PTR [rdx+96], ymm0
vmulps ymm0, ymm5, YMMWORD PTR [rsi+128]
vmovups YMMWORD PTR [rdx+128], ymm0
vmulps ymm0, ymm6, YMMWORD PTR [rsi+160]
vmovups YMMWORD PTR [rdx+160], ymm0
vmulps ymm0, ymm7, YMMWORD PTR [rsi+192]
vmovups YMMWORD PTR [rdx+192], ymm0
vmulps ymm0, ymm1, YMMWORD PTR [rsi+224]
vmovups YMMWORD PTR [rdx+224], ymm0
vmulps ymm0, ymm2, YMMWORD PTR [rsi+256]
vmovups YMMWORD PTR [rdx+256], ymm0
vmulps ymm0, ymm3, YMMWORD PTR [rsi+288]
vmovups YMMWORD PTR [rdx+288], ymm0
vmulps ymm0, ymm4, YMMWORD PTR [rsi+320]
vmovups YMMWORD PTR [rdx+320], ymm0
vmovups ymm5, YMMWORD PTR [rdi+352]
vmovups ymm6, YMMWORD PTR [rdi+384]
vmulps ymm0, ymm5, YMMWORD PTR [rsi+352]
vmovups ymm7, YMMWORD PTR [rdi+416]
vmovups ymm1, YMMWORD PTR [rdi+448]
vmovups YMMWORD PTR [rdx+352], ymm0
vmulps ymm0, ymm6, YMMWORD PTR [rsi+384]
vmovups YMMWORD PTR [rdx+384], ymm0
vmulps ymm0, ymm7, YMMWORD PTR [rsi+416]
vmovups YMMWORD PTR [rdx+416], ymm0
vmulps ymm0, ymm1, YMMWORD PTR [rsi+448]
vmovups YMMWORD PTR [rdx+448], ymm0
vmovups ymm0, YMMWORD PTR [rdi+480]
vmulps ymm0, ymm0, YMMWORD PTR [rsi+480]
vmovups YMMWORD PTR [rdx+480], ymm0
ret

View in compiler explorer.

Vector operations with 256 iterations

With VECLEN set to 256, we do get a loop in the generated code. Note that even with the loop, the processor is performing 8 multiplications per loop. Thus, the generated loop iterates only 32 times.

vector_op(float*, float*, float*):
xor eax, eax
.L2:
vmovups ymm1, YMMWORD PTR [rsi+rax]
vmulps ymm0, ymm1, YMMWORD PTR [rdi+rax]
vmovups YMMWORD PTR [rdx+rax], ymm0
add rax, 32
cmp rax, 1024
jne .L2
ret

View in compiler explorer.

Vector operations with n iterations

In the above examples, we have considered scenarios where the loop iteration count is known at compile time. Now let’s consider the case where n iterations have to be performed.

typedef float vec;
void vector_op(vec *a , vec *b, vec * __restrict c, int n) {
for (int i=0; i < n; i++) {
c[i] = a[i] * b[i];
}
}

The compiler cannot optimize the loop in advance, so we get some run-time checks and a lot of code.

vector_op(float*, float*, float*, int):
test ecx, ecx
jle .L1
lea r9d, [rcx-1]
cmp r9d, 6
jbe .L8
mov r8d, ecx
shr r8d, 3
sal r8, 5
xor eax, eax
.L4:
vmovups ymm1, YMMWORD PTR [rdi+rax]
vmulps ymm0, ymm1, YMMWORD PTR [rsi+rax]
vmovups YMMWORD PTR [rdx+rax], ymm0
add rax, 32
cmp rax, r8
jne .L4
mov eax, ecx
and eax, -8
mov r8d, eax
cmp ecx, eax
je .L11
.L3:
mov r10d, ecx
sub r9d, eax
sub r10d, eax
cmp r9d, 2
jbe .L6
vmovups xmm2, XMMWORD PTR [rdi+rax*4]
vmulps xmm0, xmm2, XMMWORD PTR [rsi+rax*4]
vmovups XMMWORD PTR [rdx+rax*4], xmm0
mov eax, r10d
and eax, -4
add r8d, eax
cmp r10d, eax
je .L1
.L6:
movsx rax, r8d
vmovss xmm0, DWORD PTR [rdi+rax*4]
vmulss xmm0, xmm0, DWORD PTR [rsi+rax*4]
vmovss DWORD PTR [rdx+rax*4], xmm0
lea eax, [r8+1]
cmp ecx, eax
jle .L1
cdqe
vmovss xmm0, DWORD PTR [rsi+rax*4]
add r8d, 2
vmulss xmm0, xmm0, DWORD PTR [rdi+rax*4]
vmovss DWORD PTR [rdx+rax*4], xmm0
cmp ecx, r8d
jle .L1
movsx r8, r8d
vmovss xmm0, DWORD PTR [rdi+r8*4]
vmulss xmm0, xmm0, DWORD PTR [rsi+r8*4]
vmovss DWORD PTR [rdx+r8*4], xmm0
.L1:
ret
.L11:
ret
.L8:
xor eax, eax
xor r8d, r8d
jmp .L3

View in compiler explorer.

Vector operations when the __restrict keyword is not used

Finally, let’s see the impact of not using __restrict keyword. Consider our first 8 iteration loop without __restrict prefix.

typedef float vec;
#define VECLEN 8
void vector_op(vec *a , vec *b, vec *c) {
for (int i=0; i < VECLEN; i++) {
c[i] = a[i] * b[i];
}
}

Now the compiler cannot assume that a and b do not overlap with c. The compiler ends up generating explicit checks to handle the overlapping case. The generated code is:

vector_op(float*, float*, float*):
lea rcx, [rdi+4]
mov rax, rdx
sub rdx, rcx
cmp rdx, 24
jbe .L2
lea rcx, [rsi+4]
mov rdx, rax
sub rdx, rcx
cmp rdx, 24
jbe .L2
vmovups ymm0, YMMWORD PTR [rsi]
vmulps ymm0, ymm0, YMMWORD PTR [rdi]
vmovups YMMWORD PTR [rax], ymm0
ret
.L2:
vmovss xmm0, DWORD PTR [rdi]
vmulss xmm0, xmm0, DWORD PTR [rsi]
vmovss DWORD PTR [rax], xmm0
vmovss xmm0, DWORD PTR [rdi+4]
vmulss xmm0, xmm0, DWORD PTR [rsi+4]
vmovss DWORD PTR [rax+4], xmm0
vmovss xmm0, DWORD PTR [rdi+8]
vmulss xmm0, xmm0, DWORD PTR [rsi+8]
vmovss DWORD PTR [rax+8], xmm0
vmovss xmm0, DWORD PTR [rdi+12]
vmulss xmm0, xmm0, DWORD PTR [rsi+12]
vmovss DWORD PTR [rax+12], xmm0
vmovss xmm0, DWORD PTR [rdi+16]
vmulss xmm0, xmm0, DWORD PTR [rsi+16]
vmovss DWORD PTR [rax+16], xmm0
vmovss xmm0, DWORD PTR [rdi+20]
vmulss xmm0, xmm0, DWORD PTR [rsi+20]
vmovss DWORD PTR [rax+20], xmm0
vmovss xmm0, DWORD PTR [rdi+24]
vmulss xmm0, xmm0, DWORD PTR [rsi+24]
vmovss DWORD PTR [rax+24], xmm0
vmovss xmm0, DWORD PTR [rdi+28]
vmulss xmm0, xmm0, DWORD PTR [rsi+28]
vmovss DWORD PTR [rax+28], xmm0
ret

View in compiler explorer.

Key takeaways

Auto-vectorization of the code can result in significant performance improvement as multiple operations are performed in a single instruction. This has the additional benefit that the compiler can unroll loops with a large number of iterations.

Note however that a lot of benefits accrue only if the compiler knows the number of iterations at compile time. If the iteration count is not known at compile-time, some performance is lost by runtime checks to pick the optimal leg of the generated code.

Letting the compiler know that the input and output vectors don’t overlap also reduces the code bloat. The compiler can avoid costly runtime checks to look for the overlap.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store