c - 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() 对例程进行计时。

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

Answer 1

您的程序集排序实现中存在错误，在解决该错误之前，速度比较是没有用的。问题是递归调用:

    myqsort(elems, sidx, i - 1);

鉴于 i 不一定不是 sidx，这可能会将小于 sidx 的值传递给函数，如果 sidx 为 0，则包括 -1。这在您的 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 秒(即稍快一些)。