Cachelocality oder wie man das nennen will
-
Hi
Ich schreib grad nen Programm, dass relativ viel mit Bäumen arbeitet um Sachen zu sortieren. Die Bäume an sich sind statisch, werden also vom Programm selbst nur noch eingelesen und hinterher durchlaufen, sie werden aber nicht während das Programm läuft verändert.
Bei der ganzen Sache ist Geschwindigkeit sehr wichtig, deshalb mach ich mir gerade Gedanken darum, ob es Vorteile hat den Speicher für die Bäume irgendwie "geordnet" anzufordern.Bisher hab ich mir folgendes gedacht:
Es sollte eigentlich Cache-freundlicher sein, wenn man nicht jede Node des Baums einzeln anfordert, weil bei großen Bäumen leicht das Ding hinterher total zerpflückt im Speicher liegt.
Daher erstelle ich jetzt alle Nodes in einem Schlag, wodurch der Baum schonmal an einem Stück im Speicher liegen sollte.Allerdings ist das alles nur so rein theoretisch überlegt. Also eigentlich hab ich keine Ahnung, wie das mit dem Cache aussieht. Ist es wirklich schlimm, wenn der Speicher etwas fragmentiert ist, oder interessiert den Prozessor das gar nicht? Ich hab zwar schon häufiger was davon gehört, dass es da so "Pages" gibt, die hin und wieder geladen oder entladen werden müssen und dass das immer recht langsam ist, aber so richtig kann ich mir da nix drunter vorstellen. Wie groß ist denn so ne "Page" ? 1 MB 50 MB? 4 KB? Ich hab keine Ahnung wie groß die Auswirkung davon wäre.
Wäre echt nett, wenn mich jemand darüber aufklären könnte, was man dringend vermeiden sollte, wenns auf Geschwindigkeit ankommt bzw. wie man es anstattdessen besser macht.
Tschö,
Jan.
-
Dieser Thread wurde von Moderator/in davie aus dem Forum C++ in das Forum Rund um die Programmierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
Hallo!
Also meistens ist die gewählte Datenstruktur entscheidend für die Performance eines Programms. Wenn Du wirklich nur noch durch die Daten durchgehen musst, dann ist es u.U. sinnvoll die Daten in einen Vektor oder eine Liste zu kopieren. Das durchgehen der Daten geht so schneller. Der Vektor ist v.a. dann sinnvoll, wenn Du nur einen bestimmten Bereich durchgehen willst/musst: Dann kannst Du nämlich nach wie vor schnell suchen (logarithmischer Aufwand, falls Vektor sortiert).
-
Jan2 schrieb:
Hi
Ich schreib grad nen Programm, dass relativ viel mit Bäumen arbeitet um Sachen zu sortieren.ok, zum sortieren sind bäume nicht extrem schlecht.
Die Bäume an sich sind statisch, werden also vom Programm selbst nur noch eingelesen und hinterher durchlaufen, sie werden aber nicht während das Programm läuft verändert.
und das programm läüft länger? also willste durchaus zeitkosten beim programmstart in kauf nehmen, damit nur später die suchzugriffe in die bäume optimal werden?
[quote]
Bisher hab ich mir folgendes gedacht:
Es sollte eigentlich Cache-freundlicher sein, wenn man nicht jede Node des Baums einzeln anfordert, weil bei großen Bäumen leicht das Ding hinterher total zerpflückt im Speicher liegt./quote]
aber hallo. nicht eigentlich wegen der speicherlokalität. der speicher ist in 4k große seiten aufgeteilt, die unabhängig voneinader in die auslagerungsdatei hüpfen konnen und wieder raus. hier darfs keine kompromisse geben, denn für einmal kopfspringen und einlagern zahlste 10000000 takte. (1GhZ sind 1e9 takte pro sekunde und die platte kann mit 10ms zugreifen). sind die daten so groß, daß sie ausgelagert werden, oder läuft das programm so lange, dann mußt du das vordringlich optimieren. die dicke fliegenklatsche dafür sind b-bäume. die zugriffe sind fein, code ist im netzt findbar.
zwischenfrage, wozu wurde sortiert? nur für schnellen suchzugriff? dann könnten hashtables besser sein.
aber b-bäume sind ein zu großes geschütz, wenn die daten doch im ram liegen bleiben. da sind schlichte binärbäume besser.Daher erstelle ich jetzt alle Nodes in einem Schlag, wodurch der Baum schonmal an einem Stück im Speicher liegen sollte.
super idee. nicht unbedingt wegen der speicherlokalität, sondern vor allem wegen der platzersparnis. weniger speicherverbrauch heißt sofort weniger einlagern. hoffe, du hast in den bäumen keine std::string liegen, die dann zwar fein angeordnet wären, der dahinterliegende speicher aber voll wirr wäre.
Allerdings ist das alles nur so rein theoretisch überlegt. Also eigentlich hab ich keine Ahnung, wie das mit dem Cache aussieht. Ist es wirklich schlimm, wenn der Speicher etwas fragmentiert ist, oder interessiert den Prozessor das gar nicht? Ich hab zwar schon häufiger was davon gehört, dass es da so "Pages" gibt, die hin und wieder geladen oder entladen werden müssen und dass das immer recht langsam ist, aber so richtig kann ich mir da nix drunter vorstellen. Wie groß ist denn so ne "Page" ? 1 MB 50 MB? 4 KB? Ich hab keine Ahnung wie groß die Auswirkung davon wäre.
4k. und die können wie gesagt unabhängig voneinader ins ram gehen und wieder auf die platte. insofern juckt den prozessor die fragmentierung gar nicht. haste datenzugriffslokalität, solltest du dieselbe lokalität im speicher hinkriegen. also sagen wie mal, daß du 2 minuten lang mit baum A arbeitest und dann 2 minuten lang mit baum B. dann sollten die bäume echt nicht vermicht im speicher liegen, damit der gerade nicht benutze baum auch komplett ausgelagert werden darf. wenn keine zugriffslokalität vorliegt und alles ins ram paßt, biste mit binärbäumen recht gut bedient und mit hashtables oft ein wenig besser. paßt zudem der kram nicht mehr ins ram (klassisches beispiel sind internet-nameserver), dann sind bei dynamischen daten b-baume und dynamische hashtables normalerweise im rennen. die hashtables cirka doppelt so schnell. mit statische daten habe kaum erfahrung. da scheint mir alles eher ne einzelfallentscheidung zu werden. ja, klar, kannst ja bestimmt statistische aussagen über die daten machen.
Wäre echt nett, wenn mich jemand darüber aufklären könnte, was man dringend vermeiden sollte, wenns auf Geschwindigkeit ankommt bzw. wie man es anstattdessen besser macht.
statische bäume? die idee klingt irgendwie krank. normalerweise haben bäume so viel speicherplatzoverhead, daß man sie nur verwendet, wenn die daten dynamisch sind.
nu weiß ich nicht, welche daten drin liegen und wie groß die einzelnen datensätze sind. aber normalerweise kann man bei statischen sachen enorm tricksen. liegen zum beispiel strings in den bäumen, kannste mit nem einfachen array und binärer suche ja mit genausovielen speicherzugriffen suchen, wie beim baum. aber ne nur 1k große indextabelle nach erstem zeichen spart dir günstistenfalls 8 speicherzugriffe pro baumabsuchung.