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() 为例程计时。

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

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 秒(即稍微快一点)。