Performance de la matrice en colonne row- par rapport à traversal

Question

Scott Meyers décrit qui traverse une matrice nettement mieux effectué sens de la rangée symétrique sur le traversant en colonne - qui est aussi significativement contre-intuitif.

Le raisonnement est lié à la façon dont sont utilisés les caches-CPU. Mais je ne comprends pas vraiment l'explication et je voudrais le faire parce que je pense qu'il est pertinent pour moi.

Est-il possible de le mettre en des termes plus simples pour quelqu'un non titulaire d'un doctorat en architecture informatique et le manque d'expérience dans la programmation au niveau matériel?

Answer 1

Dans les architectures standards d'aujourd'hui, l'utilisation du cache ce qu'on appelle « -localisation spatiale ». Telle est l'idée intuitive que si vous appelez une cellule dans la mémoire, il est probable que vous voulez lire des cellules qui sont « à proximité ». , C'est en effet ce qui se passe lorsque vous lisez 1D tableaux.

Maintenant, considérons comment une matrice est représenté dans la mémoire: une matrice 2D est simplement codé comme un tableau 1D, rangée par rangée . Par exemple, la matrice $ \ left (\ begin {array} {} ll 2, 3 \\ 4, 5 \ end {array} \ right) $ est représenté comme 2,3,4,5 $ $.

Lorsque vous commencez à lire la matrice en $ cellulaire (0,0) de $, la CPU met automatiquement en cache les cellules qui sont à proximité, qui commencent par la première ligne (et s'il y a suffisamment de cache, peut aussi aller à l'autre rangée, etc).

Si votre algorithme fonctionne ligne par ligne, le prochain appel sera un élément encore dans cette ligne, qui est mise en mémoire cache, de sorte que vous obtiendrez une réponse rapide. Toutefois, si vous appelez un élément dans une autre ligne (quoique dans la même colonne), vous devez obtenir un défaut de cache plus probable, et vous aurez besoin d'aller chercher la cellule correcte d'une mémoire supérieure.