Optimisation de code source et mémoire cache

Très intéressant, comme d'habitude.

Par contre, j'aurais peut être aimer un peu plus d'optimisation "débutant". Par exemple, dans la partie "Diminuer l'empreinte mémoire", pour moi, le padding est de l'optimisation que l'on fait dans un second temps. Il y a des erreurs que l'on revoit souvent et il serait bien que les débutants soient mieux informé.

Par exemple, un problème que l'on voit souvent est une structure du type :

1
2
3
4

struct personne {
    char prenom[50];
    char nom[50];
};

Ce code pose problème en termes d'optimisation des caches plus important que le padding.

Un autre que l'on voit souvent. Lorsque l'on lit des données dans un fichiers, on voit souvent ce genre de code :

1
2
3

vector<string> lines = read_file("blabla.txt");
for (auto string& line: lines)
    do_something(line);

Ce qui pose un problème d'allocation mémoire (1 allocation par line) et un problème de localité. Une autre approche, plus efficace, est de lire la totalité du fichier dans un bloc mémoire et avec des paires d'itérateurs :

1
2
3
4
5
6
7

string lines = read_file("blabla.txt");
auto first = begin(lines);
do {
    auto last = find_line(first, end(lines));
    do_something(first, last);
    first = last;
} until (first == end(lines))

Autre problème classique (dans la partie "structures de données"), parcourir les tableaux avec des accès aléatoires (en utilisant []). Il serait bien d'expliquer qu'il faut, si c'est possible, parcourir les tableaux séquentiellement (et donc respecter la syntaxe des algos de la STL, avec begin/end)

Bref, une petite review des erreurs classiques, pourquoi ce sont des erreurs (en termes d'optimisation du cache), comment les détecter et les optimiser.

Sinon, en C++11, il y a des nouvelles instructions pour gérer le padding. Je ne sais pas si c'est la cas en C11. En tout cas, c'est le genre de chose que j'aime bien voir Autre question : comment on connait la taille du padding dans un programme ? (et plus généralement, la taille des caches ?)

Il y a un exemple concernant les problèmes de cache que j'aime bien, c'est la comparaison entre vector et list. Cf la présentation de Sutter Modern C++: What You Need to Know

Tableaux de structures/structure de tableau. Pour aider le lecteur à faire des recherches complémentaires, je trouve que c'est pas mal de donner les termes anglais (même si la traduction est simple) : SoA (structure of array) et AoS (array of structure)

Au lieu d'utiliser des tableaux de structure, il vaut donc mieux utiliser plusieurs tableaux regroupés dans une seule structure, avec un tableau pour chaque champ de la structure

Je ne serais pas aussi affirmatif. Il y a plusieurs papiers comparatifs sur le sujet et le choix n'est pas aussi tranché. Cela dépend aussi beaucoup de la problématique.

On peut aussi citer le fait que, pour des raisons relativement techniques (liées à l’associativité du cache), il est préférable de regrouper des tableaux unidimensionnels séparés dans un seul tableau multidimensionnel. Ainsi, on peut transformer une structure de tableaux en un seul tableau multidimensionnel sans problèmes.

On voit souvent ce problème. Peut être donner un code d'exemple simple ? (et la solution)

Tableaux de pointeurs

Des codes d'exemple ?

Row et Column Major Order

Un exemple que je trouve parlant est la multiplication de matrice. Dans ce cas, il y a 2 tableaux, un qui est parcouru selon les lignes et l'autre selon les colonnes. C'est intéressant de montrer la différence entre les 2 organisations de données et la différence de performances. Montrer aussi l'avantage d'utiliser les tiles et l'impact sur les performances (et le pourquoi, niveau cache)

En tout cas, très bon début