Zugriffsgeschwindigkeit RAM

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo, ich implementiere gerade eine verkettete Liste aus C+±Objekten. Dabei habe ich mir überlegt, dass ich das Element auf das zuletzt zugegriffen wurde nach vorne bringe (Move to Front-Strategie) um die Suchgeschwindigkeit zu erhöhen.
Nun ist meine Frage ob so eine wilde umverpointerung Performanceprobleme bringt. Also auf gut deutsch gesagt. Macht es einen Unterschied ob ich Speicherzellen die aufeinanderfolgen oder nah beieinander sind auslese oder wie ein Verrückter im RAM rumspringe.

MfG Bruno

#2

Hallo, ich implementiere gerade eine verkettete Liste aus
C+±Objekten. Dabei habe ich mir überlegt, dass ich das
Element auf das zuletzt zugegriffen wurde nach vorne bringe
(Move to Front-Strategie) um die Suchgeschwindigkeit zu
erhöhen.
Nun ist meine Frage ob so eine wilde umverpointerung
Performanceprobleme bringt. Also auf gut deutsch gesagt. Macht
es einen Unterschied ob ich Speicherzellen die
aufeinanderfolgen oder nah beieinander sind auslese oder wie
ein Verrückter im RAM rumspringe.

Die Frage ist nicht pauschal zu beantworten. Grundsätzlich ist es ratsam Datenstrukturen nicht wild über den gesamten Speicher zu verteilen, da viele Systeme zusammenhängende Speicherbereiche cachen. Eine Umverzeigerung ist i.A. nicht schädlich (vorausgesetzt, Konsistenz der Daten bleibt gewahrt) und solange Du die Datenstruktur nicht neu allokierst und kopierst (Stichwort Fragmentierung) sondern nur neu verzeigerst sollte es keine Performanceprobleme geben.
Wenn Deine Zugriffsstrategie durch das Neuverzeigern optimaler wird, ist es durchaus ratsam sowas zu machen.

Aber mal eine andere Frage: Warum verwendest Du nicht die STL (Standard Template Library)?
Die Implementierung der verschiedenen Datenstrukturen ist dort recht gut und perfomant und vor allem generisch gelöst.

Klaus

#3

Aber mal eine andere Frage: Warum verwendest Du nicht die STL
(Standard Template Library)?
Die Implementierung der verschiedenen Datenstrukturen ist dort
recht gut und perfomant und vor allem generisch gelöst.

Sorry, davon hab ich null Ahnung. Compiliert mir das jeder C+±Compiler ohne irgendwelche .libs oder so? Auf Linux und Windows? Und wie verwende ich das Zeug dann?

Irgendwie is es auch der Spieltrieb *g* aber das Risiko dass ich irgendn Speicherloch einbau is natürlich auch vorhanden, vor allem weil das Ding ständig laufen soll, also darf ich keine Objecte vergessen zu löschen.

#4

Hi Bruno :wink:))

Normalerweise sollte man stets möglichst dicht zusammenhängende Speicherbereiche verwenden, damit first bzw. second level caches der CPU effektiv genutzt werden können.

In deinem Fall ist es aber nun so, dass du ohne MTF-Strategie (Move To Front) die gesamte Liste abklappern müsstest, bis du das passende Objekt gefunden hast. Im Mittel wären das n/2 Zugriffe, wenn n die Größe deiner verketteten Liste ist. Durch die MTF-Strategie reduziert sich dies drastisch, weil sich häufig benutzte Einträge weiter vorne ansammeln. MTF ist die bevorugte Strategie bei sog. selbstorganisierenden linearen Listen.

Selbst ohne MTF hast du doch das Problem, dass deine einzelnen Listenelemente relativ wild im Speicher verteilt sind. Jedenfalls aus dem Blickwinkel einer sinnvollen Cache-Strategie der CPU …

cu Stefan.

#5

Danke für die Tips,

ich bin jetzt mal soweit mit der grundlegenden Implementierung durch. So ganz sicher war ich mir nicht ob mein Code hunterprozentig richtig ist, aber ich glaube doch dass es passt. habe mal eine Liste mit 5 Elementen erstellt, dann ein paar wahllose Zugriffe auf irgendwelche Elemente und am Ende in absteigender Reihenfolge zugegriffen und es sah im Debugger so aus, als ob die Liste wieder so war wie am Anfang.

Das mit dem Move To Front habe ich aus der Informatikvorlesung im Gehirn behalten, gar nicht so unnütz was man da lernt *g*

Ich glaube die Implementierung ist jetzt ziemlich schnell, ok vielleicht hätt ich es mit ein paar weniger if’s schaffen können, da bin ich mir nicht so sicher, aber im Grunde bin ich soweit zufrieden.

Übrigens echt interessant was es da für Probleme geben kann. Z.b. war das Aufbauen der Liste durch Anhängen an die Liste anfangs unerträglich langsam, weil er natürlich jedesmal von vorne anfangen musste und alle Elemente bis zum letzten abklappern bis er anfügen kann. Jetzt habe ich noch einen Pointer auf das letzte Element eingeführt, wo ich dann direkt anhängen kann. braucht halt ein wenig mehr Speicher, aber das macht es wirklich nicht aus, ich habe meine Liste jetzt auch bidirektional verkettet, dadurch ist meine Implementierung einfacher (weil ich nur ein Element suchen brauche und dann davon auf das Element davor auch direkt zugreifen kann) wenn auch evtl. (ich hoffe nur unwesentlich) langsamer geworden.

MfG Bruno