У меня была идея, как оптимизировать лексер, и я попробовал экспериментальный код. Код без ветвей как-то медленнее, чем версия с ветвлением. Я озадачен Версия без отрубей не вводила условных ходов. Я не могу себе представить, почему это медленнее, тем более что я использовал rand () для генерации входных данных. Я не могу представить, чтобы предсказания ветвлений были хорошими со случайными данными. Кто-нибудь знает, почему версия ветвления работает быстрее?
-Edit- Согласно perf stat у кода без ответвлений много бэкэндов (51,65%). Я понял, что забыл увеличить pdata_out в версии ветки, но это не сильно сократило разрыв. Ветвление имеет 18,82% киосков.
Оба были скомпилированы с clang++-10 -O2 -mssse3 и не должны быть эквивалентными
Источник ветвления Неотраслевой источник
код ветвления, который я переписал в не ветвящийся (не приложил особых усилий)
{
auto prevToken = token;
token &= temp_array[n];
if (token)
continue;
auto len = pinput+n-data_left;
if (prevToken & LexClass::DecimalValue)
{
*pdata_out = Token::TokDecimal;
*ptoken_len=len;
ptoken_len++;
}
else if (prevToken & LexClass::Var)
{
auto push_token = Token::variable;
*pdata_out = push_token;
*ptoken_len=len;
ptoken_len++;
}
else if (prevToken & LexClass::NewLine)
{
line_start[line_start_index++] = pinput+n-data;
*pdata_out = Token::TokNewLine;
}
else if (prevToken & LexClass::WhiteSpace)
{
//NOOP
}
else {
}
token = temp_array[n];
data_left = pinput+n;
if(token == 0)
token = LexClass::WhiteSpace;
}
версия без ветвлений (не эквивалентно, и я не старался)
{
const auto input128 = _mm_loadu_si128((__m128i*)pinput);
const auto lowNibble = _mm_and_si128(input128, MaskLowNibble);
const auto highNibble = _mm_and_si128(_mm_srli_epi32(input128, 4), MaskLowNibble);
const auto lo_val = _mm_shuffle_epi8(LowTable, lowNibble);
const auto hi_val = _mm_shuffle_epi8(HighTable, highNibble);
const auto lookup_result = _mm_and_si128(lo_val, hi_val);
_mm_store_si128((__m128i*)temp_array, lookup_result);
for(int n=0; n<16; n++)
{
auto prevToken = token;
token &= temp_array[n];
if (token)
continue;
auto len = pinput+n-data_left;
auto lz = 64 - __builtin_clzll(prevToken);
auto tbl_value = tbl[lz];
auto tokenValue = 256 + (tbl_value & 0x3F);
*pdata_out = tokenValue;
pdata_out += tbl_value>>7;
*ptoken_len = len;
ptoken_len+=(tbl_value>>6) & 1;
line_start[line_start_index] = pinput+n-data;
line_start_index+=(prevToken & LexClass::NewLine) != 0 ? 1 : 0;
token = temp_array[n];
data_left = pinput+n;
token = token!=0?token:LexClass::WhiteSpace;
}
}
Различный файл S
--- branching.s 2020-04-28 01:42:57.578939280 -0400
+++ nonbranching.s 2020-04-28 01:42:53.938780661 -0400
@@ -1,5 +1,5 @@
.text
- .file "branching.cpp"
+ .file "nonbranching.cpp"
.globl _Z8GenTablev # -- Begin function _Z8GenTablev
.p2align 4, 0x90
.type _Z8GenTablev,@function
@@ -199,10 +199,14 @@
.cfi_def_cfa_register %rbp
pushq %r15
pushq %r14
+ pushq %r13
+ pushq %r12
pushq %rbx
andq $-64, %rsp
subq $128, %rsp
- .cfi_offset %rbx, -40
+ .cfi_offset %rbx, -56
+ .cfi_offset %r12, -48
+ .cfi_offset %r13, -40
.cfi_offset %r14, -32
.cfi_offset %r15, -24
callq _Z8GenTablev
@@ -253,16 +257,17 @@
movaps %xmm0, %fs:data@TPOFF+32
movups _ZL10test_input+41(%rip), %xmm0
movups %xmm0, %fs:data@TPOFF+41
- movq %fs:0, %rcx
- leaq data@TPOFF(%rcx), %rax
- leaq token_len@TPOFF(%rcx), %r15
- movl $1, %r10d
+ movq %fs:0, %rax
+ leaq data@TPOFF(%rax), %rsi
+ leaq token_len@TPOFF(%rax), %r14
+ leaq data_out@TPOFF(%rax), %r13
+ movl $1, %r9d
movdqa .LCPI1_0(%rip), %xmm1 # xmm1 = [3616804123480109617,3329059735766188339]
movdqa .LCPI1_1(%rip), %xmm0 # xmm0 = [15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15]
- movq $data@TPOFF, %r9
+ movq $data@TPOFF, %r10
movl $104857600, %r8d # imm = 0x6400000
- movl $1, %ecx
- movq %rax, %r11
+ movl $1, %eax
+ movq %rsi, %r11
.p2align 4, 0x90
.LBB1_6: # =>This Loop Header: Depth=1
# Child Loop BB1_7 Depth 2
@@ -281,56 +286,54 @@
.p2align 4, 0x90
.LBB1_7: # Parent Loop BB1_6 Depth=1
# => This Inner Loop Header: Depth=2
- movq %rax, %rdi
- movzbl %bl, %eax
- andl %ecx, %eax
+ movzbl %bl, %edi
+ andl %eax, %edi
je .LBB1_11
# %bb.8: # in Loop: Header=BB1_7 Depth=2
- movl %eax, %ecx
- movq %rdi, %rax
+ movl %edi, %eax
cmpq $15, %rdx
- jne .LBB1_20
+ jne .LBB1_13
jmp .LBB1_9
.p2align 4, 0x90
.LBB1_11: # in Loop: Header=BB1_7 Depth=2
- leaq (%r11,%rdx), %rax
- movq %rax, %rsi
- subq %rdi, %rsi
- testb $8, %cl
- jne .LBB1_12
-# %bb.14: # in Loop: Header=BB1_7 Depth=2
- testb $4, %cl
- jne .LBB1_15
-# %bb.16: # in Loop: Header=BB1_7 Depth=2
- testb $2, %cl
- je .LBB1_18
-# %bb.17: # in Loop: Header=BB1_7 Depth=2
+ leaq (%r11,%rdx), %rdi
+ movl %edi, %ebx
+ subl %esi, %ebx
+ cltq
+ bsrq %rax, %rsi
+ xorq $63, %rsi
+ movl $_ZZ4mainE3tbl, %ecx
+ subq %rsi, %rcx
+ movzbl 64(%rcx), %ecx
+ movl %ecx, %esi
+ andl $63, %esi
+ orl $256, %esi # imm = 0x100
+ movw %si, (%r13)
+ shrl $6, %ecx
+ movl %ecx, %esi
+ andl $-2, %esi
+ addq %rsi, %r13
+ movb %bl, (%r14)
+ andl $1, %ecx
+ addq %rcx, %r14
movq %fs:0, %rcx
- addl %r9d, %ecx
- movl %eax, %esi
- subl %ecx, %esi
+ addl %r10d, %ecx
+ movq %rdi, %rsi
+ # kill: def $edi killed $edi killed $rdi
+ subl %ecx, %edi
movslq %fs:line_start_index@TPOFF, %rcx
- leal 1(%rcx), %edi
- movl %edi, %fs:line_start_index@TPOFF
- movl %esi, %fs:line_start@TPOFF(,%rcx,4)
- movw $259, %fs:data_out@TPOFF # imm = 0x103
- jmp .LBB1_18
-.LBB1_12: # in Loop: Header=BB1_7 Depth=2
- movw $257, %fs:data_out@TPOFF # imm = 0x101
- jmp .LBB1_13
-.LBB1_15: # in Loop: Header=BB1_7 Depth=2
- movw $262, %fs:data_out@TPOFF # imm = 0x106
-.LBB1_13: # in Loop: Header=BB1_7 Depth=2
- movb %sil, (%r15)
- addq $1, %r15
-.LBB1_18: # in Loop: Header=BB1_7 Depth=2
- movzbl (%rsp,%rdx), %ecx
- testb %cl, %cl
- cmovel %r10d, %ecx
- movzbl %cl, %ecx
+ movl %edi, %fs:line_start@TPOFF(,%rcx,4)
+ shrl %eax
+ andl $1, %eax
+ addl %ecx, %eax
+ movl %eax, %fs:line_start_index@TPOFF
+ movzbl (%rsp,%rdx), %eax
+ testb %al, %al
+ cmovel %r9d, %eax
+ movzbl %al, %eax
cmpq $15, %rdx
je .LBB1_9
-.LBB1_20: # in Loop: Header=BB1_7 Depth=2
+.LBB1_13: # in Loop: Header=BB1_7 Depth=2
movzbl 1(%rsp,%rdx), %ebx
addq $1, %rdx
jmp .LBB1_7
@@ -341,14 +344,15 @@
addq %r8, %rdx
addq $data@TPOFF, %rdx
cmpq %rdx, %r11
- jae .LBB1_21
+ jae .LBB1_14
# %bb.10: # in Loop: Header=BB1_6 Depth=1
movdqu (%r11), %xmm1
jmp .LBB1_6
-.LBB1_21:
- movzwl %fs:data_out@TPOFF, %esi
+.LBB1_14:
movq %fs:0, %rax
- leaq token_len@TPOFF(%rax), %r14
+ leaq data_out@TPOFF(%rax), %r12
+ movzwl %fs:data_out@TPOFF, %esi
+ leaq token_len@TPOFF(%rax), %r15
movzbl %fs:token_len@TPOFF, %edx
movl $.L.str.3, %edi
xorl %eax, %eax
@@ -428,17 +432,21 @@
movl $.L.str.3, %edi
xorl %eax, %eax
callq printf
+ subq %r12, %r13
+ sarq %r13
movl %fs:line_start_index@TPOFF, %edx
- subq %r14, %r15
+ subq %r15, %r14
movl $.L.str.4, %edi
- xorl %esi, %esi
- movq %r15, %rcx
+ movq %r13, %rsi
+ movq %r14, %rcx
xorl %r8d, %r8d
xorl %eax, %eax
callq printf
xorl %eax, %eax
- leaq -24(%rbp), %rsp
+ leaq -40(%rbp), %rsp
popq %rbx
+ popq %r12
+ popq %r13
popq %r14
popq %r15
popq %rbp
@@ -626,6 +634,12 @@
.asciz "123\n0x123Af\n123.45\n0x12F3a1\nvar\nif\nifword\ni\na+b*c!\n_Word"
.size _ZL10test_input, 57
+ .type _ZZ4mainE3tbl,@object # @_ZZ4mainE3tbl
+ .section .rodata.cst8,"aM",@progbits,8
+_ZZ4mainE3tbl:
+ .asciz "\000\000\000\000\301\306\203"
+ .size _ZZ4mainE3tbl, 8
+
.type .L.str.3,@object # @.str.3
.section .rodata.str1.1,"aMS",@progbits,1
.L.str.3: