Creer un buffer trié

Version imprimable

14/07/2007, 13h49
buzzkaido

Creer un buffer trié

Bonjour,

J'ai créé un plugin pour un logiciel, et dans mon code, j'utilise un buffer d'objets.

Je suis obligé d'utiliser un buffer car il doit être envoyé sous cette forme au logiciel hôte.

Chacun des objets de ce buffer a une taille de 32 octets et le buffer est de l'ordre de 10.000 objets.

Actuellement, j'utilise donc un vecteur d'objets.

Ce buffer doit etre envoyé trié au logiciel hôte, actuellement, j'insere donc à la bonne position les objets au fur et à mesure de leur création.

Ja précise que le nombre d'insertion dans le buffer est tres petit devant le nombre d'envoit de ce buffer à l'hôte.

Etant donné que toutes les performances de mon code reposent sur ce buffer (il est lu pratiquement en permanence) je souhaite optimiser l'insertion des objets.

Comment procéder ?

Je pensais à allouer deux buffer, et lors de l'insertion :
1/ copier ce qui est avant l'objet à inserer d'un buffer vers l'autre
2/ inserer l'objet dans le nouveau buffer (à la fin donc)
3/ copier ce qui est après l'objet à inserer d'un buffer vers l'autre
4/ utiliser le nouveau buffer

ou alors :

1/ decaler de 32 octets toute le mémoire du buffer qui est après la position d'insertion
2/ inserer les données à la position nouvellement libérée

Qu'en pensez-vous ?
D'autres idées ?
Y-a-t-il moyen de tirer parti du fait que les objets fonts exactement 32 octets ?

Merci !
14/07/2007, 14h48
Mat007

Salut,

Citation:

Envoyé par buzzkaido

Etant donné que toutes les performances de mon code reposent sur ce buffer (il est lu pratiquement en permanence) je souhaite optimiser l'insertion des objets.

Tu as des performances non acceptables et tu as utilisé un 'profiler' pour arriver à la conclusion que le plus rentable à optimiser étaient ces insertions ?

Par buffer tu entends un tableau alloué à la main, c'est ça ?
Y'a une raison particulière pour ne pas utiliser de std::vector (qui implémente déjà les algorithmes que tu décris et vraisemblablement de manière plus performante que ce à quoi tu parviendrais toi-même à la main) ?

MAT.
14/07/2007, 15h41
buzzkaido

Citation:

Tu as des performances non acceptables et tu as utilisé un 'profiler' pour arriver à la conclusion que le plus rentable à optimiser étaient ces insertions ?

Etant donné que la lecture du buffer consiste à le parcourir du debut à la fin et que ce buffer est aligné en mémoire, je ne vois pas trop comment optimiser la lecture.

J'ai mesuré les temps d'executions, en lecture les performances sont tout à fait acceptables, par contre en ecriture je trouve ça très long.

Citation:

Par buffer tu entends un tableau alloué à la main, c'est ça ?

Ben... un buffer quoi ! Une zone mémoire contigüe, si tu preferes, soit l'equivalent d'un tableau.

Citation:

Y'a une raison particulière pour ne pas utiliser de std::vector

Comme dit dans mon premier post, c'est mon implementation actuelle.

Citation:

qui implémente déjà les algorithmes que tu décris et vraisemblablement de manière plus performante que ce à quoi tu parviendrais toi-même à la main

Les classes de la STL sont faites pour fonctionner dans n'importe qu'elle condition. Leur enorme avantage est la robustesse du code.

Mais dans les cas particulier, on peut faire mieux. Dans mon code, j'utilise aussi une liste chainée (pour une autre partie du code).
La liste chainée que j'ai implementée à la main (sans itérateur, sans controle de cohérence, sans template... c'est un cas particulier) est plus rapide que std::list.

Pour mon buffer, vu que c'est aussi particulier et que mes objets font 32 octets, je cherche à mettre en place une implémentation particulière qui tire profit de ... ces particularités.

Citation:

1/ decaler de 32 octets toute le mémoire du buffer qui est après la position d'insertion

A mon avis, c'est ce qui me permettrait de gagner vraiment en performances. Mais je ne sais pas trop si c'est possible.

Quand je faisait des prog en assembleur sous MS-DOS (ça nous rajeunit pas !) je me rappelle que j'avait mis en place des systèmes de ce genre pour gerer le "scrolling" d'images (par exemple).

L'idéal serait de pouvoir décaler toute une zone mémoire de 32 octets (soit 8 registres 32 bits ou 4 registres 64 bits) sans avoir à en faire une copie.

Citation:

Envoyé par Mat007

Y'a une raison particulière pour ne pas utiliser de std::vector (qui implémente déjà les algorithmes que tu décris et vraisemblablement de manière plus performante que ce à quoi tu parviendrais toi-même à la main) ?
MAT.

tu veut parler de std::sort ?

sinon, décaler une zone memoire, revient'il pas a faire une copie?

Si tu connait a l'avance apeuprés la taille de ton buffer, tu devrait pourvoir allouer un grand buffer des le debut, et le remplire.
exemple(pseudo code)
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 int* buffer = new int[11000]; int nbElem =0; for(;nbElem <11000;) { int toto = rand(); if (nbElem =0) { buffer [0] = toto; nbElem ++; continue; } else if (buffer [nbElem -1]<toto) { buffer [nbElem ] = toto; nbElem ++; continue; } int id; nbElem++ for (id=0;id<nbElem && buffer [id]>=toto;id++); //decalage de la memoire for (int j = nbElem -1;j>id;j--) buffer [j] = buffer [j-1] buffer [id] =toto; }
et si nbElem arrive au maximum, creer un nouveau buffer plus grand, et recopier l'ancien dans le nouveau.