Recherche binaire: optimization

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.

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).

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.

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 ?

Citation:

---

Envoyé par camboui

Vous me suivez ?

---

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

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.

Citation:

---

Envoyé par pseudocode

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.

Citation:

---

Envoyé par 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.

---

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 :D

Citation:

---

Envoyé par camboui

Un arbre n'est pas un tableau.
A chacun ses avantages et ses inconvénients. J'aimerais bénéficier des avantages des deux.

---

Qui peut le plus (arbre) peut le moins (tableau) : le B+ tree

Hia,

Chaque fois que ton fichier à traiter sera modifié, il faudra que tu refasses tous tes intermédiaires (si la taille change, les points intermédiaires accédés changeront [pas forcément, mais...], si les données elles-mêmes changent, n'en parlons même pas).

Donc, s'il change à chaque utilisation, oublie.

Pour ton idée d'optimiser par rapport au processeur, ça part d'un bon sentiment, mais l'optimisation des processeurs avec leurs mémoires caches, etc. n'a que peu (pas ?) d'impact pour les accès disques, qui se comptent en millisecondes, devant des nanosecondes pour la mémoire.

Citation:

---

Pour ton idée d'optimiser par rapport au processeur, ça part d'un bon sentiment, mais l'optimisation des processeurs avec leurs mémoires caches, etc. n'a que peu (pas ?) d'impact pour les accès disques, qui se comptent en millisecondes, devant des nanosecondes pour la mémoire.

---

En fait tout dépend de l'utilisation. Si c'est pour une BDD le temps d'accès au disque n'est pas négligeable.

Citation:

---

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.

---

Je ne suis pas tellement contre ton raisonnement (quoique), mais un B arbre ne me semble pas si lent que ça.

De plus, si tu veux effectuer une recherche dichotomique, il suffit de stocker le nombre d'éléments dans chacun des noeuds.

Si j'ai bien compris la suggestion de Pseudocode, il te suggère de stockr sur disque ton arbere dans un ordre bien particulier : le premir élément est la racine de l'arbre. les deux éléments suivants sont les deux filles de la racine, etc.
Quand tu vas lancer la recherche avec l'algo approprié, tu vas d'abord lire sur le disque l'émément 1 mais, sans te le dire, ton ordi va charger en mémoire tout le bloc contigu au cas ou tu en aurais besoin, ce qui est justement le cas. Ce n'est que quand tu atteindra les étages les plus profonds que chaque requête au disque donner lieu à une lecture effective du disque, et non pas de son cache.

Citation:

---

Envoyé par ol9245

Si j'ai bien compris la suggestion de Pseudocode, il te suggère de stockr sur disque ton arbere dans un ordre bien particulier : le premir élément est la racine de l'arbre. les deux éléments suivants sont les deux filles de la racine, etc.
Quand tu vas lancer la recherche avec l'algo approprié, tu vas d'abord lire sur le disque l'émément 1 mais, sans te le dire, ton ordi va charger en mémoire tout le bloc contigu au cas ou tu en aurais besoin, ce qui est justement le cas. Ce n'est que quand tu atteindra les étages les plus profonds que chaque requête au disque donner lieu à une lecture effective du disque, et non pas de son cache.

---

Pour qu'un mécanisme de cache soit efficace, il faut que les accès aient une localité spatiale et temporelle.

La question de initiale pourrait être reformulée ainsi "quelle serait la meilleure représentation d'un arbre binaire pour mieux profiter des différents mécanismes de cache matériel (cache CPU, disque,...)?"

La représentation d'un arbre binaire sous la forme d'un tableau permet de contrôler quelque peu la localité spatiale - voir la description dans http://en.wikipedia.org/wiki/Binary_tree, Methods for storing binary trees.

Pour ce qui est des gains de performances, ils sont sans doute évident côté accès disques mais pour ce qui est des caches CPU combien, comment n'est pas immédiat - je ne dis pas qu'il n'y en a pas, seulement que ce n'est pas simple à "voir" -.

Par contre, Pseudocode parle plutôt d'arbres dit "B+ trees" qui dispose d'une représentation qui a déjà une bonne localité "spatiale".
- W

Si je reprends les hypothèses que j'avais fixé au départ, il s'agissait "d'optimizer" la recherche binaire d'un tableau en mémoire via un regroupement des éléments les plus fréquemment atteints. Le but était d'espérer que ce regroupement (localité spatial) soit "vu" par le processeur. Cependant, il est plus complexe de maitriser la notion de "fréquence" pour la faire comprendre au processeur (localité temporelle. Wiztricks, merci pour ces termes très pédagogiques).

Contrairement au stockage sur disque, où l'on peut spécifier explicitement que les éléments les plus fréquemment atteints restent en mémoire (la racine d'un B tree par exemple), on ne peut en faire autant avec le stockage en mémoire en imposant au processeur de conserver en permanence certaines données dans son cache. Il pourrait plutôt en résulter un ralentissement global de l'ordinateur si les autres processus du système (sans doute nombreux) ne peuvent bénéficier de ce cache s'il est ainsi monopolisé. La localité temporelle n'est donc pas du tout garantie.
Cette réflexion, qui fait suite à vos interventions, me fait finalement douter d'un gain éventuel de performance.

Je me suis cependant lancé dans le codage pour vérifier (en C++).
La classe "vectorblock" permet d'encapsuler un petit tableau qui sera la "racine" d'un tableau quelconque en mémoire. Ce petit tableau contiendra les éléments fréquemment accédés via la recherche binaire. La taille en octets de ce tableau est fixée à 4096 octets (voir MakeHead()). Si le type "T" est "unsigned", ce tableau contiendra 511 éléments. Le tableau principal est ainsi segmenté en 512 sous tableaux.
Pour vérifier le gain éventuel par rapport à la recherche binaire il suffit de comparer les performances de
std::vector<T>::iterator vectorblock::lower_bound(const T & t)
avec
_FI std::lower_bound(_FI _F, _FI _L, const _Ty& _V) (dans <algorithm>)

Code:

---

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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

template<class T> struct T_offset { T s_t; int s_offset; T_offset():s_t(),s_offset(0) {} T_offset(const T_offset & s):s_t(s.s_t),s_offset(s.s_offset) {} T_offset & operator=(const T_offset & s) {s_t=s.s_t;s_offset=s.s_offset;return *this;} T_offset(const T & t,int offset):s_t(t),s_offset(offset) {} friend bool operator<(const T_offset & rl,const T_offset & rr) { return rl.s_t<rr.s_t; } };   template<class T> class vectorblock { void MiddleRange(std::vector<T>::iterator begin,std::vector<T>::iterator end) { if (s_depth==0) return; int n=(end-begin); if (n>2) { --s_depth; std::vector<T>::iterator middle=begin+n/2; MiddleRange(begin,middle); s_heads.push_back(T_offset<T>(*middle,middle-s_vector.begin())); MiddleRange(middle+1,end); ++s_depth; } else if (n>0) { s_heads.push_back(T_offset<T>(*begin,begin-s_vector.begin())); if (n==2) s_heads.push_back(T_offset<T>(*(begin+1),(begin+1)-s_vector.begin())); } }   std::vector< T_offset<T> > s_heads; std::vector<T> & s_vector; unsigned s_depth; public:   vectorblock(std::vector<T> & vector):s_vector(vector),s_depth(0) {}   unsigned HeadSize() { return s_heads.size(); }   void MakeHead() { unsigned depth=0,limit=4096/sizeof(T_offset<T>); while ((limit>>=1)>0) ++depth; s_depth=depth; MiddleRange(s_vector.begin(),s_vector.end()); }   std::vector<T>::iterator lower_bound(const T & t) { T_offset<T> t_o(t,0); std::vector< T_offset<T> >::iterator found=std::lower_bound(s_heads.begin(),s_heads.end(),t_o); std::vector<T>::iterator first=s_vector.begin(),last; if (found!=s_heads.begin()) first+=(found-1)->s_offset+1; if (found!=s_heads.end()) last=s_vector.begin()+found->s_offset+1; else last=s_vector.end(); return std::lower_bound(first,last,t); } };

---

Dans les meilleurs des cas, j'obtiens un gain de performance de 1 à 2%. Si je diminue la taille du bloc de 4096 octets, les gains sont négligeables. Par contre si je l'augmente, les performances se dégradent; l'optimization n'en est plus une.
En pratique, si les performances ne se dégradaient jamais, se serait toujours bon à prendre. Mais ce n'est malheureusement pas le cas (pourquoi ?). Autant ne pas prendre de risque.

Voilà, merci de votre attention :D
Le débat fut intéressant ;)
Et il fut amusant de constater que, oui, il pouvait y avoir un gain de performance :yaisse2:

Citation:

---

Dans les meilleurs des cas, j'obtiens un gain de performance de 1 à 2%. Si je diminue la taille du bloc de 4096 octets, les gains sont négligeables. Par contre si je l'augmente, les performances se dégradent; l'optimization n'en est plus une.

---

Il y a longtemps que je n'ai pas regardé l'implémentation d'un cache CPU mais en général, ils sont associatifs. Comme 4096 correspond à peut près à la taille d'une page, les dégradations sont peut être induites par des collisions.

Note: En principe, il doit exister des outils de monitoring du comportement du CPU qui devrait permettre de mettre en évidence ce type de collisions.

Mais il est clair que lorsqu'on en est rendu à ce genre d'optimisation, c'est loin d'être trivial et cela peut être frustrant parce que les gains ne sont pas toujours au rendez vous.

- W