寻找对确定排序数组中值的过程的改进

Question

函数参数是排序数组和数组的长度。目标是确定奇数或偶数长度数组的中值。

奇数长度数组是通过确定精确的中间元素来处理的，偶数长度数组是通过得到“跨越”中点的两个元素并对它们进行平均处理的。

问题是：(在even_:标签之后)，我必须以您所看到的方式重复地确定跨值的左和右。

在行mov eax, [edi+eax-4]中，我可以使用4的不同倍数来操作它，并获得我想要的任何索引位置值。但是，如果我立即按照mov eax, [edi+eax-4]指令使用mov esi, [edi+eax +/- any multiple of 4]，我总是得到"0“(esi任意选择)。

那么，我这样做是最好的方式，还是说，我在一次访问两个数组元素方面缺乏一些智慧？

GetMedian   PROC
    push ebp
    mov ebp, esp
    mov eax, [ebp+12]           ; eax = length of array.
    mov ebx, 2
    cdq
    div ebx                     ; eax = Length of array/2.
    cmp edx,0
    je even_                    ; Jump to average the straddle.
    mov ebx, TYPE DWORD
    mul ebx                     ; eax now contains our target index.
    mov edi, [ebp+8]
    mov eax, [edi+eax]          ; Access array[eax].
    jmp toTheEnd
even_:
    mov ebx, TYPE DWORD
    mul ebx                     ; eax now contains our target index.
    mov edi, [ebp+8]            ; edi now contains @array[0].
    mov eax, [edi+eax-4]        ; Dereferences array[left] so a value is in eax.
    mov esi, eax                ; save eax (value left of straddle).
    mov eax, [ebp+12]           ; eax = length of array.
    mov ebx, 2
    cdq
    div ebx
    mov ebx, TYPE DWORD
    mul ebx                     ; eax now contains our target index.
    mov edi, [ebp+8]
    mov eax, [edi+eax]          ; Access array[right] (value right of straddle).
    add eax, esi                ; list[eax-1] + list[eax].
    mov ebx, 2
    cdq
    div ebx
toTheEnd:
    pop ebp
    ret 12
GetMedian ENDP

Answer 1

顺便说一句，您的代码实际上不工作：mov ebx, 2 clobbers ebx，但是您没有保存/恢复它。因此，您已经踩到了一个寄存器，它保存在所有通常的ABI/调用约定中。请参阅x86标记wiki。

另外，我认为ret 12应该是ret 8，因为您需要两个4字节的args。(见下文)。

这里有一个有趣的想法:通过总是添加两个元素来实现无分支。对于奇数长度数组，它是相同的两个元素。对于一个等长的数组，它是中间循环和中间循环。

如果代码实际上重复地具有相同的数组长度，那么分支可以很好地预测，条件分支可能会更好(在test ecx, 1 / jnz odd上，或者在shift之后的jc上)。Esp。如果奇数长度是常见情况。有时候，它是值得做一些无条件的事情，即使它并不总是需要的。

; Untested
GetMedian   PROC
    ;; return in eax.  clobbers: ecx, edx (which don't need to be saved/restored)
    mov   ecx, [esp+8]            ; ecx = unsigned len
    mov   edx, [esp+4]            ; edx = int *arr
    shr   ecx                     ; ecx = len/2.  CF = the bit shifted out. 0 means even, 1 means odd

    mov   eax, [edx + ecx*4]      ; eax = arr[len/2]
    sbb   ecx, -1                 ; ecx += 1 - CF.  
    add   eax, [edx + ecx*4]      ; eax += arr[len/2 + len&1]

    shr   eax, 1                  ; eax /= 2  (or sar for arithmetic shift)
    ret 12    ;;; Probably a bug
GetMedian ENDP
;; 5 instructions, plus loading args from the stack, and the ret.

我停止了生成堆栈帧的指令，因为这是一个叶函数，不需要任何本地存储。使用ebp不会使任何事情变得更容易，也无助于回溯，而且也是对指令的浪费。

在大多数情况下，您必须使用setcc来根据标志在寄存器中获得0或1。但CF是特别的。加带进位和分带借使用它(我在这里的优势)，以及旋转贯穿进位指令。它在adc reg, 0中更常见，但我需要逆函数，并根据CF提出了添加0或1的sbb reg, -1。

ret 12 ，你确定是对的吗？您的2个args仅为8个字节。ret imm16在弹出返回地址后将立即添加到esp，因此计数是由于call/ret对而对堆栈指针的全部更改。

另外，我假设添加两个元素不会包装(进位或溢出)，即使它是奇数长度数组的中间元素。

或者，另一种可能更糟糕的无分支方法

; Untested
; using cmov on two loads, instead of sbb to make the 2nd load address dependent on CF
GetMedian   PROC
    mov   ecx, [esp+8]            ; ecx = unsigned len
    mov   edx, [esp+4]            ; edx = int *arr
    shr   ecx, 1                  ; ecx = len/2.  CF = the bit shifted out. 0 means even, 1 means odd

    mov   eax, [edx + ecx*4]      ; eax = arr[len/2]
    mov   edx, [edx + ecx*4 + 4]  ; edx = arr[len/2+1]  (reads past the end if len=0, and potentially touches a different cache line than len/2)
    cmovc edx, eax                ; CF still set from shr.  edx = odd ? arr[len/2] : edx

    add   eax, edx
    shr   eax, 1                  ; eax /= 2  (or sar for arithmetic shift)
    ret 8
GetMedian ENDP

分支实施：

这可能更像从C编译器中获得的结果，但某些编译器可能不够聪明，无法按照shift设置在CF上进行分支。不过，我也不会感到惊讶，我想我已经看到过gcc或嘎嘎的树枝在轮班设置的旗子上。

; Untested
GetMedian   PROC
    ;; return in eax.  clobbers: ecx, edx (which don't need to be saved/restored)
    mov   ecx, [esp+8]            ; ecx = unsigned len
    mov   edx, [esp+4]            ; edx = int *arr
    shr   ecx                     ; ecx = len/2.  CF = the bit shifted out. 0 means even, 1 means odd

    mov   eax, [edx + ecx*4]      ; eax = arr[len/2]

    jc   @@odd   ; conditionally skip the add and shift
    add   eax, [edx + ecx*4 + 4]  ; eax += arr[len/2 + 1]

    shr   eax, 1                  ; eax /= 2  (or sar for arithmetic shift)
@@odd:  ;; MASM local label, doesn't show up in the object file
    ret 8
GetMedian ENDP

另一种选择是：

    jnc   @@even
    ret   8         ; fast-path for the odd case
@@even:  ;; MASM local label, doesn't show up in the object file
    add   eax, [edx + ecx*4 + 4]  ; eax += arr[len/2 + len&1]

    shr   eax, 1                  ; eax /= 2  (or sar for arithmetic shift)
    ret 8   ; duplicate whole epilogue here: any pop or whatever

发挥比例因素，而不是转移：

屏蔽低位len，然后使用arr[len/2] = [edx + (len/2)*4] = [edx + len*2]

这使从len到shr的依赖链缩短了一个shr，但这意味着第一个负载必须在分支之后。(没有尾复制(单独的ret)，我们需要一个无条件的分支来实现if(odd){}else{}结构，而不是更简单的load; if(even){}; ret结构。)

; Untested
GetMedian   PROC
    ;; return in eax.  clobbers: ecx, edx (which don't need to be saved/restored)
    mov   ecx, [esp+8]            ; ecx = unsigned len
    mov   edx, [esp+4]            ; edx = int *arr
    test  ecx, 1
    jz   @@even
    mov   eax, [edx + ecx*2 - 2]  ; odd
    ret   8
@@even:
    mov   eax, [edx + ecx*2]
    add   eax, [edx + ecx*2 + 4]
    shr   eax, 1
    ret 8
GetMedian ENDP