Discussion :

[idmapria]

Je code une boucle de lecture de données ram avec une opération appelée environ un million de fois à chaque frame, et qui va piocher dans une demi douzaine de tableaux, et donc il faut que je trouve des trucs pour optimiser ça.

J'ai bêtement tenté l'approche qui consiste à tout régler avec des additions pointeur+offset mais j'ai pas les perfs espérées

Serait-ce plus rapide en gérant tout ça en système tableau/index ? et/ou gérer un maximum de trucs en référence ?

[Ekleog]

L'idéal est d'éviter la lecture ram, bien plus lourde que tous les calculs que tu peux imaginer sur les indices (bon ... d'accord, presque).
En gros, l'accès ram c'est 700 cycles (de mémoire), soit (à 1GHz) 700ns ~= 0.6µs. Ce qui est énorme.
Bon, le processeur a des mécanismes de prefetch, mais ça ne compte pas, en général ce n'est pas assez.

La solution est souvent d'optimiser l'utilisation de la mémoire cache, en tentant, lorsqu'on accède à une case mémoire, de l'utiliser plein de fois de suite puis de l'oublier totalement.
Ca permet d'utiliser le mécanisme de cache processeur efficacement, et donc d'éviter au maximum les coûteux accès RAM.

Il y a également l'utilisation de cases mémoire contigües qui optimisent le cache. Donc, utiliser plusieurs tableaux va automatiquement pourrir le cache - si il y a une meilleure façon d'organiser les tableaux pour en avoir un seul où les données accédées à peu près au même moment sont environ à la même adresse, ça permettrait d'utiliser mieux le fait que le cache fonctionne par lignes.

Pour plus de détails, cf. What every programmer should know about memory

[idmapria]

L'idéal est d'éviter la lecture ram, bien plus lourde que tous les calculs que tu peux imaginer sur les indices (bon ... d'accord, presque).

mais pour faire ces calculs faut bien passer par des lectures de variables donc lire de la ram non ?... je vois comment le faire en inline assembleur en passant par les registres au lieu des variables, par contre je vois pas trop comment traduire ça en c++

La solution est souvent d'optimiser l'utilisation de la mémoire cache, en tentant, lorsqu'on accède à une case mémoire, de l'utiliser plein de fois de suite puis de l'oublier totalement.
Ca permet d'utiliser le mécanisme de cache processeur efficacement, et donc d'éviter au maximum les coûteux accès RAM.

En code ça se traduit comment ? Si je crée des pointeurs en var locale ça permet un accès plus rapide à mes tableaux ?

Il y a également l'utilisation de cases mémoire contigües qui optimisent le cache. Donc, utiliser plusieurs tableaux va automatiquement pourrir le cache - si il y a une meilleure façon d'organiser les tableaux pour en avoir un seul où les données accédées à peu près au même moment sont environ à la même adresse, ça permettrait d'utiliser mieux le fait que le cache fonctionne par lignes.

Et si j'ai crée tous mes tableaux au même moment dans mon programme, ça fait pas automatiquement des blocs contigus ?

[Trademark]

mais pour faire ces calculs faut bien passer par des lectures de variables donc lire de la ram non ?... je vois comment le faire en inline assembleur en passant par les registres au lieu des variables, par contre je vois pas trop comment traduire ça en c++

Ce que tu comprends peut-être pas c'est que entre la ram (très grande) et les registres (très petit) il y a une mémoire intermédiaire (et donc intermédiairement rapide) qu'on appelle le cache. Le problème c'est que le cache est une mémoire qui est limité à quelque mb et qu'il faut bien choisir les données que tu fais transiter de la ram vers le cache, ainsi que le contraire (celle que tu vires du cache). Les algorithmes qui font ça sont appelés algorithme de remplacement de cache, et le truc que tu dois savoir à leur propos c'est qu'ils sont souvent optimisés pour respecter le principe de localité. C'est un principe qui dit que si tu accèdes à une zone mémoire à un moment T alors au moment T+1 tu vas accéder à la même zone mémoire ou à une mémoire proche.

Pour en revenir au fait, si tu as un tableau à l'adresse 0x0000001 qui fait 1 mb alors par exemple la cache va te charger tout ce tableau en mémoire (admettons quelle fait elle aussi 1mb). Tu accèdes à l'indice i de ton tableau mais juste en dessous dans ta boucle tu veux accéder à l'indice j d'un deuxième tableau à l'adresse 0x5000001 qui fait lui aussi 1mb. Tu dois alors tout virer de ta mémoire cache et remettre le deuxième tableau (vu qu'on respecte le principe de localité spatiale), Et si tu fais ça à chaque itération tu comprends que c'est très lent.

Ce que j'ai dit est a moitié vrai car c'est super simplifié et que les algos prennent en compte la localité temporelle, c'est-à-dire que si tu accèdes à une donnée à un moment T tu risques d'y accéder à T+1, tandis que spatiale, c'est si tu accèdes à l'adresse T tu risques d'accéder à l'adresse T+1 bientôt.

[idmapria]

la mémoire cache c'est là qu'on range les variables locales non ?

voilà comment j'ai structuré mes données pour l'instant:

j'ai un tableau à deux dimensions de 16 * 1024 cases d'unsigned long

et 7 petits tableaux de pointeurs de types différents (* et **) qui permettent de retrouver des adresses précalculées sans passer par des calculs... (excepté deux sur lesquels j'ai été obligé de stocker des "adresses relatives" long integer, des offset que j'additionne à des pointeurs sur ma boucle)

si je compacte mes 16 petites tables d'int en une seule, vous croyez que ça peut accélérer la lecture dedans ?

mais en fait c'est pas ça qui consomme le plus dans mon code (lire un int n'a rien de compliqué), ce qui consomme c'est le gros mic-mac entre les tableaux de pointeurs, je sais pas si ça accélèrerait quelque chose en utilisant plutôt des int rangés en ram à partir desquels je calcule les adresses on-the-fly... ça me ferait moins de données à lire car je peux les compresser avec un jeu de bitmasks mais ça ferait plus de calculs donc au final je suis pas sûr que ça gagne grand chose (d'ailleurs j'ai tenté cette manière de coder, ça changeait pas grand chose... peut-être je devrais réessayer en simplifiant au max l'encodage des données)

[Ekleog]

On n'a aucun bout de code, il nous faudrait au moins une boucle.

Je vais prendre un exemple pour montrer le principe de ce qu'il faut faire :

Code :

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

1
2
3
4
5
6
7
8
9
10
int a[1 << 20], b[1 << 20]; // 4mb / tableau (4 octets par int et 2^20 cases)
for (int i = 0 ; i < (1<<20) ; ++i) {
  a[i] = b[i] = 0;
}
for (int i = 0 ; i < (1<<20) ; ++i) {
  for (int j = 0 ; j < 10000 ; ++j) {
    a[i] = 12345 * sin(a[i]) + 42 * j;
    b[i] = 54321 * cos(b[i]) + 24 * j;
  }
}

Devient, après optimisation pour prendre en compte le cache :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
int a[1<<20], b[1<<20];
for (int i = 0 ; i < (1<<20) ; ++i) { // Boucle sur le tableau A
  a[i] = 0;
  for (int j = 0 ; j < 10000 ; ++j) {
    a[i] = 12345 * sin(a[i]) + 42 * j;
  }
}
for (int i = 0 ; i < (1<<20) ; ++i) { // Boucle sur le tableau B
  b[i] = 0;
  for (int j = 0 ; j < 10000 ; ++j) {
    b[i] = 54321 * cos(b[i]) + 24 * j;
  }
}

On peut voir que a et b peuvent être mis en cache plus intelligemment dans le deuxième cas que dans le premier !

(Au passage, les variables locales sont, dans le cas de non-tableaux, très probablement déjà transformées en registres. Et c'est le boulot du compilateur d'optimiser tes accès mémoire dès lors que tu lui fournis du code logique !)

[bretus]

la mémoire cache c'est là qu'on range les variables locales non ?

Non, ça c'est la pile (en opposition au tas : allocation dynamique)

voilà comment j'ai structuré mes données pour l'instant:

j'ai un tableau à deux dimensions de 16 * 1024 cases d'unsigned long

La remarque au dessus concernant la localité signifie que :
somme1 = a(0,i) + a(1,i) + ... + a(15,i)

est moins efficace que ça sur une matrice permutée
somme2 = a(i,0) + a(i,1) + ... + a(i,15)

Dans le deuxième cas, les données sont voisines en RAM, quand tu accèdes à a(0,i), le proc met en cache a(1,i), a(2,i) etc. (organisation ligne puis colonne).

Tu vois?

[idmapria]

heu, donc, il vaut mieux faire des boucles sur des données qui sont proches dans la ram pour que le caching soit plus facile

si j'ai bien compris.

bon... je vais voir si y'a pas moyen de restructurer mon bordel de tableaux de pointeurs en quelque chose de plus simple que je pourrais compacter sur un seul tableau

on va voir si ça accélère quelque chose