libdivide

libdivide 是一个仅包含头文件的 C/C++ 库,用于优化整数除法。整数除法是大多数 CPU 上速度最慢的指令之一,例如,在当前的 x64 CPU 上,64 位整数除法的延迟可达 90 个时钟周期,而乘法的延迟仅为 3 个时钟周期。libdivide 允许您用一系列移位、加法和乘法指令来替换昂贵的整数除法指令,从而更快地计算整数除法。

在当前的 CPU 上,使用 libdivide 时,64 位整数除法的加速率可达 10 倍,32 位整数除法的加速率可达 5 倍。libdivide 还支持 SSE2、AVX2、AVX512、NEON 和 SVE 向量除法,这些功能可提供更大的加速率。您可以使用 benchmark 程序测试在您的 CPU 上可实现的加速率。

libdivide 兼容 8 位微控制器,例如 AVR 系列: CI 编译包中包含 AtMega2560 目标。由于此类低端硬件通常不包含硬件除法器,libdivide 尤其有用。除了运行时 C 和 C++ API 之外,还包含一组 预定义宏 和 模板,用于加速对 16 位常量的除法: 8 位系统上,avr-gcc 并未对对 16 位常量的除法进行优化(https://stackoverflow.com/questions/47994933/why-doesnt-gcc-or-clang-on-arm-use-division-by-invariant-integers-using-multip)。有关 libdivide 的更多信息,请参阅 https://libdivide.com。

第一个代码片段使用整数除法将向量中的所有整数分成若干部分。这种方法很慢，因为整数除法比当前 CPU 上的其他整数算术运算至少快一个数量级。