Optimisation des accès mémoire

L'accès à de gros volumes de données stockés en mémoire peut avoir des répercutions importantes sur le temps d’exécution d'un programme. Comme les données sont généralement mémorisées dans la RAM, cela nécessite un transfert de la RAM vers le processeur. Ce transfert est coûteux car sur les PC, la RAM et le processeurs sont physiquement séparés. Lorsque l'on doit accéder fréquemment à un tableau de données la question de l'optimisation est un problème. J'ai lu et entendu beaucoup de choses sur ce sujet, voici la vérité (presque...). Cet article se focalise sur la lecture/écriture dans de grands tableaux de données stockés en mémoire. Nous ne considérerons pas le problème de l'allocation qui n'est généralement fait qu'une fois. Les tests suivants ont été réalisés sur une architecture Intel (octo-coeur I7) sous Ubuntu 14.04. Les données sont stockés en mémoire (pas de swap sur disk).

Accès continu versus Accès aléatoire

La première chose que l'on trouve dans la littérature est que l'accès continu à un tableau est plus rapide qu'un accès aléatoire. Considérons les codes suivants:

 
// Continuous access
uint16_t* array=new uint16_t [SIZE];
uint16_t Val;
for (uint64_t i=0;i

versus

// Random reading of data
uint16_t* array=new uint16_t [SIZE];
uint16_t Val;
for (uint64_t i=0;i

Les macros TIC et TOC macros mesurent le temps d'éxécution. Voici les résultats :

test1

La première conclusion est que l'accès continu est plus rapide. On pourrait imaginer que lors d'un accès mémoire, seuls les octets utiles sont copiés, mais en réalité le processeur copie des segments de données. Cela signifie que lors d'un accès continu, le nombre de copies est moindre, car les octets voisins sont déjà copiés. Lors d'un accès aléatoire, une copie doit être faite à chaque accès (si les octets ne sont pas dans le même segment. Je ne sais pas pourquoi l'écriture est plus rapide que la lecture. Si vous avez la réponse, n'hésitez pas à laisser un message en bas de la page.

New versus Malloc


L'allocation mémoire peut être faite avec les instructions new(c++) ou malloc(c). La question ici n'est pas de savoir lequel est le plus rapide, la question est de savoir si les données allouées avec l'un sont plus rapidement accessibles que les données allouées avec l'autre. Voici la réponse:

test2

Manifestement c'est équivalent. Ce n'est pas une grande surprise étant donné que dans les deux cas, les données sont stockées en mémoire. La légère différence entre les deux est probablement due aus autres processus du système qui ont pris un peu de ressources durant les tests

Accès à des tableaux multidimensionnels

Prenons l'exemple d'un tableau à deux dimensions alloué dynamiquement (par exemple une image). Nous voulons accéder au pixel de coordonnées (x,y). La première solution consiste à créer un tableau de taille width*height et d'accéder aux éléments en calculant l'index: y*width+x.

// Test 1 
uint16_t* array=new uint16_t [SIZE];
// ...
TIC_MACRO;
Val=array[y*WIDTH+x];
TOC_MACRO;

Bien sûr, cette première solution nécessite de calcul d'une multiplication et d'une addition qui peut être couteux. Une solution fréquement proposée est de créer un second tableau de pointeurs contenant l'adresse de chaque ligne du tableau principal. Cette solution nécessite une second tableau mais permet de s'affranchir du calcul de l'index:

// Test 2
uint16_t* array=new uint16_t [SIZE];
uint16_t** pArray=new uint16_t* [HEIGHT];
for (int i=0;i

Si les données ne doivent pas nécessairement être stockées de manière continue, il est même possible d'allouer chaque ligne séparément:

// Test 3
uint16_t** pArray=new uint16_t* [HEIGHT];
for (int i=0;i

Voici la comparaison:
test3

Comme on peut le constater, la première solution est la plus rapide, même si elle nécessite le calcul de l'index. Sur les machines contemporianes, un calcul de ce type ne prend en réalité que quelques cycles alors qu'un accès mémoire beaucoup plus. La seconde solution nécessite deux accès mémoires, un pour le pointer de ligne, et un autre pour la donnée. La troisième solution est encore plus mauvaise : elle nécessite plus de transferts de la mémoire vers le processeur car les données peuvent être dispersée en mémoire.

Type de données

Bien sûr, choisir letype de données approprié optimise la mémoire, but la question qui se pose ici est : est-ce que certains types de données sont plus rapides que d'autres ? J'ai entendu dore que des données alignées sur 32 ou 64 bits étaient plus rapides car les processeurs sont optimisés pour ce format de données. Par exemple, sur une architecture 32 bits un tableau de char serait moins rapide qu'un tableau de int. Voici le résultat d'éritures/lectures sur différents types de données :

test4

Il est clair que le type de données change les temps d'accès. Plus le type est grand, plus l'accès est lent. Je suppose que c'est lié au fait que de plus grands tableaux nécessitent plus de copies de la mémoires vers le processeur. Un tableau de uint64_t est 8 fois plus grand qu'un tableau de uint8_t. Ces résultats sont toutefois à prendre avec précaution car ces temps d'accès ne sont pas nécessairement vrais lorsque l'on accède à quelques octets.

Téléchargement

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *