[PS40] Sortieren

Für Fragen zu Grafik APIs wie DirectX und OpenGL sowie Shaderprogrammierung.
Antworten
Benutzeravatar
Zudomon
Establishment
Beiträge: 2170
Registriert: 25.03.2009, 08:20
Kontaktdaten:

[PS40] Sortieren

Beitrag von Zudomon »

Und ich habe noch eine Frage, wollte die allerdings in einem neuen Thread erstellen, weil die Themen an sich nichts miteinander zu tun haben.

Ich würde gerne im Pixelshader sortieren. Dabei habe ich eine Reihe von Werten. Die Anzahl variiert zwischen 1 und 64.

Im moment benutze ich einen BubbleSort

Code: Alles auswählen

  for (int i=0; i<si-1; i++) {
    for (int j=i+1; j<si; j++) {
      if (s[i]>s[j]) { 
        int t = s[i];
        s[i] = s[j];
        s[j] = t;
      }
    }
  }
Das ist nicht gerade schnell, aber es funktioniert erstmal. Jetzt wollte ich fragen, ob es sich lohnt, bei so einer kleinen Zahlenmenge auf andere Sortieralghorithmen zu gehen und wenn ja, was eignet sich am besten? Rekursion funktioniert im Shader ja noch nicht.

Gruß
Zudomon
Benutzeravatar
kimmi
Moderator
Beiträge: 1402
Registriert: 26.02.2009, 10:42
Echter Name: Kim Kulling
Wohnort: Luebeck
Kontaktdaten:

Re: [PS40] Sortieren

Beitrag von kimmi »

Du könntest Quick- oder Shelsort nehmen und die Zeit gegen deinen Bubblesort messen. Bei 64 Werten sollten andere Sortieralgos bereits einen Gewinn bringen. Können deine Werte bereits sortiert in den Algorithmus laufen? Wenn ja: eher shellsort als quicksort nehmen. Und die Rekursion müsstest du dann durch eine Iteration ersetzen. Ist zwar etwas aufwändiger, ist aber bei korrekter Implementierung sogar noch etwas schneller, weil cachefreundlicher. Wie sich das bei einem Pixelshader verhält, kann ich dir nicht sagen. da fehlt mir die Erfahrung.

Gruß Kimmi
Jörg
Establishment
Beiträge: 296
Registriert: 03.12.2005, 14:06
Wohnort: Trondheim
Kontaktdaten:

Re: [PS40] Sortieren

Beitrag von Jörg »

Ich wuerde ein Merge-Sort mit 4er-Gruppen als kleinste Groesse verwenden.

for(i=0;i<16;++i) sort4(array + 4*i);
for(i=0;i<8;++i) merge(4,array + 8*i);
for(i=0;i<4;++i) merge(8,array + 16*i);
for(i=0;i<2;++i) merge(16,array + 32*i);
merge(32,array);

Brauchst keine Rekursion o.ae. und sollte fix sein, wenn du beim mergen binaer suchst.
Benutzeravatar
Zudomon
Establishment
Beiträge: 2170
Registriert: 25.03.2009, 08:20
Kontaktdaten:

Re: [PS40] Sortieren

Beitrag von Zudomon »

Quick-, Shell- und Merge-Sort sind gute Sortierverfahren. Aber mir macht Sorgen, dass ich unter Pixelshaderbedingungen nicht gut damit zurecht komme. Da das ja bei jedem Pixel ausgeführt werden muss, habe ich da nur minimalsten Speicher zur verfügung. Wobei das Mergesort recht vielversprechend aussieht.

Vielleicht könnte man auch rumtricksen. Der Wertebereich dieser maximal 64 Werte liegt etwa bei 0 - 1023 (Integer), wobei jede Zahl nur ein einziges mal vorkommt. Vielleicht könnte man da auch mit einer Art Hashing hinkommen, wobei es dabei wiederum nicht möglich ist, mal ebend ein Array aus 1024 Integerwerte zu deklarieren...
Benutzeravatar
kimmi
Moderator
Beiträge: 1402
Registriert: 26.02.2009, 10:42
Echter Name: Kim Kulling
Wohnort: Luebeck
Kontaktdaten:

Re: [PS40] Sortieren

Beitrag von kimmi »

Teste doch mal die verschiedenen Sortier-Algorithmen und profile sie unter deinen Bedingungen.

Gruß Kimmi
Benutzeravatar
Zudomon
Establishment
Beiträge: 2170
Registriert: 25.03.2009, 08:20
Kontaktdaten:

Re: [PS40] Sortieren

Beitrag von Zudomon »

Einfacher gesagt, als getan.

Ich wollte jetzt erstmal statt direkt den Shellsort die Vorstufe dazu, den Insertion-Sort einbauen. Aber da scheitere ich schon:

Code: Alles auswählen

  int i, j, key;  

  for (j=2; j<si; j++) {
    key = s[j];
    i = j - 1;
    while (i>0 && s[i] > key ) {
      s[i+1] = s[i];
      i--;
    }
    s[i+1] = key;
  }
Habe den Code im Grunde 1:1 von Wikipedia übernommen, aber es wird dennoch falsch sortiert.
Warum weiß der Geier.
Benutzeravatar
kimmi
Moderator
Beiträge: 1402
Registriert: 26.02.2009, 10:42
Echter Name: Kim Kulling
Wohnort: Luebeck
Kontaktdaten:

Re: [PS40] Sortieren

Beitrag von kimmi »

Kann es sein, daß der Pseudocode in der Wikipedia davon ausgeht, daß die Indices bei 1 und nicht bei 0 beginnen? Nur so ein Schuß aus der Hüfte.

Gruß Kimmi
EyDu
Beiträge: 95
Registriert: 24.08.2002, 18:52
Wohnort: Berlin
Kontaktdaten:

Re: [PS40] Sortieren

Beitrag von EyDu »

Bei so wenigen Elementen könnte man auch noch Min- oder Max-Sort benutzen. Interessant bei so wenigen Werten ist sicherlich auch ein hybrider Ansatz mit einem der bereits genannten Verfahren auf Teilbereichen und einem anschließenden Merge-Schritt. Das ließe sich auch einigermaßen parallelisieren.
Benutzeravatar
Schrompf
Moderator
Beiträge: 4179
Registriert: 26.02.2009, 00:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [PS40] Sortieren

Beitrag von Schrompf »

Aus reiner Neugier: Warum willst Du im Shader was sortieren? Die Performance dafür muss doch unterirdisch sein...
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.
Benutzeravatar
Zudomon
Establishment
Beiträge: 2170
Registriert: 25.03.2009, 08:20
Kontaktdaten:

Re: [PS40] Sortieren

Beitrag von Zudomon »

@Kimmi
Danke! Es lag wirklich daran, das der Algo da von 1 statt 0 ausgeht, da hatte ich garnicht drauf geachtet.

@EyDu
Ich bin für alles offen, was mir noch mehr speed bringt, sofern ich in der Lage bin, das umzusetzen. Wenn du mir sagst, was man da genau machen könnte...

@Schrompf
Ich möchte meine Fledermaus texturieren. Aber dafür brauch ich ja Texturkoordinaten. Die extern zu erstellen, während man das Modell selbst hinterher in dem Editor erstellen kann, finde ich etwas arm. Allerdings bin ich zu blöde, da einfach mal nen Texturatlas für ein Modell zu erstellen. Hab das jetzt einige Zeit versucht, aber es hat nur sehr mittelmäßig hingehauen. Selbst mit 1024² Textur hatte ich sehr undetaillierte Ergebnisse, mal abgesehen von Seams usw. Wobei ich unbedingt einen vollkommen automatisierten Texturatlas generieren wollte. Eine andere Lösung dafür wäre gewesen, über DX den Atlas zu erstellen, allerdings funktioniert das ja nur bei DX9 und dafür extra ein Device erstellen, das Modell erzeugen, Atlas erstellen und zurücklesen wollte ich nicht, vor allem, weil auch das als Modifikator laufen sollte.
Das nächste waren diese Octreetexturen. Allerdings ist die Quali da auch sehr bescheiden und der Overhead durch den Octree im Shader nicht zu knapp. Deswegen habe ich mir jetzt was neues überlegt, was es mir erlaubt, vollkommen auf einen Texturatlas zu verzichten. Man braucht auch nicht mehr extra eine Textur anzufertigen. Außerdem existiert dann keine Beschränkung mehr darin, wie hoch das maximale Texturdetail sein darf. Es wird weder Seams noch stretching geben. Das System funktioniert eigentlich schon recht gut, aber es sind noch ein paar Kleinigkeiten zu lösen. Die Textur lässt sich dann sogar in Echtzeit ändern.
Werde auf jeden Fall hinterher mal meine Ergebnisse zeigen, wobei ich befürchte, dass das heute nichts mehr wird :D
EyDu
Beiträge: 95
Registriert: 24.08.2002, 18:52
Wohnort: Berlin
Kontaktdaten:

Re: [PS40] Sortieren

Beitrag von EyDu »

Das erklären geht schnell: Angenommen du hast N zu sortierende Elemente, dann unterteilst du diese in k, möglichst gleich große, disjunkte Teilmengen B1, ..., Bk. Dann sortierst du jedes Bi (alle parallel) und fügst diese am Ende, wie bei Merge-Sort, zu einer sortierten Ergebnis zusammen. Wie du k wählst müsstest du experimentell bestimmen. Je größer k wird, desto mehr Parallelität erreichst du, der Overhead steigt natürlich ebenfalls. Sinnvoll scheint ebenfalls ein k=2^j, da man dann gut mergen kann.

Wie schnell es letzten Endes wird weiß ich nicht, die Ergebnisse würden mich aber interessieren.
whiteambit
Beiträge: 4
Registriert: 25.06.2009, 02:30
Benutzertext: TheWhiteAmbit

Re: [PS40] Sortieren

Beitrag von whiteambit »

Oft ist es ja so das man lediglich das größte Element braucht, und nur wenn eine bestimmte Bedingung nicht zutrifft (z.B. ZBuffer nicht verdeckt, was auch immer) braucht man das zweitgrößte Element etc. In so einem fall ist ein modifizierter bubble sort gut, mit dem man zunächst durch die erste iteration mal den größten wert rausfischt, und wenn das Ereignis zutraf braucht man nichts mehr machen. Sonst macht man das ganze mit dem zweitgrößten Wert etc. Wenn es eine Situation ist bei der mit 90% warscheinlichkeit die Bedingung bei den ersten paar elementen erfüllt ist kann sowas effizienter sein. Nur mal so ein Gedanke...
Haiaiai
Beiträge: 8
Registriert: 26.06.2009, 10:18

Re: [PS40] Sortieren

Beitrag von Haiaiai »

Da du nicht rekursiv arbeiten kannst wäre evtl Heapsort zu gebrauchen, läuft wie Quicksort im Durchschnitt in O( n log n ) und dabei auch im Worst-Case stabil (Quicksort kann bei ungünstigen Daten O(n²) brauchen). Meistens ist Heapsort jedoch etwas langsamer, weil es schlechter cached. Der Algorithmus verteilt seine Zugriffe aufs Datenfeld ständig über die gesamte Länge, wobei Quicksort (und auch Bubble, insert und mergesort) länger auf einem kleinen Bereich arbeiten.

Wahrscheinlich ist der Hybridansatz doch am besten. Insertionsort für Teilbereiche, dann Mergesort. Heapsort läßt sich nicht hybrid aufsetzen, da es die gesamte Ordnung erstmal umkrempelt.
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4019
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: [PS40] Sortieren

Beitrag von Chromanoid »

Sortiers doch lieber im Prozessor und übergebe es an den shader als Textur oder so, oder?
Könnte man nicht sonst auch mit einer Textur als Target sortieren? Also die Werte in eine 64x(Anzahl der Wertreihen) Textur packen und dann vielleicht eine Art Parallel Merge Sort Algorithmus drüberjagen? Als Blockgröße für 64 Werte ist glaube ich 8 am Anfang optimal... Immer Wurzel(n) glaube ich... muss man aber dann genau nachlesen ^^
Benutzeravatar
Zudomon
Establishment
Beiträge: 2170
Registriert: 25.03.2009, 08:20
Kontaktdaten:

Re: [PS40] Sortieren

Beitrag von Zudomon »

Der Vorschlag von Haiaiai klingt super... nur bin ich nun leider im Moment an andere Baustelle zu gange, so das ich das nicht ausprobieren kann. Außerdem haben mir ja viele angeraten, doch lieber den alternativen Weg der Texturierung zu benutzen, deswegen werde ich vorerst schauen, ob ich nicht den (da ich nun ja eh wieder DX9 mache) Textur Atlas von DirectX einbauen kann.
Chromanoid hat geschrieben:Sortiers doch lieber im Prozessor und übergebe es an den shader als Textur oder so, oder?
Vorsortieren funktioniert nicht, da die Projektionen vorher clusterisiert und in einem Octtree untergerbracht werden. Dadurch sind sie nach Positionen und nicht nach Renderreihenfolge sortiert. Im Shader muss dann zunächst im Octtree ermittelt werden für welchen Pixel welche Projektionen in Frage kommen und anschließend muss nach der Renderreihenfolge sortiert werden. Sonst könnte es passieren, dass mal die eine Projektion und mal die andere Projektion zuerst gezeichnet wird. Das kann man sich wie rendern ohne Z-Buffer vorstellen, wobei die Renderreihenfolge zufällig gewählt wird.
Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 14:27

Re: [PS40] Sortieren

Beitrag von eXile »

Haiaiai hat geschrieben:Der Algorithmus verteilt seine Zugriffe aufs Datenfeld ständig über die gesamte Länge, wobei Quicksort (und auch Bubble, insert und mergesort) länger auf einem kleinen Bereich arbeiten.

Wahrscheinlich ist der Hybridansatz doch am besten. Insertionsort für Teilbereiche, dann Mergesort. Heapsort läßt sich nicht hybrid aufsetzen, da es die gesamte Ordnung erstmal umkrempelt.
In irgendeiner Bibliothek (fragt mich bloß nicht welche...) habe ich Quicksort so implementiert gesehen, dass für weniger als 8 Elemente Insertionsort verwendert wurde, ansonsten Mergesort (d.h. bei den rekursiven Mergesortaufrufen wurde bei weniger als 8 Elementen auf Insertionsort umgestellt). Das müsste man eigentlich auch iterativ hinkriegen, nur weiß ich nicht, ob diese Sonderbehandlung für wenige Elemente auf der GPU nicht eher Zeit kostet, als Zeit bringt.
Haiaiai
Beiträge: 8
Registriert: 26.06.2009, 10:18

Re: [PS40] Sortieren

Beitrag von Haiaiai »

eXile hat geschrieben: In irgendeiner Bibliothek (fragt mich bloß nicht welche...) habe ich Quicksort so implementiert gesehen, dass für weniger als 8 Elemente Insertionsort verwendert wurde, ansonsten Mergesort (d.h. bei den rekursiven Mergesortaufrufen wurde bei weniger als 8 Elementen auf Insertionsort umgestellt). Das müsste man eigentlich auch iterativ hinkriegen, nur weiß ich nicht, ob diese Sonderbehandlung für wenige Elemente auf der GPU nicht eher Zeit kostet, als Zeit bringt.
Dann war das kein Quicksort, sondern Mergesort^^. Das mit dem Insertionsort ist allgemeine Praxis glaub ich, hab ich auch schon an verschiedenen Stellen gesehen.

Quicksort läßt sich nur iterativ auflösen, wenn man einen Stack hat, in den man Feldgrößen ablegt, geht also noch nicht. Bei Implementierung auf CPU empfiehlt es sich, eine der beiden Rekursionen iterativ aufzulösen, am besten die Seite mit mehr Elementen. Das garantiert dann immerhin eine Stacknutzung von <= (log n). Habs schon erlebt das Quicksort ohne diese Maßnahme nen Stacküberlauf produziert hat bei gerade mal n = 4000.
Antworten