在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彙編程序和我用時鐘（）進行計時的例程。

編輯 糾正我的同伴stackoverflowers指出的錯誤後，性能的差異不再是問題。

Answer 1

您的程序集排序實現中有錯誤，並且速度比較在解決它之前是無用的。問題是遞歸調用：

myqsort(elems, sidx, i - 1); 

看到它不一定是i不是sidx的情況下，這可能的值小於sidx傳遞給函數，包括-1，如果sidx是0。這是

if (sidx < eidx) 

但在你的程序集的版本：在你的C實現處理

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秒（即稍快）。

Answer 2

可以優化僅使用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 

您可以安全地從您的epilog代碼中刪除mov esp, ebp，因爲它是多餘的。如果這3 pop進展順利，您已經知道堆棧指針具有正確的值。

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