本代码全网首发,使用Go plan9 windows arm64汇编,实现基础版快速排序算法。
未引入随机因子的快速排序的普通Go代码长这样。
func QuickSort(arr []int) {if len(arr) <= 1 {return}base, l, r := arr[0], 0, len(arr)-1for i := 1; i <= r; {if arr[i] > base {arr[i], arr[r] = arr[r], arr[i]r--continue}arr[i], arr[l] = arr[l], arr[i]l, i = l+1, i+1}QuickSort(arr[:l])QuickSort(arr[l+1:])
}
如下,使用windows arm64 Go plan9汇编实现的快速排序。
file: quickSort.s
#include "textflag.h"
// func QuickSortByASM(slice []int)
TEXT ·QuickSortByASM(SB), $104-24// NO_LOCAL_POINTERSMOVD R0 , tmp-8*3(SP); MOVD R1 , tmp-8*4(SP)MOVD R2 , tmp-8*5(SP); MOVD R3 , tmp-8*6(SP)MOVD R4 , tmp-8*7(SP); MOVD R5 , tmp-8*8(SP)MOVD R6 , tmp-8*9(SP); MOVD R7 , tmp-8*10(SP)MOVD R8 , tmp-8*11(SP); MOVD R9 , tmp-8*12(SP)MOVD R10, tmp-8*13(SP)MOVD slice+0(FP), R0 // arrayPtrMOVD slice+8(FP), R1 // arrayLengthMOVD $0, R2 // l_indexMOVD R1, R3 // r_index = arrayLengthSUB $1, R3 // r_index -= 1MOVD $0, R4 // pointer1MOVD $0, R5 // pointer2MOVD $8, R6 // dataSizeMOVD $1, R7 // indexMOVD (R0), R8 // base TODO random indexMOVD $0, R9CMP $1, R1; BLE LABEL_END // if arrayLength <= 1 return
LABEL_FOR_START:CMP R3, R7; BGT LABEL_FOR_END // if index > r_index returnMOVD R7, R4 // offset = indexMUL R6, R4 // offset *= dataSizeADD R0, R4 // arr[i] = R4MOVD (R4), R5 // arr[i]CMP R8, R5; BLE LABEL_SWAP // if arr[i] <= baseMOVD R3, R5 // offset = r_indexMUL R6, R5 // offset *= dataSizeADD R0, R5 // arr[r]MOVD (R5), R9 // tmp = arr[r]MOVD (R4), R10 // tmp1 = arr[i]MOVD R10, (R5) // arr[r] = arr[i]MOVD R9, (R4) // arr[i] = tmpSUB $1, R3 // r_index -= 1JMP LABEL_FOR_START
LABEL_SWAP:MOVD R7, R4MUL R6, R4ADD R0, R4MOVD R2, R5MUL R6, R5ADD R0, R5MOVD (R4), R9 // tmp = arr[i]MOVD (R5), R10 // tmp1 = arr[l]MOVD R10, (R4) // arr[i] = tmp1MOVD R9, (R5) // arr[l] = tmpADD $1, R2 // l_index += 1ADD $1, R7 // index += 1JMP LABEL_FOR_START
LABEL_FOR_END:MOVD R0, R4MOVD R2, R5MOVD R4, tmp-104(SP)MOVD R5, tmp-96(SP)CALL ·QuickSortByASM(SB)MOVD R2, R4ADD $1, R4MUL R6, R4ADD R0, R4 // right addressMOVD R1, R5 // tmp = arrayLengthSUB R2, R5 // tmp -= l_indexSUB $1, R5MOVD R4, tmp-104(SP)MOVD R5, tmp-96(SP)CALL ·QuickSortByASM(SB)
LABEL_END:MOVD tmp-8*3(SP), R0; MOVD tmp-8*4(SP), R1MOVD tmp-8*5(SP), R2; MOVD tmp-8*6(SP), R3MOVD tmp-8*7(SP), R4; MOVD tmp-8*8(SP), R5MOVD tmp-8*9(SP), R6; MOVD tmp-8*10(SP), R7MOVD tmp-8*11(SP), R8;MOVD tmp-8*12(SP), R9MOVD tmp-8*13(SP), R10RET
该汇编版本快排基于普通版快排手写而成, 未加入stackmap信息,大数据量样本可能会出现panic,仅供参考。
对数器
package mainimport ("fmt""math/rand""sort"
)func QuickSortByASM(slice []int) // 汇编函数声明func main() {N := 50for index := 0; index < 1000; index++ {slice := make([]int, N)for i := 0; i < N; i++ {slice[i] = rand.Int()}slice1 := make([]int, N)slice2 := make([]int, N)for i, v := range slice {slice1[i] = vslice2[i] = v}sort.Ints(slice1)QuickSortByASM(slice2)for i := 0; i < N; i++ {if slice1[i] != slice2[i] {fmt.Println(slice)fmt.Println(slice1)fmt.Println(slice2)panic(i)}}}fmt.Println("pass")
}
pass