x86 32 位汇编中快速排序的优化

Question

我正在尝试学习一些基本的 x86 32 位汇编编程。因此，在追求这一点时，我决定在汇编中实现快速排序（仅对整数排序）。首先我做了一个C版的排序函数，然后我做了一个汇编版本。

但是，将我的汇编版本与我的 C 版本（在 Debian 上使用 gcc 编译）进行比较时，C 版本在 10000 个整数的数组上的执行速度要快 10 倍。

所以我的问题是，是否有人可以就可以在我的快速排序汇编例程中进行的明显优化提供一些反馈。这纯粹是出于教育目的，我不希望在生成高速代码方面击败编译器制造商，但我很想知道我是否犯了任何明显的阻碍速度的错误。

C 版：

void myqsort(int* elems, int sidx, int eidx)
{

    if (sidx < eidx)
    {
        int pivot = elems[eidx];
        int i = sidx;
        for (int j = sidx; j < eidx; j++)
        {
            if (elems[j] <= pivot)
            {
                swap(&elems[i], &elems[j]);
                i = i + 1;
            }
        }
        swap(&elems[i], &elems[eidx]);
        myqsort(elems, sidx, i - 1);
        myqsort(elems, i + 1, eidx);
    }
}
void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

汇编版本（NASM）：

;
; void asm_quick_sort(int* elems, int startindex, int endindex)
; Params:
;       elems - pointer to elements to sort - [ebp + 0x8]
;       sid - start index of items - [ebp + 0xC]
;       eid - end index of items - [ebp + 0x10]
asm_quick_sort:

    push ebp
    mov ebp, esp

    push edi
    push esi
    push ebx

    mov eax, dword [ebp + 0xC]  ; store start index,  = i
    mov ebx, dword [ebp + 0x10] ; store end index
    mov esi, dword [ebp + 0x8]  ; store pointer to first element in esi

    cmp eax, ebx
    jnl qsort_done

    mov ecx, eax                        ; ecx = j, = sid
    mov edx, dword [esi + (0x4 * ebx)]  ; pivot element, elems[eid], edx = pivot
qsort_part_loop:
    ; for j = sid; j < eid; j++
    cmp ecx, ebx                    ; if ecx < end index
    jnb qsort_end_part
    ; if elems[j] <= pivot
    cmp edx, dword [esi + (0x4*ecx)]
    jb qsort_cont_loop
    ; do swap, elems[i], elems[j]
    push edx ; save pivot for now
    mov edx, dword [esi + (0x4*ecx)]        ; edx = elems[j]
    mov edi, dword [esi + (0x4*eax)]        ; edi = elems[i]
    mov dword [esi + (0x4*eax)], edx        ; elems[i] = elems[j]
    mov dword [esi + (0x4*ecx)], edi        ; elems[j] = elems[i]
    pop edx ; restore pivot
    ; i++
    add eax, 0x1
qsort_cont_loop:
    add ecx, 0x1
    jmp qsort_part_loop
qsort_end_part:
    ; do swap, elems[i], elems[eid]
    mov edx, dword [esi + (0x4*eax)]        ; edx = elems[i]
    mov edi, dword [esi + (0x4*ebx)]        ; edi = elems[eid]
    mov dword [esi + (0x4*ebx)], edx        ; elems[eidx] = elems[i]
    mov dword [esi + (0x4*eax)], edi        ; elems[i] = elems[eidx]

    ; qsort(elems, sid, i - 1)
    ; qsort(elems, i + 1, eid)
    sub eax, 0x1
    push eax
    push dword [ebp + 0xC]  ; push start idx
    push dword [ebp + 0x8]  ; push elems vector
    call asm_quick_sort
    add esp, 0x8
    pop eax
    add eax, 0x1
    push dword [ebp + 0x10] ; push end idx
    push eax
    push dword [ebp + 0x8]  ; push elems vector
    call asm_quick_sort
    add esp, 0xC


qsort_done:
    pop ebx
    pop esi
    pop edi

    mov esp, ebp
    pop ebp

    ret

我从 C 调用汇编例程，并使用 clock() 为例程计时。

编辑在纠正了我的 Whosebugers 同事指出的错误后，性能差异不再是问题。

Answer 1

您可以仅使用 1 个额外的寄存器 EDI 来优化元素交换，而无需在 EDX 中压入和弹出枢轴值：

mov  edi, dword [esi + (0x4*eax)]   ; edi = elems[i]
xchg dword [esi + (0x4*ecx)], edi   ; elems[j] = edi, edi = elems[j]
mov  dword [esi + (0x4*eax)], edi   ; elems[i] = edi

第二个交换也可以缩短：

mov  edi, dword [esi + (0x4*ebx)]   ; edi = elems[eid]
xchg dword [esi + (0x4*eax)], edi   ; elems[i] = edi, edi = elems[i]
mov  dword [esi + (0x4*ebx)], edi   ; elems[eid] = edi

您可以安全地从结尾代码中删除 mov esp, ebp，因为它是多余的。如果这 3 pop 一切顺利，您就已经知道堆栈指针具有正确的值。

qsort_done:
  pop ebx
  pop esi
  pop edi
  mov esp, ebp    <-- This is useless!
  pop ebp
  ret

Answer 2

您的程序集排序实现有一个错误，在您解决它之前，速度比较是无用的。问题是递归调用：

    myqsort(elems, sidx, i - 1);

鉴于 i 不一定是 sidx，这可能会将小于 sidx 的值传递给函数，如果 [=15 则包括 -1 =] 为 0。这是在您的 C 实现中处理的：

if (sidx < eidx)

但是在你的汇编版本中：

cmp eax, ebx
jae qsort_done

那是一条无符号比较分支指令！您应该使用 jge。由于这个问题，我看到了段错误。修复后，根据我的快速测试（使用 -O3 编译），两种实现的性能似乎大致相同。我使用了以下测试驱动程序：

#include <stdlib.h>
#include <stdio.h>

void myqsort(int * elems, int sidx, int eidx);

#define SIZE 100000

int main(int argc, char **argv)
{
    int * elems = malloc(SIZE * sizeof(int));

    for (int j = 0; j < 1000; j++) {

        for (int i = 0; i < SIZE; i++) {
            elems[i] = rand();
        }

        myqsort(elems, 0, SIZE - 1);
    }
    return 0;
}

对于 C 版本，运行-时间约为 5.854 秒。使用汇编版本，它是 5.829 秒（即稍微快一点）。

x86 32 位汇编中快速排序的优化

Optmization for quicksort in x86 32-bit assembly

c

assembly

quicksort