Tweet
I have managed to convert Ethan Winer's 1992 QB quick sort to
PowerBASIC inline assembler. Ethan's original algorithm was fast
as it was ported to PowerBASIC code but with the reduction of
instructions written in assembler, its speed has increased by a
reasonable amount.
On my own box, a 600 PIII, it sorts a million randomly generated
LONG integers in about 560 milliseconds which is starting to become
competitive in speed terms. It is about 5 times faster on this type
of data than the Comb Sort I posted before.
The encoding is reasonably efficient, it could probably be tweaked here
and there but there are no real speed gains left in it, there was some
gain in the loop code but the real gains in speed were in the capacity
to handle the array data directly in assembler. This algo is destined
for MASM as it does not have PowerBASIC's built in array support.
The low level power of PowerBASIC has made porting high level code to assembler
a far simpler task than some toothless OOP terror and its capacity to
prototype code for MASM would make it a compiler with an unusually
powerful capacity.
It is easy enough to use, the first parameter is the address of the first
element in the array that needs to be sorted, the second parameter is
the number of elements that are to be sorted.
Regards,
[email protected]pbq.com.au
[This message has been edited by Steve Hutchesson (edited September 19, 2001).]
PowerBASIC inline assembler. Ethan's original algorithm was fast
as it was ported to PowerBASIC code but with the reduction of
instructions written in assembler, its speed has increased by a
reasonable amount.
On my own box, a 600 PIII, it sorts a million randomly generated
LONG integers in about 560 milliseconds which is starting to become
competitive in speed terms. It is about 5 times faster on this type
of data than the Comb Sort I posted before.
The encoding is reasonably efficient, it could probably be tweaked here
and there but there are no real speed gains left in it, there was some
gain in the loop code but the real gains in speed were in the capacity
to handle the array data directly in assembler. This algo is destined
for MASM as it does not have PowerBASIC's built in array support.
The low level power of PowerBASIC has made porting high level code to assembler
a far simpler task than some toothless OOP terror and its capacity to
prototype code for MASM would make it a compiler with an unusually
powerful capacity.
It is easy enough to use, the first parameter is the address of the first
element in the array that needs to be sorted, the second parameter is
the number of elements that are to be sorted.
Code:
Prototypes
~~~~~~~~~~
DECLARE FUNCTION SysAllocStringByteLen LIB "oleaut32.dll" _
alias "SysAllocStringByteLen" _
(ByVal cpyString as LONG,ByVal bytelen as LONG) as LONG
DECLARE FUNCTION SysFreeString LIB "oleaut32.dll" _
alias "SysFreeString" _
(ByVal strhandle as LONG) as LONG
Code
~~~~
nrQsort VarPtr(MyArray(0)),1000
Algorithm
~~~~~~~~~
' #########################################################################
SUB nrQsort (ByVal Arr as LONG,ByVal count as LONG)
#REGISTER NONE
LOCAL First as LONG
LOCAL Last as LONG
LOCAL cntr as LONG
LOCAL bLen as LONG
LOCAL hMem as LONG
LOCAL temp as LONG
! mov esi, Arr ; source address in ESI
' --------------------------
' allocate temporary buffer
' --------------------------
! mov eax, count
! add eax, 40
! mov bLen, eax
SysAllocStringByteLen 0, bLen
! mov hMem, eax
! mov edi, hMem ; buffer address in EDI
' ------------------------------------
' set First and Last reference values
' ------------------------------------
! mov First, 0
! mov eax, count
! dec eax
! mov Last, eax ; Last = count - 1
outer_loop:
' -------------------
' calculate midpoint
' -------------------
! mov eax, Last
! add eax, First
! shr eax, 1
' =========================
! mov ebx, [esi+eax*4] ; midpoint in EBX
! mov temp, ebx
' =========================
! mov ecx, First
! mov edx, Last
' ---------------------------------------------------------
inner_loop:
! cmp [esi+ecx*4], ebx
! jge wl2 ; JLE for descending sort
! inc ecx
! jmp inner_loop
wl2:
! cmp [esi+edx*4], ebx
! jle wl2Out ; JGE for descending sort
! dec edx
! jmp wl2
wl2Out:
! cmp ecx, edx ; If ecx > edx, exit inner loop
! jg exit_innerx
' =========================
! mov eax, [esi+ecx*4]
! mov ebx, [esi+edx*4] ; swap elements
! mov [esi+ecx*4], ebx
! mov [esi+edx*4], eax
' =========================
! mov ebx, temp ; restore EBX
! inc ecx
! dec edx
! cmp ecx, edx
! jle inner_loop
exit_innerx:
' ---------------------------------------------------------
! cmp ecx, Last ; If ecx < Last jump over
! jg iNxt
' =========================
! mov eax, cntr
! mov [edi+eax*4], ecx
! mov ebx, Last
! mov [edi+eax*4+4], ebx
' =========================
! add cntr, 2
iNxt:
! mov ebx, temp ; restore EBX
! mov Last, edx ; Last = EDX
! cmp edx, First ; compare Last & First
! jg outer_loop
! cmp cntr, 0
! jz qsOut
! sub cntr, 2
' =========================
! mov eax, cntr
! mov ebx, [edi+eax*4]
! mov First, ebx
! mov ebx, [edi+eax*4+4]
! mov Last, ebx
' =========================
! mov ebx, temp ; restore EBX
! jmp outer_loop
qsOut:
SysFreeString hMem
END SUB
' #########################################################################
[email protected]pbq.com.au
[This message has been edited by Steve Hutchesson (edited September 19, 2001).]
Comment