So from my previous blog I had this very specific piece of code:
template<typename T>
concept CharType = std::integral<T>;
template<CharType C>
inline constexpr std::size_t chseqlen1(const C* pbuf) {
std::size_t len = 0;
while (pbuf[len] != 0) {
len++;
}
return len;
}
Appended the 1 in the name, to create distinction.
And it vectorizes PERFECTLY in g++. But then I somehow came up with a second version of chseqlen which literally does the same thing BUT DOES NOT VECTORIZE, despite having the same optimization flags as the original one.
This is version 2:
template<CharType C>
inline constexpr std::size_t chseqlen2(const C* pbuf) {
std::size_t len = 0;
while (*pbuf != 0) {
pbuf++;
len++;
}
return len;
}
Why did it NOT vectorize? Well, we gotta explore!
Also the way I came up with version-2 is genuinely funny! Like I wanted to show my friends in college about how g++ optimizes and vectorizes a very simple loop into hundreds of SIMD instructions! Just for my muscle memory to kick in, and I typed out the standard and usual crappy C version with pointer arithmetic — and g++ just refused to vectorize!!
GCC LITERALLY HAD 1 JOB! 1 PLACE TO SHINE! AND IT DIDN'T!!
But why?? We shall explore 😏😏
Implementation Pipeline
We defined them as templates, so we gotta implement them to get actual code! Here's the implementation:
void getlen1(const int* s, std::size_t& l) {
l = chseqlen1(s);
}
void getlen2(const int* s, std::size_t& l) {
l = chseqlen2(s);
}
I intentionally used const int* over here. If we had used const char* then gcc would have yeeted the whole thing with a strlen 🫠... But we gotta see vectorization!
Compiler flags
Pretty small section but extremely important (which is why it deserved its own section!). We use this compiler flags for all the code:
-std=c++20 -O3 -mavx2
Yea, we're using AVX2 machinery over here!
Generated Assembly
Generated assembly for version 1:
"getlen1(int const*, unsigned long&)":
mov r10d, DWORD PTR [rdi]
mov r8, rsi
test r10d, r10d
je .L22
lea rdx, [rdi+4]
shr rdx, 2
neg rdx
mov rax, rdx
and eax, 7
je .L3
mov r9d, DWORD PTR [rdi+4]
test r9d, r9d
je .L23
test dl, 6
je .L24
mov esi, DWORD PTR [rdi+8]
test esi, esi
je .L25
cmp rax, 2
jbe .L26
mov ecx, DWORD PTR [rdi+12]
test ecx, ecx
je .L27
and edx, 4
je .L28
mov r11d, DWORD PTR [rdi+16]
test r11d, r11d
je .L29
cmp rax, 4
je .L3
mov r10d, DWORD PTR [rdi+20]
test r10d, r10d
je .L30
cmp rax, 5
je .L3
mov r9d, DWORD PTR [rdi+24]
test r9d, r9d
je .L31
cmp rax, 7
jne .L32
mov esi, DWORD PTR [rdi+28]
test esi, esi
je .L2
.L3:
mov rsi, rax
.L4:
lea rcx, [rdi+4+rax*4]
vpxor xmm1, xmm1, xmm1
xor eax, eax
.L7:
vpcmpeqd ymm0, ymm1, YMMWORD PTR [rcx+rax*4]
mov rdx, rax
add rax, 8
vptest ymm0, ymm0
je .L7
add rsi, rdx
lea rax, [rsi+1]
mov ecx, DWORD PTR [rdi+rax*4]
lea rdx, [0+rax*4]
test ecx, ecx
je .L41
mov r11d, DWORD PTR [rdi+4+rdx]
test r11d, r11d
je .L43
mov r10d, DWORD PTR [rdi+8+rdx]
test r10d, r10d
je .L44
mov r9d, DWORD PTR [rdi+12+rdx]
test r9d, r9d
je .L45
mov ecx, DWORD PTR [rdi+16+rdx]
test ecx, ecx
je .L46
mov eax, DWORD PTR [rdi+20+rdx]
test eax, eax
je .L47
mov eax, DWORD PTR [rdi+24+rdx]
test eax, eax
je .L48
mov eax, DWORD PTR [rdi+28+rdx]
test eax, eax
je .L49
mov eax, DWORD PTR [rdi+32+rdx]
test eax, eax
je .L50
mov eax, DWORD PTR [rdi+36+rdx]
test eax, eax
je .L51
mov r11d, DWORD PTR [rdi+40+rdx]
test r11d, r11d
je .L52
mov r10d, DWORD PTR [rdi+44+rdx]
test r10d, r10d
je .L53
mov r9d, DWORD PTR [rdi+48+rdx]
test r9d, r9d
je .L54
mov ecx, DWORD PTR [rdi+52+rdx]
test ecx, ecx
je .L55
mov edx, DWORD PTR [rdi+56+rdx]
lea rax, [rsi+16]
test edx, edx
je .L56
.L41:
vzeroupper
.L2:
mov QWORD PTR [r8], rax
ret
.L24:
mov esi, 1
jmp .L4
.L26:
mov esi, 2
jmp .L4
.L28:
mov esi, 3
jmp .L4
.L32:
mov esi, 6
jmp .L4
.L46:
lea rax, [rsi+5]
vzeroupper
jmp .L2
.L29:
mov eax, 4
jmp .L2
.L22:
xor eax, eax
mov QWORD PTR [r8], rax
ret
.L43:
lea rax, [rsi+2]
vzeroupper
jmp .L2
.L23:
mov eax, 1
jmp .L2
.L44:
lea rax, [rsi+3]
vzeroupper
jmp .L2
.L25:
mov eax, 2
jmp .L2
.L45:
lea rax, [rsi+4]
vzeroupper
jmp .L2
.L27:
mov eax, 3
jmp .L2
.L47:
lea rax, [rsi+6]
vzeroupper
jmp .L2
.L30:
mov eax, 5
jmp .L2
.L54:
lea rax, [rsi+13]
vzeroupper
jmp .L2
.L56:
lea rax, [rsi+15]
vzeroupper
jmp .L2
.L48:
lea rax, [rsi+7]
vzeroupper
jmp .L2
.L31:
mov eax, 6
jmp .L2
.L49:
lea rax, [rsi+8]
vzeroupper
jmp .L2
.L50:
lea rax, [rsi+9]
vzeroupper
jmp .L2
.L51:
lea rax, [rsi+10]
vzeroupper
jmp .L2
.L52:
lea rax, [rsi+11]
vzeroupper
jmp .L2
.L53:
lea rax, [rsi+12]
vzeroupper
jmp .L2
.L55:
lea rax, [rsi+14]
vzeroupper
jmp .L2
Generated assembly for version 2 🫠:
"getlen2(int const*, unsigned long&)":
mov ecx, DWORD PTR [rdi]
xor eax, eax
test ecx, ecx
je .L58
.L59:
add rax, 1
mov edx, DWORD PTR [rdi+rax*4]
test edx, edx
jne .L59
.L58:
mov QWORD PTR [rsi], rax
ret
Yea, we're getting scalar for version 2.
Diagnosing GCC
To diagnose gcc, we gotta look at exactly what it is doing for optimization! And these flags will help us in that:
-fopt-info-vec-missed-fdump-tree-vect-details
Okay, I'll leave this blog unfinished right here, cuz I actually need to read through the vect-details to understand what exactly gcc is doing. But I'd definitely update the blog. Just publishing it like this — take it as a teaser!
Anyway, see you later oomfie~!
Top comments (0)