x86 32位程序集中快速排序的优化
我正在尝试学习一些基本的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()对例程进行计时。
编辑性能上的差异不再是纠正了我的同事堆栈花指出的错误之后的问题。
回答 2
Stack Overflow用户
发布于 2015-10-03 14:59:09
在程序集排序实现中有一个错误，在解决它之前，速度比较是无用的。问题在于递归调用：
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秒(即稍快)。
Stack Overflow用户
发布于 2015-10-03 13:27:48
您可以使用一个额外的寄存器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
rethttps://stackoverflow.com/questions/32916387
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号