Métaprogrammation et "ultra" optimisation de tableaux

Bonjour.

Je viens de me poser une question un peu débile, mais j'aurai besoin que vous m'éclairiez un peu.

Pour optimiser les tableaux, ce que j'ai retenu du tuto sur la métaprogrammation de Laurent Gomila (http://loulou.developpez.com/tutoriels/cpp/metaprog/), c'est que la métaprog permet de construire des "arbres" pour éviter de multiples variables temporaires.

Toutefois, je me posais une question. Une fois ces arbres générés, on reste quand même avec des tableaux et l'utilisation de l'opérateur [] qui permet d'aller chercher une variable dans le tableau. Est-ce que des bibliothèques existent où, pour encore gagner en perfs et obtenir le maximum "théorique", l'opérateur [] n'est utilisé que du côté du programmeur et est remplacé à la compilation par n variables indépendantes ?

Par exemple, comme si :

Code:

---

double mamatrice[2][2];

---

était remplacé à la compilation par 4 variables indépendantes :

Code:

---

1 2 3 4

double mamatrice_0_0; double mamatrice_0_1; double mamatrice_1_0; double mamatrice_1_1;

---

Cela permettrait-il d'atteindre de meilleures perfs ?
Existe-t-il des lib qui utilisent ce genre de méthodes ?

Merci.

C'est peut etre possible, mais tu te retrouveras a ne devoir utiliser que des constantes pour acceder aux celulles du pseudo-tableu, ce qui revient a avoir les variables coté programmeur. Du coup, plus de parcours du tableau dans une boucle,...

Bref, pas vriment utilisable.

Bonjour,

Citation:

---

Envoyé par Kaluza

Par exemple, comme si :

Code:

---

double mamatrice[2][2];

---

était remplacé à la compilation par 4 variables indépendantes :

Code:

---

1 2 3 4

double mamatrice_0_0; double mamatrice_0_1; double mamatrice_1_0; double mamatrice_1_1;

---

---

En dehors des templates, c'est déjà le cas : C et C++ sont des langages compilés dont la majorité du travail est faite en amont, à la compilation, lorsque c'est possible.

Lorsque tu déclares une variable, par exemple « int x », tu demandes à ton compilateur de prévoir la place dans la pile pour un entier et tu associes un symbole — « x » — qui est résolu en l'adresse de cette zone, fût-elle relative. Ce symbole n'existe qu'à la compilation, et il n'en reste rien une fois l'exécutable produit.

Lorsque tu déclares un tableau, ici un tableau d'entiers, tu prévois la place pour n entiers consécutifs et tu associes là encore un symbole à ce tableau, mais cette place réservée reste en un seul morceau, et le symbole, là encore, donne son emplacement en mémoire (plus précisément celui de son premier octet).

Lorsque tu vas indexer ton tableau avec une variable, par exemple « tab[i] », l'adresse finale effective dépendra bien sûr de la valeur de i à l'exécution. Donc, un morceau de code sera généré pour faire l'addition en temps voulu. Par contre, si tu te réfères à une case fixe, par exemple « tab[5] », alors tu additionnes directement deux valeurs fixes (l'adresse du tableau et l'offset de l'entrée numérotée « 5 ») et connues à la compilation.

Le compilateur résout donc l'équation et utilise une adresse fixe, exactement comme pour une variable individuelle. Utiliser quatre variables :

Code:

---

1 2 3 4

mamatrice_0_0; mamatrice_0_1; mamatrice_1_0; mamatrice_1_1;

---

… ou un tableau avec des index constants :

Code:

---

1 2 3 4

mamatrice[0][0]; mamatrice[0][1]; mamatrice[1][0]; mamatrice[1][1];

---

… revient donc rigoureusement au même en termes de performances.

Maintenant, la méta-programmation ne sert pas à fabriquer des tableaux, et ne les optimisera pas plus que si tu déclarais des tableaux ordinaires. L'exemple en question sert à mettre en évidence le fait que l'on peut — entre autres — utiliser ses propriétés pour initialiser ces tableaux selon une fonction mathématique récursive plutôt que pré-calculer soi-même ces valeurs ou lancer la fonction à l'exécution.

Il en reste que l'opérateur de template « < > » n'est pas un index sur une ressource commune comme on le fait avec un tableau. Ça sert à spécifier des noms de type ou de classe à partir desquels le compilateur va, à chaque fois, recompiler du code complètement indépendant. Donc, dans l'exemple de la factorielle, écrire le code (extrait du tutoriel) :

Code:

---

1 2 3 4 5 6 7 8 9 10

template<unsigned int N> struct Fact { enum {Value = N * Fact<N - 1>::Value}; }; template<> struct Fact<0> { enum {Value = 1}; };   unsigned int x = Fact<4>::Value;

---

… revient exactement à écrire :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

struct Fact0 { enum { Value = 1 }; };   struct Fact1 { enum { Value = 1 * Fact0::Value }; };   struct Fact2 { enum { Value = 2 * Fact1::Value }; };   struct Fact3 { enum { Value = 3 * Fact2::Value }; };   struct Fact4 { enum { Value = 4 * Fact3::Value }; };   unsigned int x = Fact4::Value;

---

… soit cinq structures complètement indépendantes entre elles et qui, en l'état, ne sont mêmes pas instanciées en mémoire. Toutes les valeurs numériques sont connues à la compilation. La dernière ligne est donc elle-même directement résolue en

Code:

---

1 2	unsigned int x = 24;

---

… avant même la génération du code.

@Obsidian: L'op faisait référence à la partie du tuto sur les expressions templates, qui servent bien à optimiser les calculs sur les tableaux (plus généralement les matrices), et pas seulement l'initialisation via des fonctions récursives.

@OP: Si tu fais comme tu le dit tu perds la propriété naturelle des tableaux C qui est la localité spatiale qui est utile pour optimiser les parcours de tableaux. Donc je ne pense pas que ton idée serait un avantage (*). Fais un benchmark pour t'en assurer.

(*) Je parle de tableaux utilisé au runtime et optimisé grace à la méta-prog, pas des conteneurs de méta-prog comme proposé par boost::mpl.