Créer 100 blocs mémoire

Bonjour,
Je vous explique mon problème. Je fais des tests en exécutant un programme 1000 fois, et mesure à chaque fois son temps d'exécution, pour en faire la moyenne.
Le truc c'est que d'après ce que j'ai compris, le système copie alors les blocs mémoire de la RAM utilisés pas le programme dans le cache, pour un accès plus rapide.
Le problème c'est que cela fausse mes résultats (vu que pour une utilisation normale d'une programme, c'est à dire une seule exécution, le système ne ferait pas ça).
Afin de m'aider à résoudre ce problème, on m'a posé la question suivante:
Comment créer 100 blocs de mémoire de même taille, mais ayant donc des adresses différentes?
Merci d'avance pour vos réponses :P

Si je ne me trompe pas, quand tu alloues la mémoire de la manière suivante:

Code:

---

malloc(nbCases*sizeof(int))

---

Tu alloues toutes les cases adjacentes.

Pourquoi ne pas essayer de faire une boucle de 0 à 100 et faire un malloc dont tu stockeras dans un tableau ce qu'il te fournira.
Effectivement, je trouve ça laid mais si tu veux des adresses différentes (ou surtout non adjacentes), je pense que cela fait ce que tu recherches.

Le tableau étant juste là pour pouvoir accéder à la zone allouée bien sûr :mouarf:

Citation:

---

Envoyé par Analou

Bonjour,
Je vous explique mon problème. Je fais des tests en exécutant un programme 1000 fois, et mesure à chaque fois son temps d'exécution, pour en faire la moyenne.
Le truc c'est que d'après ce que j'ai compris, le système copie alors les blocs mémoire de la RAM utilisés pas le programme dans le cache, pour un accès plus rapide.
Le problème c'est que cela fausse mes résultats (vu que pour une utilisation normale d'une programme, c'est à dire une seule exécution, le système ne ferait pas ça).
Afin de m'aider à résoudre ce problème, on m'a posé la question suivante:
Comment créer 100 blocs de mémoire de même taille, mais ayant donc des adresses différentes?
Merci d'avance pour vos réponses :P

---

Un tel artefact serait facile à repérer dans une série statistique, si tu a toujours un temps long et 999 temps plus court!
MAIS de toutes façons je doute que tu aies à te préoccuper d'un tel effet:
le cache a une durée de vie limitée, de plus en fonction de l'activité de ta machine si on parle bien de 1000 EXECUTIONS DE PROGRAMME (et non 1000 appels de fonction dans un MEME PROCESSUS), il paraît peu probable que l'adresse soit la même à chaque exécution, car de nombreux processus tournent en permanence sur un ordinateur, demandant et libérant de la mémoire...

Citation:

---

Envoyé par therwald

il paraît peu probable que l'adresse soit la même à chaque exécution, car de nombreux processus tournent en permanence sur un ordinateur, demandant et libérant de la mémoire...

---

Certaines suites d'appels peuvent justement utiliser les mêmes adresses ou du moins une partie, ce qui m'est déjà arrivé à de nombreuses reprises dans un de mes projets où je dispose même d'une trace de la mémoire utilisée.

Grâce à ce module de traçage j'ai pu remarquer que le programme utilisais souvent les même adresses. Il faut se dire une chose, même si tu fait un free, cela ne veut pas dire que le système sous-jacent le fasse immédiatement alors à la prochaine demande d'allocation il se peut que le système te renvoie vers les même adresses.

Joa,

Effectivement.

Si le temps entre les exécutions n'est pas trop long, on retombe fréquemment sur la même adresse. :)

Ne pas oublier non plus que les adresses sont vues du processus lui-même, indépendamment de la vraie position en mémoire physique (qui peut changer).
En fait, un programme donné sans ASLR et avec les mêmes données d'entrée n'a aucune raison de ne pas toujours allouer le même bloc à la même adresse (de son point de vue).

Effectivment, je n'avais pas considéré ce point de vue (adresse virtuelle). Il n'en reste pas moins que je serais surpris que la zone physique soit toujours en cache. Pensez vous que ça pourrait être le cas? Je voyais plutôt le cache comme à courte durée de vie, permettant plutôt d'accélérer les traitements répétitifs au sein d'un même process, à condition que les commutations de contexte ne s'en mêlent pas, d'ailleurs.

Ah, côté cache et mémoire physique, je ne connais pas assez pour affirmer quoi que ce soit.

Citation:

---

Le truc c'est que d'après ce que j'ai compris, le système copie alors les blocs mémoire de la RAM utilisés pas le programme dans le cache, pour un accès plus rapide.

---

il faut d'abord s'assurer si c'est le cas.
Pour cela il faut connaitre l'assembleur ( x86 ) et voir dans le code assembleur généré du programme si on adresse directement des zones de RAM avec par exemple LEA ( Load Effective Adress ) ou MOV PTR...
Si en assembleur le code fait des PUSH et des POP c'est qu'on peut penser effectivement que le CPU utilise la mémoire cache

Pour répondre à ta question l'allocation des blocs mémoires cela dépend de l'OS ça fait 100 fois qu'on l'écrit
Donc avec des API comme HeapAlloc si tu est sous Windows ça devrait peut-être marcher

Citation:

---

Tu alloues toutes les cases adjacentes.

---

en appelant malloc rien ne prouve que les adresses mémoires soient adjacentes...
on peut s'en rendre compte en mettant des point d'arrêts sur la ligne de code où on fait l'allocation du pointeur en exécutant pas-à-pas

Citation:

---

Pourquoi ne pas essayer de faire une boucle de 0 à 100 et faire un malloc dont tu stockeras dans un tableau ce qu'il te fournira.
Effectivement, je trouve ça laid mais si tu veux des adresses différentes (ou surtout non adjacentes), je pense que cela fait ce que tu recherches.

---

il vaut mieux utiliser des listes chaînées mais là encore ce n'est pas forcément une solution..faut voir

Citation:

---

Envoyé par Analou

Comment créer 100 blocs de mémoire de même taille, mais ayant donc des adresses différentes?
Merci d'avance pour vos réponses :P

---

Salut
Tu peux essayer de définir un tableau de 100 pointeurs puis d'allouer de la mémoire pour chaque pointeur

Code:

---

1 2 3

int *pt[100]; for (i=0; i < 100; i++) pt[i]=malloc(nb_cases * sizeof(int));

---

Donc les 100 pt[i] seront contigus en mémoire, chaque malloc te donnera lui-aussi nb_cases contigües ; mais chaque malloc te donnera une adresse différente et pas forcément à suivre (bien qu'il y ait des probabilités que ce soit le cas)

Citation:

---

Envoyé par Mat.M

en appelant malloc rien ne prouve que les adresses mémoires soient adjacentes...

---

Ah si, un malloc de n éléments te garantit que les n cases prévues pour stocker chaque élément seront contigües en mémoire. Sinon comment le compilo ferait ensuite pour aller taper dans pt[i] si chaque case pt[i] était dispatchée au hasard ???

Citation:

---

Envoyé par Mat.M

il faut d'abord s'assurer si c'est le cas.
Pour cela il faut connaitre l'assembleur ( x86 ) et voir dans le code assembleur généré du programme si on adresse directement des zones de RAM avec par exemple LEA ( Load Effective Adress ) ou MOV PTR...
Si en assembleur le code fait des PUSH et des POP c'est qu'on peut penser effectivement que le CPU utilise la mémoire cache

---

Là je ne suis pas sûr de te suivre...à ma connaissance l'utilisation du cache dépend surtout du mode d'accès à la mémoire...sauf si on travaille en registre quelle que soit l'instruction, un accès à la mémoire RAM est caché avec la zone adjacente dans l'espoir que les prochains accès seront voisins, donc pris en charge par le cache.
Le point intéressant suivant c'est quand les données sont elles vidées du cache? A priori, quand il faut de la place pour des donnes plus fraiches et que les anciennes données sont marquées peu intéressantes par l'algorithme de gestion. Plus il s'écoule de temps, plus la probabilité que les données soient ressorties du cache augmente...
EDIT: à la relecture je me suis trouvé embrouillé, j'ai préféré rectifier

La gestion des caches L1 - L2 - L3 est assez spéciale en fait...
Aujourd'hui, seul le L3 est sur la carte mère il me semble, donc l'algorithme dépendra du fabricant de celle-ci...

Par contre les L1 et L2 sont internes au CPU, et là, je ne peux que vous conseiller ce "vieux" lien qui est très instructif : lien

En fonction de la taille des caches (à voir sur chaque CPU), des algorithmes des caches, de l'OS qui préempte (et rafraichit donc les @ à chaque accès par un processus), de l'algorithme du malloc, de la taille demandée à malloc, le nombre de mallocs.... alors l'écriture peut être répercutées en RAM ou pas.
Dans tous les cas, les adresses seront quand même MMUtisées avec optionnellement ASLR...

Ajoute mon petit texte à tout ce qui a été précédemment déduit, et tu auras une explication assez complète à remettre en ordre sur la gestion mémoire depuis un processus jusqu'au CPU en passant par les caches et la carte mère.

Pour répondre à la question de therwald, je fais 1000 appels de fonctions (une boucle for dans un main).
Pour résoudre mon problème, j'ai finalement fait un tableau de pointeurs.
L'architecture de mon programme est donc:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

int main() for(i=0; i<nombre_executions_programme; i++) { création de tab[i]; } for(i=0; i<nombre_executions_programme; i++) { exécution du programme; } for(i=0; i<nombre_executions_programme; i++) { libération de tab[i]; } return 0; }

---

Le temps d’exécution de mon programme a doublé, je pense donc que j'ai atteint le but recherché.
Cependant, lorsque je lance mon programme sur mon pc, la 1ère itération est toujours plus lente que les suivantes, alors que lorsque je le lance sur une carte ARM, les itérations sont toutes approximativement égales.
Auriez-vous une idée de là où ça peut venir?

Bonjour,

Les designeurs de CPU se cassent la tête pour maximiser le nombre de cache hit quelque soit le programme, malloc ou non.

Si tu veux faire des tests en forçant les caches miss il faut que tu les désactivent ou que tu invalides ligne de cache associée à ton pointeur.
Pour ce faire je pense qu'il n'y a que l'assembleur.
Je ne pense pas que l'OS te donne accès a ce genre de routines.

A mon avis, dfficile de contrôler le cache comme ça. Il est possible que ton accélération résiduelle corresponde à la mise en cache du code, et là je vois pas trop ce que tu y peux...
Si tu veux des stats sur l'exécution à froid, fais 1000 exécutions du programme. Pour démontrer que tes 1000 exécutions ne sont pas biaisées, tu peux conserver quelques itérations (pas forcément 1000) dans ton programme, de manière à pouvoir comparer tes 1000 itérations 1 aux itérations de rang n>1.

bon courage