GetUniqueColors

  • Hallo Oscar,


    zunächst: verneigen0010.gif TOP(!!) Leistung.


    Ggf solltest du in deinem Post die Version posten, welche kein AssembleIt() benötigt, für diejenigen die "nur" deinen Code ausprobieren wollen benötigt man ausschliesslich AutoIt!

    Das _DllStructCreate64() habe ich auch rausgenommen, ist nur für die 64-Bit-Kompatibilität (also 64-Bit-ASM-Code) nötig.


    Jetzt noch ein ganz privates Statement meinerseits....DANKE! Ich war all die Jahre zu faul, einen Quicksort in ASM zu erstellen, ich werde mich in Zukunft an deinem Code bedienen.:P



    Mein Quicksort ist eine rekursive Variante, die den Stack ausgiebig nutzt, aber dafür ansonsten nur den Speicher der Pixelstruct (für das Bild) benutzt.

    Das ist auch der Hauptgrund für die vergleichbare "Langsamkeit". Stack heißt Speicherzugriffe, und die kosten Zeit. Schlimmstenfalls liegen die rechten/linken Pixeladressen nicht im Cache und dann tritt der Supergau auf: Cachemiss. Das kostet je nach Prozessor massig Takte!

    Daran ist aber nicht deine Umsetzung schuld, sondern der für die landläufige PC-Architektur "langsame" (sprich Speicherzugriffstechnisch aufwendige) Quicksort-Algorithmus.

    Mir würde jetzt auf Anhieb nicht einfallen, wie man vorliegenden Code stark beschleunigen könnte.

    :klatschen:


    //EDIT

    Habe mal per RDTSC die Prozessor-Takte pro Pixel ausgeben lassen, bei kleinen Bildern ist Quicksort algorithmusbedingt "langsam" mit ca. 200-300 Takten/Pixel.

    Bei deinem 7680 x 4320 Testbild gibt der Algorithmus richtig Gas und kommt bei mir auf 15-20 Takte/Pixel!!!

    //EDIT2

    Nachdem nochmals verifiziert, komme ich mit diversen 12MP-Bildern auf ca. 150 Takte/Pixel

  • zunächst: TOP(!!) Leistung.

    Danke! Als Assembler-Anfänger hört man das gern. :)

    Ich habe zwar schonmal in Assembler programiert, aber das war auf dem C64. :D

    Jetzt noch ein ganz privates Statement meinerseits....DANKE! Ich war all die Jahre zu faul, einen Quicksort in ASM zu erstellen, ich werde mich in Zukunft an deinem Code bedienen

    Oh, das hätte ich jetzt nicht gedacht!

    Darfst Dich aber gern bedienen.:) 

    Das ist auch der Hauptgrund für die vergleichbare "Langsamkeit". Stack heißt Speicherzugriffe, und die kosten Zeit. Schlimmstenfalls liegen die rechten/linken Pixeladressen nicht im Cache und dann tritt der Supergau auf: Cachemiss. Das kostet je nach Prozessor massig Takte!

    Daran ist aber nicht deine Umsetzung schuld, sondern der für die landläufige PC-Architektur "langsame" (sprich Speicherzugriffstechnisch aufwendige) Quicksort-Algorithmus.

    Mir würde jetzt auf Anhieb nicht einfallen, wie man vorliegenden Code stark beschleunigen könnte.

    Ok!

    Bei der "Partition-Funktion" habe ich noch zwei Stackzugriffe entfernen können. Ich muss die einfach am Ende nicht vom Stack löschen, dann brauche ich sie nicht doppelt auf den Stack packen.

    Bei der rekursiven Quicksort geht das hingegen nicht, weil ich einerseits die ecx,edx-Werte brauche und zum anderen aber den ebx-Wert als right bzw. left uebergeben muss.

    Aber mir ist da gerade noch etwas eingefallen, wie man evtl. noch Stackzugriffe reduzieren kann.

    Ich werde aber erst morgen dazu kommen, das auszutesten. Mal sehen, ob es was bringt...

  • Hier mal die Version mit Zählen der Takte pro Pixel, vielleicht hilft dir das ja weiter.


    Und noch die letzte AssembleIt()-Version, bissl finetuning unter der Oberfläche.

    Bspw. benötigt man für den Debugger die ORG-Direktive nicht mehr im Code


    Assembleit2_64.zip

  • Kaum zu glauben, aber ich habe nochmal 300ms bei dem 33MP-Bild rausholen können. Die unten stehende Variante benötigt bei mir jetzt unter 3 Sekunden.

    Mein "Trick" ist der, dass ich eine Quick-/Bubblesort-Kombination einsetze (bei wenigen Elementen ist Bubblesort schneller als Quicksort).

    Wenn sich in den einzelnen Partitionen von Quicksort weniger als 10 Pixel (experimentell ermittelt) befinden, dann wird der Rest mit Bubblesort sortiert.

    Das spart diverse Rekursionen und damit auch Stackzugriffe ein.

  • Mein "Trick" ist der, dass ich eine Quick-/Bubblesort-Kombination einsetze (bei wenigen Elementen ist Bubblesort schneller als Quicksort).

    Wirklich fix für kleine Größen ist Insertion-Sort. Nutze ich z. B. in meiner _ArraySortFlexible.

    Weiterhin kannst du die Wahl des Pivot-Elementes verbessern - z.B. per Median of Three.

    Ein fixer Partitionierungsalgorithmus (ich vermute du nimmst den von Hoare?) wie z.B. Introselect oder Floyd-Rivest wäre der nächste Schritt.

    Weitere Optimierungen wäre eine Implementierung eines Dual-Pivot Quicksort (also das Array dritteln statt halbieren).


    Aber warum sich das alles antun wenn es sowas bereits fertig gibt (und was dann gleich problemlos für 32 Bit und 64 Bit)?

    Hab meine DLLs daher mal um Quicksort-Varianten erweitert. Einmal Single-Thread, einmal Multi-Thread.

    Für Chesstiger hab ich auch mal zwei Radix-Sort-Varianten mit eingebaut.

    Liegt als Zip-Datei im Anhang.


    Ergebnis bei mir: Für 32 Bit Bilder scheint die Multi-Thread-Quicksort-Variante die erste Wahl zu sein, für 24-Bit-Bilder die Single-Thread-Array-Variante.

  • Hier meine Resultate von AspirinJunkie 's Version (#86)

    Als Testbild habe ich Oscar 's generiertes riesen Bild genommen.


    Die letzten zwei Funktionen sind extrem langsam...

  • Ergebnis bei mir: Für 32 Bit Bilder scheint die Multi-Thread-Quicksort-Variante die erste Wahl zu sein, für 24-Bit-Bilder die Single-Thread-Array-Variante.

    Kann ich bestätigen! Das ist auch bei mir die schnellste Variante. :thumbup:

    Wobei man bei Deinem Script nur die zu testende Variante auskommentieren darf. Alle hintereinander durchlaufen lassen verfälscht das Ergebnis, weil dann _GDIPlus_BitmapLockBits mit den gecachten Daten arbeitet.

    Meine 32-Bit ASM-Version ist immerhin schneller als Deine 32-Bit-Single-Thread-Quicksort-Version. Deine 64-Bit-Version zieht dann gleich. Von daher bin ich mit meiner ASM-Version schon sehr zufrieden. :)

    Die 64-Bit-Multi-Thread-Quicksort-Version ist aber drei Mal so schnell (auf meinem Quadcore-Rechner), wie meine Version.


    Und außerdem hat die ASM-Version den Vorteil, dass man sie einfacher in das AutoIt-Script packen kann und von der Größe (ASM-Version = 188 Byte) wollen wir erst gar nicht reden. :)

  • Hallo Oscar,


    wenn du Registerpressure hast (und welcher ASM-Programmierer hat das nicht^^) dann kannst du sehr einfach auch zum zwischenspeichern von Werten/Registerinhalten auf die XMM-Register zugreifen

    Code
    1. ;~ push edi ; Pixel[loopleft] sichern
    2. movd xmm0,dword[esi+ebx*4] ; Pixel[loopright] holen
    3. movd dword[esi+eax*4],xmm0 ; nach Pixel[loopleft] schreiben
    4. ;~ pop edi ; Pixel[loopleft] wiederherstellen

    Bringt im vorliegenden Fall nicht viel, aber einmal PUSH/POP ist eingespart. Im Debugger werden diese 128-Bit Register auch angezeigt incl. aller ihrer sowohl als auch integer oder float (4-Byte) Teile.

    Wenn du weißt, was du tust, kannst du auch noch das EBP-Register, also den Basepointer in deinem Code verwenden. Am Anfang des Programms pushen und am Ende wieder restaurieren, dort steht nach einem Call die Rücksprungadresse fürs "Return" :o).

    In den allermeisten Programmen ändert sich während der Laufzeit EBP nicht....wie gesagt, man muss wissen, was man da tut....


    Du kannst deinen ASM-code übrigens sehr einfach auch in AutoIt multithreadingfähig machen. Für deinen Algorithmus ist das ziemlich ungünstig, aber das am Anfang genannte Verfahren, also Farben an ihrer entsprechenden Adresse speichern und dann die Anzahl der "gesetzten" Adressen zur Summe der Farben zählen schreit geradezu nach Multithreading.

    Hier ein Beispiel <-das ist ein Link

    Mich interessiert die Variante, die Pixelfarbe als Adresse in einem Bit statt in einem Byte (wie von Mars gezeigt) abzuspeichern und dann die Bits als Summe der Anzahl der Farben zu zählen. Selbst für den vollen 32-Bit Farbraum, also incl. Alphakanal wären das gerade mal 500MB Speicher ( 255^4 Farben / 8 Bit pro byte). Vielleicht habe ich dafür ja bissl Zeit, dann sollte aber auch die Multithreadingvariante kommen :o)

  • Bringt im vorliegenden Fall nicht viel, aber einmal PUSH/POP ist eingespart. Im Debugger werden diese 128-Bit Register auch angezeigt incl. aller ihrer sowohl als auch integer oder float (4-Byte) Teile.

    Ah, ok!

    Dazu muss der Prozessor SSE unterstützen, oder? Die XMM-Register gehören doch zu der SSE-Unterstützung?

    Merken: Lieber in ein Register moven, als den Stack zu benutzen. :)


    Du kannst deinen ASM-code übrigens sehr einfach auch in AutoIt multithreadingfähig machen. Für deinen Algorithmus ist das ziemlich ungünstig, aber...

    Danke, für das Beispiel!

    Damit werde ich mich mal beschäftigen. Es ist zwar ungünstig, dass die Threads von AutoIt aus gestartet werden, aber wenn ich eine Interprozesskommunikation hinbekomme, dann sollte sich das sortieren beschleunigen lassen.

    Selbst für den vollen 32-Bit Farbraum, also incl. Alphakanal wären das gerade mal 500MB Speicher

    Naja, "gerade mal 500MB"? :/

    Auch wenn die meisten mittlerweile mehrere GB Hauptspeicher besitzen, finde ich die 500MB nur dafür ziemlich übertrieben.

    Ich werde mich da eher an der Multi-Thread-Version versuchen. Schon allein, weil mich das Thema mehr anspricht. :)

  • Andy Die MT-Variante mit bits steht ja irgendwo. Ist aber leider auch langsamer.


    Davon ab... Ich habe jetzt auch etwas rumprobiert. Eigentlich sollte RadixSort hier das mit Abstand schnellste sein. Im Durchschnittsfall (ist hier gegeben) hat QuickSort die Komplexitätsklasse O(n*log(n)), wie alle besseren vergleichenden Sortieralgorithmen. RadixSort liegt aber in O(n), ist also linear. Der Zeitbedarf steigt also linear mit jedem neuen zu sortierenden Objekt.

    Wobei RadixSort nur effizient ist, wenn die maximale Schlüssellänge eher klein ist. Wenn man das klassischs RadixSort nimmt, wird nach Dezimalstellen sortiert, bei einem Int sind das dann maximal 10 Stellen. Das Problem ist wie gemacht für diesen Sortieralgorithmus. Spätestens bei großen Datenmengen sollte er gewinnen. Tut er aber nicht... Ich hab nur noch nicht raus, warum.

  • Wirklich fix für kleine Größen ist Insertion-Sort.

    Ok, Insertionsort ist tatsächlich schneller als Bubblesort!

    Die Kombination "Quick-/Insertionsort" bringt nochmal ca. 300 ms bei dem 33MP-Bild. Jetzt bin ich bei rund 2700 ms (32-Bit Single-Thread).

    Ich lasse jetzt Insertionsort ran, sobald weniger als 32 Pixel in einer Partition sind. Das hat sich bei Versuchen als schnellste Variante ergeben.

    Hier ist die neue Version:

  • Das hier ist der beste Thread seit langem. So viel Elan für etwas das bereits auf 5 Arten erfolgreich gelöst wurde :love:

  • So viel Elan für etwas das bereits auf 5 Arten erfolgreich gelöst wurde

    Vom Prinzip her ja, aber man kann das ja noch verbessern. ;)

    Und so nebenbei lerne ich noch, wie man AutoIt mit Assembler-Routinen verbessern kann.

    Zum Beispiel: Ein _ArraySort, mit einem Array das 1Mio Elemente (DWORDs) enthält, dauert auf meinem Rechner fast 40 Sekunden. Das gleiche Array mit Assembler sortiert dauert 60 Millisekunden. Selbst wenn man noch Array2Struct und Struct2Array (jeweils ca. 1.2s) mitrechnet, ist das mit unter 3 Sekunden noch sehr schnell.

  • Andy Die MT-Variante mit bits steht ja irgendwo. Ist aber leider auch langsamer.


    Davon ab... Ich habe jetzt auch etwas rumprobiert. Eigentlich sollte RadixSort hier das mit Abstand schnellste sein. Im Durchschnittsfall (ist hier gegeben) hat QuickSort die Komplexitätsklasse O(n*log(n)), wie alle besseren vergleichenden Sortieralgorithmen. RadixSort liegt aber in O(n), ist also linear. Der Zeitbedarf steigt also linear mit jedem neuen zu sortierenden Objekt.

    Wobei RadixSort nur effizient ist, wenn die maximale Schlüssellänge eher klein ist. Wenn man das klassischs RadixSort nimmt, wird nach Dezimalstellen sortiert, bei einem Int sind das dann maximal 10 Stellen. Das Problem ist wie gemacht für diesen Sortieralgorithmus. Spätestens bei großen Datenmengen sollte er gewinnen. Tut er aber nicht... Ich hab nur noch nicht raus, warum.


    Bei mir kackt Radix Sort bei großen Bildern unter FreeBasic ab, da anscheinend FB den benutzten Speicher nicht richtig verwalten kann (Speicherschutzverletzung)!

    Ein 2D Array mit aBucket[w*h][10] und rekursivem Aufruf macht Probleme, aber bei kleinen Bildern ist Quick Sort immer noch schneller.


    Wer den FB Code testen möchte:


    Insertion Sort kann ich auch mal testen...