-
Notifications
You must be signed in to change notification settings - Fork 4
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
DDP Benchmarks #20
Comments
Große Listen performen sehr schlecht. Ich habe eine Liste mit fast einer Millionen Elementen. Diese Elemente sind Texte der Länge ~100. Das hinzufügen von Elementen über die Kapazität hinaus bewirkt, wie ich gesehen habe, ein memmove. Also werden in meinem Fall bei jedem Insert ~100MB an Daten verschoben. Außerdem lösche ich Elemente vom Beginn der Liste. Auch dies bewirkt wieder einen memmove, der wieder ~100MB an Daten verschiebt. Mein Algotithmus, der ~7mio insertions und deletions ausführen soll ist auch nach 4 Stunden noch nicht fertig. |
Das ist leider kein Fehler der Listen Implementation, sondern liegt in der Natur von Vektoren (oder Array-Listen oder wie man sie auch nennen möchte). Da Vektoren zusammenhängend im Speicher liegen sind sie sehr Platz effizient, aber gerade beim Inserten/Löschen am Anfang sehr ineffizient, da die Daten allesamt kopiert werden müssen. Das Programm erstellt einen Vektor und fügt N Mal einen string der Länge 100 ans Ende an. Vektoren sind bei so großen Kapazitäten einfach die falsche Datenstruktur, bzw. häufiges Löschen und Einfügen am Anfang ist der falsche Algorithmus. Hier ein paar Vorschläge zur Verbesserung:
Eigentlich würde ich auch noch Vorschlagen eine Linked-List zu benutzen, aber das kann man mangels Referenz-Typen momentan (noch) nicht in DDP implementieren. Dein Vorschlag die Kapazität Prozentual zu erhöhen ist prinzipiell gut, aber bringt nichts beim Löschen bzw. Inserten, denn dabei sind die Kopien (durch die zusammenhängende Struktur notwendig) nicht vermeidbar. |
@Magi3r hier sind auch nochmal Benchmarks zum Inserten am Ende von DDP Listen: Wie man sieht ist das ziemlich effizient. Code:
|
Ja, ich kann meinen Code definitiv noch deutlich optimieren. (Zum Beispiel keine Texte sondern nur Zahlen speichern.) |
Es wäre interressant Benchmarks von DDP-Code zu haben, insbesondere von Code der viel mit Listen arbeitet.
Das würde es ermöglichen herauszufinden welche Stellen im Kompilierer/in der Listen Implementation noch verbessert werden sollten.
Natürlich geht es bei DDP nicht um Performance, aber es schadet trotzdem nicht offensichtliche große Probleme zu beheben.
The text was updated successfully, but these errors were encountered: