寻求改进确定排序数组中位数的过程
Looking for improvement to a procedure to determine a sorted array's median
函数参数为排序后的数组和数组的长度。目标是确定奇数或偶数长度数组的中位数。
奇数长度数组简单地通过确定确切的中间元素来处理，偶数长度数组通过获取 "straddle" 中点的两个元素并取它们的平均值来处理。
问题是：（在 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
顺便说一句，您的代码实际上不起作用：mov ebx, 2 破坏了 ebx，但您没有 save/restore 它。因此，您已经踏上了在所有常用 ABI/调用约定中保留调用的寄存器。请参阅 x86 标签 wiki。
另外，我认为 ret 12 应该是 ret 8，因为你需要两个 4 字节的参数。 （见下文）。
这里有一个有趣的想法：通过始终添加两个元素来实现无分支。对于奇数长度数组，它是相同的两个元素。对于偶数长度的数组，就是中间向下舍入和中间向上舍入。
如果您的代码实际上重复具有相同的数组长度，那么分支会很好地预测，条件分支可能会更好（在 test ecx, 1 / jnz odd 或 jc轮班后）。特别是如果奇数长度是常见的情况。 有时候无条件地做某事是值得的，即使并不总是需要。
; 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 很特别。 add-with-carry 和 sub-with-borrow 使用它（我在这里利用它），循环进位指令也是如此。 adc reg, 0 更常见，但我需要倒数，并想出了 sbb reg, -1 根据 CF 添加 0 或 1。
你确定ret 12是对的吗？您的 2 个参数只有 8 个字节。 ret imm16 在 弹出 return 地址后将立即数添加到 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 编译器获得的结果，但某些编译器可能不够智能，无法按照移位设置在 CF 上分支。不过，无论哪种方式我都不会感到惊讶。我想我已经在 shifts 设置的标志上看到了 gcc 或 clang 分支。
; 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，但这意味着第一次加载必须在分支之后进行。 （如果没有尾部重复（单独的 rets），我们需要在某处无条件分支来实现 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
函数参数为排序后的数组和数组的长度。目标是确定奇数或偶数长度数组的中位数。
奇数长度数组简单地通过确定确切的中间元素来处理，偶数长度数组通过获取 "straddle" 中点的两个元素并取它们的平均值来处理。
问题是：（在 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
顺便说一句，您的代码实际上不起作用：mov ebx, 2 破坏了 ebx，但您没有 save/restore 它。因此，您已经踏上了在所有常用 ABI/调用约定中保留调用的寄存器。请参阅 x86 标签 wiki。
另外，我认为 ret 12 应该是 ret 8，因为你需要两个 4 字节的参数。 （见下文）。
这里有一个有趣的想法：通过始终添加两个元素来实现无分支。对于奇数长度数组，它是相同的两个元素。对于偶数长度的数组，就是中间向下舍入和中间向上舍入。
如果您的代码实际上重复具有相同的数组长度，那么分支会很好地预测，条件分支可能会更好（在 test ecx, 1 / jnz odd 或 jc轮班后）。特别是如果奇数长度是常见的情况。 有时候无条件地做某事是值得的，即使并不总是需要。
; 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 很特别。 add-with-carry 和 sub-with-borrow 使用它（我在这里利用它），循环进位指令也是如此。 adc reg, 0 更常见，但我需要倒数，并想出了 sbb reg, -1 根据 CF 添加 0 或 1。
你确定ret 12是对的吗？您的 2 个参数只有 8 个字节。 ret imm16 在 弹出 return 地址后将立即数添加到 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 编译器获得的结果，但某些编译器可能不够智能，无法按照移位设置在 CF 上分支。不过，无论哪种方式我都不会感到惊讶。我想我已经在 shifts 设置的标志上看到了 gcc 或 clang 分支。
; 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，但这意味着第一次加载必须在分支之后进行。 （如果没有尾部重复（单独的 rets），我们需要在某处无条件分支来实现 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