DDP Benchmarks

[bafto]

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.

[Magi3r]

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. Vielleicht könnte man die Kapazität, statt immer um 1 zu erhöhen, prozentual zur momentanen Kapazität erhöhen? Also so in der Art: Kapazität zu 80% ausgelastet -> Kapazität um 30% erhöhen Kapazität zu 50% ausgelastet -> Kapazität um 30% reduzieren

[bafto]

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. Vielleicht könnte man die Kapazität, statt immer um 1 zu erhöhen, prozentual zur momentanen Kapazität erhöhen? Also so in der Art: Kapazität zu 80% ausgelastet -> Kapazität um 30% erhöhen Kapazität zu 50% ausgelastet -> Kapazität um 30% reduzieren

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.

Hier mal ein Beispiel in C++:

Das Programm erstellt einen Vektor und fügt N Mal einen string der Länge 100 ans Ende an. Danach löscht es N Mal das vorderste Element. Sehr grob geschätzt vervierfacht sich die Dauer wenn sich N verdoppelt. Hochgerechnet würden die 7Mio Elemente dann etwa 13 Stunden brauchen, bis alle gelöscht sind. (Die Mathe ist hier alles nur so Pi-mal-Daumen, aber auf jeden Fall dauert es sehr lange da 7Mio halt eine ziemlich große Zahl ist)

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:

• Wenn du weißt wie groß die Liste am Ende wird, dann pre-allocate sie (in DDP Die Text Liste t ist 7000000 Mal "".) und arbeite mit Indexen
• Anstatt das Erste Element jedes Mal zu löschen könntest du vielleicht einfach einen Start-Index benutzen. Wenn du das Erste Element löschen möchtest erhöht sich dieser einfach um 1.
• Wenn möglich nicht alle Daten in eine Liste packen und im ganzen bearbeiten, sondern in Paketen abfertigen. (der Vorschlag könnte aber auch Quatsch sein, ich kenne das Problem nicht, was du lösen willst)

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. Die Performance beim simplen am-Ende-Anfügen ist von DDP Listen gar nicht mal so schlecht (das benchmarke ich gleich aber auch nochmal).

[bafto]

@Magi3r hier sind auch nochmal Benchmarks zum Inserten am Ende von DDP Listen:

Wie man sieht ist das ziemlich effizient. Bloß beim Inserten/Löschen am Anfang wirds dann langsam durch die Kopien.

Code:

Binde "Duden/Ausgabe" ein.
Binde "Duden/Listen" ein.
Binde "Duden/Zeit" ein.

Die Zahlen Liste N ist eine Liste, die aus 10, 100, 1000, 10000, 100000, 1000000, 2000000, 7000000 besteht.
Die Zahl max ist die Länge von ((N an der Stelle (die Länge von N)) als Text).
Der Text t ist "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".

Für jede Zahl i von 1 bis 5, mache:
    Schreibe '\n'.
    Schreibe "N:        ".
    Für jede Zahl n in N, mache:
        Der Text n_t ist n als Text.
        Schreibe ' ' max minus die Länge von n_t plus 3 Mal. 
        Schreibe n_t.
        Schreibe " ".

    Schreibe "\nText:     ".
    Für jede Zahl n in N, mache:
        Die Zahl start ist die Millisekunden seit Programmstart.
        Die Text Liste vec ist eine leere Text Liste.
        Für jede Zahl i von 1 bis n, mache:
            Füge t an vec an.
        Die Zahl dauer ist die Millisekunden seit Programmstart minus start.
        Schreibe ' ' max minus (die Länge von (dauer als Text) minus 1) Mal.
        Schreibe (dauer als Text).
        Schreibe "ms ".

[Magi3r]

Ja, ich kann meinen Code definitiv noch deutlich optimieren. (Zum Beispiel keine Texte sondern nur Zahlen speichern.) Allerdings ist mir bei meinem naiven Ansatz trotzdem aufgefallen, wie langsam das alles ging. Tatsächlich gefällt mir die Idee mit einer Variable, die den Index speichert. Das spart dann die Lösch-Operationen ein.