计数数组中“小于x”的元素

Question

假设您希望在排序数组中查找值^{1的第一个匹配项。对于小数组（二进制搜索之类的东西没有回报），您可以通过简单地计算小于该值的值的数量来实现这一点：结果就是您要查找的索引。}

在x86中，您可以使用adc（加进位）来实现该方法的高效无分支²实现（rdi中的起始指针rsi中的长度和要在edx中搜索的值）：

  xor eax, eax
  lea rdi, [rdi + rsi*4]  ; pointer to end of array = base + length
  neg rsi                 ; we loop from -length to zero

loop:
  cmp [rdi + 4 * rsi], edx
  adc rax, 0              ; only a single uop on Sandybridge-family even before BDW
  inc rsi
  jnz loop

答案以rax结束。如果你展开它（或者如果你有一个固定的、已知的输入大小），只有cmp；adc指令对被重复，因此每次比较的开销接近2个简单指令（以及有时融合的负载）。哪种Intel微体系结构引入了ADC reg，0单uop特例？

然而，这仅适用于无符号比较，其中进位标志保存比较结果。有没有等效有效的序列来计算符号比较？不幸的是，似乎没有“如果小于则添加1”指令：adc、sbb，进位标志在这方面是特殊的。

我对元素没有特定顺序的一般情况感兴趣，并且在数组排序的情况下，排序假设导致更简单或更快的实现。

^{1，或者，如果该值不存在，则为第一个较大的值。一、 这就是所谓的“下限”搜索。}

无分支方法每次都必须做相同的工作量——在这种情况下，检查整个阵列，因此这种方法只有在阵列较小且分支预测失误的成本相对于总搜索时间较大时才有意义。




Answer 1

匿名用户

在保证对数组进行排序的情况下，可以使用cmovl带有表示要添加的正确值的“立即”值。cmovl没有立即，因此您必须事先将它们加载到寄存器中。

这种技术在展开时是有意义的，例如：

; load constants
  mov r11, 1
  mov r12, 2
  mov r13, 3
  mov r14, 4

loop:
  xor ecx, ecx
  cmp [rdi +  0], edx
  cmovl rcx, r11
  cmp [rdi +  4], edx
  cmovl rcx, r12
  cmp [rdi +  8], edx
  cmovl rcx, r13
  cmp [rdi + 12], edx
  cmovl rcx, r14
  add rax, rcx
  ; update rdi, test loop condition, etc
  jcc loop

每次比较有2个UOP，加上开销。cmovl指令之间有一个4周期（BDW和更高版本）依赖链，但它没有携带。

一个缺点是必须在循环外设置1,2,3,4常数。如果不展开，它也不能很好地工作（您需要将add rax，rcx累加化）。

Answer 2

有一个技巧可以通过切换顶部将有符号比较转换为无符号比较，反之亦然

bool signedLessThan(int a, int b)
{
    return ((unsigned)a ^ INT_MIN) < b; // or a + 0x80000000U
}

它之所以有效，是因为2补码中的范围仍然是线性的，只是交换了有符号和无符号空间。所以最简单的方法可能是比较前的异或

  xor eax, eax
  xor edx, 0x80000000     ; adjusting the search value
  lea rdi, [rdi + rsi*4]  ; pointer to end of array = base + length
  neg rsi                 ; we loop from -length to zero

loop:
  mov ecx, [rdi + 4 * rsi]
  xor ecx, 0x80000000
  cmp ecx, edx
  adc rax, 0              ; only a single uop on Sandybridge-family even before BDW
  inc rsi
  jnz loop

如果可以修改数组，则只需在检查之前进行转换

在ADX中，有一个ADOX使用从的进位。不幸的是，签名比较也需要SF，而不仅仅是of，因此不能这样使用它

  xor ecx, ecx
loop:
  cmp [rdi + 4 * rsi], edx
  adox rax, rcx            ; rcx=0; ADOX is not available with an immediate operand

并且必须做更多的位操作来纠正结果

Answer 3

PCMPGT PADDD或PSUBD对于大多数CPU来说可能是一个非常好的主意，即使对于小尺寸，可能需要简单的标量清理。或者甚至只是纯粹的标量，使用movd加载，见下文。

对于标量整数，避免使用XMM regs，使用SETCC根据您想要的任何标志条件创建0/1整数。如果要使用32位或64位加法指令而不是仅使用8位，则将tmp寄存器（可能在循环外）异或置零，并将CC设置为该寄存器的低8位。

cmp，0基本上是对arry set条件的窥视孔优化。好了，没有什么比符号比较条件更有效的了。cmp/setcc/add最多3个UOP，而cmp/adc最多2个UOP。因此，展开以隐藏循环开销更为重要。

请参阅x86汇编中将寄存器设置为零的最佳方法的底部部分：xor、mov或and？有关如何有效地零扩展SETCC r/m8但不导致部分寄存器暂停的更多详细信息。看看为什么GCC不使用部分寄存器？用于提醒跨uarches的部分注册行为。

是的，CF在很多方面都很特别。它是唯一一个设置/清除/补码（stc/clc/cmc）指令的条件标志。原因是bt等。指令集CF，并且该移位指令转移到CF中。是的，ADC/SBB可以直接将其添加/细分到另一个寄存器中，这与任何其他标志不同。

可以用ADOX（从Broadwell开始的Intel，从Ryzen开始的AMD）来阅读OF，但这仍然对我们没有帮助，因为它严格来说是OF，而不是SF=签名小于条件的。

这对于大多数ISA来说是典型的，而不仅仅是x86。（AVR和其他一些ISA可以设置/清除任何条件标志，因为它们有一条指令在状态寄存器中占据立即位位置。但它们仍然只有ADC/SBB，用于将进位标志直接添加到整数寄存器。）

ARM 32位可以使用任何条件代码（包括带符号的小于）来执行谓词的addlt r0、r0和#1，而不是带进位的add和立即数0。ARM确实有ADC立即数，您可以在这里将其用于C标志，但不能在Thumb模式下使用（在这种模式下，避免it指令对add进行谓词很有用），因此您需要一个零寄存器。

AArch64可以做一些谓词的事情，包括用任意条件谓词增加cinc。

但是x86不能。我们只有cmovcc和setcc可以将CF==1以外的条件转换为整数。（或者使用ADOX，对于OF==1。）

脚注1：EFLAGS中的一些状态标志，如中断IF（sti/cli）、方向DF（std/cld）和对齐检查（stac/clac）有设置/清除指令，但没有条件标志ZF/SF/OF/PF或BCD携带AF。

cmp[rdi 4*rsi]， edx即使在Haswell/Skylake上也会因为索引寻址模式而取消层压，并且它没有读/写目标寄存器（所以它不像add reg，[mem]。）

如果只针对Sandybridge系列进行调优，那么最好只增加一个指针并减少大小计数器。虽然这确实节省了后端（未使用域）UOP以实现RS尺寸效应。

实际上，您希望使用指针增量展开。

您提到了从0到32的大小，因此如果RSI=0，我们需要跳过循环。您问题中的代码只是一个do{}while，它不这样做。NEG根据结果设置标志，因此我们可以对此进行JZ。您会希望它可以进行宏融合，因为NEG与从0开始的SUB完全一样，但根据Agner Fog的说法，它在SnB/IvB上没有。因此，如果您真的需要处理size=0，那么我们在启动时会再花费一次uop。

实现integer=（a的标准方法

xor    edx,edx            ; can be hoisted out of a short-running loop, but compilers never do that
                          ; but an interrupt-handler will destroy the rdx=dl status
cmp/test/whatever         ; flag-setting code here
setcc  dl                 ; zero-extended to a full register because of earlier xor-zeroing
add    eax, edx

有时编译器（尤其是gcc）将使用setcc dl，这将movzx置于关键路径上。这不利于延迟，当Intel CPU对两个操作数使用（部分）相同寄存器时，mov消除在Intel CPU上不起作用。

对于小型数组，如果您不介意只有一个8位计数器，您可以只使用8位添加，这样您就不必担心循环内的零扩展。

; slower than cmp/adc: 5 uops per iteration so you'll definitely want to unroll.

; requires size<256 or the count will wrap
; use the add eax,edx version if you need to support larger size

count_signed_lt:          ; (int *arr, size_t size, int key)
  xor    eax, eax

  lea    rdi, [rdi + rsi*4]
  neg    rsi              ; we loop from -length to zero
  jz    .return           ; if(-size == 0) return 0;

       ; xor    edx, edx        ; tmp destination for SETCC
.loop:
  cmp    [rdi + 4 * rsi], edx
  setl   dl               ; false dependency on old RDX on CPUs other than P6-family
  add    al, dl
       ; add    eax, edx        ; boolean condition zero-extended into RDX if it was xor-zeroed

  inc    rsi
  jnz    .loop

.return:
  ret

或者，使用CMOV，使循环携带的dep链长2个周期（或在Broadwell之前的Intel上为3个周期，其中CMOV为2个UOP）：

  ;; 3 uops without any partial-register shenanigans, (or 4 because of unlamination)
  ;;  but creates a 2 cycle loop-carried dep chain
  cmp    [rdi + 4 * rsi], edx
  lea    ecx, [rax + 1]        ; tmp = count+1
  cmovl  eax, ecx              ; count = arr[i]<key ? count+1 : count

因此，在最好的情况下（循环展开和指针增量允许cmp到微熔合），每个元素需要3个UOP，而不是2个UOP。

SETCC是一个uop，所以这是循环内的5个融合域uop。在Sandybridge/IvyBridge上情况要糟糕得多，在后来的SnB系列上仍然以低于1个时钟的速度运行。（一些古老的CPU具有缓慢的setcc，例如Pentium 4，但它在我们仍然关心的所有事情上都很有效。）

展开时，如果希望其运行速度超过每个时钟1，则有两种选择：为每个setcc目标使用单独的寄存器，为假相关性创建多个dep链，或使用一个xor edx，循环内的edx将错误依赖性分解为多个短dep链，这些链仅耦合附近负载（可能来自同一缓存线）的setcc结果。您还需要多个累加器，因为延迟为1c。

显然，您需要使用指针增量，以便edx可以与非索引寻址模式微融合，否则cmp/setcc/add总共是4个uops，这是Intel CPU上的管道宽度。

写入AL后读取EAX的调用者不会出现部分寄存器失速，即使在P6系列上也是如此，因为我们先将其异或归零。Sandybridge不会将其与RAX分开重命名，因为add al， dl是一个读取-修改-写入，IvB和更高版本永远不会将AL与RAX分开重命名（只有AH/BH/CH/DH）。P6/SnB系列以外的CPU根本不进行部分寄存器重命名，只有部分标志。

这同样适用于读取循环内EDX的版本。但是，使用push/pop保存/恢复RDX的中断处理程序会破坏其异或零状态，导致P6系列上的每次迭代都会导致部分寄存器暂停。这是灾难性的糟糕，因此这是编译器从不提升异或归零的原因之一。他们通常不知道循环是否会长期运行，也不会承担风险。手动操作时，您可能希望对每个展开的循环体展开一次并异或零，而不是对每个cmp进行一次。

两者都是x86-64上的基线。由于（在SnB系列上）将负载折叠到cmp中得不到任何好处，因此您不妨将标量movd加载到XMM寄存器中。MMX具有较小代码大小的优势，但在完成时需要EMM。它还允许未对齐的内存操作数，因此对于更简单的自动矢量化可能很有趣。

在AVX512之前，我们只有大于可用的比较，因此需要额外的movdqa xmm， xmm指令才能执行键

AVX会很好，因为vpcmpgtd xmm0，xmm1，[rdi]要做的事

我们可以减少key并使用（arr[i]

如果key已经是最负数（因此key-1将换行），那么任何数组元素都不能小于它。如果可能的话，这确实会在循环之前引入分支。

 ; signed version of the function in your question
 ; using the low element of XMM vectors
count_signed_lt:          ; (int *arr, size_t size, int key)
                          ; actually only works for size < 2^32
  dec    edx                 ; key-1
  jo    .key_eq_int_min
  movd   xmm2, edx    ; not broadcast, we only use the low element

  movd   xmm1, esi    ; counter = size, decrement toward zero on elements >= key
      ;;  pxor   xmm1, xmm1   ; counter
      ;;  mov    eax, esi     ; save original size for a later SUB

  lea    rdi, [rdi + rsi*4]
  neg    rsi          ; we loop from -length to zero

.loop:
  movd     xmm0, [rdi + 4 * rsi]
  pcmpgtd  xmm0, xmm2    ; xmm0 = arr[i] gt key-1 = arr[i] >= key = not less-than
  paddd    xmm1, xmm0    ; counter += 0 or -1
    ;;  psubd    xmm1, xmm0    ; -0  or  -(-1)  to count upward

  inc      rsi
  jnz      .loop

  movd   eax, xmm1       ; size - count(elements > key-1)
  ret

.key_eq_int_min:
  xor    eax, eax       ; no array elements are less than the most-negative number
  ret

这应该与您在Intel SnB系列CPU上的循环速度相同，外加一点点额外开销。它有4个保险丝域UOP，因此每个时钟可以发出1个。movd加载使用常规加载端口，并且至少有2个矢量ALU端口可以运行PCMPGTD和PADDD。

哦，但是在IvB/SnB上，宏融合inc/jnz需要端口5，而PCMPGTD/PADDD都只在p1/p5上运行，因此端口5吞吐量将是一个瓶颈。在HSW和更高版本上，分支在端口6上运行，因此后端吞吐量没有问题。

更糟糕的是，在AMD CPU上，内存操作数cmp可以使用索引寻址模式而不受惩罚。（在Intel Silvermont和Core 2/Nehalem上，内存源cmp可以是具有索引寻址模式的单个uop。）

在推土机系列上，一对整数核共享一个SIMD单元，因此坚持整数寄存器可能是一个更大的优势。这也是为什么int

PowerPC64的Clang（包括在Godbolt链接中）为我们展示了一个巧妙的技巧：零或符号扩展到64位，减法，然后获取结果的MSB作为0/1整数，添加到计数器。PowerPC具有出色的位域指令，包括rldicl。在这种情况下，它被用来向左旋转1，然后将其上面的所有位置零，即将MSB提取到另一个寄存器的底部。（请注意，PowerPC文档对位的MSB=0、LSB=63或31进行编号。）

如果不禁用自动矢量化，它会将Altivec与vcmpgtsw一起使用，我假设它与您从名称中期望的一样。

# PowerPC64 clang 9-trunk -O3 -fno-tree-vectorize -fno-unroll-loops -mcpu=power9
# signed int version

# I've added "r" to register names, leaving immediates alone, because clang doesn't have `-mregnames`

 ... setup
.LBB0_2:                  # do {
    lwzu   r5, 4(r6)         # zero-extending load and update the address register with the effective-address.  i.e. pre-increment
    extsw  r5, r5            # sign-extend word (to doubleword)
    sub    r5, r5, r4        # 64-bit subtract
    rldicl r5, r5, 1, 63    # rotate-left doubleword immediate then clear left
    add    r3, r3, r5        # retval += MSB of (int64_t)arr[i] - key
    bdnz .LBB0_2          #  } while(--loop_count);

我认为，如果clang使用了算术（符号扩展）负载，它本可以避免循环内的extsw。唯一更新地址寄存器（保存增量）的lwa似乎是索引形式lwaux RT、RA、RB，但如果clang将其放入另一个寄存器中，则可以使用它。（似乎没有lwau指令。）可能是lwau速度慢，或者可能是错过了优化。我使用了-mcpu=power9，所以即使该指令仅通电，它也应该可用。

这个技巧可能对x86有所帮助，至少对上卷循环是这样。这样每次比较需要4个UOP，不计算循环开销。尽管x86的位字段提取功能相当糟糕，但我们实际上只需要逻辑右移来隔离MSB。

count_signed_lt:          ; (int *arr, size_t size, int key)
  xor     eax, eax
  movsxd  rdx, edx

  lea     rdi, [rdi + rsi*4]
  neg     rsi          ; we loop from -length to zero

.loop:
  movsxd   rcx, dword [rdi + 4 * rsi]   ; 1 uop, pure load
  sub      rcx, rdx                     ; (int64_t)arr[i] - key
  shr      rcx, 63                      ; extract MSB
  add      eax, ecx                     ; count += MSB of (int64_t)arr[i] - key

  inc      rsi
  jnz      .loop

  ret

这没有任何虚假依存关系，但4-uop xor-zero/cmp也没有。这里唯一的优点是，即使使用索引寻址模式，这也是4个UOP。一些AMD CPU可以通过ALU和加载端口运行MOVSXD，但Ryzen的延迟与常规加载相同。

如果迭代次数少于64次，只要吞吐量重要，而不是延迟重要，就可以这样做。（但使用setl可能仍然可以做得更好）

.loop
  movsxd   rcx, dword [rdi + 4 * rsi]   ; 1 uop, pure load
  sub      rcx, rdx                     ; (int64_t)arr[i] - key
  shld     rax, rcx, 1    ; 3 cycle latency

  inc rsi  / jnz .loop

  popcnt   rax, rax                     ; turn the bitmap of compare results into an integer

但是，shld的3个周期延迟使其成为大多数应用中的一个障碍，即使它只是SnB系列上的一个uop。rax-