我需要计算两个向量的点积：包含64位无符号整数的uint64_t a[N], b[N];(N<=60)。正是这个循环：
unsigned __int128 ans = 0;
for(int i=0;i<N;++i)
ans += (unsigned __int128) a[i] * (unsigned __int128) b[i];
ans将溢出，因此结果必须保持在像256位这样的宽整数中。但是由于N<60，我们甚至可以保持160(64*2+32)位整数的结果。
慢速解决方案：
- 手动处理溢出：
unsigned __int128 ans = 0;
uint64_t overflow = 0;
for(int i=0;i<N;++i){
auto temp = ans;
ans += (unsigned __int128) a[i] * (unsigned __int128) b[i];
if(ans<temp) overflow++;
}
这是缓慢的，因为添加if会使程序减慢约2.2倍。
- 使用类似
boost::multiprecision::uint256_t或GMP的库
可能的快速解决方案：如果我们在64位机器上进行汇编编程，那么可以使用3个64位寄存器执行加法，先使用add，然后使用adc和adc，从低位到高位。
但我不想求助于ASM，因为它很难维护，而且不可移植。
我的目标是使它快速且可维护。
EDIT：Peter在他的评论中指出，clang支持我使用adc的想法，而gcc仍然使用分支(手动处理溢出)。
您绝对不需要256位累加器。N整数的和只能在最多N进位时产生，因此64位overflow进位计数器对于2^64个元素长的向量的点积就足够了。即128位乘积的和的总宽度只需要是192＝64*3或160＝128+32位。即一个额外的寄存器。
是的，用于此操作的最佳x86-64 asm是mov-从一个阵列加载，mul或mulx使用另一个阵列的内存源，然后add+adc到ans，再adc reg, 0以累积进位。
(可能使用一些循环展开，可能使用2个或更多累加器(3个寄存器的集合)。如果为英特尔CPU展开，可能会避免mul内存源的索引寻址模式，因此它可以对负载进行微熔断。不幸的是，GCC/clang没有生成相对于另一个数组索引一个数组的循环，以最大限度地减少循环开销(1个指针增量)，同时避免其中一个数组使用索引寻址模式，因此编译器无法获得最佳asm。但是叮当很好。)
clang9.0使用-O3 -march=broadwell -fno-unroll-loops为您的代码生成Clang识别出通常的a<b习惯用法，即使使用128位整数，也可以执行无符号a+=b，从而产生add reg,reg/adc reg,reg/adc reg,0(不幸的是，Clang的循环展开将优化为mov；setc；movzx；add而不是adc reg,0，这与循环展开的好处背道而驰！这是一个应该报告的遗漏优化错误。)
GCC实际上在if()上分支，您可以通过将其无分支地写为overflow += sum<prod;来修复它。但这对GCC的另一个主要遗漏优化没有帮助：实际上，对sum < prod与cmp/sbb进行128位比较，而不仅仅是使用最后一个adc的CF输出。GCC知道如何优化CCD_ 37(使用进位标志的有效128位加法)，但显然不适合从CCD_。
通过更改源代码来避免错过优化可能是不可能的，这是gcc开发人员必须在gcc中修复的一个错误(所以你应该在他们的bugzilla上将其报告为遗漏的优化错误https://gcc.gnu.org/bugzilla/；包括到该问答的链接；A) 。尝试自己完全手动使用uint64_t块会更糟糕：中间的块有进位和进位。这很难在C中正确写入，GCC也不会将其优化为adc。
即使使用overflow += __builtin_add_overflow(sum, prod, &sum);也没有完全帮助，给了我们相同的cmp/sbb/adcGCC代码https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html表示"编译器将尝试在可能的情况下使用硬件指令来实现这些内置函数，如加法后溢出的条件跳转、进位的条件跳转等。"，但显然它不知道如何处理128位整数。
#include <stdint.h>
static const int N = 2048;
using u128 = unsigned __int128;
u128 dp(uint64_t a[], uint64_t b[], uint64_t *overflow_out)
{
u128 sum = 0;
uint64_t overflow = 0;
for(int i=0;i<N;++i){
u128 prod = a[i] * (unsigned __int128) b[i];
//sum += prod;
//overflow += sum<prod; // gcc uses adc after a 3x mov / cmp / sbb; clang is still good
overflow += __builtin_add_overflow(sum, prod, &sum); // gcc less bad, clang still good
}
*overflow_out = overflow;
return sum;
}
Clang很好地编译了这个(Godbolt)：
# clang9.0 -O3 -march=broadwell -fno-unroll-loops -Wall -Wextra
... zero some regs, copy RDX to R8 (because MUL uses that implicitly)
.LBB0_1: # =>This Inner Loop Header: Depth=1
mov rax, qword ptr [rsi + 8*rcx]
mul qword ptr [rdi + 8*rcx]
add r10, rax
adc r9, rdx # sum += prod
adc r11, 0 # overflow += carry_out
inc rcx
cmp rcx, 2048
jne .LBB0_1 # }while(i < N);
mov qword ptr [r8], r11 # store the carry count
mov rax, r10
mov rdx, r9 # return sum in RDX:RAX
ret
请注意，您不需要ADOX/ADCX或MULX来提高效率。无序的exec可以交错多个短FLAGS依赖链。
您可以将另外3个寄存器用于另一个192位累加器(求和和和进位)，但这可能是不必要的。
这看起来像是前端的9个uops(假设mul不能保持索引寻址模式微融合(解锁)，但cmp/jcc将宏融合)，因此它最多每2.25个时钟周期运行1次。Haswell和早期版本将adc reg,reg作为2个uop运行，但Broadwell将3输入指令(FLAGS+2 regs)改进为1个uop。CCD_ 46是SnB家族上的一个特例。
循环携带的依赖链每个只有1个循环长：add进入r10，adc进入r9，adc进入r11。这些ADC指令的FLAGS输入是一个短的非循环携带依赖链的一部分，无序执行会把它当作早餐。
Ice Lake的5宽管道将运行得更快，比如每次迭代可能1.8个周期，假设它仍然解锁mul的内存操作数。
Zen有一个5指令宽的管道，如果它包含任何多uop指令，则有6个uop宽。因此，它可能会以每次迭代2个周期的速度运行，因为它的2c吞吐量会被完全乘法所限制。(正常的imul r64, r64非加宽乘法是1/时钟，Zen上的延迟为3c，与Intel相同。)
Zen 2将mul m64和mulx加速至1/clock(https://www.uops.info/html-tp/ZEN2/MUL_M64-Measurements.html)，并且可能是该循环中逐时运行速度最快的CPU。
通过对一个阵列相对于另一个阵列进行一些展开和索引，这种手动优化版本的每乘成本可能接近6个uops=mov负载(1个uop)+mul-mem(2个uop。
它仍然会成为前端的瓶颈，2个uops(指针增量和cmp/jcc)的最小循环开销意味着4的展开可以使我们每6.5个周期而不是每6个周期进行4次乘法运算，或完全展开的理论最大值的92%(假设内存或次优调度没有停滞，或者至少无序的执行足以吸收这一点，而不会使前端停滞。后端应该能够在Haswell和更高版本上跟上前端，因此ROB应该有空间吸收一些小气泡，但可能不会错过L3或TLB。)
我认为在这里使用SIMD没有任何好处；加法的最宽元素大小是64位，即使AVX512也只有64x64=>128位乘法。除非您可以转换为double，在这种情况下，AVX512可以更快地运行此。