Performance Problem in geschachtelter Schleife
-
Jester schrieb:
Tim06TR schrieb:
*hust* iterator *hust*
Das dreht doch am völlig falschen Ende. Wenn die Daten nicht cachefreundlich im Speicher liegen, dann hilft auch ein iterator nichts.
Jain
Wenn du dir einen speziellen Iterator schreibst, der die originalen Daten in cachefreundlicher Reihenfolge durchläuft hilfts schonw as
-
Skym0sh0 schrieb:
Jain
Wenn du dir einen speziellen Iterator schreibst, der die originalen Daten in cachefreundlicher Reihenfolge durchläuft hilfts schonw as
Was wieder aufs Umordnen des Speichers und einen Iterator, der den Speicher ganz normal durchläuft herausläuft?
-
Nein, je nach Anwendung gibt es ja keine einzige und eindeutige Traversierung.
Z.B. wenn du irgendeine Kommutative Operation ausführen willst, kannst die Speicherzugriffe so aufteilen wie du willst.
Aber das ist eigentlich nur ein kleienr Spezialfall. Im Allgemeinen läufts auf eine Umstrukturierung hinaus. Und naja, egal ob man Speicher umschaufelt oder alles mit vielen Cachemisses durchläuft, man hat schon verloren. (Es sei denn man kann die Daten beim Erzeugen anders strukturieren.)
-
Auf x86 kann man mit SSE prefetch Befehle benutzen wenn es sehr auf die Leistung ankommt. (PREFETCHNTA, PREFETCH0, PREFETCH1, PREFETCH2)
3dNow hatte auch schon prefetching, und ich glaube MMX hat auch einen prefetch Befehl, kann den aber gerade nicht finden.
-
Prefetching bringt dir aber auch nicht viel wenn der Speicher einfach nicht mitkommt.
-
Skym0sh0 schrieb:
Und naja, egal ob man Speicher umschaufelt oder alles mit vielen Cachemisses durchläuft, man hat schon verloren. (Es sei denn man kann die Daten beim Erzeugen anders strukturieren.)
Naja, warum verloren das kommt doch immer drauf an, oder? Wenn sich (wie bei mir) die Daten für sehr lange Zeit nicht ändern ist das "Speicher umschaufeln" quasi vernachlässigbar. Letztendlich muss ich die Daten sogar nur einmal umsortieren (bei Programmstart halt) und kann dann den Rest des Lebens von besserer Performance profitieren.
Mal ne andere Frage, kann man das Caching und dadurch die Cache-Effizienz auch selbst beeinflussen? Oder ist das vom Betriebssystem fest vorgegeben und damit "fix"?
Also etwa dass nicht die Werte in der Nähe des Speichers gecached werden sondern eben die die etwas weiter weg liegen (wie hier mit dem
j_old += 2048)?
-
happystudent schrieb:
Mal ne andere Frage, kann man das Caching und dadurch die Cache-Effizienz auch selbst beeinflussen? Oder ist das vom Betriebssystem fest vorgegeben und damit "fix"?
Du kannst es nicht direkt veraendern. Unter Umstaenden kann das Wechseln auf groessere Pages helfen (z.B. von 4 kb auf 2 mb), denn afaik kann der Prozessor nicht ueber die Pagegrenzen hinweg cachen, aber im Allgemeinen ist die einzige sinnvolle Loeasung eine geeignetere Programmstruktur zu finden.
-
Ok, alles klar, dacht ich mir irgendwie schon.
Mal noch ne ganz andere Frage. Ich habe mich mal bei Wikipedia über das Thema Cache eingelesen. Dort habe ich unter anderem den folgenden Satz gefunden: "Da es technisch aufwändig und damit meist wirtschaftlich nicht sinnvoll ist, einen Cache zu bauen, der sowohl groß als auch schnell ist, kann man mehrere Caches verwenden".
Der Cache ist also anscheinend so klein da teuer. Der schnelle L1 Cache bewegt sich ja oft im Bereich von Kilobyte.
Warum kann man dann nicht optional seinen Rechner mit mehr Cache ausrüsten (ähnlich wie beim RAM)? Ich meine das macht ja offensichtlich schon einen gewaltigen Geschwindigkeits Unterschied aus und wenn Leute dazu bereit sind hunderte Euro in eine neue Grafikkarte zu investieren warum gibt es dann nicht zum Beispiel einen L1-Cache von 128 MB (halt für ordentlich viel Geld) zum Aufrüsten?
Oder würde das noch aus anderen Gründen so nicht gehen/den erhoften Vorteil bringen?
-
Weil der Cache um schnell zu sein nicht weit von der CPU entfernt sein kann und auf dem Die nicht unbegrenzt Platz ist?
-
Die Caches sind in der CPU eingebaut. Man hat frueher auch externe verwendet, quasi ein besonders schnelles Stueck Arbeitsspeicher, aber inzwischen laufen die CPUs so schnell, dass ein externer Cache fast gar nichts mehr bringt.
-
happystudent schrieb:
Warum kann man dann nicht optional seinen Rechner mit mehr Cache ausrüsten (ähnlich wie beim RAM)?
Das wäre schön! *träum*
Die Zeiten sind lange vorbei.
Der CPU-Cache liegt heute direkt auf dem Chip. Da is' nix mit aufrüsten...
-
Marthog schrieb:
Die Caches sind in der CPU eingebaut. Man hat frueher auch externe verwendet, quasi ein besonders schnelles Stueck Arbeitsspeicher, aber inzwischen laufen die CPUs so schnell, dass ein externer Cache fast gar nichts mehr bringt.
Hm das versteh ich nicht. Die CPU bremst hier doch gar nicht sondern der Speicherzugriff. Also ich hab ja die Vorstellung das eine Kette nur so stark ist wie ihr schwächstes Glied und dementsprechend würde mir doch auch die schnellste CPU nichts bringen wenn der Speicherzugriff so langsam ist.
Oder wie in meinem Beispiel, wenn ich
j_old += 2048benutzt habe war es extrem langsam. Wenn der Cache jetzt groß genug wäre um die nächsten 2048 Daten aufzunehmen müsste es doch genauso schnell sein wie bei "guter" Reihenfolge, also einen deutlichen Geschwindigkeits-Boost bringen?
-
