- Offizieller Beitrag
In GetUniqueColors gab es die Aufgabenstellung alle Farben in einem Bild zu zählen.
Hier soll es jetzt um das sortieren von 32-Bit-Integerwerten gehen. Wenn man ein AutoIt-Array mit 1Mio Elementen hat und dieses mit _ArraySort sortieren will, dann dauert das ziemlich lange (ca. 26 Sekunden auf meinem Rechner und mit Zufallsdaten).
Das Ganze dauert in Assembler ca. 56 Millisekunden. Zumindest das reine sortieren. Um in Assembler mit dem AutoIt-Array arbeiten zu können, müssen wir es in eine Struct kopieren und nach dem sortieren in Assembler müssen wir die Daten aus der Struct wieder in das Array zurück kopieren.
Dieses umkopieren dauert jedes Mal ca. 1.2 Sekunden. Somit ergibt sich für das sortieren mit dem Assemblerprogramm eine Gesamtlaufzeit von ca. 2.5 Sekunden. Das ist aber immer noch ein mächtiger Geschwindigkeitsgewinn (nur ein Zehntel der Zeit).
Dieses Assemblerprogramm möchte ich euch hier vorstellen.
Dazu habe ich die Quicksort-Funktion aus dem obigen Thread noch verbessert:
- Beim Start wird überprüft, ob die Daten bereits sortiert vorliegen. Das kostet zwar ein paar Millisekunden für den Test, aber es ist schneller als die sortierten Daten erneut durch die Funktion zu schicken.
- Quicksort wird nicht ausschließlich verwendet. Bei weniger als 45 Elementen pro Partition werden die verbleibenden Elemente mit InsertionSort sortiert. Diese Kombination ist schneller, als ein reines Qiucksort.
- Das Pivotelement ist jetzt nicht mehr das erste (linke) Element einer Partition, sondern das Mittlere. Das bringt einen enormem Geschwindigkeitsgewinn bei teilsortierten Listen.
Ausgabe bei mir:
ASM-Code-Size: 221 Bytes
Test-Array: 1000000 Elemente
ArrayCreate: 1237.211 ms
Array2Struct: 1116.148 ms
ASM_Sort: 55.360 ms
Struct2Array: 1190.879 ms
_ArraySort: 25923.010 ms
Wer selbst am ASM-Code rumbasteln will, benötigt "Assembleit2_64" von Andy und muss die Zeilen 4 und 166 aktivieren und die Zeilen 167 und 168 auskommentieren.
Ansonsten habe ich alles ausgiebig kommentiert, sodass der Ablauf verständlich wird.
#AutoIt3Wrapper_UseX64=n ; 32Bit-Modus
#include <Memory.au3>
#include <Array.au3>
;~ #include "assembleit2_64.au3"
#Region ASM-Code
#cs ASM_Sort
Use32 ; 32Bit Modus!
mov esi,dword[esp+4] ; esi = Pointer auf die Datenstruct
mov edx,dword[esp+8] ; edx = right = Anzahl der Daten
dec edx ; um eins verringern, weil die Datenstruct bei 0 beginnt
xor ecx,ecx ; ecx (auf 0 setzen)
@check1: ; Schleife, zum testen, ob die Daten bereits sortiert sind (aufwaerts)
mov eax,dword[esi+ecx*4] ; eax = Data[ecx]
inc ecx ; ecx++
cmp ecx,edx ; ecx > edx?
ja @SortReturn ; Ja, dann alle Daten getestet, also bereits sortiert (Funktion beenden)
cmp eax,dword[esi+ecx*4]
jbe @check1 ; Wenn Data[ecx] <= Data[ecx+1], dann weiter mit @check1
xor ecx,ecx ; ecx (auf 0 setzen)
@check2: ; Schleife, zum testen, ob die Daten bereits sortiert sind (abwaerts)
mov eax,dword[esi+ecx*4] ; eax = Data[ecx]
inc ecx ; ecx++
cmp ecx,edx ; ecx > edx?
ja @SortReturn ; Ja, dann alle Daten getestet, also bereits sortiert (Funktion beenden)
cmp eax,dword[esi+ecx*4]
jae @check2 ; Wenn Data[ecx] >= Data[ecx+1], dann weiter mit @check2
xor ecx,ecx ; ecx = left (auf 0 setzen)
push edx ecx ; right und left auf den Stack (fuer Quicksort)
call quicksort ; Quicksort aufrufen (die Datenstruct sortieren)
@SortReturn:
ret ; Daten sortiert (Funktion beenden)
quicksort: ; die Quick-/Insertionsort-Funktion
mov ecx,dword[esp+4] ; ecx = left
mov edx,dword[esp+8] ; edx = right
cmp ecx,edx ; left und right vergleichen
jae @end ; wenn left >= right, dann Funktion beenden
mov eax,edx
sub eax,ecx ; right - left
cmp eax,45 ; mehr als 45 Elemente?
jg @quick ; wenn ja, dann Quicksort
mov edi,ecx ; Nein, dann Insertionsort
inc edi ; edi = $i = left + 1
@fori:
mov ebx,dword[esi+edi*4] ; ebx = Data[Insert]
mov eax,edi ; eax = $j = Insertpos
@forj: ; Einfuegeschleife
cmp eax,ecx ; Anfang erreicht?
jbe @break ; Ja, dann @break
cmp dword[esi-4+eax*4],ebx ; Data[j-1] < Data[Insert]
jbe @break ; Ja, dann @break
movd xmm0,dword[esi-4+eax*4] ; Data[j-1] holen
movd dword[esi+eax*4],xmm0 ; als Data[j] speichern
dec eax ; j--
jmp @forj ; forj fortsetzen
@break:
mov dword[esi+eax*4],ebx ; Data[Insert] nach Data[j] speichern
inc edi ; i++
cmp edi,edx ; i > right
jbe @fori ; Nein, dann @fori
ret 8 ; Insertionsort beendet, Funktion verlassen
@quick: ; hier beginnt der Quicksort-Bereich
push edx ecx ; edx und ecx auf den Stack (fuer Partition)
call partition ; Partition aufrufen (ebx = split)
pop ecx edx ; ecx und edx wiederherstellen
push ebx edx ; Register sichern
push ebx ecx ; ebx und ecx auf den Stack (right und left fuer Quicksort)
call quicksort ; Quicksort aufrufen (rekursiv)
pop edx ebx ; Register wiederherstellen
inc ebx ; ebx++
push edx ebx ; edx und ebx auf den Stack (right und left fuer Quicksort)
call quicksort ; Quicksort aufrufen (rekursiv)
@end:
ret 8 ; Quicksort-Funktion beendet (2 DWORDs = 8 Byte vom Stack loeschen)
partition: ; Funktion zum partitionieren der Daten
mov ecx,dword[esp+4] ; ecx = left
mov edx,dword[esp+8] ; edx = right
mov eax,edx ; eax = edx (right)
sub eax,ecx ; eax = eax - ecx (right minus left)
shr eax,1 ; eax shift right (geteilt durch 2)
add eax,ecx ; eax += ecx (= middle)
movd xmm0,dword[esi+ecx*4]
movd xmm1,dword[esi+eax*4] ; swap Data[left] <-> Data[middle]
movd dword[esi+eax*4],xmm0
movd dword[esi+ecx*4],xmm1
movd edi,xmm1 ; edi = Pivotwert = Data[left]
mov eax,ecx
dec eax ; eax = left - 1
mov ebx,edx
inc ebx ; ebx = right + 1
@loop: ; Hauptschleife
@left: ; Schleife fuer die linke Seite
inc eax ; left++
cmp dword[esi+eax*4],edi ; Vergleich Data[left] mit Pivotwert
jb @left ; wenn kleiner, dann Schleife @left
@right: ; Schleife fuer die rechte Seite
dec ebx ; right--
cmp dword[esi+ebx*4],edi ; Vergleich Data[right] mit Pivotwert
ja @right ; wenn groesser, dann Schleife @right
cmp eax,ebx ; Vergleich left und right
jae @return ; wenn groesser/gleich, dann @return
mov ecx,dword[esi+eax*4] ; Data[left] gegen Data[right] austauschen
mov edx,dword[esi+ebx*4]
mov dword[esi+eax*4],edx
mov dword[esi+ebx*4],ecx
jmp @loop ; und mit @loop fortfahren
@return:
ret ; right zurueckgeben (ebx)
#ce
#EndRegion ASM-Code
#region AssembleIt ; wenn diese 3 Zeilen aktiv sind, dann wird der obige ASM-Code in Binaercode umgewandelt
;~ $binarycode = _AssembleIt2('retbinary', 'ASM_Sort') ; gibt nur den assemblierten code zurück
;~ ConsoleWrite('$binarycode = "' & $binarycode & '"' & @CRLF)
;~ Exit
#EndRegion AssembleIt
#Region ASM-Binaercode ; $__g_bASMCode entspricht dem obigen ASM-Code im Binaerformat
Global Const $__g_bASMCode = '0x8B7424048B5424084A31C98B048E4139D1771D3B048E76F331C98B048E4139D1770E3B048E73F331C95251E801000000C38B4C24048B54240839D1735089D029C883F82D7F2B89CF478B1CBE89F839C87614395C86FC760E660F6E4486FC660F7E048648EBE8891C864739D776DBC208005251E818000000595A53525351E8AEFFFFFF5A5B435253E8A4FFFFFFC208008B4C24048B54240889D029C8D1E801C8660F6E048E660F6E0C86660F7E0486660F7E0C8E660F7ECF89C84889D34340393C8672FA4B393C9E77FA39D8730E8B0C868B149E891486890C9EEBE2C3'
Global Const $__g_iMemSize = StringLen($__g_bASMCode) / 2 - 1 ; Codelaenge ermitteln
Global Const $__g_pMem = _MemVirtualAlloc(0, $__g_iMemSize, $MEM_COMMIT, $PAGE_EXECUTE_READWRITE) ; Virtuellen Speicher reservieren
If $__g_pMem = 0 Then Exit MsgBox(16, 'Error!', "Can't allocate virtual memory!")
Global $__g_tASMCode = DllStructCreate('byte[' & $__g_iMemSize & ']', $__g_pMem) ; Structur fuer den Binaercode erstellen
DllStructSetData($__g_tASMCode, 1, $__g_bASMCode) ; den Binaercode in die Structur schreiben
Global $__g_pASMCode = DllStructGetPtr($__g_tASMCode) ; den Pointer der Structur holen
ConsoleWrite(StringFormat('ASM-Code-Size:\t%i Bytes\n', $__g_iMemSize))
#EndRegion ASM-Binaercode
#Region Test-Vorbereitungen
Global $iCount = 1000000, $iTimer, $ret ; $iCount = Anzahl der Array-Elemente
Global $aRanData[$iCount], $aData
ConsoleWrite(StringFormat('Test-Array:\t%i Elemente\n', $iCount))
#EndRegion Test-Vorbereitungen
#Region Zufalls-Array erstellen
$iTimer = TimerInit()
For $i = 0 To $iCount - 1
$aRanData[$i] = Random(0, 2^31-1, 1)
;~ $aRanData[$i] = $i ; aufwaerts sortiert
;~ $aRanData[$i] = $iCount - $i ; abwaerts sortiert
Next
;~ $tmp = $aRanData[$iCount - 1] ; swap A[last] <-> A[0]
;~ $aRanData[$iCount - 1] = $aRanData[0]
;~ $aRanData[0] = $tmp
ConsoleWrite(StringFormat('ArrayCreate:\t%.3f ms\n\n', Round(TimerDiff($iTimer), 3)))
#EndRegion Zufalls-Array erstellen
#Region Array2Struct
$aData = $aRanData ; damit die Ausgangsbedingungen gleich sind
$iTimer = TimerInit()
Global $tData = DllStructCreate('dword[' & $iCount & ']')
Global $pData = DllStructGetPtr($tData)
For $i = 0 To $iCount - 1
DllStructSetData($tData, 1, $aData[$i], $i + 1)
Next
ConsoleWrite(StringFormat('Array2Struct:\t%.3f ms\n', Round(TimerDiff($iTimer), 3)))
#EndRegion Array2Struct
#Region ASM-Code aufrufen
$iTimer = TimerInit()
;~ $ret = _AssembleIt2('dword', 'ASM_Sort', 'ptr', $pData, 'dword', $iCount)
$ret = DllCallAddress('uint:cdecl', $__g_pASMCode, 'ptr', $pData, 'dword', $iCount)
$ret = $ret[0]
ConsoleWrite(StringFormat('ASM_Sort:\t%.3f ms\n', Round(TimerDiff($iTimer), 3)))
#EndRegion ASM-Code aufrufen
#Region Struct2Array
$iTimer = TimerInit()
For $i = 0 To $iCount - 1
$aData[$i] = DllStructGetData($tData, 1, $i + 1)
Next
ConsoleWrite(StringFormat('Struct2Array:\t%.3f ms\n\n', Round(TimerDiff($iTimer), 3)))
#EndRegion Struct2Array
#Region AutoIt ArraySort
$aData = $aRanData ; damit die Ausgangsbedingungen gleich sind
$iTimer = TimerInit()
_ArraySort($aData, 0, 0, 0, 0, 1) ; mit Dual-Pivot aufrufen (ist hier schneller)
ConsoleWrite(StringFormat('_ArraySort:\t%.3f ms\n', Round(TimerDiff($iTimer), 3)))
#EndRegion AutoIt ArraySort
;~ _ArrayDisplay($aData)
_MemVirtualFree($__g_pMem, $__g_iMemSize, $MEM_DECOMMIT)
Alles anzeigen