cod*_*imp 10 c++ performance x86 inline-assembly
我正在编写C++代码来查找内存中非0xFF的第一个字节.为了利用bitscanforward,我编写了一个我非常喜欢的内联汇编代码.但是对于"可读性"以及未来的校对(即SIMD矢量化),我想我会给g ++优化器一个机会.g ++没有矢量化,但它确实得到了我所做的几乎相同的非SIMD解决方案.但由于某种原因,它的版本运行速度慢得多,速度慢260000倍(即我必须循环我的版本260,000x才能达到相同的执行时间).我除了一些差异,但不是那么多!有人可以指出它为什么会这样吗？我只是想知道在未来的内联汇编代码中出错.
C++的起点如下,(就计数准确性而言,此代码中存在一个错误,但我已将其简化为此速度测试):
uint64_t count3 (const void *data, uint64_t const &nBytes) {
uint64_t count = 0;
uint64_t block;
do {
block = *(uint64_t*)(data+count);
if ( block != (uint64_t)-1 ) {
/* count += __builtin_ctz(~block); ignore this for speed test*/
goto done;
};
count += sizeof(block);
} while ( count < nBytes );
done:
return (count>nBytes ? nBytes : count);
}
汇编代码g ++提出的是:
_Z6count3PKvRKm:
.LFB33:
.cfi_startproc
mov rdx, QWORD PTR [rsi]
xor eax, eax
jmp .L19
.p2align 4,,10
.p2align 3
.L21:
add rax, 8
cmp rax, rdx
jnb .L18
.L19:
cmp QWORD PTR [rdi+rax], -1
je .L21
.L18:
cmp rax, rdx
cmova rax, rdx
ret
.cfi_endproc
我的内联汇编是
_Z6count2PKvRKm:
.LFB32:
.cfi_startproc
push rbx
.cfi_def_cfa_offset 16
.cfi_offset 3, -16
mov rbx, QWORD PTR [rsi]
# count trailing bytes of 0xFF
xor rax, rax
.ctxff_loop_69:
mov r9, QWORD PTR [rdi+rax]
xor r9, -1
jnz .ctxff_final_69
add rax, 8
cmp rax, rbx
jl .ctxff_loop_69
.ctxff_final_69:
cmp rax,rbx
cmova rax,rbx
pop rbx
.cfi_def_cfa_offset 8
ret
.cfi_endproc
据我所知,除了将数据字节与0xFF进行比较的方法外,它基本相同.但我不敢相信这会导致计算时间的巨大差异.
可以想象我的测试方法导致错误,但我所做的只是更改下面的函数名称和迭代长度,简单的for循环如下所示:(当N为1 << 20时,'a'的所有字节除外最后一个字节是0xFF)
测试1
for (uint64_t i=0; i < ((uint64_t)1<<15); i++) {
n = count3(a,N);
}
测试2
for (uint64_t i=0; i < ((uint64_t)1<<33); i++) {
n = count2(a,N);
}
编辑:
这是我真正的内联汇编代码,包括SSE count1(),x64-64 count(),然后是普通的-c ++版本count0()和count3().我摔倒在这个兔子洞里,希望我能得到g ++来接受我count0()自己的,然后到达我的count1()甚至是count2().但是它没有做任何事,绝对没有优化:(我应该补充一点,我的平台没有AVX2,这就是为什么我希望让g ++自动进行矢量化,这样代码会在我更新平台时自动更新.
在联汇编明确寄存器的使用条款,如果我没有让他们明确,G ++会重复使用相同的寄存器nBytes和count.
就加速而言,在XMM和QWORD之间,我发现真正的好处就是我复制的"循环展开"效应count2().
uint32_t count0(const uint8_t *data, uint64_t const &nBytes) {
for (int i=0; i<nBytes; i++)
if (data[i] != 0xFF) return i;
return nBytes;
}
uint32_t count1(const void *data, uint64_t const &nBytes) {
uint64_t count;
__asm__("# count trailing bytes of 0xFF \n"
" xor %[count], %[count] \n"
" vpcmpeqb xmm0, xmm0, xmm0 \n" // make array of 0xFF
".ctxff_next_block_%=: \n"
" vpcmpeqb xmm1, xmm0, XMMWORD PTR [%[data]+%[count]] \n"
" vpmovmskb r9, xmm1 \n"
" xor r9, 0xFFFF \n" // test if all match (bonus negate r9)
" jnz .ctxff_tzc_%= \n" // if !=0, STOP & tzcnt negated r9
" add %[count], 16 \n" // else inc
" cmp %[count], %[nBytes] \n"
" jl .ctxff_next_block_%= \n" // while count < nBytes, loop
" jmp .ctxff_done_%= \n" // else done + ALL bytes were 0xFF
".ctxff_tzc_%=: \n"
" tzcnt r9, r9 \n" // count bytes up to non-0xFF
" add %[count], r9 \n"
".ctxff_done_%=: \n" // more than 'nBytes' could be tested,
" cmp %[count],%[nBytes] \n" // find minimum
" cmova %[count],%[nBytes] "
: [count] "=a" (count)
: [nBytes] "b" (nBytes), [data] "d" (data)
: "r9", "xmm0", "xmm1"
);
return count;
};
uint64_t count2 (const void *data, uint64_t const &nBytes) {
uint64_t count;
__asm__("# count trailing bytes of 0xFF \n"
" xor %[count], %[count] \n"
".ctxff_loop_%=: \n"
" mov r9, QWORD PTR [%[data]+%[count]] \n"
" xor r9, -1 \n"
" jnz .ctxff_final_%= \n"
" add %[count], 8 \n"
" mov r9, QWORD PTR [%[data]+%[count]] \n" // <--loop-unroll
" xor r9, -1 \n"
" jnz .ctxff_final_%= \n"
" add %[count], 8 \n"
" cmp %[count], %[nBytes] \n"
" jl .ctxff_loop_%= \n"
" jmp .ctxff_done_%= \n"
".ctxff_final_%=: \n"
" bsf r9, r9 \n" // do tz count on r9 (either of first QWORD bits or XMM bytes)
" shr r9, 3 \n" // scale BSF count accordiningly
" add %[count], r9 \n"
".ctxff_done_%=: \n" // more than 'nBytes' bytes could have been tested,
" cmp %[count],%[nBytes] \n" // find minimum of count and nBytes
" cmova %[count],%[nBytes] "
: [count] "=a" (count)
: [nBytes] "b" (nBytes), [data] "D" (data)
: "r9"
);
return count;
}
inline static uint32_t tzcount(uint64_t const &qword) {
uint64_t tzc;
asm("tzcnt %0, %1" : "=r" (tzc) : "r" (qword) );
return tzc;
};
uint64_t count3 (const void *data, uint64_t const &nBytes) {
uint64_t count = 0;
uint64_t block;
do {
block = *(uint64_t*)(data+count);
if ( block != (uint64_t)-1 ) {
count += tzcount(~block);
goto done;
};
count += sizeof(block);
} while ( count < nBytes );
done:
return (count>nBytes ? nBytes : count);
}
uint32_t N = 1<<20;
int main(int argc, char **argv) {
unsigned char a[N];
__builtin_memset(a,0xFF,N);
uint64_t n = 0, j;
for (uint64_t i=0; i < ((uint64_t)1<<18); i++) {
n += count2(a,N);
}
printf("\n\n %x %x %x\n",N, n, 0);
return n;
}
现在您已经发布了完整的代码:调用将count2(a,N)在循环中提升main.循环计数(例如1<<18)的运行时间仍然略微增加,但是所有循环正在进行的是单个add.编译器优化它看起来更像这个源:
uint64_t hoisted_count = count2(a,N);
for (uint64_t i=0; i < ((uint64_t)1<<18); i++) {
n += hoisted_count; // doesn't optimize to a multiply
}
没有寄存器冲突:%rax保存内联的asm语句的结果count2.然后它被用作微循环中的源操作数,n通过重复添加将其乘以.
(请参阅Godbolt Compiler Explorer上的asm ,并注意关于void*s:clang 上的算术的所有编译器警告拒绝编译代码):
## the for() loop in main, when using count2()
.L23:
addq %rax, %r12
subq $1, %rdx
jne .L23
%rdx这里是循环计数器,%r12是持有的累加器n.IDK为什么gcc没有将它优化为恒定时间乘法.
据推测,速度低260k的版本无法将整个环境提升count2出来.从gcc的角度来看,内联asm版本要简单得多:asm语句被视为其输入的纯函数,而gcc甚至不知道它触及内存的任何信息.C版本触及了大量内存,并且证明它可以被提升要复杂得多.
"memory"在asm语句中使用clobber确实防止它在我检查godbolt时被吊起.您可以main在向量块之前判断是否存在分支目标.
但无论如何,在运行时会像n + rep_count对n * rep_count.
该asm语句不使用"memory"clobber或任何内存输入来告诉gcc它读取输入指针指向的内存. 可能会发生不正确的优化,例如,从修改数组元素的循环中提升.(请参阅手册中的Clobbers部分,以获取使用虚拟匿名struct内存输入而不是使用毯子式内存的示例"memory".不幸的是,当内存块没有编译时常量大小时,我不认为这是可用的.)
I think -fno-inline prevents hoisting because the function isn't marked with __attribute__((const)) or the slightly weaker __attribute__((pure)) to indicate no side-effects. After inlining, the optimizer can see that for the asm statement.
count0 doesn't get optimized to anything good because gcc and clang can't auto-vectorize loops where the number of iterations isn't known at the start. i.e. they suck at stuff like strlen or memchr, or search loops in general, even if they're told that it's safe to access memory beyond the end of the point where the search loop exits early (e.g. using char buf[static 512] as a function arg).
Like I commented on the question, using xor reg, 0xFFFF/jnz is silly compared to cmp reg, 0xFFFF/jnz, because cmp/jcc can macro-fuse into a compare-and-branch uop. cmp reg, mem/jne can also macro-fuse, so the scalar version that does a load/xor/branch is using 3x as many uops per compare. (Of course, Sandybridge can only micro-fuse the load if it doesn't use an indexed addressing mode. Also, SnB can only macro-fuse one pair per decode block, and but you'd probably get the first cmp/jcc and the loop branch to macro-fuse.) Anyway, the xor is a bad idea. It's better to only xor right before the tzcnt, since saving uops in the loop is more important than code-size or uops total.
你的标量循环是9个融合域uops,这是每2个时钟在一次迭代中发出的太多.(SnB是一个4宽的管道,对于微小的环路,它实际上可以维持它.)
问题的第一个版本中的代码中的缩进与... count += __builtin_ctz处于同一级别if,使我认为您在计算不匹配块,而不是仅仅查找第一个.
不幸的是,我为这个答案的第一个版本编写的asm代码并没有解决与OP更新和更清晰的代码相同的问题.请参阅SSE2 asm的旧答案,使用pcmpeqb/paddb计算0xFF字节,使用psadbw计算水平和以避免环绕.
Branching on the result of a pcmpeq takes many more uops than branching on a cmp. If our search array is big, we can use a loop that tests multiple vectors at once, and then figure out which byte had our hit after breaking out of the loop.
This optimization applies to AVX2 as well.
Here's my attempt, using GNU C inline asm with -masm=intel syntax. (Intrinsics might give better results, esp. when inlining, because the compiler understands intrinsics and so can do constant-propagation through them, and stuff like that. OTOH, you can often beat the compiler with hand-written asm if you understand the trade-offs and the microarchitecture you're targeting. Also, if you can safely make some assumptions, but you can't easily communicate them to the compiler.)
#include <stdint.h>
#include <immintrin.h>
// compile with -masm=intel
// len must be a multiple of 32 (TODO: cleanup loop)
// buf should be 16B-aligned for best performance
size_t find_first_zero_bit_avx1(const char *bitmap, size_t len) {
// return size_t not uint64_t. This same code works in 32bit mode, and in the x32 ABI where pointers are 32bit
__m128i pattern, vtmp1, vtmp2;
const char *result_pos;
int tmpi;
const char *bitmap_start = bitmap;
asm ( // modifies the bitmap pointer, but we're inside a wrapper function
"vpcmpeqw %[pat], %[pat],%[pat]\n\t" // all-ones
".p2align 4\n\t" // force 16B loop alignment, for the benefit of CPUs without a loop buffer
//IACA_START // See the godbolt link for the macro definition
".Lcount_loop%=:\n\t"
// " movdqu %[v1], [ %[p] ]\n\t"
// " pcmpeqb %[v1], %[pat]\n\t" // for AVX: fold the load into vpcmpeqb, making sure to still use a one-register addressing mode so it can micro-fuse
// " movdqu %[v2], [ %[p] + 16 ]\n\t"
// " pcmpeqb %[v2], %[pat]\n\t"
" vpcmpeqb %[v1], %[pat], [ %[p] ]\n\t" // Actually use AVX, to get a big speedup over the OP's scalar code on his SnB CPU
" vpcmpeqb %[v2], %[pat], [ %[p] + 16 ]\n\t"
" vpand %[v2], %[v2], %[v1]\n\t" // combine the two results from this iteration
" vpmovmskb %k[result], %[v2]\n\t"
" cmp %k[result], 0xFFFF\n\t" // k modifier: eax instead of rax
" jne .Lfound%=\n\t"
" add %[p], 32\n\t"
" cmp %[p], %[endp]\n\t" // this is only 2 uops after the previous cmp/jcc. We could re-arrange the loop and put the branches farther apart if needed. (e.g. start with a vpcmpeqb outside the loop, so each iteration actually sets up for the next)
" jb .Lcount_loop%=\n\t"
//IACA_END
// any necessary code for the not-found case, e.g. bitmap = endp
" mov %[result], %[endp]\n\t"
" jmp .Lend%=\n\t"
".Lfound%=:\n\t" // we have to figure out which vector the first non-match was in, based on v1 and (v2&v1)
// We could just search the bytes over again, but we don't have to.
// we could also check v1 first and branch, instead of checking both and using a branchless check.
" xor %k[result], 0xFFFF\n\t"
" tzcnt %k[result], %k[result]\n\t" // runs as bsf on older CPUs: same result for non-zero inputs, but different flags. Faster than bsf on AMD
" add %k[result], 16\n\t" // result = byte count in case v1 is all-ones. In that case, v2&v1 = v2
" vpmovmskb %k[tmp], %[v1]\n\t"
" xor %k[tmp], 0xFFFF\n\t"
" bsf %k[tmp], %k[tmp]\n\t" // bsf sets ZF if its *input* was zero. tzcnt's flag results are based on its output. For AMD, it would be faster to use more insns (or a branchy strategy) and avoid bsf, but Intel has fast bsf.
" cmovnz %k[result], %k[tmp]\n\t" // if there was a non-match in v1, use it instead of tzcnt(v2)+16
" add %[result], %[p]\n\t" // If we needed to force 64bit, we could use %q[p]. But size_t should be 32bit in the x32 ABI, where pointers are 32bit. This is one advantage to using size_t over uint64_t
".Lend%=:\n\t"
: [result] "=&a" (result_pos), // force compiler to pic eax/rax to save a couple bytes of code-size from the special cmp eax, imm32 and xor eax,imm32 encodings
[p] "+&r" (bitmap),
// throw-away outputs to let the compiler allocate registers. All early-clobbered so they aren't put in the same reg as an input
[tmp] "=&r" (tmpi),
[pat] "=&x" (pattern),
[v1] "=&x" (vtmp1), [v2] "=&x" (vtmp2)
: [endp] "r" (bitmap+len)
// doesn't compile: len isn't a compile-time constant
// , "m" ( ({ struct { char x[len]; } *dummy = (typeof(dummy))bitmap ; *dummy; }) ) // tell the compiler *which* memory is an input.
: "memory" // we read from data pointed to by bitmap, but bitmap[0..len] isn't an input, only the pointer.
);
return result_pos - bitmap_start;
}
这实际上编译和汇编为asm,看起来像我的预期,但我没有测试它.请注意,它会将所有寄存器分配留给编译器,因此它更适合内联.即使没有内联,它也不会强制使用必须保存/恢复的调用保留寄存器(例如,使用"b"约束).
未完成:用于处理最后一个32B子块数据的标量代码.
基于Agner Fog指南/表格的英特尔SnB系列CPU的静态性能分析.另请参阅x86标记wiki. 我假设我们在缓存吞吐量方面没有瓶颈,因此这种分析仅适用于L2缓存中的数据热,或者只有L1缓存足够快.
This loop can issue out of the front-end at one iteration (two vectors) per 2 clocks, because it's 7 fused-domain uops. (The front-end issues in groups of 4). (It's probably actually 8 uops, if the two cmp/jcc pairs are decoded in the same block. Haswell and later can do two macro-fusions per decode group, but previous CPUs can only macro-fuse the first. We could software-pipeline the loop so the early-out branch is farther from the p < endp branch.)
All of these fused-domain uops include an ALU uop, so the bottleneck will be on ALU execution ports. Haswell added a 4th ALU unit that can handle simple non-vector ops, including branches, so could run this loop at one iteration per 2 clocks (16B per clock). Your i5-2550k (mentioned in comments) is a SnB CPU.
I used IACA to count uops per port, since it's time consuming to do it by hand. IACA is dumb and thinks there's some kind of inter-iteration dependency other than the loop counter, so I had to use -no_interiteration:
g++ -masm=intel -Wall -Wextra -O3 -mtune=haswell find-first-zero-bit.cpp -c -DIACA_MARKS
iaca -64 -arch IVB -no_interiteration find-first-zero-bit.o
Intel(R) Architecture Code Analyzer Version - 2.1
Analyzed File - find-first-zero-bit.o
Binary Format - 64Bit
Architecture - SNB
Analysis Type - Throughput
Throughput Analysis Report
--------------------------
Block Throughput: 2.50 Cycles Throughput Bottleneck: Port1, Port5
Port Binding In Cycles Per Iteration:
-------------------------------------------------------------------------
| Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 |
-------------------------------------------------------------------------
| Cycles | 2.0 0.0 | 2.5 | 1.0 1.0 | 1.0 1.0 | 0.0 | 2.5 |
-------------------------------------------------------------------------
N - port number or number of cycles resource conflict caused delay, DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3), CP - on a critical path
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion happened
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256 instruction, dozens of cycles penalty is expected
! - instruction not supported, was not accounted in Analysis
| Num Of | Ports pressure in cycles | |
| Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | |
---------------------------------------------------------------------
| 2^ | | 1.0 | 1.0 1.0 | | | | CP | vpcmpeqb xmm1, xmm0, xmmword ptr [rdx]
| 2^ | | 0.6 | | 1.0 1.0 | | 0.4 | CP | vpcmpeqb xmm2, xmm0, xmmword ptr [rdx+0x10]
| 1 | 0.9 | 0.1 | | | | 0.1 | CP | vpand xmm2, xmm2, xmm1
| 1 | 1.0 | | | | | | | vpmovmskb eax, xmm2
| 1 | | | | | | 1.0 | CP | cmp eax, 0xffff
| 0F | | | | | | | | jnz 0x18
| 1 | 0.1 | 0.9 | | | | | CP | add rdx, 0x20
| 1 | | | | | | 1.0 | CP | cmp rdx, rsi
| 0F | | | | | | | | jb 0xffffffffffffffe1
On SnB: pcmpeqb can run on p1/p5. Fused compare-and-branch can only run on p5. Non-fused cmp can run on p015. Anyway, if one of the branches doesn't macro-fuse, the loop can run at one iteration per 8/3 = 2.666 cycles. With macro-fusion, best-case is 7/3 = 2.333 cycles. (IACA doesn't try to simulate distribution of uops to ports exactly the way the hardware would dynamically make those decisions. However, we can't expect perfect scheduling from the hardware either, so 2 vectors per 2.5 cycles is probably reasonable with both macro-fusions happening. Uops that could have used port0 will sometimes steal port1 or port5, reducing throughput.)
As I said before, Haswell handles this loop better. IACA thinks HSW could run the loop at one iteration per 1.75c, but that's clearly wrong because the taken loop-branch ends the issue group. It will issue in a repeating 4,3 uop pattern. But the execution units can handle more throughput than the frontend for this loop, so it should really be able to keep up with the frontend on Haswell/Broadwell/Skylake and run at one iteration per 2 clocks.
Further unrolling of more vpcmpeqb/vpand is only 2 uops per vector (or 3 without AVX, where we'd load into a scratch and then use that as the destination for pcmpeqb.) So with sufficient unrolling, we should be able to do 2 vector loads per clock. Without AVX, this wouldn't be possible without the PAND trick, since a vector load/compare/movmsk/test-and-branch is 4 uops. Bigger unrolls make more work to decode the final position where we found a match: a scalar cmp-based cleanup loop might be a good idea once we're in the area. You could maybe use the same scalar loop for cleanup of non-multiple-of-32B sizes.
If using SSE, with movdqu/pcmpeqb xmm,xmm, we can use an indexed addressing mode without it costing us uops, because a movdqu load is always a single load uop regardless of addressing mode. (It doesn't need to micro-fuse with anything, unlike a store). This lets us save a uop of loop overhead by using a base pointer pointing to the end of the array, and the index counting up from zero. e.g. add %[idx], 32/js to loop while the index is negative.
With AVX, however, we can save 2 uops by using a single-register addressing mode so vpcmpeqb %[v1], %[pat], [ %[p] + 16 ] can micro-fuse. This means we need the add/cmp/jcc loop structure I used in the example. The same applies to AVX2.
所以我想我发现了问题。我认为内联汇编中使用的寄存器之一（尽管有破坏列表）与 g++ 对它们的使用相冲突，并且破坏了测试迭代。我提供了 g++ 版本的代码，作为内联汇编代码返回，并获得了与我自己的相同的 260000 倍加速。而且，回想起来，“加速”计算时间短得离谱。
最后，我如此关注体现为函数的代码，以至于我没有注意到 g++ 实际上也将该函数内联（我正在使用 -O3 优化）到测试 for 循环中。当我强制g++不内联（即-fno-inline）时，260000x加速度消失了。
我认为 g++ 在未经我许可的情况下内联整个函数时未能考虑内联汇编代码的“破坏列表”。
学过的知识。我需要更好地处理内联汇编约束或阻止函数内联__attribute__ ((noinline))
编辑：确实发现 g++ 用于raxmain() for 循环计数器，与我使用rax.