Discussion :

[camboui]

Bonjour,

Lors d'une recherche binaire (dichotomique), par exemple dans un vecteur d'1 million d'éléments (~=2^20), il y a jusqu'à 20 itérations. La probabilité pour que l'élément à trouver le soit dans les 10 premières itérations est de 0,001 (un sur mille, ~1000=2^10). Autant dire que ces 10 premières itérations sont (presque) toujours réalisées.

La proposition d'optimization consiste à créer un tableau ne contenant que le sous-ensemble des éléments nécessaires à ces 10 premières itérations. Le but est que les infos de ce tableau, pour lesquelles l'accès est très fréquent, soient regroupées afin qu'elles tiennent dans un block du cache data de niveau 1 du processeur. Qu'en pensez-vous, y aurait-il un gain de performance ?

On peut déplacer le problème en plaçant le tableau sur disque et en laissant le millième du tableau sur lequel l'accès est le plus fréquent en mémoire vive. Intuitivement le gain me parait évident: les dix premières itérations se font en mémoire, puis les 10 suivantes aussi après une seule lecture sur disque d'un block d'un millième de la taille du tableau complet.

D'une manière plus générale, de tout tableau, en fonction du nombre et de la taille de ses éléments, on pourrait extraire récursivement le sous-tableau des éléments fréquemment accédés lors d'une recherche binaire.
Par exemple, sur un tableau d'un milliard d'éléments, on extrait les mille éléments susceptibles d'être atteint par les 10 premères itérations. Chacun de ces mille éléments sont à la tête d'un tableau d'un million d'éléments duquel on peut à nouveau extraire mille éléments. Lors d'un recherche binaire, l'élément à trouver le serait en ne lisant, au plus, que 3 blocks de mille éléments (sur 1 milliard).

Merci.

[ToTo13]

Bonjour,

mmm... j'ai un doute sur le gain :s
Pour trouver un élément dans un tableau de mille éléments, il faut dix itérations.
Avec ton idée, il faut trois fois dix itérations pour trouver un élément dans un tableau de un milliard, ce qui est équivalent au nombre d'itération nécessaires pour trouver un élément dans un tableau de un milliard d'éléments (~2^30).

[jkalzsmu]

Je pense aussi que le gain de temps n'est pas forcement flagrant.

Tu vas forcement gagner du temps puisque tu stocke en RAM des informations sur ta structure. Mais ce gain de temps sera de moins en moins flangrant si la taille de ton tableau initial augmente.

[camboui]

Je crois que vous ne m'avez pas compris.
Le but n'est pas de remettre en cause la recherche binaire (le nombre d'itérations ne sera pas diminué), mais de constater que le traitement des informations se fait par block sur disque, dans les caches des processeurs aussi, afin de répartir différemment les informations pour tirer parti de ce traitement par block.

En reprenant l'exemple du tableau sur disque de 1 milliard d'éléments, l'implémentation tel quel de l'algo binaire provoquera 30 lectures sur disque et 30 itérations. Dans ma proposition, il n'y aurait que 3 lectures (mais toujours 30 itérations). On bénéficie ainsi des spécificités hardware qui "aime" que les infos soient regroupées en petits blocks.

Vous me suivez ?

[pseudocode]

Vous me suivez ?

Heu... quelle difference entre ton idée et un arbre binaire qui serait stocké suivant un parcours en largeur ?

[camboui]

Heu... quelle difference entre ton idée et un arbre binaire qui serait stocké suivant un parcours en largeur ?

Un arbre n'est pas un tableau. A chacun ses avantages et ses inconvénients. J'aimerais bénéficier des avantages des deux.
Et effectivement, dans un arbre binaire (bien fait) les éléments "milieu" sont groupés. Par contre, lorsqu'on veut un accès séquentiel...
Je cherche donc une manière optimal d'accéder de manière directe, séquentielle et dichotomique à des infos.

Bonjour,

ok sur le principe... mais est ce vraiment un gain si nécessaire ?
Pour ma part je ne suis pas assez calé au niveau hardware pour savoir si c'est vraiment utile.

Plus qu'utile ou nécessaire, est-ce que le gain est significatif ? Je ne sais pas, c'est pour ça que je le demande... Et je suis curieux d'avoir la réponse. Intuitivement je pense que oui.

Si les fabricants de hardware se décarcasse pour nous mettre des mémoires caches un peu partout, technologie que je crois volontiers très complexe, c'est que les gains en performances sont bien réels. Si, de plus, on peut cibler nos implémentations en tenant compte de cette technologie afin de maximaliser ses bénéfices, pourquoi se priver ?

Bref, au lieu de jouer les avocats du diable, encouragez-moi

[ToTo13]

Bonjour,

ok sur le principe... mais est ce vraiment un gain si nécessaire ?
Pour ma part je ne suis pas assez calé au niveau hardware pour savoir si c'est vraiment utile.