c - 有效地将无符号值除以2的幂，四舍五入

Question

我想有效地将​​unsigneda整数除以2的任意幂，然后取整。所以我在数学上想要的是ceiling(p/q)0。在C语言中，不利用q受限域的Strawman实现可能类似于以下function1:

/** q must be a power of 2, although this version works for any q */
uint64_t divide(uint64_t p, uint64_t q) {
  uint64_t res = p / q;
  return p % q == 0 ? res : res + 1;
} 

...当然，我实际上并不想在机器级别使用除法或mod，因为即使在现代硬件上也要花费很多时间。我正在寻找一种使用移位和/或其他廉价操作的强度降低方法-充分利用 q是2的幂的事实。

您可以假设我们有一个有效的 lg(unsigned int x)函数，如果 x是2的幂，它会返回 x的以2为底的对数。

如果 q为零，则未定义的行为很好。

请注意，简单的解决方案: (p+q-1) >> lg(q)通常不起作用-例如，尝试使用 p == 2^64-100 and q == 256 2。

平台详情

我对C语言中的解决方案感兴趣，这些解决方案可能在各种平台上都可以很好地运行，但是为了具体起见，请给予奖励，并且由于对性能的任何明确讨论都需要包含目标体系结构，因此我将具体介绍关于我将如何测试它们:

Skylake CPU

带有编译标志的

gcc 5.4.0 -O3 -march=haswell

使用gcc内建函数(例如，bitscan /前导零内建函数)很好，尤其是我已经实现了我说的 lg()函数，如下所示:

inline uint64_t lg(uint64_t x) {
  return 63U - (uint64_t)__builtin_clzl(x);
}

inline uint32_t lg32(uint32_t x) {
  return 31U - (uint32_t)__builtin_clz(x);
}

我验证了这些代码至少可以通过 bsr编译成一条 -march=haswell指令，尽管显然存在减法。您当然可以忽略这些，而在解决方案中使用所需的任何其他内置函数。

基准测试

我为现有答案写了一个 benchmark，并将在进行更改时共享和更新结果。

为可能进行内联的小型操作编写良好的基准非常困难。当将代码内联到调用站点中时，该函数的许多工作可能会消失，尤其是在循环3中。

您可以通过确保未内联代码来避免整个内联问题:在另一个编译单元中声明它。我尝试使用 bench二进制文件来实现，但是实际上结果是毫无意义的。几乎所有实现每次调用都以4或5个周期为限，但是即使是一个除了 return 0也不执行任何操作的伪方法也需要花费相同的时间。因此，您主要只是在测量 call + ret开销。此外，您几乎永远不会真正使用这样的功能-除非您搞砸了，否则它们将可用于内联并且会改变一切。

因此，我将最关注的两个基准是循环调用被测方法，从而实现内联，跨函数优化，循环提升甚至矢量化。

总体上有两种基准类型:延迟和吞吐量。关键区别在于，在等待时间基准测试中，每次对 divide的调用都依赖于先前的调用，因此一般而言，调用不能轻易重叠4:

uint32_t bench_divide_latency(uint32_t p, uint32_t q) {
    uint32_t total = p;                         
    for (unsigned i=0; i < ITERS; i++) {                
      total += divide_algo(total, q);                       
      q = rotl1(q);                         
    }
    return total;
  }

请注意，正在运行的 total取决于每个除法调用的输出，并且它也是 divide调用的输入。

另一方面，吞吐量变量不会将一个划分的输出馈送到下一个划分。这样一来，一个调用的工作就可以与随后的调用(由编译器，尤其是CPU)重叠，甚至允许向量化:

uint32_t bench_divide_throughput(uint32_t p, uint32_t q) { 
    uint32_t total = p;                         
    for (unsigned i=0; i < ITERS; i++) {                
      total += fname(i, q);                     
      q = rotl1(q);                     
    }                                   
    return total;                           
  }

请注意，这里我们将循环计数器作为除数输入-这是可变的，但不依赖于先前的除法调用。

此外，每个基准具有除数 q的三种行为:

编译时常数除数。例如，对divide(p, 8)的调用。这在实践中很常见，当在编译时知道除数时，代码可以简单得多。

不变除数。在这里，除数在编译时是未知的，但在整个基准测试循环中是恒定的。这允许编译时常数进行优化的子集。

可变除数。除数在循环的每次迭代中更改。上面的基准测试功能使用“向左旋转1”指令更改除数来显示此变体。

结合所有内容，您总共可以获得6个不同的基准。

结果

总体

为了选择总体上最佳的算法，我查看了建议算法的12个子集中的每个子集: (latency, throughput) x (constant a, invariant q, variable q) x (32-bit, 64-bit)，并为每个子测试分配了2、1或0的分数，如下所示:

最佳算法(容差5％以内)得分为2。

“足够接近”的算法(比最佳算法慢不超过50％)的得分为1。

其余算法得分为零。

因此，最大总分是24，但是没有算法可以达到该目的。以下是总体总结果:

╔═══════════════════════╦═══════╗
║       Algorithm       ║ Score ║
╠═══════════════════════╬═══════╣
║ divide_user23_variant ║    20 ║
║ divide_chux           ║    20 ║
║ divide_user23         ║    15 ║
║ divide_peter          ║    14 ║
║ divide_chrisdodd      ║    12 ║
║ stoke32               ║    11 ║
║ divide_chris          ║     0 ║
║ divide_weather        ║     0 ║
╚═══════════════════════╩═══════╝

因此，对于此特定测试代码，在此特定编译器以及在此平台上而言，与chux的建议(实际上是相同的代码)结合使用，user2357112“variant”(带有 ... + (p & mask) != 0)的性能最佳。

以下是所有子得分的总和:

╔══════════════════════════╦═══════╦════╦════╦════╦════╦════╦════╗
║                          ║ Total ║ LC ║ LI ║ LV ║ TC ║ TI ║ TV ║
╠══════════════════════════╬═══════╬════╬════╬════╬════╬════╬════╣
║ divide_peter             ║     6 ║  1 ║  1 ║  1 ║  1 ║  1 ║  1 ║
║ stoke32                  ║     6 ║  1 ║  1 ║  2 ║  0 ║  0 ║  2 ║
║ divide_chux              ║    10 ║  2 ║  2 ║  2 ║  1 ║  2 ║  1 ║
║ divide_user23            ║     8 ║  1 ║  1 ║  2 ║  2 ║  1 ║  1 ║
║ divide_user23_variant    ║    10 ║  2 ║  2 ║  2 ║  1 ║  2 ║  1 ║
║ divide_chrisdodd         ║     6 ║  1 ║  1 ║  2 ║  0 ║  0 ║  2 ║
║ divide_chris             ║     0 ║  0 ║  0 ║  0 ║  0 ║  0 ║  0 ║
║ divide_weather           ║     0 ║  0 ║  0 ║  0 ║  0 ║  0 ║  0 ║
║                          ║       ║    ║    ║    ║    ║    ║    ║
║ 64-bit Algorithm         ║       ║    ║    ║    ║    ║    ║    ║
║ divide_peter_64          ║     8 ║  1 ║  1 ║  1 ║  2 ║  2 ║  1 ║
║ div_stoke_64             ║     5 ║  1 ║  1 ║  2 ║  0 ║  0 ║  1 ║
║ divide_chux_64           ║    10 ║  2 ║  2 ║  2 ║  1 ║  2 ║  1 ║
║ divide_user23_64         ║     7 ║  1 ║  1 ║  2 ║  1 ║  1 ║  1 ║
║ divide_user23_variant_64 ║    10 ║  2 ║  2 ║  2 ║  1 ║  2 ║  1 ║
║ divide_chrisdodd_64      ║     6 ║  1 ║  1 ║  2 ║  0 ║  0 ║  2 ║
║ divide_chris_64          ║     0 ║  0 ║  0 ║  0 ║  0 ║  0 ║  0 ║
║ divide_weather_64        ║     0 ║  0 ║  0 ║  0 ║  0 ║  0 ║  0 ║
╚══════════════════════════╩═══════╩════╩════╩════╩════╩════╩════╝

在这里，每个测试的名称都类似于XY，在{Latency，Throughput}中使用X，在{Constant Q，Invariant Q，Variable Q}中使用Y。因此，例如，LC是“具有常数q的延迟测试”。

分析

在最高级别上，解决方案大致可分为两类:快速(排名前6名的整理者)和慢速(排名后2名)。差异更大:所有快速算法在至少两个子测试中都是最快的，通常，当它们没有首先完成时，它们就属于“足够接近”的类别(只有在 stoke和 chrisdodd)。但是，慢速算法在每个测试中得分为0(甚至没有接近)。因此，您几乎可以从进一步考虑中消除慢速算法。

自动向量化

在快速算法中，最大的区别在于 auto-vectorize的能力。

在等待时间测试中，没有一种算法能够自动向量化，这是有道理的，因为 latency tests旨在将其结果直接输入到下一个迭代中。因此，您实际上只能以串行方式计算结果。

但是，对于吞吐量测试，许多算法能够针对恒定Q和不变Q情况自动矢量化。在这两个测试中，除数 q是循环不变的(在前一种情况下，它是编译时常量)。被除数是循环计数器，因此它是可变的，但是是可预测的(特别是可以通过将8与上一个输入 vector [0, 1, 2, ..., 7] + [8, 8, ..., 8] == [8, 9, 10, ..., 15]相加来简单地计算被除数的 vector )。

在这种情况下， gcc能够向量化 peter， stoke， chux， user23和 user23_variant。由于某种原因，它无法向量化 chrisdodd，这可能是因为它包含了一个分支(但是，由于许多其他解决方案都具有条件​​元素，但条件 vector 仍然被向量化，因此条件严格地不能向量化)。影响是巨大的:矢量化算法显示出的吞吐量比不但不是很快的变体提高了约8倍。

矢量化不是免费的!以下是每个函数的“常量”变体的函数大小， Vec?列显示函数是否向量化:

Size Vec? Name
 045    N bench_c_div_stoke_64
 049    N bench_c_divide_chrisdodd_64
 059    N bench_c_stoke32_64
 212    Y bench_c_divide_chux_64
 227    Y bench_c_divide_peter_64
 220    Y bench_c_divide_user23_64
 212    Y bench_c_divide_user23_variant_64

趋势很明显-向量化函数的大小约为非向量化函数的4倍。这是因为核心循环本身更大( vector 指令往往更大，并且它们更多)，并且因为循环设置(尤其是后循环代码)更大:例如，向量化版本需要简化为将 vector 中的所有部分和求和。循环计数是固定的，并且是8的倍数，因此不会生成尾码-但是如果可变，则生成的码会更大。

此外，尽管运行时有了很大的改进，但 gcc的向量化实际上很差。这是彼得例程的向量化版本的摘录:

  on entry: ymm4 == all zeros
  on entry: ymm5 == 0x00000001 0x00000001 0x00000001 ...
  4007a4:       c5 ed 76 c4             vpcmpeqd ymm0,ymm2,ymm4
  4007ad:       c5 fd df c5             vpandn   ymm0,ymm0,ymm5
  4007b1:       c5 dd fa c0             vpsubd   ymm0,ymm4,ymm0
  4007b5:       c5 f5 db c0             vpand    ymm0,ymm1,ymm0

该块可独立处理源自 DWORD的8个 ymm2元素。如果我们将 x用作 DWORD的单个 ymm2元素，并且 y ymm1的传入值，则这些指令对应于:

                    x == 0   x != 0
x  = x ? 0 : -1; //     -1        0
x  = x & 1;      //      1        0
x  = 0 - x;      //     -1        0
x  = y1 & x;     //     y1        0

因此，前三个指令可以简单地用第一个指令代替，因为两种情况下的状态都是相同的。因此，这是在该依赖关系链中添加了两个循环(循环未循环加载)和两个额外的指令。显然， gcc的优化阶段在某种程度上与矢量化代码的交互性很差，因为在标量代码中很少会错过这种琐碎的优化。同样，检查 other vectorized versions会显示很多性能下降。

分行与无分行

几乎所有解决方案都编译为无分支代码，即使C代码具有条件分支或显式分支。条件部分足够小，以至于编译器通常决定使用条件移动或某些变体。一个异常(exception)是 chrisdodd，它在所有吞吐量测试中都带有一个分支(检查 p == 0是否已编译)，但没有一个延迟测试。这是恒定 q吞吐量测试中的一个典型示例:

0000000000400e60 <bench_c_divide_chrisdodd_32>:
  400e60:       89 f8                   mov    eax,edi
  400e62:       ba 01 00 00 00          mov    edx,0x1
  400e67:       eb 0a                   jmp    400e73 <bench_c_divide_chrisdodd_32+0x13>
  400e69:       0f 1f 80 00 00 00 00    nop    DWORD PTR [rax+0x0]
  400e70:       83 c2 01                add    edx,0x1
  400e73:       83 fa 01                cmp    edx,0x1
  400e76:       74 f8                   je     400e70 <bench_c_divide_chrisdodd_32+0x10>
  400e78:       8d 4a fe                lea    ecx,[rdx-0x2]
  400e7b:       c1 e9 03                shr    ecx,0x3
  400e7e:       8d 44 08 01             lea    eax,[rax+rcx*1+0x1]
  400e82:       81 fa 00 ca 9a 3b       cmp    edx,0x3b9aca00
  400e88:       75 e6                   jne    400e70 <bench_c_divide_chrisdodd_32+0x10>
  400e8a:       c3                      ret    
  400e8b:       0f 1f 44 00 00          nop    DWORD PTR [rax+rax*1+0x0]

400e76的分支跳过 p == 0的情况。实际上，编译器可能只是剥离了第一个迭代(显式计算其结果)，然后完全避免了跳转，因为在此之后，它可以证明 p != 0。在这些测试中，分支是完全可预测的，这可能会给使用分支实际编译的代码带来优势(因为compare＆分支代码本质上是脱节的并且接近免费)，并且是 chrisdodd获胜的重要原因吞吐量，可变q情况。

详细的测试结果

在这里，您可以找到一些详细的测试结果以及有关测试本身的一些详细信息。

潜伏

下面的结果在1e9次迭代中测试了每种算法。只需将时间/通话时间乘以时钟频率即可计算出周期。通常，您可以假设 4.01之类的东西与 4.00相同，但是更大的诸如 5.11之类的偏差似乎是真实且可复制的。
divide_plusq_32的结果使用 (p + q - 1) >> lg(q)，但仅供引用，因为大 p + q的此功能失败。 dummy的结果是一个非常简单的函数: return p + q，可让您估计基准开销5(加法本身最多需要一个周期)。

==============================
Bench: Compile-time constant Q
==============================
                  Function         ns/call    cycles
           divide_peter_32            2.19      5.67
           divide_peter_64            2.18      5.64
                stoke32_32            1.93      5.00
                stoke32_64            1.97      5.09
              stoke_mul_32            2.75      7.13
              stoke_mul_64            2.34      6.06
              div_stoke_32            1.94      5.03
              div_stoke_64            1.94      5.03
            divide_chux_32            1.55      4.01
            divide_chux_64            1.55      4.01
          divide_user23_32            1.97      5.11
          divide_user23_64            1.93      5.00
  divide_user23_variant_32            1.55      4.01
  divide_user23_variant_64            1.55      4.01
       divide_chrisdodd_32            1.95      5.04
       divide_chrisdodd_64            1.93      5.00
           divide_chris_32            4.63     11.99
           divide_chris_64            4.52     11.72
         divide_weather_32            2.72      7.04
         divide_weather_64            2.78      7.20
           divide_plusq_32            1.16      3.00
           divide_plusq_64            1.16      3.00
           divide_dummy_32            1.16      3.00
           divide_dummy_64            1.16      3.00


==============================
Bench: Invariant Q
==============================
                  Function         ns/call    cycles
           divide_peter_32            2.19      5.67
           divide_peter_64            2.18      5.65
                stoke32_32            1.93      5.00
                stoke32_64            1.93      5.00
              stoke_mul_32            2.73      7.08
              stoke_mul_64            2.34      6.06
              div_stoke_32            1.93      5.00
              div_stoke_64            1.93      5.00
            divide_chux_32            1.55      4.02
            divide_chux_64            1.55      4.02
          divide_user23_32            1.95      5.05
          divide_user23_64            2.00      5.17
  divide_user23_variant_32            1.55      4.02
  divide_user23_variant_64            1.55      4.02
       divide_chrisdodd_32            1.95      5.04
       divide_chrisdodd_64            1.93      4.99
           divide_chris_32            4.60     11.91
           divide_chris_64            4.58     11.85
         divide_weather_32           12.54     32.49
         divide_weather_64           17.51     45.35
           divide_plusq_32            1.16      3.00
           divide_plusq_64            1.16      3.00
           divide_dummy_32            0.39      1.00
           divide_dummy_64            0.39      1.00


==============================
Bench: Variable Q
==============================
                  Function         ns/call    cycles
           divide_peter_32            2.31      5.98
           divide_peter_64            2.26      5.86
                stoke32_32            2.06      5.33
                stoke32_64            1.99      5.16
              stoke_mul_32            2.73      7.06
              stoke_mul_64            2.32      6.00
              div_stoke_32            2.00      5.19
              div_stoke_64            2.00      5.19
            divide_chux_32            2.04      5.28
            divide_chux_64            2.05      5.30
          divide_user23_32            2.05      5.30
          divide_user23_64            2.06      5.33
  divide_user23_variant_32            2.04      5.29
  divide_user23_variant_64            2.05      5.30
       divide_chrisdodd_32            2.04      5.30
       divide_chrisdodd_64            2.05      5.31
           divide_chris_32            4.65     12.04
           divide_chris_64            4.64     12.01
         divide_weather_32           12.46     32.28
         divide_weather_64           19.46     50.40
           divide_plusq_32            1.93      5.00
           divide_plusq_64            1.99      5.16
           divide_dummy_32            0.40      1.05
           divide_dummy_64            0.40      1.04

通量

这是吞吐量测试的结果。请注意，这里的许多算法都是自动矢量化的，因此，这些算法的性能相对较好:在许多情况下，仅占周期的一小部分。一个结果是，与大多数延迟结果不同，64位函数的速度要慢得多，因为矢量化在较小的元素尺寸下更有效(尽管间隙比我预期的要大)。

==============================
Bench: Compile-time constant Q
==============================
                  Function         ns/call    cycles
                stoke32_32            0.39      1.00
            divide_chux_32            0.15      0.39
            divide_chux_64            0.53      1.37
          divide_user23_32            0.14      0.36
          divide_user23_64            0.53      1.37
  divide_user23_variant_32            0.15      0.39
  divide_user23_variant_64            0.53      1.37
       divide_chrisdodd_32            1.16      3.00
       divide_chrisdodd_64            1.16      3.00
           divide_chris_32            4.34     11.23
           divide_chris_64            4.34     11.24
         divide_weather_32            1.35      3.50
         divide_weather_64            1.35      3.50
           divide_plusq_32            0.10      0.26
           divide_plusq_64            0.39      1.00
           divide_dummy_32            0.08      0.20
           divide_dummy_64            0.39      1.00


==============================
Bench: Invariant Q
==============================
                  Function         ns/call    cycles
                stoke32_32            0.48      1.25
            divide_chux_32            0.15      0.39
            divide_chux_64            0.48      1.25
          divide_user23_32            0.17      0.43
          divide_user23_64            0.58      1.50
  divide_user23_variant_32            0.15      0.38
  divide_user23_variant_64            0.48      1.25
       divide_chrisdodd_32            1.16      3.00
       divide_chrisdodd_64            1.16      3.00
           divide_chris_32            4.35     11.26
           divide_chris_64            4.36     11.28
         divide_weather_32            5.79     14.99
         divide_weather_64           17.00     44.02
           divide_plusq_32            0.12      0.31
           divide_plusq_64            0.48      1.25
           divide_dummy_32            0.09      0.23
           divide_dummy_64            0.09      0.23


==============================
Bench: Variable Q
==============================
                  Function         ns/call    cycles
                stoke32_32            1.16      3.00
            divide_chux_32            1.36      3.51
            divide_chux_64            1.35      3.50
          divide_user23_32            1.54      4.00
          divide_user23_64            1.54      4.00
  divide_user23_variant_32            1.36      3.51
  divide_user23_variant_64            1.55      4.01
       divide_chrisdodd_32            1.16      3.00
       divide_chrisdodd_64            1.16      3.00
           divide_chris_32            4.02     10.41
           divide_chris_64            3.84      9.95
         divide_weather_32            5.40     13.98
         divide_weather_64           19.04     49.30
           divide_plusq_32            1.03      2.66
           divide_plusq_64            1.03      2.68
           divide_dummy_32            0.63      1.63
           divide_dummy_64            0.66      1.71

a至少通过指定无符号，我们可以避免与C和C++中带符号整数的右移行为有关的整个蠕虫病毒。

0当然，这种表示法实际上在C中无效，因为 /会截断结果，因此 ceiling什么也不做。因此，请考虑使用伪符号而不是直接C。

1我也对所有类型都是 uint32_t而不是 uint64_t的解决方案感兴趣。

2通常，由于溢出， p引起问题的任何 q和 p + q >= 2^64。

3也就是说，该函数应该处于循环中，因为只有在相当紧密的循环中调用的微观函数的性能才需要打半个周期才真正重要。

4这有点简化-只有红利 p依赖于先前迭代的输出，因此与 q处理有关的一些工作仍然可以重叠。

5但是，请谨慎使用此类估计-开销不是简单的累加。如果开销显示为4个周期，并且某个函数 f占用5，则由于执行方式重叠，很难说 f中的实际工作成本为 5 - 4 == 1。

Answer 1

这个答案是关于asm的理想选择。我们想要说服编译器为我们提供的内容。 (除了作为对编译器输出进行基准测试时的比较点，我不建议实际使用嵌入式asm。https://gcc.gnu.org/wiki/DontUseInlineAsm)。

我确实设法从纯C中获得了很好的asm输出，用于ceil_div_andmask，请参见下文。 (在Broadwell / Skylake上比CMOV差，但在Haswell上可能不错。不过，两种情况下的user23 / chux版本看起来都更好。)作为我得到编译器的少数几种情况之一，值得一提发出我想要的asm。

克里斯·多德(Chris Dodd)的return ((p-1) >> lg(q)) + 1带有d = 0特殊情况处理的一般想法是最好的选择之一。即它在asm中的最佳实现很难与其他任何事物的最佳实现相抗衡。 Chux的(p >> lg(q)) + (bool)(p & (q-1))也具有优势(例如从p-> result降低了等待时间)，并且当相同的q用于多个除法时，CSE也更多。有关gcc对其进行的延迟/吞吐量分析，请参见下文。

如果将相同的e = lg(q)重复用于多个除数，或者将相同的除息用于多个除数，则不同的实现可以对表达式的CSE进行更多处理。 它们还可以使用AVX2 有效地矢量化。

Branches are cheap and very efficient if they predict very well，因此如果几乎从未使用过d==0，则最好分支。如果d==0并不罕见，那么无分支的asm平均将表现更好。理想情况下，我们可以用C编写一些东西，使gcc在配置文件引导的优化过程中做出正确的选择，并在两种情况下都编译为良好的汇编。

由于最好的无分支asm实现与分支实现相比不会增加太多延迟，因此除非分支可能在99％的时间内都以相同的方式运行，否则无分支可能是可行的方法。这可能会在p==0上分支，但可能会不太可能在p & (q-1)上分支。

很难指导gcc5.4发出最佳的信号。 This is my work-in-progress on Godbolt)。

我认为针对该算法的Skylake的最佳序列如下。 (显示为AMD64 SysV ABI的独立功能，但在假设编译器将发出内联到循环中的类似内容且未附加RET的情况下讨论吞吐量/延迟)。

从计算d-1到检测d == 0 进行分支，而不是单独的测试和分支。很好地减少了uop计数，特别是在SnB系列上，其中JC可以与SUB进行宏融合。

ceil_div_pjc_branch:
 xor    eax,eax          ; can take this uop off the fast path by adding a separate xor-and-return block, but in reality we want to inline something like this.
 sub    rdi, 1
 jc    .d_was_zero       ; fuses with the sub on SnB-family
 tzcnt  rax, rsi         ; tzcnt rsi,rsi also avoids any false-dep problems, but this illustrates that the q input can be read-only.
 shrx   rax, rdi, rax
 inc    rax
.d_was_zero:
 ret

融合域uops:5(不计算ret)，其中一个是异或零(无执行单元)

HSW / SKL延迟与成功的分支预测:

(d == 0):对d或q没有数据依赖性，破坏了dep链。 (控制对d的依赖以检测错误的预测并退出分支)。

(d!= 0):q->结果:tzcnt + shrx + inc = 5c

(d!= 0): d->结果:sub + shrx + inc = 3c

吞吐量:可能只是uop吞吐量瓶颈

我已经尝试过，但是未能使gcc从减法分支到CF上，但是它总是想做一个单独的比较。我知道gcc可以在减去两个变量后被哄骗到CF上分支，但是如果一个是编译时常量，则可能会失败。 (IIRC，这通常会编译为使用无符号vars的CF测试: foo -= bar; if(foo>bar) carry_detected = 1;)

与ADC / SBB无分支，用于处理d==0情况。零处理仅向关键路径添加一条指令(与d == 0且无特殊处理的版本相比)，但还会将另一条指令从INC转换为 sbb rax, -1，以使CF撤消 -= -1。在Broadwell之前，使用CMOV较为便宜，但需要额外的说明进行设置。

ceil_div_pjc_asm_adc:
 tzcnt  rsi, rsi
 sub    rdi, 1
 adc    rdi, 0          ; d? d-1 : d.  Sets CF=CF
 shrx   rax, rdi, rsi
 sbb    rax, -1         ; result++ if d was non-zero
 ret    

融合域uops:SKL上为5(不计算ret)。 HSW上的7

SKL延迟:

q->结果:tzcnt + shrx + sbb = 5c

d->结果:sub + adc + shrx(q上的起点从此处开始)+ sbb = 4c

吞吐量:TZCNT在p1上运行。 SBB，ADC和SHRX仅在p06上运行。因此，我认为我们在每次迭代p06的3 uops上遇到瓶颈，因此最好以的速度运行，每1.5c 进行一次迭代。

如果q和d同时准备就绪，请注意，此版本可以与TZCNT的3c延迟并行运行SUB / ADC。如果两者都来自同一条高速缓存未命中的高速缓存行，那肯定是可能的。无论如何，在d-> result依赖链中尽可能晚在q上引入dep是一个优势。

用gcc5.4从C那里获得这个似乎不太可能。随身携带是有一个内在的，但是gcc却使它一团糟。它不对ADC或SBB使用立即数操作数，而是将进位值存储在每个操作之间的整数reg中。 gcc7，clang3.9和icc17都由此产生了可怕的代码。

#include <x86intrin.h>
// compiles to completely horrible code, putting the flags into integer regs between ops.
T ceil_div_adc(T d, T q) {
  T e = lg(q);
  unsigned long long dm1;  // unsigned __int64
  unsigned char CF = _addcarry_u64(0, d, -1, &dm1);
  CF = _addcarry_u64(CF, 0, dm1, &dm1);
  T shifted = dm1 >> e;
  _subborrow_u64(CF, shifted, -1, &dm1);
  return dm1;
}
    # gcc5.4 -O3 -march=haswell
    mov     rax, -1
    tzcnt   rsi, rsi
    add     rdi, rax
    setc    cl
    xor     edx, edx
    add     cl, -1
    adc     rdi, rdx
    setc    dl
    shrx    rdi, rdi, rsi
    add     dl, -1
    sbb     rax, rdi
    ret

CMOV修复整个结果:q-> result的延迟更差，因为它在d-> result dep链中使用得更快。

ceil_div_pjc_asm_cmov:
 tzcnt  rsi, rsi
 sub    rdi, 1
 shrx   rax, rdi, rsi
 lea    rax, [rax+1]     ; inc preserving flags
 cmovc  rax, zeroed_register
 ret    

融合域uops:SKL上为5(不计算ret)。 HSW上的6

SKL延迟:

q->结果:tzcnt + shrx + lea + cmov = 6c(比ADC / SBB差1c)

d->结果:sub + shrx(q上的de从这里开始)+ lea + cmov = 4c

吞吐量:TZCNT在p1上运行。 LEA是p15。 CMOV和SHRX为p06。 SUB是p0156。理论上仅瓶颈在融合域uop吞吐量上，因此每1.25c 迭代一次。由于有许多独立的操作，因此从SUB或LEA窃取p1或p06引起的资源冲突不应该是吞吐量问题，因为每1.25c迭代1次，没有端口被只能在该端口上运行的uops所饱和。

CMOV为SUB获得操作数:我希望能找到一种方法来为后面的指令创建一个操作数，该指令在需要时会产生零，而无需依赖q，e或SHRX结果。如果 d在 q之前或同时准备就绪，这将有所帮助。

这没有实现该目标，因此在循环中需要额外的7字节 mov rdx,-1。

ceil_div_pjc_asm_cmov:
 tzcnt  rsi, rsi
 mov    rdx, -1
 sub    rdi, 1
 shrx   rax, rdi, rsi
 cmovnc rdx, rax
 sub    rax, rdx       ; res += d ? 1 : -res
 ret    

适用于具有昂贵CMOV 的BDW前CPU的低延迟版本，使用SETCC为AND创建掩码。

ceil_div_pjc_asm_setcc:
 xor    edx, edx        ; needed every iteration

 tzcnt  rsi, rsi
 sub    rdi, 1

 setc   dl              ; d!=0 ?  0 : 1
 dec    rdx             ; d!=0 ? -1 : 0   // AND-mask

 shrx   rax, rdi, rsi
 inc    rax
 and    rax, rdx        ; zero the bogus result if d was initially 0
 ret    

d->结果仍为 4c延迟(q->结果为6)，因为SETC / DEC与SHRX / INC并行发生。总uop计数:8.这些insn中的大多数可以在任何端口上运行，因此应每2个时钟1个iter。

当然，对于HSW之前的版本，您还需要替换SHRX。

我们可以使gcc5.4发出几乎一样好的东西:(仍然使用单独的TEST代替基于sub rdi, 1设置mask，但是其他方法与上述相同)。看到它on Godbolt。

T ceil_div_andmask(T p, T q) {
    T mask = -(T)(p!=0);  // TEST+SETCC+NEG
    T e = lg(q);
    T nonzero_result = ((p-1) >> e) + 1;
    return nonzero_result & mask;
}

当编译器知道p不为零时，它将利用并制作出精美的代码:

// http://stackoverflow.com/questions/40447195/can-i-hint-the-optimizer-by-giving-the-range-of-an-integer
#if defined(__GNUC__) && !defined(__INTEL_COMPILER)
#define assume(x) do{if(!(x)) __builtin_unreachable();}while(0)
#else
#define assume(x) (void)(x) // still evaluate it once, for side effects in case anyone is insane enough to put any inside an assume()
#endif

T ceil_div_andmask_nonzerop(T p, T q) {
  assume(p!=0);
  return ceil_div_andmask(p, q);
}
    # gcc5.4 -O3 -march=haswell
    xor     eax, eax             # gcc7 does tzcnt in-place instead of wasting an insn on this
    sub     rdi, 1
    tzcnt   rax, rsi
    shrx    rax, rdi, rax
    add     rax, 1
    ret

Chux / user23_variant

从p->结果仅获得3c的延迟，并且常数q可以使CSE发挥很大作用。

T divide_A_chux(T p, T q) {
  bool round_up = p & (q-1);  // compiles differently from user23_variant with clang: AND instead of 
  return (p >> lg(q)) + round_up;
}

    xor     eax, eax           # in-place tzcnt would save this
    xor     edx, edx           # target for setcc
    tzcnt   rax, rsi
    sub     rsi, 1
    test    rsi, rdi
    shrx    rdi, rdi, rax
    setne   dl
    lea     rax, [rdx+rdi]
    ret

在TZCNT之前执行SETCC将允许就位TZCNT，保存xor eax,eax。我还没有研究过如何在循环中内联。

融合域uops:HSW / SKL上的8(不计算ret)

HSW / SKL延迟:

q->结果:(tzcnt + shrx(p)| sub + test(p)+ setne)+ lea(或加)= 5c

d->结果:test(q的起始位置从此处开始)+ setne + lea = 3c 。 (shrx-> lea链较短，因此不是关键路径)

吞吐量:可能只是前端瓶颈，每2c 一个迭代。保存xor eax,eax可以使每1.75c的速度提高一倍(但当然，任何循环开销都将成为瓶颈的一部分，因为前端瓶颈就是这样)。