Discussion :

[vingt sens]

Bonjour,

J'ai effectué une optimisation de la vitesse de calcul d'une opération en optimisant la mémoire cache et je me pose des questions sur la libération de la mémoire cache pour éviter des fuites mémoires.

J'ai une liste d'objet de types différents qui héritent d'une classe commune. En temps normal, j'utiliserais une liste de pointeur vers cette classe commune et je ferrais un simple parcours de la liste. Cela signifie que l'on a une liste d'adresse mémoire, cette liste d'adresse est elle même allouée à un emplacement particulier.

En terme de gestion de la mémoire, cela signifie que le programme va faire un accès à adresse mémoire de la liste, ce qui enclenche un chargement dans la mémoire cache d'une portion de la RAM qui contient cette liste d'adresse. Ensuite lorsque l'on accede à un élément de la liste, on va charger dans la mémoire cache la portion qui concerne cet objet. Enfin, une fois l'objet traité, on accède de nouveau à la liste en chargeant de nouveau la mémoire cache. Ainsi à chaque changement de portion de mémoire, on perd du temps. Sans compter que le traitement d'un objet peut dépendre d'un objet voisin ce qui demande d'autres mise à jour de la mémoire cache.

La solution que j'ai implémenté consiste à utiliser une liste chaînée dont les objets sont placés de manière consécutive dans la mémoire, ainsi les chargements de la mémoire cache deviennent plus rare.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
27
28
29
30
31
32
 
// exemple de trois objets de type différents qui héritent de ClassP
// 1) taille de chaque type de classe
uint sizeA = sizeof(ClassA);
uint sizeB = sizeof(ClassB);
uint sizeC = sizeof(ClassC);
// 2) allocation de l'espace mémoire et calcul des adresses des futurs objets 
void* address = malloc(sizeA+sizeB+sizeC);
void* addressA = address;
void* addressB = addressA+sizeA; // l'addition n'étant pas valable pour le void* en réalité je passe par un cast vers char*, je n'écris pas ces opérations par soucis de lisibilité
void* addressC = addressB+sizeB;
// 3) creation des objets aux addresses définies
ClassA* a = new(addressA) ClassA(); // a == addressA == address
ClassB* b = new(addressB) ClassB(); // b == addressB
ClassC* c = new(addressC) ClassC(); // c == addressC
// 4) paramétrage des objets
a->next = b;
b->next = c;
c->next = nullptr;
// 5) traitement
ClassP *current = a;
do
{
  a->exec();
  current = current->next;
}
while(current != nullptr)
// 6) liberation de l'espace mémoire
delete a;
delete b,
delete c;
free(address);

tout d'abord, ai-je réinventé la roue et existe t'il un type standard de liste permettant d'effectuer la même opération?

ensuite, ce qui me gène est la libération de l'espace mémoire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
delete a; // a == address
free(address);

je fais appel à 'delete a' pour accéder au destructeur avant de désallouer, mais dans les faits je désalloue deux fois la même adresse mémoire (ce qui ne fonctionne pas).

j'imagine que lors de l'allocation, il existe une liste dans le système de gestion du programme qui fait le lien entre les addresses et la taille des objets alloués. De cette manière si j'alloue l'emplacement pour un objet le programme est capable d’empêcher une allocation sur cet espace mémoire et de désallouer la bonne taille.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
char* c = (char*) malloc(15);
free(c) // on n'indique pas la taille à la libération, cela signifie que le programme connait la taille de l'allocation d'une autre manière
 
ClassP* p = new ClassA();
delete(p) // on a perdu l'information de la classe d'origine: sizeof(ClassA) != sizeof(classP),
          // donc le programme connait la taille de l'allocation sans avoir besoin de connaitre le type

Dans mon exemple plus haut, j'effectue une sorte de double allocation et je désalloue deux fois.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
void* address = malloc(size)
ClassA* a = new(address) ClassA();
delete a;
free(address);

- Est ce que `delete a` seul ne désalloue pas en même temps le pointeur address?
- Est ce que `free(address)` est il suffisant pour désallouer en même temps `a`, `b` et `c`? quid du destructeur?

merci d'avance

[mintho carmo]

> tout d'abord, ai-je réinventé la roue et existe t'il un type standard de liste permettant d'effectuer la même opération?

Non, mais ce que tu veux faire ressemble au pattern Object Pool. Cf par exemple https://gameprogrammingpatterns.com/object-pool.html

> je fais appel à 'delete a' pour accéder au destructeur avant de désallouer, mais dans les faits je désalloue deux fois la même adresse mémoire (ce qui ne fonctionne pas).
> Est ce que `delete a` seul ne désalloue pas en même temps le pointeur address?
> Est ce que `free(address)` est il suffisant pour désallouer en même temps `a`, `b` et `c`? quid du destructeur?

Oui. C'est un des rares cas où appeler directement le destructeur (donc sans passer par delete) est valide. Cf les codes d'exemple de la doc : https://en.cppreference.com/w/cpp/la...#Placement_new

Dans tous les cas, mesures bien les performances. Parce que c'est typiquement le genre d'optimisation qui peut avoir un gain nul (ou négligeable) si ce n'est pas nécessaire. D'ailleurs, as tu décidé de faire cela parce que tu as observer une perte de performance due au cache en faisant du profiling ? Ou c'est juste une optimisation random ?

[jo_link_noir]

Cela me fait penser à Boost.intrusive, le pool d'allocation en moins. La liste ne gère pas l'allocation qui se fait à l'extérieur, même si celle-ci peut contenir des nœuds de pointeur comme unique_ptr et contenir des types différents (manipulé sous la forme d'un pointeur commun).

Pour le pool, mon avis que std::pmr::unsynchronized_pool_resource fait le taf. Voir carrément un std::list avec cet allocateur.

Le faire à la main impose pas mal de piège et manipulation manuelle. Par exemple, ici tu ne prends pas en compte l'alignement des classes, cela peut fonctionner au prix d'un surcoût sur certaines architectures et un plantage sur d'autres.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
struct A{char c;};
struct B{int i;};
struct C{A a; B; };
 
sizeof(A) == 1
sizeof(B) == 4
sizeof(C) == 8
 
new(addr + sizeA) B => l'instance n'est pas aligné sur la frontière d'un int.

Chose qui peut être corrigé avec std::align.

[vingt sens]

Bonjour, merci pour vos réponse, j'ai été négligeant de ne pas répondre plus tôt, je vous prie de m'en excuser.

Dans tous les cas, mesures bien les performances. Parce que c'est typiquement le genre d'optimisation qui peut avoir un gain nul (ou négligeable) si ce n'est pas nécessaire. D'ailleurs, as tu décidé de faire cela parce que tu as observer une perte de performance due au cache en faisant du profiling ? Ou c'est juste une optimisation random ?

D'après les tests que j'ai effectué, j'arrive à obtenir des gains entre 2 et 3 (mais il ne s'agit pas du code final). Comme il s'agit de passer de très nombreuses fois dans cette boucle (2^N), l'effet n'est pas si négligeable que ça d'autant que je suis contraint en terme de réaction du système (calcul < 1 minute).
Pourquoi, ai-je tenter cette optimisation? Tout simplement parce que je cherchais des moyens de réduire les temps de calculs et que je connaissais la théorie de la mémoire cache. Je voulais savoir si cela pouvait m'apporter quelque chose, j'ai effectué quelques recherches sur les performances des listes et j'ai tenté ce test. Après j'ai d'autres solutions d'optimisation: tenter de déterminer par avance les passages qui auront peu d'impacts sur la solution et les éliminer, décomposer la liste des éléments en groupe plus ou moins indépendant (2^N1+2^N2 avec N1+N2 = N mais interaction des groupes est à gérer en plus), usage du multi-threading sur CPU voir GPU.

Oui. C'est un des rares cas où appeler directement le destructeur (donc sans passer par delete) est valide

intéressant, je ne savais pas qu'il était permit d’appeler directement le destructeur.

Le faire à la main impose pas mal de piège et manipulation manuelle. Par exemple, ici tu ne prends pas en compte l'alignement des classes,

Ok, il faut tout avoir en tête quand on fait ce genre de chose, maintenant que tu le dis, cette histoire d’alignement me semble évidente.

Je vais voir si je peux faire une une version non optimisé pour comparer les performances, en faisant cette fois-ci attention à l’alignement.

Sinon, pour les solutions, il faut que je regarde.

Je vous remercie encore

[koala01]

Salut,

Bonjour, merci pour vos réponse, j'ai été négligeant de ne pas répondre plus tôt, je vous prie de m'en excuser.

C'est bon pour une fois, nous ne t'en tiendrons pas rigueur

Plus sérieusement: cela arrive très souvent, on a l'habitude, et on ne t'en tiendra pas rigueur

D'après les tests que j'ai effectué, j'arrive à obtenir des gains entre 2 et 3 (mais il ne s'agit pas du code final). Comme il s'agit de passer de très nombreuses fois dans cette boucle (2^N), l'effet n'est pas si négligeable que ça d'autant que je suis contraint en terme de réaction du système (calcul < 1 minute).

En fait, jo_link n'a jamais dit que tu avais tord de le faire. Il t'a juste mis en garde -- et à juste titre -- sur un point que les gens ont beaucoup trop facilement tendance à oublier:

Premature optimisation is the root for all evill

Il est clair qu'une boucle présentant une complexité en O(2^N) est une candidate plus que plausible aux optimisations, mais ca, il ne pouvait pas le deviner, vu que tu ne l'avais pas dit

Et, dans de telles conditions, mieux vaux prévenir que guérir en faisant une "piqûre de rappel" que de se retrouver face à quelqu'un qui finit avec un code completement illisible et qui ... se plaint toujours de problèmes de performance, parce qu'il a essayer d'optimiser tous les points qui n'en valaient pas la peine, mais n'a rien fait pour optimiser ceux qui auraient pu apporter les meilleurs gains

Pourquoi, ai-je tenter cette optimisation?

Oh, mais on ne doute absolument pas de tes raisons. On sait bien qu'elles sont de toutes façons parfaitement justifiées à tes yeux.

On n'est d'ailleurs pas opposé par principe aux optimisations, pour autant qu'elles soient soutenues par des mesures qui prouvent leur efficacité, ou, à tout le moins, par une analyse démontrant que l'on va clairement agir sur l'un des points du code sur lequel on passe le plus de temps.

Tu sais sans doute que, de manière tout à fait empirique, considère généralement que 80 à 90% du temps d'exéction est utilisé par 10 à 20 % du code seulement. Encore une fois, si une des boucles principales s'effectue selon une complexité en O(2^N), elle part effectivement favorite pour l'optimisation

En l'occurrence, un gain de l'ordre de 1:2 ou 1:3 la justifie pleinement

Tout simplement parce que je cherchais des moyens de réduire les temps de calculs et que je connaissais la théorie de la mémoire cache. Je voulais savoir si cela pouvait m'apporter quelque chose, j'ai effectué quelques recherches sur les performances des listes et j'ai tenté ce test.

Effectivement, les cache misses, dans les boucles dans lesquelles on passe le plus de temps, sont une des causes principales de diminution des performances.

Si tu ne parlais pas d'objets polymorphes (qui impliquent souvent le recours à l'allocation dynamique de la mémoire), le simple fait de remplacer une liste par un tableau, pour lequel on réserve directement une taille suffisante, fait souvent des miracles sur ce point

Après j'ai d'autres solutions d'optimisation: tenter de déterminer par avance les passages qui auront peu d'impacts sur la solution et les éliminer, décomposer la liste des éléments en groupe plus ou moins indépendant (2^N1+2^N2 avec N1+N2 = N mais interaction des groupes est à gérer en plus), usage du multi-threading sur CPU voir GPU.

Cela peut effectivement être tenté, mais, encore une fois, rappelle toi ce qu'a dit knuth, parce que tu pars sur des possibilités qui vont te compliquer énormément la vie, en termes de débuggage entre autres

Avant de te lancer dans de telles démarche, veille d'abord et avant tout à avoir quelque chose qui fonctionne correctement, et à t'assurer que tu as vraiment besoin d'améliorer les performances. Car, si, en l'état, tu peux déjà obtenir ton résultat en 59 secondes ou moins, tu restes "dans les clous" non

En plus, l'idée du multi-threading est souvent largement surfaite

intéressant, je ne savais pas qu'il était permit d’appeler directement le destructeur.

Ah, oui, on évoque très rarement le placement new, parce que c'est une approche "de haut vol", qui ne se justifie réellement que lorsque l'on part, justement, vers un système d'allocation des ressources personnalisées

Mais c'est l'un des grands avantages de C++: il fourmille littéralement de possibilités peu / mal connues, dont on ne fait pas la publicité car elles pointent un fusil chargé sur ton pied, mais qui s'avèrent, dans certaines circonstances, particulièrement utiles

Je vais voir si je peux faire une une version non optimisé pour comparer les performances, en faisant cette fois-ci attention à l’alignement.

Ce que tu pourrait aussi envisager, vu que tu as créé ton propre allocateur (et, en toute logique, ton propre déallocateur, vu qu'ils vont par paire), c'est utiliser la classe std::unique_ptr pour stocker les éléments dans ta liste, en précisant le deuxième paramètre template, celui qui utilise std::default_delete par defaut, de manière à profiter pleinement du RAII

[Luc Hermitte]

Petite piqûre de rappel au cas où: A moins qu'une structure chaînée soit absolument ce dont tu as besoin, en général, même et surtout avec des milliers d'éléments un vecteur écrase à plate couture une liste chaînée pour les raisons de cache justement. Et ce même quand on s'amuse à ajouter et retirer en plein milieu -- à fréquence raisonnable par rapport au parcours séquentiel.