Effizienz des Speichermanagers

[Dejan Vu]

Zitat von Patito:

- Wegen der Messtoleranz sind 1000000 Nodes fast schon zu wenig...

Wiederhole die Tests einfach ein paar Mal. Es geht hier eh nur um relative Performance (wer ist schneller?).

Wenn Du weißt, das 1 Mio Einträge ungefähr 100ms brauchen, dann misst Du einfach 10 Mio / N mal, wobei N die Anzahl der Samples sind. Dann bist Du pro Test bei ca. 1 Sekunde und im sicheren Bereich (von wegen Messfehler etc.)

[Namenloser]

Zitat von Dejan Vu:

Ich würde noch vergleichen, wie sich die Strukturen bei kleineren Datenmengen verhalten. Hier macht sich der generelle Overhead stärker bemerkbar. Bei sehr kleinen Listen ist ein einfaches sortiertes Array oft schneller als ein Baum, weil eigentlich kein Overhead vorhanden ist.

Man muss wirklich aufpassen ob und wann man diese 'Ungetüme' (300+ Zeilen für eine 'einfache Liste' ist schon happig) verwenden sollte und wann nicht.

Ich hatte deswegen auch erst überlegt, einfach ein Array zu nehmen. Aber dann kam der Perfektionist in mir wieder durch und dachte sich, es wäre doch schön, wenn trotzdem garantiert wäre, dass die asymptotische Laufzeit nicht aus dem Ruder läuft. Hab mir dann erst überlegt, ob man das Array vielleicht irgendwie erweitern könnte, aber habe dann nach einer Weile gemerkt, dass ich eigentlich gerade Bäume neu erfinde... und dann habe gedacht, okay, dann kann ich auch gleich die richtigen Dinger implementieren. Dachte anfangs auch nicht, dass das so aus dem Ruder läuft, denn auf den Folien sah das nach einem sehr einfachen Konzept aus. Ist es ja eigentlich auch. Aber wenn man es dann implementiert, tun sich doch plötzlich Sonderfälle auf, die man durch bloßes Draufschauen niemals gesehen hätte... und auf einmal ist der Code viel länger als man gedacht hätte.

Zum Glück sind bei Pascal die Kompilierzeiten kurz, da kann man sich solche „Ungetüme“ wenigstens noch leisten...

[JamesTKirk]

Zitat von Patito:

FPC 2.7.1 -O1

...

FPC 2.7.1 -O3

Blöde Frage: hast du verwendeten Units (insbesondere den AVLTree aus der FCL) jedesmal vom Source kompiliert? Wenn nicht solltest du zumindest die AVLTree Unit kopieren, weil standardmäßig werden die Units in Packages (und die RTL sowie der Compiler) mit -O2 kompiliert.

Kleine Info noch nebenbei: in 2.7.1 gibt as auch noch -O4 und für -O3 könntest du noch -Oodeadvalues(damit fehlt nur noch das Field Reordering für -O4) und -Oodeadstore bzw. für -O4 nur -Oodeadstore noch einschalten (eine aktuelle 2.7.1 vorausgesetzt ). Wenn du -Oodeadstore, -Oodeadvalues und -Ooconstprop unter -O- bis -O2 einsetzen willst, musst du auch noch -Oodfa aktivieren.

Gruß,
Sven

[Dejan Vu]

Zitat von Namenloser:

Zum Glück sind bei Pascal die Kompilierzeiten kurz, da kann man sich solche „Ungetüme“ wenigstens noch leisten...

Na ja. Mein Compiler kompiliert nur das, was ich geändert habe.

Was ich meinte war: Wenn eine Datenstruktur bei 10 Mio Einträgen wunderbar performant ist, aber mein Anwendungsfall nur 10 Elemente beinhaltet (das aber 1 Mio x pro Sekunde) muss man sich 2x überlegen, ob meine Datenstruktur die geeignete ist.

Compilerzeiten und Dateigrößen sind da (für mich) zweitrangig.

Boyer-Moore z.B. ist bekanntermaßen der schnellste Stringmatcher. Aber nur bei großen Alphabeten und langen zu suchenden Strings in noch längeren Zeichenketten.

[Patito]

[QUOTE=JamesTKirk;1255922]

Zitat von Patito:

FPC 2.7.1 -O1

...

FPC 2.7.1 -O3

Blöde Frage: hast du verwendeten Units (insbesondere den AVLTree aus der FCL) jedesmal vom Source kompiliert? Wenn nicht solltest du zumindest die AVLTree Unit kopieren, weil standardmäßig werden die Units in Packages (und die RTL sowie der Compiler) mit -O2 kompiliert.

Sieht ganz danach aus. Mit -O3 sollte es ja eigentlich nicht langsamer werden.
Ich habe die Unit jetzt mal ins Projekt reingenommen:

FPC 2.7.1 -O1
AVL Tree
AL (1000000)I: 234 L: 141 R: 156
DL (1000000)I: 202 L: 156 R: 156
RD (1000000)I: 656 L: 530 RH: 374 RIH: 437

FPC 2.7.1 -O3
AVL Tree
AL (1000000)I: 203 L: 94 R: 109
DL (1000000)I: 171 L: 94 R: 125
RD (1000000)I: 577 L: 436 RH: 328 RIH: 390

Das sollte jetzt passen. -O4 klingt interessant... mal schauen...

[BUG]

Zitat von Dejan Vu:

Wenn eine Datenstruktur bei 10 Mio Einträgen wunderbar performant ist, aber mein Anwendungsfall nur 10 Elemente beinhaltet (das aber 1 Mio x pro Sekunde) muss man sich 2x überlegen, ob meine Datenstruktur die geeignete ist.

Jup, das wird in der C++ Gemeinde auch gerne diskutiert. Alles was als gesamte Collection in eine Speicherseite passt, soll in in einem (sortierten) Vektor ganz gut aufgehoben sein.
Lokalität und wenig Speicherverwaltung FTW

[Namenloser]

Eine Speicherseite (4096 Bytes) erscheint mir recht viel. Bei der Größe würde es mich doch wundern, wenn ein Baum nicht schneller wäre. Ich kann mir vorstellen, dass Arrays bis ~100 oder vielleicht 200 Elemente (sagen wir mal Ints) überlegen sind.

[BUG]

Naja, wenn man etwas schielt, ist die binäre Suche in einem sortierten Vector/Array eine Suche in einem Binärbaum. Damit hat man maximal log_2(4096) = 12 Schritte, um einen Eintrag zu finden.
Den Vorteil hat man dann aber nur beim Suchen, beim Einfügen/Löschen können Kopieroperationen teuer werden.

Dabei kommt es natürlich auch darauf an, wie die anderen Datenstrukturen verwaltet werden.
Ein Baum, der durch seine Verteilung im Speicher auch nur einen Pagefault mehr auslöst, sollte dadurch für mostly-read-Fälle deutlich unattraktiver werden

[Namenloser]

Das Suchen ist wohl auch eher nicht das Problem. Aber das Einfügen und Löschen eines Elements ist beim Array O(n), weil die Elemente im Speicher umkopiert werden müssen.

[Dejan Vu]

Zitat von Namenloser:

weil die Elemente im Speicher umkopiert werden müssen.

... was dann widerum erstens ein ASM Befehl und zweitens bei kleinen Arrays im Cache und drittens in wenigen Takten, also mitnichten unbedingt so viel Langsamer ist. Denn während das kleine Array -schwupps- kopiert wurde, muss ja beim Baum vom Speichermanager ein Speicherblock angefordert und diverse Zeiger umgebogen werden. Unterm Strich u.U. mehr Takte also so ein hurtiges Copy.

"Big Oh ist nicht alles. Es gibt auch noch diese häßliche Konstante"