performance - 保存左移(SHL)中偏移的位

Question

请考虑以下英特尔8086汇编程序：

CX保持非零值。

L: ADD AX, AX
   ADC DX, 0
   LOOP L

我被要求理解上面的代码并重写它以提高效率。
据我了解：


它将2 ^ CX * AX的值保存到AX中
计算进位标志在该过程中被设置为1的次数，并将其保存在DX中。


假设这是正确的，我认为更好的代码会将SHL的值转换为AX，CX倍。
SHL AX, CX
但是，我想不出一种在过程中求和进位的方法。 （或计算原始AX的CX最高有效位中的“ 1”位数。）

任何指导和协助都将不胜感激。

Answer 1

您对当前代码的工作方式的理解基本上是正确的。为了确保我们理解它，让我们逐步执行一个示例执行。通常，这种事情可以通过调试器来完成，但是我们真正需要的只是我们的头部和一个可以显示二进制值的计算器。

假设AX为55312（选择较大的初始值可使我们立即看到进位的影响）。 CX将为4，当然DX已预先清零。


迭代1：55312 + 55312溢出16位值的范围，因此将进位设置为1，现在AX为45088。由于设置了进位，因此DX =1。CX减为3。
迭代2：45088 + 45088再次溢出，因此进位被设置，并且AX现在为24640。
DX = 2; CX = 2。
迭代3：24640 + 24640不会溢出，因此未设置进位，因此AX现在为49280。
DX = 2; CX = 1。
迭代4：49280 + 4928溢出，因此进位被设置，并且AX现在为33024。
DX = 3; CX = 0。


因此，当我们完成时，DX为3。如果我们看一下起始值的二进制表示形式：

1101 1000  0001 0000
↑                  ↑
bit 15             bit 0

您可以看到对直觉的确认：此值的高4位（ CX）中的置位（1）位的数目为3，等于 DX。

这些类型的位级别观察会导致聪明的，位混乱的技巧，这是大多数优化突破的关键，并且您已经通过思考您实际执行的代码来发现这一点，这非常好。

收集我们的想法，让我们明确地写出算法，假定 AX是输入值，而 CX包含迭代次数：


隔离 CX中的高位 AX位，丢弃其余部分。
计算 AX中的设置位数。


如果我们针对的是现代处理器（英特尔Nehalem，AMD Barcelona和更新的处理器），那么使用 SHR右移，然后使用 POPCNT指令对所需位数中的设置位数进行计数就很简单了。范围。例如：

; AX == input value
; CX == number of iterations

neg    cx
add    cx, 16     ; cx = 16 - cx

shr    ax, cl     ; ax = ax << cx

popcnt ax, ax     ; ax = # of 1 bits in ax

这将很快。没有分支/循环；只需4条简单说明。您只需要查看执行周期中的少数几个周期，就不会出现分支预测错误的可能性。

但是，如果您将目标定位为不存在 POPCNT指令的较旧的CPU，该怎么办？好吧，您需要模拟它。有多种快速方法可以实现人口计数/汉明权重算法。在奔腾或更高版本上，最快的方法是：

; AX == input value
; CX == number of iterations

neg  cx
add  cx, 16     ; cx = 16 - cx

shr  ax, cl     ; ax = ax << cx

; emulate popcnt
mov  dx, ax
shr  dx, 1
and  dx, 21845
sub  ax, dx
mov  cx, ax
and  ax, 13107
shr  cx, 2
and  cx, 13107
add  cx, ax
mov  dx, cx
shr  dx, 4
add  dx, cx
and  dx, 3855
mov  ax, dx
shr  ax, 8
add  ax, dx
and  ax, 63

这是 this method的16位适应，它使用一系列移位，加法和掩码来并行化位计数。这些都是简单的指令，它仍然是无分支的，因此在大多数处理器上都相当快，但是8088/8086却没有！在那些古老的恐龙上，即使是像这样的简单指令，也要花费多个周期才能执行，而且更糟糕的是，它们都必须被解码，因此缓慢的内存访问速度往往会使事情变慢。如果您确实要针对8088/8086进行优化，则需要使用查找表来实现填充计数算法。而且，在这些处理器上，经常被遗忘的1字节 XLAT指令是迄今为止在表中查找值的最快方法：

LUT DB   0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8

; AX == input value
; CX == number of iterations

neg  cx
add  cx, 16            ; cx = 16 - cx

shr  ax, cl            ; ax = ax << cx

; emulate popcnt using LUT
mov  bx, OFFSET LUT
xlat                   ; equivalent to: mov al, [bx + al]
xchg al, ah
xlat                   ; equivalent to: mov al, [bx + al]
add  al, ah
xor  ah, ah

这将花费256个字节来将查找表（LUT）存储在代码中，但是8088/8086的执行速度肯定比执行所有该算法要快。我们可以通过计算周期来近似估计执行速度：

neg  cx               ; 3         cycles
add  cx, 16           ; 4         cycles
shr  ax, cl           ; 8+(4*CL)  cycles
mov  bx, OFFSET LUT   ; 4         cycles
xlat                  ; 11        cycles
xchg al, ah           ; 4         cycles
xlat                  ; 11        cycles
add  al, ah           ; 3         cycles
xor  ah, ah           ; 3         cycles
                      ;-----------------
                      ; 51+(4*CL) cycles

请注意，这里的慢指令是右移。它需要固定的8个周期，每个移位的位（即移位计数，在 CL中）还要加上4个额外的周期。不幸的是，我们对此无能为力。这意味着我们的最佳情况性能约为50个周期，最坏情况的性能仍低于120个周期。

将其与原始代码进行比较：

   xor  dx, dx        ; 3 cycles
L: add  ax, ax        ; 3 cycles
   adc  dx, 0         ; 4 cycles
   loop L             ; taken: 17 cycles; not-taken: 5 cycles
                      ;---------------------------------------
                      ; 8+(24*CL) cycles

在此，大约的循环数取决于 CX（循环计数），因为它确定分支被采用的次数。因此，在最佳情况下，此代码大约需要32个周期。在最坏的情况下，大约需要400个周期。

我想重申一下，即使在像8086这样的简单芯片上，周期计数也不是精确的，但它确实为我们提供了一种评估性能的合理方法。您的原始代码确实具有更好的最佳情况性能（在 CX很小的情况下），但是我们基于LUT的经过优化的，基于位计数的方法具有更好的最坏情况性能，更重要的是，它可以扩展更好。您可以通过以下两种方法的图形比较清楚地看到这一点：



只要 CX小，您的原始代码就是一个合理的实现。但是随着 CX的增大，由于所有这些 LOOP，例程变得越来越慢。我们基于LUT的方法具有更大的开销（这还没有算上LUT加到二进制文件中的膨胀），但是随着 CX的变大，它才真正开始得到回报。总之，我们已经将增加的代码大小用于执行速度，这是常见的优化折衷方案。

现在，我需要清洁一下。我一直秘密地假设 CX永远不会大于16。如果 CX大于16，我一直向您展示的所有“优化”代码都将无法工作，因为 SHR指令将尝试移出太多位。如果需要处理 CX> 16，则需要调整代码，以将 CX限制为小于或等于16。这意味着有条件分支或一系列巧妙的位-旋转指令，这两种指令都会增加代码的复杂性并增加其周期数。换句话说，这将增加“优化”方法的基准开销，但是此方法将比原始方法继续更好地扩展。图形上，红线将向上平移。

（您的原始代码不需要进行任何修改，它可以处理高达65,535的 CX值，而不会产生任何额外的损失，因为它只会保持 LOOP。但是，正如我们已经看到的那样，每一个都会付出重大的性能损失。这些 LOOP中的一个。）

经过“调整”的代码如下所示：

    LUT DB   0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8

    ; AX == input value
    ; CX == number of iterations

    mov  bx, 16                          ; 4 cycles
    cmp  cx, bx        ; cx < 16?        ; 3 cycles
    jae  SkipShift                       ; 4 cycles (fall-through); 16 cycles (branch)
    sub  bx, cx                          ; 3 cycles
    mov  cx, bx        ; cx  -= 16       ; 2 cycles
    shr  ax, cl        ; ax <<= cx       ; 8+(4*CL) cycles
SkipShift:
    mov  bx, OFFSET LUT                  ; 4 cycles
    xlat                                 ; 11 cycles
    xchg al, ah                          ; 4 cycles
    xlat                                 ; 11 cycles
    add  al, ah                          ; 3 cycles
    xor  ah, ah                          ; 3 cycles

如果采用此 JAE，您将要支付16个周期的罚款，但是在这种情况下，我们可以跳过减法和平移，以弥补那些丢失的周期。如果不采用 JAE，并且执行失败，那么我们只会丢失4个周期。总体而言，最佳情况下的性能约为60个周期，而最坏情况下的性能约为慢速的两倍。