假设您要查找value1在排序数组中的第一个匹配项。对于小型数组（二进制搜索之类的方法不起作用），您可以通过简单地计算小于该值的值的数量来实现此目的：结果就是您要使用的索引。
在x86中，您可以使用adc（带进位添加）来实现该方法的有效的free-free2实现（起始指针在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条简单指令（有时会合并负载）。 Which Intel microarchitecture introduced the ADC reg,0 single-uop special case?但是，这仅适用于无符号比较，其中进位标志保存比较的结果。是否有任何等效的计数签名比较有效序列？不幸的是，似乎没有“如果小于则加1”的指令：
adc，sbb和进位标志在这方面是特殊的。我对元素没有特定顺序的一般情况感兴趣，并且在这种情况下，如果排序假设导致数组更简单或更快速地实现，则在这种情况下对数组进行排序。
1或者，如果该值不存在，则使用第一个更大的值。即，这就是所谓的“下限”搜索。
2无分支方法每次都必须执行相同的工作量-在这种情况下，要检查整个数组，因此这种方法仅在数组较小时才有意义，因此相对于总搜索时间而言，分支错误预测的成本较高。
最佳答案
PCMPGT + PADDD或PSUBD对于大多数CPU来说可能是一个不错的主意，即使是小尺寸的CPU，也可能需要简单的标量清理。甚至使用movd负载只是纯标量，请参见下文。
对于标量整数，避免使用XMM规则，请使用SETCC从所需的任何标志条件创建0/1整数。如果您想使用32位或64位ADD指令而不是仅使用8位，则将tmp寄存器（可能在循环外部）或SETCC减至零（低至8）。cmp / adc reg,0基本上是针对b low / c arry-set条件的窥孔优化。 AFAIK，对于有符号比较的条件，没有什么比这更有效的了。 cmp / setcc / add的最佳速度为3微秒，而cmp / adc的最佳速度为2微秒。因此展开以隐藏循环开销显得尤为重要。
有关如何有效地对SETCC r/m8进行零扩展而不引起部分寄存器停顿的更多详细信息，请参见What is the best way to set a register to zero in x86 assembly: xor, mov or and?的底部。并请参见Why doesn't GCC use partial registers?来提醒整个uarches中的部分注册行为。
是的，CF在很多方面都很特殊。它是唯一具有置位/清除/补码（stc / clc / cmc）指令的条件标志1。 bt / bts / etc是有原因的。指令设置CF，然后将移位指令移入CF。是的，与其他标志不同，ADC / SBB可以将其直接添加/订阅到另一个寄存器中。
OF可以用ADOX进行类似的读取（Intel自Broadwell以来为AMD，Ryzen为AMD以来），但这仍然无济于事，因为它严格是OF，而不是SF！= OF小于符号的条件。
这对于大多数ISA来说都是典型的，而不仅仅是x86。 （AVR和其他一些设备可以设置/清除任何条件标志，因为它们具有an instruction that takes an immediate bit-position in the status register。但是它们仍然只有ADC / SBB可以直接将进位标志添加到整数寄存器。）
ARM 32位可以使用任何条件代码（包括带符号小于号）来执行谓词addlt r0, r0, #1，而不是使用带立即数0的带进位加法。ARM确实具有ADC-immediate，您可以在此处将其用作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系列进行调整，则最好增加一个指针并减少大小计数器。尽管这确实为RS尺寸效果节省了后端（未融合域）信息。
实际上，您希望以指针增量展开。
您提到的大小从0到32，所以如果RSI = 0，我们需要跳过循环。您问题中的代码只是一个do{}while，不会执行此操作。 NEG根据结果设置标志，因此我们可以对此进行JZ。您希望它可以进行宏融合，因为NEG就像从0开始的SUB，但是根据Agner Fog的说法，它不在SnB / IvB上。如果您确实需要处理size = 0，那么这将使我们在启动时付出另一笔麻烦。
使用整数寄存器
实现integer += (a < b)或任何其他标志条件的标准方法是编译器的工作（Godbolt）：
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 edx,dl，这会将MOVZX置于关键路径上。这对延迟不利，并且当Intel CPU对两个操作数使用相同寄存器时，移动消除在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 uops）：
;; 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而不是2。SETCC是单个uop，因此这是循环内的5个融合域uops。在Sandybridge / IvyBridge上，情况要糟得多，在以后的SnB系列中，每个时钟的运行速度仍然低于1。 （一些旧的CPU的setcc速度很慢，例如奔腾4，但是在我们仍然关心的所有事情上它都是高效的。）
展开时，如果希望每个时钟运行速度快于1个
cmp，则有两个选择：为每个setcc目标使用单独的寄存器，为错误的依赖关系创建多个dep链，或在内部使用一个xor edx,edx循环将循环携带的错误依赖项分解为多个短的dep链，这些短的dep链仅耦合附近负载的setcc结果（可能来自同一缓存行）。您还需要多个累加器，因为add延迟为1c。显然，您将需要使用指针增量，以便
cmp [rdi], edx可以在非索引寻址模式下进行微熔，否则cmp / setcc / add总共为4 ups，这就是Intel CPU上的流水线宽度。调用者在写入AL之后，即使在P6系列上，也不会因EAX读取而导致部分寄存器停顿，因为我们先对其进行了异或归零。 Sandybridge不会将其与RAX分开重命名，因为
add al,dl是读-修改-写操作，并且IvB和更高版本永远不会将RAL与RAX分开重命名（仅AH / BH / CH / DH）。除P6 / SnB系列以外的CPU根本不执行部分寄存器重命名，仅执行部分标志。对于在循环内读取EDX的版本也是如此。但是，使用push / pop来保存/恢复RDX的中断处理程序将破坏其Xor归零状态，从而导致P6系列上的每次迭代都导致部分寄存器停顿。这是灾难性的糟糕，因此这是编译器从不进行异或归零的原因之一。他们通常不知道循环是否会长时间运行，也不会冒险。用手，您可能想对每个展开的循环主体展开一次，并将其异或为零，而不是对每个
cmp / setcc进行一次。您可以将SSE2或MMX用于标量东西
两者都是x86-64上的基准。由于将负载折叠到
cmp中并没有获得任何收益（在SnB系列上），因此最好将标量movd负载使用到XMM寄存器中。 MMX具有较小的代码大小的优势，但完成后需要EMMS。它还允许未对齐的内存操作数，因此对于更简单的自动矢量化来说可能很有意思。在AVX512之前，我们只能进行大于可用的比较，因此需要额外的
movdqa xmm,xmm指令来执行key > arr[i]而不会破坏键，而不是arr[i] > key。 （这是gcc和clang在自动向量化时所做的事情）。对于
vpcmpgtd xmm0, xmm1, [rdi]执行key > arr[i]而言，AVX会很好，例如将gcc和clang与AVX一起使用。但这是一个128位负载，我们希望保持其简单和标量。我们可以递减
key并使用(arr[i]<key) = (arr[i] <= key-1) = !(arr[i] > key-1)。我们可以计算数组大于key-1的元素，然后从大小中减去它。因此，我们可以仅使用SSE2进行操作，而无需花费额外的说明。如果
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个融合域域，因此每个时钟可以发出1个。
movd加载使用常规加载端口，并且至少有两个矢量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。）
在Bulldozer系列上，一对整数内核共享一个SIMD单元，因此坚持使用整数寄存器可能会带来更大的优势。这也是为什么int XMM
movd / movq具有更高的延迟，再次损害了该版本的原因。其他技巧：
PowerPC64的Clang（包含在Godbolt链接中）向我们展示了一个巧妙的技巧：将零或符号扩展到64位，相减，然后获取结果的MSB，作为添加到
counter的0/1整数。 PowerPC具有出色的位域指令，包括rldicl。在这种情况下，它被用于向左旋转1，然后将其上的所有位归零，即将MSB提取到另一个寄存器的底部。 （请注意，PowerPC文档对MSB = 0，LSB = 63或31的位进行编号。）如果您不禁用自动矢量化，它将使用带有
vcmpgtsw / vsubuwm循环的Altivec，我认为它可以实现您期望的名称。# 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将4放在另一个寄存器中，则可以使用它。 （似乎没有lwau指令。）lwaux可能很慢，或者可能是错过了优化。我使用了-mcpu=power9，因此即使该指令仅适用于POWER，它也应该可用。这个技巧可能会对x86有所帮助，至少对于汇总循环而言。
每次比较以这种方式需要4 oups，不计算循环开销。尽管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 / setl / add也没有。此处的唯一优点是，即使采用索引寻址模式，也只有4 oups。某些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-> rax依赖项是循环传递的。