An std::thread übergebenen Raw-Pointer löschen



  • @Rav1642 sagte in An std::thread übergebenen Raw-Pointer löschen:

    @Finnegan sagte in An std::thread übergebenen Raw-Pointer löschen:

    Ich empfehle eher einen std::vector<float> für anglesals einen manuell verwalteten C-Array-Pointer. Den kannst du bei Bedarf auch in einen Smartpointer packen oder auch moven (std::move), wenn du den Besitz an dem herumreichen willst.

    Es gibt zwei Gründe, weshalb ich mich dazu entschied: mein superschneller RadixSort sortiert nur auf Arrays (übergeben per Pointer und der Größe).

    Und wo ist da dein Problem mit einem std::vector<>? Dein Hauptproblem ist, daß Du nicht wirklich C++ kannst.

    auch

    @Rav1642 sagte in An std::thread übergebenen Raw-Pointer löschen:

    Zudem bin ich bisher davon überzeugt, dass das Tempo von vector plus "normalem" sort nicht reichen.

    stereoptics - Radix Tricks:

    My mergesort (from my class library) achieves about 12 sorts/sec on this test, approximately equivalent to the std::sort routine in Microsoft's implementation of the STL, distributed with Visual C++ (a quicksort, I believe.) Both of these implementations are considered incredibly well optimized.

    After all the above optimizations, the radix achieves 97 sorts/sec on this test, a quite amazing improvement.



  • @Swordfish sagte in An std::thread übergebenen Raw-Pointer löschen:

    Und wo ist da dein Problem mit einem std::vector<>? Dein Hauptproblem ist, daß Du nicht wirklich C++ kannst.

    Vielen Dank für deinen Beitrag. Ich habe nicht gerade behauptet, besonders gut in C++ zu sein. Wäre ich besonders gut, bräuchte ich wahrscheinlich keine Hilfe. Deine Antwort wirkt etwas passiv aggressiv auf mich. Ich hoffe, dass das nicht so gemeint war und freue mich auf Hilfestellungen.



  • @Rav1642 sagte in An std::thread übergebenen Raw-Pointer löschen:

    etwas passiv aggressiv auf mich. Ich hoffe, dass das nicht so gemeint war und freue mich auf Hilfestellungen.

    Hast du meinen Beitrag gelesen?

    Du sollst das so einfach nicht machen.



  • @Rav1642 sagte in An std::thread übergebenen Raw-Pointer löschen:

    Ich hoffe, dass das nicht so gemeint war und freue mich auf Hilfestellungen.

    std::vector<foo> bar;
    // ...
    &bar[0]; // da hast den pointer auf einen zusammenhängenden Speicherbereich
    bar.size();  // und da hast die Anzahl der Elemente.
    

    Vergiss rohe Pointer und new[]. Danke.

    Aber Dein Radix-Sort auf floating point values ist sowieso nicht schneller als std::sort()-Implementierungen in gängigen Standardlibraries. Wenn Du anderes behaupten willst dann miss.



  • Und apropos, ein Anfängerfehler, den ich auch des öfteren in einigen Foren gemacht habe:

    Wie gesagt, ich verwende SFML

    Musst Du nicht dreimal wiederholen und Links dazu schicken. Die Leute hier wissen, was das ist 😉 Sieht man schon im Code, das Du das nutzt.



  • Dieser Beitrag wurde gelöscht!


  • Jop. Und so langsam habe ich dann verstanden, das die tolle Idee von mir schon seit x Jahrhunderten existiert.



  • @Swordfish sagte in An std::thread übergebenen Raw-Pointer löschen:

    Aber Dein Radix-Sort auf floating point values ist sowieso nicht schneller als std::sort()-Implementierungen in gängigen Standardlibraries.

    Ich kann zumindest bestätigen, dass boost::spreadsort teilweise deutlich schneller ist, als MSVC std::sort.



  • @Mechanics

    @Rav1642 sagte in An std::thread übergebenen Raw-Pointer löschen:

    Es gibt zwei Gründe, weshalb ich mich dazu entschied: mein superschneller RadixSort sortiert nur auf Arrays (übergeben per Pointer und der Größe). Zudem bin ich bisher davon überzeugt, dass das Tempo von vector plus "normalem" sort nicht reichen.

    2.1.-Spreadsort:

    They are hybrids using both radix and comparison-based sorting, specialized to sorting common data types, such as integers, floats, and strings.
    [...]
    Unlike many radix-based algorithms, the underlying spreadsort algorithm is designed around worst-case performance.



  • @Rav1642 sagte in An std::thread übergebenen Raw-Pointer löschen:

    @manni66 sagte in An std::thread übergebenen Raw-Pointer löschen:

    Warum benutzt du nicht std::sort?

    Ich möchte ganz gerne den RadixSort nutzen, der eine Laufzeit von O(n * m) hat, wobei m fest 10 ist, so dass die Laufzeit in O(n) liegt.

    std::sort ist O(nlogn)\mathcal{O}(n\log n).

    logn\log n ist aber gerade die Anzahl an Bits, die du mindestens für die Schlüssel brauchst, damit diese überhaupt nn voneinander verschiedene Werte annehmen können.

    Wenn deine Schlüssellänge also maximal 10 Bits ist, wie du hier implizierst, dann kannst du eh nur maximal 2102^{10} voneinander verschiedene Schlüssel zum Sortieren haben (es sei denn, du erlaubst mehrfache Elemente mit dem selben Schlüssel). Dann ist logn10\log n \leq 10 und damit für dieses praktische Szenario effektiv ebenfalls konstant.

    Man könnte sogar argumentieren, dass ein O(nlogn)\mathcal{O}(n\log n) -Algorithmus für n210n \leq 2^{10} in O(1)\mathcal{O}(1) liegt, da er nie mehr als 21010=102402^{10}\cdot10=10240 Schritte benötigt.

    Das ist natürlich wenig hilfreich um die Laufzeit des Algorithmus für Probleme beliebiger Größe zu bewerten. Ich will hier nur deutlich machen, dass du dich nicht von dem O(n)\mathcal{O}(n) täuschen lassen solltest. Das heisst nicht automatisch, dass der Algorithmus für dein Problem auch tatsächlich schneller ist. Der betrachtet das Problem lediglich aus einer anderen Perspektive.

    @Finnegan sagte in An std::thread übergebenen Raw-Pointer löschen:

    Ich empfehle eher einen std::vector<float> für anglesals einen manuell verwalteten C-Array-Pointer. Den kannst du bei Bedarf auch in einen Smartpointer packen oder auch moven (std::move), wenn du den Besitz an dem herumreichen willst.

    Es gibt zwei Gründe, weshalb ich mich dazu entschied: mein superschneller RadixSort sortiert nur auf Arrays (übergeben per Pointer und der Größe). Zudem bin ich bisher davon überzeugt, dass das Tempo von vector plus "normalem" sort nicht reichen.
    Bezüglich std::move muss ich mich noch einmal einlesen, ich danke dir also für den Hinweis!

    Wie schon andere erwähnt haben, kannst du dir von einem std::vector-Objekt auch einen C-Array-Pointer geben lassen, wenn du den tatsächlich benötigen solltest (std::sort braucht den nicht).

    Mit std::move kannst du im Prinzip nur den internen Pointer auf das Array weiterreichen (ohne den gesamten std::vector kopieren zu müssen). Das ist so effizient wie einen rohen Pointer zu übergeben, allerdings mit dem Vorteil, dass das Ganze im std::vector mit seinem sauberen Interface verpackt bleibt (kein manuelles delete und sowas).

    @Finnegan sagte in An std::thread übergebenen Raw-Pointer löschen:

    Welches Problem möchtest du eigentlich mit der Sortierung lösen?

    Jetzt kommt die Besonderheit von SFML:
    SFML kennt VertexArrays, mit denen ich ausgehend von einer gemeinsamen Mitte (der Lichtquelle) Dreiecke erstellen kann, die alle an dieser Mitte hängen. Es ist wie bei Kreisen, die wie geschnittene Pizzen aus Triangles bestehen.

    Schon verstanden, dein Problem. Triangle Fan.

    Ich kann es umsetzen, aber mir ist die Performance sehr wichtig. Je besser dieses Lichtsystem läuft, desto weniger Einschränkungen habe ich an anderen Stellen. Da ich einen 144-Hertz-Monitor habe, bin ich ebenfalls etwas fps-geschädigt und hätte gerne den besten Weg, auch wenn ich weiß, dass ich möglicherweise noch nicht die beste Richtung eingeschlagen habe. Ich bin sehr bereit, weite Teile zu verwerfen, wenn mir etwas Besseres aufgezeigt wird.

    Ich denke, dass du die Leistungsfähigkeit moderner Computer unterschätzt. Doom 2 von 1994 hat z.B. ein ähnliches Verfahren verwendet um die Wände zu rendern. Und zwar mit einem Strahl für jede Pixelspalte. Das war selbst auf den Computern vor 26 Jahren schon ziemlich flott (auch wenn natürlich John Carmack ziemlich brilliant war, was gerade solche Optimierungen in Spielen anging). Da würde ich mir keinen allzu grossen Kopf drum machen. Für die paar Vertices und Lichtquellen die du in solchen 2D-Szenen wie in der von dir verlinkten Demo hast, wirst du da keinen Unterschied bemerken, wenn du da nicht etwas super-ineffizientes programmierst. Premature Optimization und so.

    Ich würde an der Stelle erst dann optimieren, wenn die Framerate tatsächlich zum Problem werden sollte. Dann weisst du auch besser, wo dein Code tatsächlich Performance-Probleme hat, und ich wette, dass es nicht der Sortieralgorithmus sein wird. Da wirst du dann lieber solche Optimierungen machen wollen wie z.B. diese Berechnung nicht 144 mal pro Sekunde durchzuführen, sondern z.B. nur dann, wenn z.B. eine Lichtquelle oder eine Wand bewegt wurde (nur dann ändert sich auch die Geometrie deines Triangle Fan) oder auch nicht mit allen Vertices für alle Lichtquellen, sondern nur in einem gewissen Falloff-Bereich des Lichtes. Licht reicht zwar physikalisch ewig weit, aber für praktische Computergrafik wird es ab einer gewissen Entfernung so schwach, dass man einfach sagen kann, dass der Lichtkegel da zuende ist - also alle Vertices nicht mit in die Berechnung einbezieht, die außerhalb des maximalen Ausbreitungsbereichs des Lichtes liegen.

    Ich würde gerne die GPU einbeziehen, habe dort angefangen zu lesen und habe das mit mehr Aufwand assoziiert. Vielleicht täusche ich mich. Das Lichtsystem sollte bis spätestens Ende des Monats stehen, lieber früher, damit ich nicht in Verzug gerate. Ich muss zugeben, dass ich die Sorge habe, mit GPU-Berechnungen zu viel Aufwand zu betreiben, welchen ich bereuen könnte.

    Ja, wenn du das noch nie gemacht hast und unter Zeitdruck stehst, dann mach besser erstmal mit deiner derzeitigen Idee weiter.

    Die Anzahl der Lichtquellen ist noch die große Frage. Ich wollte eigentlich mehrere einzelne Lichtquellen zu einer zusammenschließen, um die Schatten smooth zu bekommen, aber der aktuelle Ansatz ist dafür ungeeignet, da nach wie vor zu rechenintensiv. Es fehlen noch die Schnittpunktberechnungen und Spiellogik ist ebenfalls nicht implementiert.
    Bei wahrscheinlich übertriebenen 2000 Vertices und 12 Lichtquellen bin ich bei 37 fps (4770k@4,4GHz (4/8C), GTX 1070, Windows).
    700 Vertices, 8 Lichter machen 87 fps.
    100 Vertices, 50 Lichter machen 31 fps.

    Das ist mit deinem aktuellen Code gemessen? Da würde ich mal genau untersuchen, woran das liegt. 2000 Vertices und 12 Lichter macht 24.000 Vertex-Licht-Paare, sehe ich das richtig? 24.000 Einträge mit sowas wie std::sort zu sortieren ist eigentlich fast nix. Mich wundert, dass du da nur auf 31 fps kommst. Geh dem mal genauer auf den Grund (Profiler und so).

    Ansonsten schau nochmal was ich oben beschrieben habe: Du must die Lichtausbreitungs-Geometrie für eine Lichtquelle nur dann neu berechnen, wenn sich auch deren Position oder eine der Wände verändert haben und nicht mit jedem Frame. Und bedenke, dass das Licht ab einer gewissen Entfernung so schwach ist, dass es "praktisch nicht mehr da ist". Schau auch, ob das Problem nicht eher beim Rendering selbst liegt und die Funktionen, mit denen du die Szene zeichnest, vielleicht nicht die effizientesten für deinen Anwendungsfall sind.


Anmelden zum Antworten