Merci pour cette (longue) lecture avec une analyse complète et intéressante.
Je reste curieux de la raison du choix du type la structure pour la matrice, un std::vector<std::vector<int>> plutôt qu'un std::vector<int> de dimension lignes*colonnes, peut-être était-ce un choix délibéré pour la simplicité d'accès aux lignes/colonnes. Ça reste acceptable vu la contraire initiale de la taille de matrice d'ordre ×ばつ10. Cela dis, si on cherche les meilleures performance possible, ce point n'est probablement pas négligeable et ce std::vector<std::vector<int>> me jette quelques grains de sable dans les yeux, pour plusieurs raisons :
* std::vector est un conteneur qui stocke les données de façon contiguë dans une zone mémoire allouée dynamiquement. Grossièrement, la structure est composée de trois pointeurs : début/fin de la zone allouée, et première "case" libre (ça peut varier selon l'implémentation)
* std::vector<std::vector<int>> est donc une structure qui pointe sur une zone allouée dynamiquement, qui elle contient des std::vector<int> qui chacun d'entre eux pointent sur d'autres zones allouées dynamiquement
* Il y a déjà un impact à l'initialisation, puisqu'il faudra allouer autant de zones que les dimensions de la matrice le nécessite (mais c'est hors benchmark ici)
* Il n'y a aucune garantie que toutes ces "petites zones" soie allouée de façon contiguë (c'est plutôt improbable), donc on augmente le risque de cache-miss
* Je ne m'étends pas sur le surcoût d'utilisation de mémoire induit par la structure
Je serais curieux de comparer ces résultats à ceux exploitant une représentation de la matrice dans une seule zone continue (par ex avec un std::vector<int>). J'aurais bien voulu ajouter un comparatif à ce commentaire, mais je ne vais malheureusement pas avoir le loisir de m'amuser avec ce problème dans les prochain temps.
# Impact de la structure
Posté par n6p7 . En réponse au journal Exercices de programmation et benchmarks. Évalué à 6.
Merci pour cette (longue) lecture avec une analyse complète et intéressante.
Je reste curieux de la raison du choix du type la structure pour la matrice, un
std::vector<std::vector<int>>plutôt qu'unstd::vector<int>de dimensionlignes*colonnes, peut-être était-ce un choix délibéré pour la simplicité d'accès aux lignes/colonnes. Ça reste acceptable vu la contraire initiale de la taille de matrice d'ordre ×ばつ10. Cela dis, si on cherche les meilleures performance possible, ce point n'est probablement pas négligeable et cestd::vector<std::vector<int>>me jette quelques grains de sable dans les yeux, pour plusieurs raisons :*
std::vectorest un conteneur qui stocke les données de façon contiguë dans une zone mémoire allouée dynamiquement. Grossièrement, la structure est composée de trois pointeurs : début/fin de la zone allouée, et première "case" libre (ça peut varier selon l'implémentation)*
std::vector<std::vector<int>>est donc une structure qui pointe sur une zone allouée dynamiquement, qui elle contient desstd::vector<int>qui chacun d'entre eux pointent sur d'autres zones allouées dynamiquement* Il y a déjà un impact à l'initialisation, puisqu'il faudra allouer autant de zones que les dimensions de la matrice le nécessite (mais c'est hors benchmark ici)
* Il n'y a aucune garantie que toutes ces "petites zones" soie allouée de façon contiguë (c'est plutôt improbable), donc on augmente le risque de cache-miss
* Je ne m'étends pas sur le surcoût d'utilisation de mémoire induit par la structure
Je serais curieux de comparer ces résultats à ceux exploitant une représentation de la matrice dans une seule zone continue (par ex avec un
std::vector<int>). J'aurais bien voulu ajouter un comparatif à ce commentaire, mais je ne vais malheureusement pas avoir le loisir de m'amuser avec ce problème dans les prochain temps.