Cachemisses - relevanz

hustbaer

@Miss Cache:

Ganz einfaches & IMO sehr reales Beispiel:

Du hast ein 2D Array, in den du alle Werte in einem rechteckigen Ausschnitt verdoppeln willst.
Da es um einen rechteckigen Ausschnitt geht kann man nicht einfach eine Schleife von 0 bis (width * height - 1) laufen lassen.
Also schreibt man zwei schleifen.

Variante 1:

int* array = ...

size_t const xStep = 1;
size_t const yStep = arrayWidth;

for (size_t x = left; x < right; x++)
{
    int* p = &arrary[x * xStep + y * yStep];
    for (size_t y = top; y < bottom; y++)
    {
        *p += *p;
        p += yStep;
    }
}

Variante 2:

int* array = ...

size_t const xStep = 1;
size_t const yStep = arrayWidth;

for (size_t y = top; y < bottom; y++)
{
    int* p = &arrary[x * xStep + y * yStep];
    for (size_t x = left; x < right; x++)
    {
        *p += *p;
        p += xStep;
    }
}

Variante 1 ist wesentlich langsamer als Variante 2.
Wenn man ein wenig über Caches & Speicherzugriffe bescheid weiss, ist klar warum.
Wenn man nichts über Caches weiss, könnte man Variante 1 programmieren, und nichtmal auf die Idee kommen dass das noch schneller geht.

Weiters ist der in dem "gallery-of-processor-cache-effects" Posting/Paper auch beschriebene "false sharing" Effekt sehr real, das passiert oft genug. Nur wird es oft nicht bemerkt, da kaum jemand ein Programm von einem Tool ala Intel Thread-Profiler untersuchen lässt. Und wenn man nicht weiss wo die Bremsklötze sind, warum sollte man dann auf die Idee kommen andere Varianten auszuprobieren.

Miss Cache schrieb:

Das mit dem Cachemiss sieht mir relativ überbewertet aus.

Dein persönliches Empfinden ist unbegründet. Es gibt genügend Paper, die gerade das Gegenteilige belegen.

OK, bei der Bildverarbeitung kann man schon etwas langsam machen, wenn man überhaupt keine Ahung von Caches hat und quer durch den Speicher geht, aber davon, dass Cachemisses das sind was jetzt Programme so furchbar langsam macht, sind wir weit weg. Die meisten Programme sind viel schlechter durchdacht, als ein bekannter Bildverarbeitungsalgo. da läßt sich viel einfacher viel mehr rausholen, als man jetzt versuchen müsste alles perfekt auf den Cache anzupassen. Bei den meisten Programmen dürfte es ungefähr so sinnvoll sein nach Cachemisses zu suchen, wie mit ner Dampfwalze in nen Windkanal zu gehen.

meeeep schrieb:

Miss Cache schrieb:

Das mit dem Cachemiss sieht mir relativ überbewertet aus.

Dein persönliches Empfinden ist unbegründet. Es gibt genügend Paper, die gerade das Gegenteilige belegen.

Ja, leider gibt es (wahrscheinlich) keine Paper, die untersuchen wieviele Programme einfach schlecht programmiert sind und ganz unabhängig von Cachemisses deutlich schneller sein könnten, wenn nicht soviel Müll programmiert werden würde. Da könnte man dann etwas über viel größere Performancegewinne lesen, als in den Papers über Cachemisses.

Und was hat das mit dem Thema zu tun?

Tim schrieb:

Und was hat das mit dem Thema zu tun?

Ich bezeifle einfach, dass das die großen Probleme moderner Programme sind.

TGGC schrieb:

Cache Misses sind in einem normalen PCs das ungefaher langsamste was er so macht. Sie werden immer relevanter, da die Speicheranbindungen langsamer wachsen als alles andere.

rüdiger schrieb:

Die Relevanz ist heutzutage größer denn je. Das liegt nämlich daran, dass die Geschwindigkeit der CPUs drastisch wächst. Aber die Anbindung zum RAM nicht schnell genug nachkommt. Das heißt das Zugriffe zum RAM proportional teurer werden und daher wird es relevanter, dass man sich besser darum kümmert, dass die wichtigen Daten in den Cache passen.

siehe zB http://research.scee.net/files/presentations/gcapaustralia09/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf

Aber ja, in einem Referat über Cachemisses darf/muss man natürlich sowas erzählen, wie wichtig sie heutzutage sind usw. das kommt gut. Wenn man da sagen würde, bei dem Müll den 95% von euch (die Zuhöreren sind gemeint) so programmieren werdet, braucht ihr nicht über Cachemisses nachdenken, würde das dem Lehrer wahrscheinlich nicht so gefallen. Das wäre so, als würde man bei nem Referat über Gesetzgebungsverfahren nicht von Bundesrat, Bundestag und dem formalen Zeug reden, sondern über Lobbypolitik herziehen.

Miss Cache schrieb:

OK, bei der Bildverarbeitung kann man schon etwas langsam machen, wenn man überhaupt keine Ahung von Caches hat und quer durch den Speicher geht, aber davon, dass Cachemisses das sind was jetzt Programme so furchbar langsam macht, sind wir weit weg.

antiquiertes denken ...

Die meisten Programme sind viel schlechter durchdacht, als ein bekannter Bildverarbeitungsalgo. da läßt sich viel einfacher viel mehr rausholen, als man jetzt versuchen müsste alles perfekt auf den Cache anzupassen. Bei den meisten Programmen dürfte es ungefähr so sinnvoll sein nach Cachemisses zu suchen, wie mit ner Dampfwalze in nen Windkanal zu gehen.

Da empfehle ich die "3 big lies" zu lesen.
1. Software is a Platform
2. Code designed around model of the world
3. Code is more important than data
http://www.insomniacgames.com/assets/filesthreebiglies2010.pdf

MrCache schrieb:

Miss Cache schrieb:

OK, bei der Bildverarbeitung kann man schon etwas langsam machen, wenn man überhaupt keine Ahung von Caches hat und quer durch den Speicher geht, aber davon, dass Cachemisses das sind was jetzt Programme so furchbar langsam macht, sind wir weit weg.

antiquiertes denken ...

Wir werden ja sehen, wie wichtig sie werden. Hier wurde ja auch schon Haskell als die Zukunft angepriesen, weil man angeblich nur damit die Probleme moderner Multicoresysteme in den Griff bekommt. Monster.de liefer immer noch keine Jobs für "haskell".

Miss Cache schrieb:

meeeep schrieb:

Miss Cache schrieb:

Das mit dem Cachemiss sieht mir relativ überbewertet aus.

Dein persönliches Empfinden ist unbegründet. Es gibt genügend Paper, die gerade das Gegenteilige belegen.

Ja, leider gibt es (wahrscheinlich) keine Paper, die untersuchen wieviele Programme einfach schlecht programmiert sind und ganz unabhängig von Cachemisses deutlich schneller sein könnten, wenn nicht soviel Müll programmiert werden würde. Da könnte man dann etwas über viel größere Performancegewinne lesen, als in den Papers über Cachemisses.

Du hast Recht in dem Punkt das konzeptionelle Verbesserungen einen wesentlich größeren Performance-Gewinn bringen als reine Cache-Optimierungen. Das bedeutet allerdings noch lange nicht, dass diese nicht relevant sind.
Ansonsten, nenne doch bitte ein Problem der Informatik, wo das schnellste Programm wegen schlechter Programmierung so langsam ist.