 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Andreas Volz
Guest
|
 Posted: Fri Apr 21, 2006 2:06 pm Post subject: Cache Implementierung - map |
 |
|
Hi,
ich habe folgende Klasse in einer Bibliothek:
class Target : public std::map <int, Vector3f>
{
private:
....
public:
bool load (const std::string& filename);
bool save (const std::string& filename);
};
Ein Vector3f ist einfach eine Klasse mit x/y/z und den zugehörigen
Operatoren.
Hat in der Vergangenheit gut funktioniert. Jetzt es sich aber gezeigt,
dass ich am Programmstart relativ viele "Targets" laden muss. Es sind
mehrere Megabyte ASCII Daten und der Start des Programms dauert dadurch
einige Sekunden je nach Geschwindigkeit des Rechners. Es werden jedoch
sehr viele dieser Daten erst während des Programmablaufs oder sogar
überhaupt nicht benötigt. Allerdings möchte ich das Programms nicht mit
Ladelogik dahingehend versehen. Meine aktuelle Idee ist es eine Art
"Cache" zu implementieren. Die Klasse bekommt ein Flag die anzeigt ob
es physisch geladen wurde oder nicht. Die Datei wird also einmalig erst
beim ersten Zugriff auf den Inhalt von der Platte gelesen. Das würde
sowohl die Startzeit, als auch den Speicherverbrauch reduzieren.
Meine Frage ist wie ich das am besten mit der map umsetze. Vielleicht
wäre es im Design besser gewesen nicht von einer map abzuleiten,
sondern Target eine map besitzen zu lassen. Dann hätte dieser
Mechanismus z.B. in einer getDataMap() Funktion stecken können. So sehe
ich keine andere Lösung als alle Zugriffsmöglicheiten der map mit
einer eigenen Implementierung zu überschreiben und zu prüfen ob der
Inhalt schon geladen wurde.
Gibt es andere Ideen wie man es realisieren könnte?
Gruß
Andreas
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
 |
Marcel Müller
Guest
|
| Posted: Fri Apr 21, 2006 7:06 pm Post subject: Re: Cache Implementierung - map |
|
|
Andreas Volz wrote:
| Quote: | class Target : public std::map <int, Vector3f
{
private:
...
public:
bool load (const std::string& filename);
bool save (const std::string& filename);
};
Ein Vector3f ist einfach eine Klasse mit x/y/z und den zugehörigen
Operatoren.
Hat in der Vergangenheit gut funktioniert. Jetzt es sich aber gezeigt,
dass ich am Programmstart relativ viele "Targets" laden muss. Es sind
mehrere Megabyte ASCII Daten und der Start des Programms dauert dadurch
einige Sekunden je nach Geschwindigkeit des Rechners. Es werden jedoch
sehr viele dieser Daten erst während des Programmablaufs oder sogar
überhaupt nicht benötigt. Allerdings möchte ich das Programms nicht mit
Ladelogik dahingehend versehen. Meine aktuelle Idee ist es eine Art
"Cache" zu implementieren. Die Klasse bekommt ein Flag die anzeigt ob
es physisch geladen wurde oder nicht. Die Datei wird also einmalig erst
beim ersten Zugriff auf den Inhalt von der Platte gelesen. Das würde
sowohl die Startzeit, als auch den Speicherverbrauch reduzieren.
|
Von der Sache her ist die Überlegung natürlich nicht verkehrt, aber der
Schuss könnte auch gut und gerne nach hinten losgehen, nämlich dann,
wenn die Daten statt der Reihe nach nun völlig durcheinander geladen
werden müssen. Bei diesem Zugriffsmuster sind die Hardware-Caches
bekanntermaßen unwirksam und vor allem Festplattenzugriffe um ein
vielfaches langsamer.
Wenn man da Geschwindigkeit hereinbringen will, muss man die zu
erwartenden Zugriffsmuster auf den Cache schon genauer unter die Lupe
nehmen.
- Wie sind die Items im Definitionsbereich der map verteilt?
Gibt es Häufungen oder sind die Schlüssel völlig zufällig?
-> Ist map überhaupt eine geeigneter Container? Der Overhead ist
bei so kleinen Objekten beträchtlich. Der Aufbau der Baumstruktur
aufwendig. Alternativen: hash_map oder sortierter vector.
- Welche Items werden notwendigerweise zusammen benötigt?
-> Cache-Lines bilden, die auf einen Schlag geladen werden.
- Wie groß ist der Overhead der verzögerten Ladung?
Lohnt das überhaupt? Oder ist es besser, den Ladevorgang zu
optimieren?
- Wird auf die Objekte sehr oft zugegriffen?
-> Kommt es eher auf die Lade- oder die Zugriffszeit an?
- Was ist mit Fehlermeldungen, die jetzt später auftreten?
Kann das Programm sinnvoll damit umgehen, wenn zu einem späteren
Zeitpunkt ein Gefordertes Item nicht geladen werden kann?
- Kann man nicht die ASCII-Daten schon Verarbeitungsfreundlich
gestalten, also z.B. sortieren? Dann könnte man das ganze Ding
sequentiell in einen vector laden und darauf per binary search
zugreifen. Das halbiert den Speicherbedarf gegenüber der map auch
bestimmt um die Hälfte. Und die Ladezeit dürfte minimal ausfallen,
wenn man die erforderliche Vektorgröße vorher kennt.
Marcel
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
Christoph Kliemt
Guest
|
| Posted: Fri Apr 21, 2006 9:25 pm Post subject: Re: Cache Implementierung - map |
|
|
Hallo!
Andreas Volz <usenet-spam-trap (AT) brachttal (DOT) net> writes:
| Quote: | Hi,
ich habe folgende Klasse in einer Bibliothek:
class Target : public std::map <int, Vector3f> { private: ... public:
bool load (const std::string& filename);
bool save (const std::string& filename); };
|
Nein, Du willst nicht von std::containern erben. Es sei denn, Du
stehst auf Schusslöchern im Fuss.
[...]
| Quote: | Meine aktuelle Idee ist es eine Art "Cache" zu implementieren. Die
Klasse bekommt ein Flag die anzeigt ob es physisch geladen wurde
oder nicht. Die Datei wird also einmalig erst beim ersten Zugriff
auf den Inhalt von der Platte gelesen. Das würde sowohl die
Startzeit,
|
Startzeit sehe ich ein.
| Quote: | als auch den Speicherverbrauch reduzieren.
|
Das jetzt nicht wirklich.
| Quote: | Meine Frage ist wie ich das am besten mit der map umsetze. Vielleicht
wäre es im Design besser gewesen nicht von einer map abzuleiten,
sondern Target eine map besitzen zu lassen.
|
Genau.
| Quote: | Dann hätte dieser Mechanismus z.B. in einer getDataMap() Funktion
stecken können. So sehe ich keine andere Lösung als alle
Zugriffsmöglicheiten der map mit einer eigenen Implementierung zu
überschreiben und zu prüfen ob der Inhalt schon geladen wurde.
|
Minderprickelnd. Aber im Prinzip hast Du die Lösung ja beschrieben,
dass die map ein member deiner Klasse ist. Normalerweise reichtst Du
dann die nötigen Operationen an die Map weiter, und bei Bedarf werden
die Zugriffe über eigene Methoden "passend gemacht".
hth,
Christoph
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
Andreas Volz
Guest
|
| Posted: Sat Apr 22, 2006 2:06 pm Post subject: Re: Cache Implementierung - map |
|
|
Am Fri, 21 Apr 2006 20:53:53 +0200 schrieb Marcel Müller:
| Quote: | Von der Sache her ist die Überlegung natürlich nicht verkehrt, aber
der Schuss könnte auch gut und gerne nach hinten losgehen, nämlich
dann, wenn die Daten statt der Reihe nach nun völlig durcheinander
geladen werden müssen. Bei diesem Zugriffsmuster sind die
Hardware-Caches bekanntermaßen unwirksam und vor allem
Festplattenzugriffe um ein vielfaches langsamer.
|
Ich hab auch einen kleinen Fehler gemacht. Die Klasse Target soll immer
ganz geladen werden. Das ist die Struktur, welche als Cache dienen soll:
typedef map <string, Target> TargetMap;
Aber an der Problematik ändert sich dadurch wenig.
| Quote: | Wenn man da Geschwindigkeit hereinbringen will, muss man die zu
erwartenden Zugriffsmuster auf den Cache schon genauer unter die Lupe
nehmen.
|
Also ich gehe jetzt von TargetMap aus. Das Target muss immer ganz
geladen werden...
| Quote: | - Wie sind die Items im Definitionsbereich der map verteilt?
Gibt es Häufungen oder sind die Schlüssel völlig zufällig?
|
Der Schlüssel (string) kann eigentlich beliebig gewählt werden. In
Realität sind es aber Einträge der Art "Verzeichnis/Datei" wobei
natürlich der vordere Verzeichnisteil meist mehrfach vorkommt.
Vielleicht wäre es auch ein Idee zu verhindern, dass beliebige Strings
genutzt werden können und alles in einem Baum abzulegen. Wobei ich dann
auch gleich die reale Verzeichnisstruktur nutzen könnte. Ich wollte
mich eben davon lösen.
| Quote: | -> Ist map überhaupt eine geeigneter Container? Der Overhead ist
bei so kleinen Objekten beträchtlich. Der Aufbau der Baumstruktur
aufwendig. Alternativen: hash_map oder sortierter vector.
|
hash_map hab ich auch schon überlegt. Sortierter Vektor geht nicht,
weil die Reihenfolge definiert ist. Wobei ich das nochmal überlegen
müsste. Es sind momentan etwa 1000 Einträge. Ich vermute mal das
Maximum wird höchstens bei 2000-3000 liegen.
| Quote: | - Welche Items werden notwendigerweise zusammen benötigt?
|
Wie schon gesagt, das mit Target war ein Fehler. Es wird immer ein
ganzes Target aus TargetMap benötigt.
| Quote: | -> Cache-Lines bilden, die auf einen Schlag geladen werden.
- Wie groß ist der Overhead der verzögerten Ladung?
|
Das verstehe ich beides nicht ganz.
| Quote: | Lohnt das überhaupt? Oder ist es besser, den Ladevorgang zu
optimieren?
|
Ich hab natürlich schon mit binären Daten gearbeitet. Damals mit der
Idee die Datengröße zu verringern. Hat etwa eine Ersparnis von 50%
gebracht. Ich hab mich dann dagegen entschieden wegen der Big-Endian/
Little-Endian Komplexität. Bezüglich Ladegeschwindigkeit hab ich das
nicht untersucht. Könnte ich nochmal testen. Die ASCII-Daten sind aber
sehr einfach formatiert. Beispiel:
-8.180817,0.704855,4.918237
-8.162949,0.671900,4.963268
-8.161950,0.737917,4.945174
-8.162560,0.671539,4.945185
....
Das ganze lese ich mit sscanf ein. Vielleicht lässt sich das noch
optimieren. Bei der Masse an Dateien und Schleifendurchläufen würde da
jede Micro-Optimierung vielleicht schon etwas bringen.
| Quote: | - Wird auf die Objekte sehr oft zugegriffen?
|
Gemischt. Es hängt vom Nutzer und seinem Arbeitsverhalten im Programm
ab. Wobei ich gerade die Datenstruktur nochmal überdenke. Der Zugriff
auf die einzelnen Elemente von Target sind meist so im Verhältnis 1:100
im Gegensatz zu der Häufigkeit von TargetMap. Soll heißen ich greife
auf eine Element von TargetMap zu und danach 100x auf Target.
Ich müsste mal messen ob da eine Optimierung bei Target nicht mehr Sinn
als bei dem Zugriff auf TargetMap. Soll heißen vielleicht kann ich
tatsächlich alle Maps zu Vektoren machen. Wenn ich mir meinen
Algorithmus so ansehe könnte ein Vektor auch funktionieren. Eigentlich
durchlaufe ich ein Target (Map) eh nur mit einem Iterator.
Der Algorithmus und die Datenstruktur ist evolutionär entstanden. Da
ist natürlich nicht immer alles perfekt! Einiges müsste ich nochmal
überdenken.
| Quote: | -> Kommt es eher auf die Lade- oder die Zugriffszeit an?
|
Die Zugriffszeiten sind eher wichtig.
| Quote: | - Was ist mit Fehlermeldungen, die jetzt später auftreten?
|
Zum Beispiel bei illegalen Datenformaten? Ja, das hab ich auch schon
überlegt. Exceptions wollte ich aus Geschwindigkeitsgründen nicht
nutzen.
| Quote: | Kann das Programm sinnvoll damit umgehen, wenn zu einem späteren
Zeitpunkt ein Gefordertes Item nicht geladen werden kann?
|
Das ist tatsächlich ein ungelöstes Problem. Ich hätte für diesen Fall
einfach "leere" Objekte geliefert.
| Quote: | - Kann man nicht die ASCII-Daten schon Verarbeitungsfreundlich
gestalten, also z.B. sortieren? Dann könnte man das ganze Ding
sequentiell in einen vector laden und darauf per binary search
zugreifen. Das halbiert den Speicherbedarf gegenüber der map auch
bestimmt um die Hälfte. Und die Ladezeit dürfte minimal ausfallen,
wenn man die erforderliche Vektorgröße vorher kennt.
|
Hm, vielleicht sollte ich wirklich nochmal auf die Ebene von
Zeitmessungen gehen und einige Implementierungen real vergleichen. Aber
danke schon mal für die Anregungen bisher.
Gruß
Andreas
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
Marcel Müller
Guest
|
| Posted: Sun Apr 23, 2006 12:32 pm Post subject: Re: Cache Implementierung - map |
|
|
Hallo,
Andreas Volz schrieb:
| Quote: | Ich hab auch einen kleinen Fehler gemacht. Die Klasse Target soll immer
ganz geladen werden. Das ist die Struktur, welche als Cache dienen soll:
typedef map <string, Target> TargetMap;
Aber an der Problematik ändert sich dadurch wenig.
|
Doch, der Schlüssel ist nun ein String und damit ganz sicher nicht
stetig verteilt.
| Quote: | Wenn man da Geschwindigkeit hereinbringen will, muss man die zu
erwartenden Zugriffsmuster auf den Cache schon genauer unter die Lupe
nehmen.
Also ich gehe jetzt von TargetMap aus. Das Target muss immer ganz
geladen werden...
|
OK, damit hat sich die Frage erledigt.
| Quote: | -> Ist map überhaupt eine geeigneter Container? Der Overhead ist
bei so kleinen Objekten beträchtlich. Der Aufbau der Baumstruktur
aufwendig. Alternativen: hash_map oder sortierter vector.
hash_map hab ich auch schon überlegt. Sortierter Vektor geht nicht,
weil die Reihenfolge definiert ist. Wobei ich das nochmal überlegen
müsste. Es sind momentan etwa 1000 Einträge. Ich vermute mal das
Maximum wird höchstens bei 2000-3000 liegen.
|
Das ist nicht viel. Insbesondere, wenn wie beschrieben nur ein Bruchteil
davon pro Programmlauf geladen werden.
| Quote: | - Welche Items werden notwendigerweise zusammen benötigt?
Wie schon gesagt, das mit Target war ein Fehler. Es wird immer ein
ganzes Target aus TargetMap benötigt.
-> Cache-Lines bilden, die auf einen Schlag geladen werden.
- Wie groß ist der Overhead der verzögerten Ladung?
Das verstehe ich beides nicht ganz.
|
Ich ging davon aus, dass mit einem Target auch mit großer
Wahrscheinlichkeit noch weitere Targets benötigt werden. Bei einen
flachen Struktur wäre das sehr wahrsheinlich, bei der jetzt genannten
zweistufigen Struktur zumindest mal möglich.
Solche gemeinsam geladenen Targets nennt man Cache-Lines.
| Quote: | Lohnt das überhaupt? Oder ist es besser, den Ladevorgang zu
optimieren?
Ich hab natürlich schon mit binären Daten gearbeitet. Damals mit der
Idee die Datengröße zu verringern. Hat etwa eine Ersparnis von 50%
gebracht.
|
Logisch. das ist in etwa die Kompression, die man bei zufälligen Zahlen
erwarten kann.
| Quote: | Ich hab mich dann dagegen entschieden wegen der Big-Endian/
Little-Endian Komplexität.
|
Bekommt man in den Griff, wenn man als erstes einen Signatur-Wert in
jede Datei schreibt. Je nachdem, wie der gelesen wird, muss eine
Umsetzung erfolgen oder nicht.
Bei aktivierter Umsetzung spart man aber nicht mehr so viel gegenüber
dem pflegeleichteren ASCII.
[...]
| Quote: | Das ganze lese ich mit sscanf ein. Vielleicht lässt sich das noch
optimieren. Bei der Masse an Dateien und Schleifendurchläufen würde da
jede Micro-Optimierung vielleicht schon etwas bringen.
|
Ich glaube nicht, dass sich dieser Aufwand lohnt.
| Quote: | - Wird auf die Objekte sehr oft zugegriffen?
Gemischt. Es hängt vom Nutzer und seinem Arbeitsverhalten im Programm
ab. Wobei ich gerade die Datenstruktur nochmal überdenke. Der Zugriff
auf die einzelnen Elemente von Target sind meist so im Verhältnis 1:100
im Gegensatz zu der Häufigkeit von TargetMap. Soll heißen ich greife
auf eine Element von TargetMap zu und danach 100x auf Target.
|
Aus dem und den oben ganannten Zahlen schließe ich: TargetMap ist
optimalerweise wirklich vom Typ map.
| Quote: | Ich müsste mal messen ob da eine Optimierung bei Target nicht mehr Sinn
als bei dem Zugriff auf TargetMap. Soll heißen vielleicht kann ich
tatsächlich alle Maps zu Vektoren machen. Wenn ich mir meinen
Algorithmus so ansehe könnte ein Vektor auch funktionieren. Eigentlich
durchlaufe ich ein Target (Map) eh nur mit einem Iterator.
|
Da ist map völlig verkehrt.
Sind denn alle Targets gleich groß?
Wenn ja: vector nehmen und immer gleich mit erwartete Größe
konstruieren, um Resize-Operationen zu vermeiden.
Wenn nein: eine vector in der Ladefunktion halten, der immer wieder
benutzt wird und vor dem Einstellen der Daten in TargetMap selbige in
einen vector optimaler Größe umwandeln. Sinnvollerweise ist TragetMap
dann gleich map<string, const Target> (ich glaube das ging bei map),
dann spielt auch keiner an den Daten herum.
Das sollte den Speicherbedarf DRASTISCH reduzieren, selbst wenn
nachwievor alle Targets geladen werden, und die Iteration wird auch eine
Ecke schneller.
Auch der Ladevorgang wird profitieren, da die sukkzessive Bevölkerung
der map von Target mit monotonen Schlüsselwerten den Worst-Case
darstellt. Es werden sehr viele Rotationen in der Baumstruktur benötigt.
Kleiner Tip noch: das mit der Vermeidung der Resize-Operationen bei
vector ist in diesem Kontext echt wichtig, da es unter bestimmten
Umständen sonst zu einem drastisch ansteigenden Speicherbedarf kommen
kann. Dass passiert, wenn zwischen den Resize-Vorgängen nöch kleinere
Speicherblöcke vom Heap angefordert werden. In diesem Fall führt die
Fragmentierung des virtuellen Adressraums dazu, dass das jeweils neue,
größere Segment niemals früher freigegebenen Speicher nutzen kann.
| Quote: | - Was ist mit Fehlermeldungen, die jetzt später auftreten?
Zum Beispiel bei illegalen Datenformaten? Ja, das hab ich auch schon
überlegt. Exceptions wollte ich aus Geschwindigkeitsgründen nicht
nutzen.
|
? - Exceptions sind nicht langsam, solange sie nicht geworfen werden.
Und wir sprechen ja hier nicht über die Optimierung eines
Programmabbruchs, oder?
| Quote: | Kann das Programm sinnvoll damit umgehen, wenn zu einem späteren
Zeitpunkt ein Gefordertes Item nicht geladen werden kann?
Das ist tatsächlich ein ungelöstes Problem. Ich hätte für diesen Fall
einfach "leere" Objekte geliefert.
|
Notfalls kann man beim Programmstart zumindest eine rudimentäre
Validierung durchführen.
| Quote: | - Kann man nicht die ASCII-Daten schon Verarbeitungsfreundlich
gestalten, also z.B. sortieren? Dann könnte man das ganze Ding
sequentiell in einen vector laden und darauf per binary search
zugreifen. Das halbiert den Speicherbedarf gegenüber der map auch
bestimmt um die Hälfte. Und die Ladezeit dürfte minimal ausfallen,
wenn man die erforderliche Vektorgröße vorher kennt.
Hm, vielleicht sollte ich wirklich nochmal auf die Ebene von
Zeitmessungen gehen und einige Implementierungen real vergleichen. Aber
danke schon mal für die Anregungen bisher.
|
Ich würde jetzt keine Zeitmessung machen. Das ist Zeitverschwendung.
Erstmal müssen aus den Targets Vektoren werden.
Gehe ich recht in der Annahme, der int ist die Zeilennummer im ASCII?
Die ist ja bekanntermassen stetig.
Das bringt aus dem Stand einen Faktor 2-3 im Speicher. Ob die Ladezeit
davon auch signifikant profitiert, hängt davon ab, ob es bisher eher an
der CPU oder an der Platte gehangen hat. Aber da ist das genannte
Delayed-Load schon das richtige.
Alternativ könnte man die Files dann auch einfach bei der Installation
schon auf die nativen Binärformate umschlüssen. Oder von mir aus auch
beim ersten Programmlauf aus allen ASCII-Files Binärfiles in der nativen
Kodierung machen.
Das eröffnet eine völlig neue Optimierungsmethode: Memory mapped files.
Die Binärdateien könnten als MMF direkt eingebunden werden. Das würde
die gesammte Cache-Logik ersparen und auf die MMU verlegen. Bei
Speicherknappheit würden die Speicherseiten der MMFs auch nicht im
Swapfile landen, sondern bei Bdarf aus der Binärdatei nachgeladen. Und
wenn man nicht auf die MMF-Inhalte zugreift, würden sie gar nicht
geladen, sondern nur der virtuelle Adressraum belegt.
Besonders effizient wird die Sache, wenn man aus allen Files /eine/
Binärfile mit eingebautem Directory macht. Allerdings ist es dazu
erforderlich, dass das Speicherlayout im File und im RAM absolut
identisch sind, also keine Pointer, sondern Offsets zum Fileanfang und
Handbetrieb beim Zugriff (Adressberechnung).
Außerdem weiß ich nicht ob alle Plattformen mit einer so großen Zahl von
MMFs umgehen können.
Im C++-Standard bewegt man sich mit MMF aber definitiv nicht mehr.
Marcel
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
Andreas Volz
Guest
|
| Posted: Sun Apr 23, 2006 1:06 pm Post subject: Re: Cache Implementierung - map |
|
|
Am Fri, 21 Apr 2006 19:25:21 +0200 schrieb Christoph Kliemt:
| Quote: | ich habe folgende Klasse in einer Bibliothek:
class Target : public std::map <int, Vector3f> { private: ...
public: bool load (const std::string& filename);
bool save (const std::string& filename); };
Nein, Du willst nicht von std::containern erben. Es sei denn, Du
stehst auf Schusslöchern im Fuss.
|
Ok, ich hab aktuell ein paar Probleme einen Cachelayer darüber zu
legen. Aber kannst du mir erklären wo du die Gefahren dabei siehst? Ich
dachte es wäre eine gute Idee, wenn ich meine Datenstrukturen wir eine
Map oder einen Vektor nutzen kann. Dabei aber einfache mit load() und
save() die Dateiverwaltung implementiere. Das würde mich wirklich
interessieren, da ich es nämlich recht häufig in dieser Bibliothek
genutzt habe.
| Quote: | Meine aktuelle Idee ist es eine Art "Cache" zu implementieren. Die
Klasse bekommt ein Flag die anzeigt ob es physisch geladen wurde
oder nicht. Die Datei wird also einmalig erst beim ersten Zugriff
auf den Inhalt von der Platte gelesen. Das würde sowohl die
Startzeit,
Startzeit sehe ich ein.
als auch den Speicherverbrauch reduzieren.
Das jetzt nicht wirklich.
|
Naja, ich hab ja geschrieben der Zugriff auf die Daten hängt vom
Benutzer des Anwendungsprogramms ab. Am Anfang braucht das Programm
also sehr wenig Speicherplatz, weil zwar alle Daten zum Laden markiert
wurden, aber noch nicht physikalisch geladen wurden. Wenn im Laufe der
Sitzung auf immer mehr Daten zugegriffen wird füllt sich langsam der
Speicher. Entsprechend könnte man zeitgesteuert Daten wieder aus
dem "Cache" entfernen. Der Speicherverbrauch richtet sich also nach dem
effektiven Arbeitsverhalten.
| Quote: | Meine Frage ist wie ich das am besten mit der map umsetze.
Vielleicht wäre es im Design besser gewesen nicht von einer map
abzuleiten, sondern Target eine map besitzen zu lassen.
Genau.
Dann hätte dieser Mechanismus z.B. in einer getDataMap() Funktion
stecken können. So sehe ich keine andere Lösung als alle
Zugriffsmöglicheiten der map mit einer eigenen Implementierung zu
überschreiben und zu prüfen ob der Inhalt schon geladen wurde.
Minderprickelnd. Aber im Prinzip hast Du die Lösung ja beschrieben,
dass die map ein member deiner Klasse ist. Normalerweise reichtst Du
dann die nötigen Operationen an die Map weiter, und bei Bedarf werden
die Zugriffe über eigene Methoden "passend gemacht".
|
Während ich jetzt wieder eine Implementierung von map nach vector
geändert habe ist mir auch ein möglicher Grund dafür eingefallen. Ich
brauche bei einer internen Implementationsänderung nicht die
Schnittstelle zu ändern. So musste ich alle map-Zugriffe zu
Vector-Zugriffen umbasteln. :-(
Gruß
Andreas
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
Andreas Volz
Guest
|
| Posted: Sun Apr 23, 2006 1:06 pm Post subject: Re: Cache Implementierung - map |
|
|
Am Fri, 21 Apr 2006 20:53:53 +0200 schrieb Marcel Müller:
| Quote: | ...
-> Kommt es eher auf die Lade- oder die Zugriffszeit an?
|
Wegen der Ladezeiten:
void Target::fromStream (std::ifstream &in_stream)
{
char buffer[MAX_LINE_BUFFER] = "";
float x, y, z;
int vertex_number;
clear ();
while (in_stream.getline (buffer, MAX_LINE_BUFFER))
{
if (sscanf (buffer, "%d,%f,%f,%f\n", &vertex_number, &x, &y, &z) ==
4) {
Vector3f target_vec (x, y, z);
Target &target = (*this);
TargetData td;
td.vertex_number = vertex_number;
td.morph_vector = target_vec;
target.push_back (td);
}
else
{
cerr << "illegal target format line: " << endl << buffer << endl;
}
}
}
Sieht jemand eine Möglichkeit das relevant zu beschleunigen? Ja, sscanf
ist nicht der elegante C++ Weg, aber ich mag es. Kostet mich das hier
evtl. unnötig Zeit?
Gruß
Andreas
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
Christoph Kliemt
Guest
|
| Posted: Sun Apr 23, 2006 6:50 pm Post subject: Re: Cache Implementierung - map |
|
|
Andreas Volz <usenet-spam-trap (AT) brachttal (DOT) net> writes:
| Quote: | Am Fri, 21 Apr 2006 19:25:21 +0200 schrieb Christoph Kliemt:
ich habe folgende Klasse in einer Bibliothek:
class Target : public std::map <int, Vector3f> { private: ...
public: bool load (const std::string& filename); bool save (const
std::string& filename); };
Nein, Du willst nicht von std::containern erben. Es sei denn, Du
stehst auf Schusslöchern im Fuss.
Ok, ich hab aktuell ein paar Probleme einen Cachelayer darüber zu
legen. Aber kannst du mir erklären wo du die Gefahren dabei siehst?
|
Das Problem ist, dass stl-container keinen viruellen dtor haben.
Problem dabei (schnell und schmutzig zusammengehackt):
#include <iostream>
class TestObject
{
public:
int level;
TestObject( int l ) : level( l )
{
std::cout << "ctor TestObject" << level << std::endl;
};
~TestObject()
{
std::cout << "dtor TestObject" << level << std::endl;
}
};
class Base
{
private:
TestObject testObject;
public:
Base() : testObject( 0 ) {};
virtual void print() { std::cout << "print : " << testObject.level << std::endl; };
virtual ~Base() {};
};
class Child : public Base
{
private:
TestObject testObject;
public:
virtual void print() { std::cout << "print : " << testObject.level << std::endl; };
Child() : testObject( 1 ) {};
~Child() {};
};
int main(int argc, char *argv[])
{
std::cout << "child class" << std::endl;
Child* child = new Child;
child -> print();
delete child;
std::cout << "base class" << std::endl;
Base* base = new Child;
base -> print();
delete base;
}
Das spuckt aus:
child class
ctor TestObject0
ctor TestObject1
print : 1
dtor TestObject1
dtor TestObject0
base class
ctor TestObject0
ctor TestObject1
print : 1
dtor TestObject1
dtor TestObject0
lässt man aber das virtual vor dem dtor von base weg:
child class
ctor TestObject0
ctor TestObject1
print : 1
dtor TestObject1
dtor TestObject0
base class
ctor TestObject0
ctor TestObject1
print : 1
dtor TestObject0
da fehlt dann der dtor TestObject1... kleines gemeines Leak.
Wenn man g++ mit -Wall laufen lässt meckert der Compiler auch.
[...]
| Quote: | Während ich jetzt wieder eine Implementierung von map nach vector
geändert habe ist mir auch ein möglicher Grund dafür eingefallen. Ich
brauche bei einer internen Implementationsänderung nicht die
Schnittstelle zu ändern. So musste ich alle map-Zugriffe zu
Vector-Zugriffen umbasteln. 
|
Ähmja... eigentlich wollte ich Dich in diesem Posting vor dieser
Gefahr warnen, aber da Du jetzt ja schon diese Erfahrung gemacht
hast... ;-)
hth, bis denne,
Christoph
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
Marc Wieden
Guest
|
| Posted: Mon Apr 24, 2006 12:55 am Post subject: Re: Cache Implementierung - map |
|
|
Hallo erstmal!
On Sun, 23 Apr 2006 14:49:23 +0200, Andreas Volz wrote:
| Quote: |
Wegen der Ladezeiten:
void Target::fromStream (std::ifstream &in_stream)
{
char buffer[MAX_LINE_BUFFER] = "";
float x, y, z;
int vertex_number;
clear ();
while (in_stream.getline (buffer, MAX_LINE_BUFFER))
{
if (sscanf (buffer, "%d,%f,%f,%f\n", &vertex_number, &x, &y, &z) ==
4) {
Vector3f target_vec (x, y, z);
Target &target = (*this);
TargetData td;
td.vertex_number = vertex_number;
td.morph_vector = target_vec;
target.push_back (td);
|
In den oberen Zeilen hast du pro Durchlauf für Vector3f:
1 Konstruktor, 1 Kopierkonstruktor und einen Zuweisungsoperator
Für TargetData:
1 Konstruktor und 1 Kopierkonstruktor
Bei einem push_back wird immer der Kopierkonstruktor des übergeben
Objektes aufgerufen. Wenn du für TargetData einen Konstruktor erstellst
der die vertex_number und den morph_vector annimmt läßt sich der Block
umschreiben zu:
target.push_back(TargetData(vertex_number,Vector3f(x,y,z))
Das wären dann nur noch je ein Konstruktoraufruf für Vector3f und
TargetData. Das sollte sich schon merklich in der Laufzeit
niederschlagen.
| Quote: | }
else
{
cerr << "illegal target format line: " << endl << buffer << endl;
}
}
}
Sieht jemand eine Möglichkeit das relevant zu beschleunigen?
|
s.o.
Marc
--
_howie_ @IRC
GSF 600N 95/98 => 34Mm VFR 98/ => 110Mm "Blue-Eye"
Ein Motorrad ist dafür da um von A über B und C wieder nach A zu fahren und
das möglichst schnell um die Runde nochmal fahren zu können. c Simon Lenzen
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
Torsten Robitzki
Guest
|
| Posted: Mon Apr 24, 2006 5:06 pm Post subject: Re: Cache Implementierung - map |
|
|
Hallo Andreas,
Andreas Volz wrote:
| Quote: | Am Fri, 21 Apr 2006 20:53:53 +0200 schrieb Marcel Müller:
...
-> Kommt es eher auf die Lade- oder die Zugriffszeit an?
Wegen der Ladezeiten:
snip
Sieht jemand eine Möglichkeit das relevant zu beschleunigen? Ja, sscanf
ist nicht der elegante C++ Weg, aber ich mag es. Kostet mich das hier
evtl. unnötig Zeit?
|
kommentier doch einfach mal den Teil aus, der die gelesene Zeile
verarbeitet und meß einmal mit und einmal ohne diese Verarbeitung, die
Zeit, die benötigt wird um eine Datei zu lesen. Ich könnte mir denken,
das da kein großer Unterschied sein wird. In der Regel ist und bleibt IO
immer noch das teuerste, was man so hat. Je nach dem, wie das Verhältnis
von Verarbeitungszeit zu Lesezeit ist gibt es dann unterschiedlichste
Ansätze hier was zu optimieren.
Bei hohem IO Anteil:
- IO z.B. durch kompaktere Datenformate verringern. In Deinem Beispiel
könntest Du einfache alle Integer hintereinander in eine Datei schreiben.
Bei hohem CPU Anteil:
- Profiler in die Hand nehmen und den messen lassen. Dann die Hotspots
(wenn es welche gibt) wegoptimieren. Und anschließend wieder messen.
Bei ähnlichem IO und CPU Anteil
- Versuchen, den IO und CPU Anteil sich überlappen zu lassen, sprich
wärend Du eine Zeile verarbeitest, dafür sorgen, das die Festplatte
bereits damit beschäftigt ist, die nächsten Daten bereits zu lesen. Das
läßt sich allerdings mit iso c++ nicht machen.
mfg Torsten
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
Marcel Müller
Guest
|
| Posted: Mon Apr 24, 2006 5:06 pm Post subject: Re: Cache Implementierung - map |
|
|
Hallo!
Andreas Volz schrieb:
| Quote: | Wegen der Ladezeiten:
void Target::fromStream (std::ifstream &in_stream)
{
char buffer[MAX_LINE_BUFFER] = "";
float x, y, z;
int vertex_number;
clear ();
while (in_stream.getline (buffer, MAX_LINE_BUFFER))
{
if (sscanf (buffer, "%d,%f,%f,%f\n", &vertex_number, &x, &y, &z) ==
4) {
|
Und schon wieder unterscheiden sich die Angaben zum letzten Posting. In
den Beispieldaten war keine Vertexnummer zu sehen.
Und wieder die Fragen: sind die Vertexnummern stetig? Sind die Zeilen in
den Files sortiert?
In ersterem Falle würde ich einen vector (oder deque) mit Arrayzugriff
empfehlen. (Vertexnummer <-> Index eineindeutig)
Das liefert Aufwandsklasse O(1) beim Zugriff.
Andernfalls eine vector aus
struct target_entry
{ int vertex_number;
Vector3f target_vec;
};
Der Zugriff wäre dann über binary_search zu realisieren. Die
Zugriffsfunktion liefert natürlich nur den Vector zurück. (Also ein
map-artiges Interface mit einer anderen internen Repräsentation)
Das wäre Aufwandsklasse O(log n) beim Zugriff.
Falls die Daten nicht sortiert sind, empfehle ich nacher ein Quicksort.
Das ist definitiv besser als erst in eine map zu lesen und dann in einen
sortierten vector zu kopieren.
Das ist ein einmaliger Mehraufwand der Klasse O(n * log n).
Wenn zuallererst der neue Eintrag im vector instanziiert wird, kann man
mit scanf auch direkt in den Zielspeicherplatz lesen. Das erspart den
Copy-Konstruktor. (Das bringt aber nicht die Hölle, da das temporäre
Objekt mit großer Wahrscheinlichkeit im L1 Cache liegt.)
Das indirekte Lesen über getline/sscanf ist nicht sehr elegant, da die
Daten zweimal Byte für Byte geparst werden. Wenn schon scanf, dann würde
ich in dem Fall direkt mit scanf auf einen C-Style Filestream zugreifen.
Das bringt etwas. (Schätze 20-30% weniger CPU-Last.)
Marcel
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
Andreas Volz
Guest
|
| Posted: Tue Apr 25, 2006 1:06 pm Post subject: Re: Cache Implementierung - map |
|
|
Am Mon, 24 Apr 2006 18:39:30 +0200 schrieb Torsten Robitzki:
| Quote: | kommentier doch einfach mal den Teil aus, der die gelesene Zeile
verarbeitet und meß einmal mit und einmal ohne diese Verarbeitung,
die Zeit, die benötigt wird um eine Datei zu lesen. Ich könnte mir
denken, das da kein großer Unterschied sein wird. In der Regel ist
und bleibt IO immer noch das teuerste, was man so hat. Je nach dem,
wie das Verhältnis von Verarbeitungszeit zu Lesezeit ist gibt es dann
unterschiedlichste Ansätze hier was zu optimieren.
Bei hohem IO Anteil:
- IO z.B. durch kompaktere Datenformate verringern. In Deinem
Beispiel könntest Du einfache alle Integer hintereinander in eine
Datei schreiben.
|
Das Datenformat ist soweit eigentlich recht fest. Ich könnte es ändern,
aber dann müsste ich auch alle anderen darauf basierten Programme
ändern (Skripte,...). Da kann ich auch gleich binary nehmen und einen
ASCII<->Binary Konverter zur Verfügung stellen.
| Quote: | Bei hohem CPU Anteil:
- Profiler in die Hand nehmen und den messen lassen. Dann die
Hotspots (wenn es welche gibt) wegoptimieren. Und anschließend wieder
messen.
|
Also die CPU-Anteile hab ich durch meine Änderungen der Einleseroutine
(siehe Posting nebenan...) reduzieren können. Insgesamt um etwa 0,8 s.
| Quote: | Bei ähnlichem IO und CPU Anteil
- Versuchen, den IO und CPU Anteil sich überlappen zu lassen, sprich
wärend Du eine Zeile verarbeitest, dafür sorgen, das die Festplatte
bereits damit beschäftigt ist, die nächsten Daten bereits zu lesen.
Das läßt sich allerdings mit iso c++ nicht machen.
|
Du meinst damit sicher den Einsatz von Threads. Ich bin mir nicht
sicher ob du den Einsatz auf dem gleichen Level wie ich siehst. Ich
hatte die Idee die GUI zu starten und im Hintergrund die Daten zu
laden. Bis der evtl. Splashscreen fertig ist und der Nutzer anfangen
kann zu arbeiten braucht es dann die gleiche Zeit, aber es kommt einem
subjektiv kürzer vor.
Gruß
Andreas
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
Andreas Volz
Guest
|
| Posted: Tue Apr 25, 2006 1:06 pm Post subject: Re: Cache Implementierung - map |
|
|
Am Mon, 24 Apr 2006 18:43:39 +0200 schrieb Marcel Müller:
| Quote: | if (sscanf (buffer, "%d,%f,%f,%f\n", &vertex_number, &x, &y,
&z) == 4) {
Und schon wieder unterscheiden sich die Angaben zum letzten Posting.
In den Beispieldaten war keine Vertexnummer zu sehen.
|
Ich hab noch mehr Datenformate als dieses. Im Anfangsposting hab ich
zufällig das falsche eingefügt.
| Quote: | Und wieder die Fragen: sind die Vertexnummern stetig? Sind die Zeilen
in den Files sortiert?
|
Nein, sie sind nicht stetig. Es ist also nicht die Zeilennummer,
sondern ein Verweis auf eine Zeile in einer anderen Datei. Wird also
benötigt.
| Quote: | Das indirekte Lesen über getline/sscanf ist nicht sehr elegant, da
die Daten zweimal Byte für Byte geparst werden. Wenn schon scanf,
dann würde ich in dem Fall direkt mit scanf auf einen C-Style
Filestream zugreifen. Das bringt etwas. (Schätze 20-30% weniger
CPU-Last.)
|
Ich hab es jetzt so gemacht:
FILE *fd;
Target &target = (*this);
clear ();
fd = fopen (filename.c_str (), "r");
int ret = 0;
do
{
TargetData td;
ret = fscanf (fd, "%d,%f,%f,%f", &td.vertex_number,
&td.morph_vector.x, &td.morph_vector.y,
&td.morph_vector.z);
if ((ret != 4) && (ret != EOF))
{
cerr << "Illegal line while reading target '" << filename << "'!"
<< endl; clear ();
return false;
}
target.push_back (td);
} while (ret != EOF);
fclose (fd);
Geht schon mal etwas schneller. Nach meinen Messungen dauert das
laden von 800 Targets nur 1.8 s, statt 2.5 s vorher. Das ist schon
mal nicht ganz schlecht. Jeweils nach dem zweiten Start, damit ich
vergleichbare Werte bekommen. Beim ersten Start dauert es so um die 5 s
für 17 MB ACSII Daten. Und genau diesen ersten Start würde ich gerne
noch schneller hin bekommen. Aber ich vermute mal wesentlich schneller
bekomme ich das nicht hin, wenn alles auf einmal eingelesen werden soll.
Gruß
Andreas
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
Andreas Volz
Guest
|
| Posted: Tue Apr 25, 2006 4:08 pm Post subject: Re: Cache Implementierung - map |
|
|
Am Sun, 23 Apr 2006 10:32:45 +0200 schrieb Marcel Müller:
| Quote: | Ich hab mich dann dagegen entschieden wegen der Big-Endian/
Little-Endian Komplexität.
Bekommt man in den Griff, wenn man als erstes einen Signatur-Wert in
jede Datei schreibt. Je nachdem, wie der gelesen wird, muss eine
Umsetzung erfolgen oder nicht.
Bei aktivierter Umsetzung spart man aber nicht mehr so viel gegenüber
dem pflegeleichteren ASCII.
|
Das ist auch eine gute Idee. Ich hab in meinen Tests eben Little-Endian
als Dateiformat festgelegt und dann über ein #ifdef die richtige
Implementierung gewählt (bytes drehen oder nicht).
| Quote: | Ich müsste mal messen ob da eine Optimierung bei Target nicht mehr
Sinn als bei dem Zugriff auf TargetMap. Soll heißen vielleicht kann
ich tatsächlich alle Maps zu Vektoren machen. Wenn ich mir meinen
Algorithmus so ansehe könnte ein Vektor auch funktionieren.
Eigentlich durchlaufe ich ein Target (Map) eh nur mit einem
Iterator.
Da ist map völlig verkehrt.
|
Ja, tatsächlich. Zeit beim Einlesen hat es nicht viel gebracht, aber
der Speicherbedarf ist um 800 kb gesunken!
| Quote: | Sind denn alle Targets gleich groß?
|
Nein, aber es gibt eine maximale Größe im Bereich von 10000 Einträgen.
Wird allerdings so gut wie nie erreicht. Der Durchnitt liegt bei
mehreren hundert.
| Quote: | Wenn ja: vector nehmen und immer gleich mit erwartete Größe
konstruieren, um Resize-Operationen zu vermeiden.
|
Ich hab zu beginn der Laderoutine auf Verdacht mal einen resize mit 200
gemacht, weil das ein guter Wert ist. Hat aber weder am Speicher noch
an der Ladezeit etwas geändert.
| Quote: | Wenn nein: eine vector in der Ladefunktion halten, der immer wieder
benutzt wird und vor dem Einstellen der Daten in TargetMap selbige in
einen vector optimaler Größe umwandeln. Sinnvollerweise ist TragetMap
dann gleich map<string, const Target> (ich glaube das ging bei map),
dann spielt auch keiner an den Daten herum.
|
Mittlerweile hab ich herausgefunden, dass fast alle Zeit beim
wirklichen IO drauf gehen. Ich vermute damit lässt sich effektiv auch
nix mehr gewinnen.
| Quote: | Das sollte den Speicherbedarf DRASTISCH reduzieren, selbst wenn
nachwievor alle Targets geladen werden, und die Iteration wird auch
eine Ecke schneller.
|
Ah, beim letzten Kommentar ging es um der Speicherbedarf! Hm, dann
werde ich das nochmal testen. Obwohl momentan meine 17 MB geladenen
ASCII-Daten etwa 2 MB Speicher belegen. Jedenfalls sagt "top" das über
meine Anwendung (gemessen mit Differenz nur GUI!). Das ist auch so ein
Punkt den ich nicht verstehe. Selbst als binäre Daten sind es etwa 8 MB
auf der Platte. Wie kann mein map/vector Datenstruktur dann (mit
Prozess) nur 2 MB groß sein? Oder spinnt top?
| Quote: | Auch der Ladevorgang wird profitieren, da die sukkzessive Bevölkerung
der map von Target mit monotonen Schlüsselwerten den Worst-Case
darstellt. Es werden sehr viele Rotationen in der Baumstruktur
benötigt.
|
Ich hab das Anlegen/Aufbau der gesamten map ohne das wirkliche Laden
von der Platte gemessen. Diesen Einfluss kann man vernachlässigen!
| Quote: | Kleiner Tip noch: das mit der Vermeidung der Resize-Operationen bei
vector ist in diesem Kontext echt wichtig, da es unter bestimmten
Umständen sonst zu einem drastisch ansteigenden Speicherbedarf kommen
kann. Dass passiert, wenn zwischen den Resize-Vorgängen nöch kleinere
Speicherblöcke vom Heap angefordert werden. In diesem Fall führt die
Fragmentierung des virtuellen Adressraums dazu, dass das jeweils
neue, größere Segment niemals früher freigegebenen Speicher nutzen
kann.
|
Wie gesagt, muss ich nochmal testen. Aber Speicher scheint nicht mein
Problem zu sein. s.o.
| Quote: | Erstmal müssen aus den Targets Vektoren werden.
|
Ist passiert.
| Quote: | Gehe ich recht in der Annahme, der int ist die Zeilennummer im ASCII?
Die ist ja bekanntermassen stetig.
|
Wie schon in dem anderen Posting geschrieben. Nein, es ist nicht die
Zeilennummer. Kann man also nicht weglassen.
| Quote: | Das bringt aus dem Stand einen Faktor 2-3 im Speicher. Ob die
Ladezeit davon auch signifikant profitiert, hängt davon ab, ob es
bisher eher an der CPU oder an der Platte gehangen hat. Aber da ist
das genannte Delayed-Load schon das richtige.
|
Es hängt am IO.
| Quote: | Alternativ könnte man die Files dann auch einfach bei der
Installation schon auf die nativen Binärformate umschlüssen. Oder von
mir aus auch beim ersten Programmlauf aus allen ASCII-Files
Binärfiles in der nativen Kodierung machen.
|
Dann kann ich ja auch gleich binäre Daten liefern. Natürlich, das
swappen der Bytes kostet natürlich auch wieder CPU. Alles nicht so
einfach...
Gruß
Andreas
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
Marcel Müller
Guest
|
| Posted: Tue Apr 25, 2006 7:06 pm Post subject: Re: Cache Implementierung - map |
|
|
Andreas Volz wrote:
| Quote: | Geht schon mal etwas schneller. Nach meinen Messungen dauert das
laden von 800 Targets nur 1.8 s, statt 2.5 s vorher. Das ist schon
mal nicht ganz schlecht. Jeweils nach dem zweiten Start, damit ich
vergleichbare Werte bekommen. Beim ersten Start dauert es so um die 5 s
für 17 MB ACSII Daten. Und genau diesen ersten Start würde ich gerne
noch schneller hin bekommen. Aber ich vermute mal wesentlich schneller
bekomme ich das nicht hin, wenn alles auf einmal eingelesen werden soll.
|
Nein. - Höchstens mit einer schnelleren Platte.
Ich weiß nicht, was jetzt verwendet wird, aber eine durchschnittliche
IDE-Platte hat so 9-12ms mittlere Zugriffszeit. Bei 800 Files wird man
also eine Zeit in der Größenordnung von 8-10s erwarten müssen. Dass es
sogar besser ist, liegt vermutlich daran, dass die Dateien eben nicht
wahllos auf der Platte verteilt sind, sondern nahe beisammen stehen. Das
ist aber eine in keiner Weise garantierte Eigenschaft.
Ich vermute mal, mit einer Cheetah-15k wären unter vergleichbaren
Bedingungen 4s drin.
Die Datenmenge von 17MB ist dabei übrigens völlig irrelevant.
Wenn man hier wirklich etwas Beschleunigen will, muss man die 800 Files
in einer Datei vereinen. Die IO-Zeit dürfte dabei auf vielleicht 0,5s
sinken. Wenn dann die CPU nicht zum Engpass wird, hat man nur noch eine
halbe Sekunde Ladezeit. In dem Punkt kommen dann erst die Optimierungen
im C++-Code zum tragen.
Marcel
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
