我编写了一个汇编程序QuickSort，发现它比java中的array.sort慢。我想知道是否有人会知道为什么我无法与某些高级语言的速度相提并论(我假设 C 可能也会更快(
我已经测试了 1,000,000 * 1024 字节。我有大约 2 秒的时间来完成排序，而 Java 中的 Array.Sort 将在大约 .8 秒内完成
我认为实际移动数据没有任何问题，因为我已经独立测试过并且移动得非常快。
%macro $copyBytes 3
mov RSI,%1 ; Grab the Src Address
mov RDI,%2 ; Grab the Dst Address
mov rcx,%3 ; Grab the length
%%l:movsb ; Move the data
loop %%l
%endmacro
%imacro $getAddress 2
mov %1,r_Table ; Start of Table to RSI/RDI
mov rax,%2 ; Lower/Upper to RAX
mul r_recordLength ; Multiply by Record Length
add %1,rax ; add offset to RSI/RDI
%endmacro
%define r_recordLength r8
%define r_startPos r10
%define r_noOfBytes r11
%define r_Ubound r15
%define @left r10
%define @right r11
%define @pivotValue r12
%define @prevLeft r13
[section .bss]
d_startPos resq 1
d_noOfBytes resq 1
pivotValue resb 128 ; This gives tha max sortkey size
LeftAddress resq 1
RightAddress resq 1
[section .text]
; Call the recursive SORT
push 0 ; Push the 1st Left
push r_Ubound ; Push the 1st Right
Call _QSort
pop rax
pop rax
;-----------------------------------------------------------------------
; Recursive Sort
;-----------------------------------------------------------------------
_QSort:
mov @left,qword[rsp+16] ; get the Left Index
mov @right,qword[rsp+8] ; get the Right Index
; if left >= right ; Exit when Left is not < Right
cmp @left,@right
jnl .Exit
; pivotValue = RandomNo[ [ left + right / 2 ] ] CALCULATE pivotValue
mov rax,@left ; Grab the left
add rax,@right ; add the right
shr rax,1 ; and divide by 2
$getAddress RSI,rax ; get the address of this slot
$copyBytes RSI,pivotValue,qword[d_noOfBytes] ; and copy it to pivotValue
; prevLeftIdx = [moveThem]
push @left ; preserve the Left index
push @right ; preserve the Right index
call _moveThem ; do the moves
pop @right ; restore the Right index
pop @left ; restore the Left index
mov @prevLeft,rax ; and save the returned value
; -------------------------------------
; Recursive Call - (left, prevLeft - 1)
; -------------------------------------
push @left ; preserve the Left index
push @right ; preserve the Right index
push @left ; push the 1st parameter (Left)
mov rax,@prevLeft ; get the previous left
dec rax ; minus 1
push rax ; push the 2nd parameter
Call _QSort ; Call yourself
pop rax ; Junk this
pop rax ; Junk this
pop @right ; restore the Right index
pop @left ; restore the Left index
; ----------------------------------
; Recursive Call - (prevLeft, right)
; ----------------------------------
push @left ; preserve the Left index
push @right ; preserve the Right index
push @prevLeft ; push the 1st parameter (previous left
push @right ; push the 2nd parameter (Right0
Call _QSort ; Call yourself
pop rax ; Junk this
pop rax ; Junk this
pop @right ; restore the Right index
pop @left ; restore the Left index
.Exit:
_QSort_EXIT:
ret
_moveThem:
; repeat.while (left <= right)
cmp @left,@right ; Compare Left to Right Index
jg .Exit ; exit if Left is > Right
; repeat.while (Key[left] < pivotValue)
; left = left + 1
; end.repeat
.start1:$getAddress RSI,@left ; Get the Start of the record
add RSI,qword[d_startPos] ; add the requested starting position
mov qword[LeftAddress],RSI ; and save it
mov RDI,pivotValue ; Get the start of the pivotValue
mov rcx,qword[d_noOfBytes] ; Grab the length (LOOP Ctr)
cld ; Clear the direction flag - left to right
repe cmpsb ; Compare the String
jnl .cont1 ; If result not < than exit While Loop
inc @left ; get the next table slot
jmp .start1 ; and repeat
.cont1:
cmp @left,@right ; Compare Left to Right Index
jg .Exit ; exit if Left is > Right
; repeat.while (Key[right]> pivotValue)
; right = right - 1
; end.repeat
.start2:$getAddress RSI,@right ; Get the Start of the record
add RSI,qword[d_startPos] ; add the requested starting position
mov qword[RightAddress],RSI ; and save it
mov RDI,pivotValue ; Get the start of the pivotValue
mov rcx,qword[d_noOfBytes] ; Grab the length (LOOP Ctr)
cld ; Clear the direction flag - left to right
repe cmpsb ; Compare the string
jng .cont2 ; If result not > than exit While Loop
dec @right ; get the previous table slot
jmp .start2 ; and repeat
.cont2:
cmp @left,@right ; Compare Left to Right Index
jg .Exit ; exit if Left is > Right
jl .DoTheMove ; Do the move if less than
; No need to do the move if left = right
inc @left ; increment the left
jmp .Exit ; and head for the exit
; if left <= right - SWAP left and right data
.DoTheMove:
mov RSI,qword[LeftAddress] ; grab the Left address
mov RDI,qword[RightAddress] ; grab the Right address
mov rcx,r_recordLength ; and grab the record length
.start3:cmp rcx,8 ; Have we still got 8 bytes to move
jb .start4 ; If not go and pick up the last few bytes
mov rax,qword[RSI] ; grab the left 8 bytes
mov rbx,qword[RDI] ; grab the right 8 bytes
xchg rax,rbx ; swap them over
mov qword[RSI],rax ; put the right 8 bytes to the left
mov qword[RDI],rbx ; put the left 8 bytes to the right
add RSI,8 ; setup RSI for the next 8 bytes
add RDI,8 ; setup RDI for the next 8 bytes
sub rcx,8 ; take 8 away from the counter
jmp .start3 ; and loop around
.start4:cmp rcx,0 ; Have we still got anything to move
jna .cont4 ; If not we are done
mov ah,byte[RSI] ; grab the left byte
mov al,byte[RDI] ; grab the right byte
xchg ah,al ; swap them over
mov byte[RSI],ah ; put the right byte to the left
mov byte[RDI],al ; put the left byte to the right
add RSI,1 ; setup RSI for the next byte
add RDI,1 ; setup RDI for the next bytes
sub rcx,1 ; take 1 away from the counter
jmp .start4 ; and loop around
.cont4:
inc @left ; Next Left
dec @right ; Previous Right
jmp _moveThem ; Back to the Start
.Exit:
mov rax,@left ; Return the Left value
_moveThem_EXIT:
ret
import java.util.Arrays;
class QuickSort {
public static void Sort(String[] strArray, int lowerIndex, int higherIndex)
{
int left = lowerIndex;
int right= higherIndex;
int x;
String pivot, temp;
pivot = strArray[lowerIndex+(higherIndex-lowerIndex)/2];
while (left <= right) {
x = strArray[left].compareTo(pivot);
while (x < 0) {
left++;
x = strArray[left].compareTo(pivot);
}
x = strArray[right].compareTo(pivot);
while (x > 0) {
right--;
x = strArray[right].compareTo(pivot);
}
if (left <= right) {
temp = strArray[left];
strArray[left] = strArray[right];
strArray[left] = temp;
left++;
right--;
}
}
if (lowerIndex < right)
Sort(strArray,lowerIndex,right);
if (left < higherIndex)
Sort(strArray,left,higherIndex);
}
}
public class V2_11 {
public static void main(String[] args) {
String strArray[] = new String[1000001];
String letters[] = {"a","b","c","d","e","f","g","h","i","j",
"k","l","m","n","o","p","q","r","s","t",
"u","v","w","x","y","z"};
String word;
String spaces[] = new String[998];
int random;
//---------------
//Build the Array
//---------------
System.out.println("Filling Array");
System.out.println(java.time.LocalTime.now());
for (int i=0;i < 1000000;i++){
word="";
for (int j=0;j< 26;j++){
random = (int)(Math.random() * 9 + 0);
word=word+letters[random];
}
strArray[i]=word+spaces;
}
System.out.println(java.time.LocalTime.now());
//--------------
//Sort the Array
//--------------
System.out.println("Sorting");
System.out.println(java.time.LocalTime.now());
//---Arrays.sort(strArray);
QuickSort.Sort(strArray,0, 999999);
System.out.println(java.time.LocalTime.now());
//-------------------
//Display some Reults
//-------------------
for (int i=100;i< 110;i++)
{
System.out.println(strArray[i]);
}
}
}
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <sys/time.h>
#include <stdlib.h>
struct timeval start, stop;
double secs = 0;
char strArray[1000000][27];
char pivotValue[27];
char temp[27];
int prevLeftIdx;
int moveThem(int left, int right)
{ int x;
while (left <= right) {
x = strcmp(strArray[left],pivotValue);
while (x < 0) {
left++;
x = strcmp(strArray[left],pivotValue);
}
x = strcmp(strArray[right],pivotValue);
while (x > 0) {
right--;
x = strcmp(strArray[right],pivotValue);
}
if (left <= right) {
strcpy(temp,strArray[left]);
strcpy(strArray[left],strArray[right]);
strcpy(strArray[right],temp);
left++;
right--;
}
}
return left;
}
int QuickSort(int left, int right)
{
if (left>=right)
{return 0;}
strcpy(pivotValue, strArray[(left+right)/2]);
prevLeftIdx=moveThem(left,right);
QuickSort(left,prevLeftIdx-1);
QuickSort(prevLeftIdx,right);
}
int main()
{
char letters[26] = "abcdefghijklmnopqrstuvwxyz";
char c_Null[1] = " ";
char word[27];
int i,j,random;
//---------------
//Build the Array
//---------------
puts("Filling Array");
gettimeofday(&start, NULL);
srand(time(NULL));
for (i=0;i < 1000000;i++){
for (j=0;j< 26;j++){
random = rand() % 24;
word[j] = letters[random];
}
word[j] = *c_Null;
strcpy(strArray[i],word);
}
gettimeofday(&stop, NULL);
secs = (double)(stop.tv_usec - start.tv_usec) / 1000000 + (double)(stop.tv_sec - start.tv_sec);
printf("time taken %fn",secs);
//--------------
//Sort the Array
//--------------
puts("Sorting");
gettimeofday(&start, NULL);
QuickSort(0, 999999);
gettimeofday(&stop, NULL);
secs = (double)(stop.tv_usec - start.tv_usec) / 1000000 + (double)(stop.tv_sec - start.tv_sec);
printf("time taken %fn",secs);
//-------------------
//Display some Reults
//-------------------
for (i=0;i<10 ;i++)
{
puts(strArray[i]);
}
}
RESULTS FOR C program
Filling Array
time taken 0.245878
Sorting
time taken 0.473481
aaaagajqpbutmaxxhgjkauwmwg
aaaakestelpvsrgiemafwtujev
aaaamnvrdueegvfilkvsabdomd
aaaapspaurwurvecikmjibkwfk
aaaauclobckwflwushhnhiafws
aaabaiueabmqlumijuhlrvmgtf
aaabcqehhoeegkhpeondnbsqjb
aaabmwxdrcpfxlhbmggxvjcaoc
aaabplwowigaxmpjipqxkntilc
aaacjsuqkmbwnglltqsspvvtlr
找到了一个至少让我满意的解决方案。
作为起点，快速排序算法对 1,000,000 个元素的 qwords 数组执行如下操作。(5 次运行的时间以秒为单位( .091067， .087505， .087407， .088104， .086983 - 所以..相当快
在 1,000,000 * 1024 字节的字符串数组上，第 1 个 8 字节的排序次数是：- 2.265867， 2.241919， 2.281978， 2.264712， 2.291069 - 所以..没那么热
在 1,000,000 * 1024 字节的字符串数组上，对第一个 8 字节(代码更改后(进行排序的时间是：- 0.719363， 0.688310， 0.717557， 0.710861， 0.746405 - 与Java相当，如果不是更好的话
代码修复包括替换
mov rsi,Src Address
mov rdi,Dst Address
mov rcx,SortKey Length
repe cmpsb
跟
mov rax,[Src Address]
bswap rax
mov rbx,[Dst Address]
bswap
cmp rax,rbx
我猜您正在一次比较 8 字节，它会更快是有道理的。这显然不是最好的方法，但不会偏离我不想进入的东西，它会做得很好。
作为旁注，代码需要完成以处理可变长度键，但这只是坐下来做工作的情况。我希望这能帮助任何偶然发现这个线程的人。(特别感谢@PeterCordes他的努力(