Effizienz des Speichermanagers

**BUG**

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.

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"

**BUG**

Zitat von Dejan Vu:

Denn während das kleine Array -schwupps- kopiert wurde

Ich sehe es ja ein, mit 4kB habe ich hoch gegriffen

Aber es merkt sich gut als obere Grenze und im Ernstfall muss man eh messen.

Effizienz des Speichermanagers

AW: Effizienz des Speichermanagers

AW: Effizienz des Speichermanagers

AW: Effizienz des Speichermanagers

AW: Effizienz des Speichermanagers

AW: Effizienz des Speichermanagers

AW: Effizienz des Speichermanagers

Forumregeln

Namenloser Registriert seit: 7. Jun 2006 Ort: Karlsruhe 3.724 Beiträge FreePascal / Lazarus	#2 AW: Effizienz des Speichermanagers 17. Apr 2014, 20:19 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.
	Zitat

Namenloser Registriert seit: 7. Jun 2006 Ort: Karlsruhe 3.724 Beiträge FreePascal / Lazarus	#4 AW: Effizienz des Speichermanagers 17. Apr 2014, 21:25 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.
	Zitat

BUG Registriert seit: 4. Dez 2003 Ort: Cottbus 2.094 Beiträge	#6 AW: Effizienz des Speichermanagers 17. Apr 2014, 22:17 Zitat von Dejan Vu: Denn während das kleine Array -schwupps- kopiert wurde Ich sehe es ja ein, mit 4kB habe ich hoch gegriffen Aber es merkt sich gut als obere Grenze und im Ernstfall muss man eh messen.
	Zitat