Tableau déchiqueté & performances

Version imprimable

13/05/2013, 11h43
oodini

Tableau déchiqueté & performances

Hello,

Pour l'implémentation d'un tableau déchiqueté, l'utilisation de vecteurs de vecteurs, plutôt qu'une tambouille à base de tableaux de pointeurs, représente--t-elle une baisse significative de performances ?

Seules les performances en lecture m'intéressent. Le remplissage est déterministe, et n'induira pas de problème de réallocation.
13/05/2013, 12h36
Neckara

Bonjour,

Je pense que la meilleure solution reste encore de tester ;)

Après, "baisse significative de performances" dépend surtout de ce que ton programme fera et du nombre de données qu'il manipulera.

Si tu t'amuses à lire des fichiers tout en ayant une interface graphique 3D et que tu ne manipules que 4 valeurs, prendre un tableau de pointeurs ou un vecteur de vecteur ne fera pas grande différence.

Par contre si ton programme ne fait que lire les données de ton vecteur de vecteur ou de ton tableau de pointeur et que tu as un nombre important de valeurs à traiter alors oui, peut-être que cela pourra jouer.
13/05/2013, 16h18
oodini

Pour l'instant, il y a un tableau de pointeurs qui m'emmènent quelque part sur un même tableau d'octets. L'élément pointé me donne le nombre d'éléments auquel je dois m'attendre, puis j'itère sur les octets suivants (modulo une taille de classe : c'est de la désérialisation) avec un passage par un reinterpret_cast().

J'ai plutôt envie, à la lecture, de transformer tout ça en un vecteur de vecteurs.
13/05/2013, 17h37
Joel F

un vecteur de vecteur n'est pas contigu et va pourrir ton cache
13/05/2013, 17h50
Neckara

Sinon, c'est un peu tiré par les cheveux, mais ne pourrait-on pas stocker toutes les données dans un seul vecteur "data" comme tu le fait avec ta méthode de tableau de pointeur puis créer un vector de Ligne contenant des Lignes.

Une Ligne hériterait alors de vector et redéfinierait les méthodes de sorte qu'il aille rechercher les données dans le vecteur "data" à chaque demandes (DP Proxy je ne m'abuse).

Ainsi tu ne devrais pas trop perdre en performances et tu aura un conteneur "STL".
13/05/2013, 18h05
Iradrille

Citation:

Envoyé par Neckara

Une Ligne hériterait alors de vector et redéfinierait les méthodes de sorte qu'il aille rechercher les données dans le vecteur "data" à chaque demandes (DP Proxy je ne m'abuse).

L'héritage et les conteneurs STL, ça va très mal ensemble, les destructeurs ne sont pas virtuels.
13/05/2013, 18h08
backlash

Un seul vecteur résout complètement le problème sans perte de performance!
13/05/2013, 18h49
Neckara

Citation:

Envoyé par Iradrille

L'héritage et les conteneurs STL, ça va très mal ensemble, les destructeurs ne sont pas virtuels.

J'avais oublié :aie:

Il n'y a peut être pas besoin d'héritage alors, je sais que les itérateurs doivent hériter de pas mal de choses ( mais il suffit d'utiliser ceux du vecteur "data"), mais pour les conteneurs je ne suis pas sûr que ce soit le cas.

Citation:

Envoyé par Iradrille

L'héritage et les conteneurs STL, ça va très mal ensemble, les destructeurs ne sont pas virtuels.

... ce qui n'empêche pas d'utiliser l'héritage privé, de rendre publiques les méthodes de std::vector que l'on souhaite exposer, et d'implémenter sois-même celles qui ont un comportement différent de la base :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 template<typename T> class Ligne : private std::vector<T> { using base = std::vector<T>; public : using base::iterator; using base::const_iterator; using base::reverse_iterator; using base::const_reverse_iterator; using base::begin; using base::end; using base::rbegin; using base::rend; // ... T& operator [] (std::size_t i) { ... } const T& operator [] (std::size_t i) const { ... } }

13/05/2013, 21h44
Iradrille

Citation:

Envoyé par Kalith

... ce qui n'empêche pas d'utiliser l'héritage privé

ok, je connaissais pas ça, ça peut être utile dans pas mal de cas, merci =)
14/05/2013, 00h27
Bousk

Citation:

Envoyé par Iradrille

L'héritage et les conteneurs STL, ça va très mal ensemble, les destructeurs ne sont pas virtuels.

Ce qui ne dérange que si tu comptes utiliser ton container avec du polymorphisme
Ecrire class MyVector : public std::vector ne gène en rien tant que tu ne manipules par MyVector comme étant un std::vector, mais uniquement des MyVector
Ca revient plus ou moins à se limiter à l'héritage private dans son utilisation, moyennant un minimum d'attention du programmeur.
C'est pas forcément du plus propre, mais quel gain de temps on peut gagner
14/05/2013, 10h04
oodini

Bonjour,

Ce que vous proposez est intéressant, mais je n'ai malheureusement pas le temps pour l'implémenter. :(

Je vais donc en rester à l'existant pour éviter les problèmes de manque de localité des données.
14/05/2013, 10h54
oodini

En fait, comme je compte mettre mes vecteurs en mémoire partagée, où la mémoire allouable est contrainte dans un espace réduit, je ne devrais finalement pas être confronté au problème de la localité des données.
14/05/2013, 11h18
ternel

Attention, pas de pointeurs dans la mémoire partagée.
(des pointeurs vers elle, ok, mais pas dedans)
14/05/2013, 11h23
oodini

Boost.Interprocess offre un pointeur intelligent basé sur un offset pour gérer l'utilisation des pointeurs.
14/05/2013, 11h25
Neckara

Citation:

Envoyé par leternel

Attention, pas de pointeurs dans la mémoire partagée.
(des pointeurs vers elle, ok, mais pas dedans)

Si des pointeurs dans la mémoire partagée pointent vers une zone de cette même mémoire partagée est-ce qu'il y a vraiment un problème ?
Je pense que non mais je commence à avoir un doute :aie:
14/05/2013, 11h30
oodini

Je débute dans le domaine, mais d'après ce que j'ai cru comprendre, il n'y a pas moyen de travailler avec des pointeurs, quelle que soit leur forme, entre deux zones mémoire.

Si c'est au sein de la même zone mémoire, il faut utiliser un pointeur spécial, sauf si c'est un seul et unique processus qui travaille avec ces pointeurs.
14/05/2013, 12h07
ternel

les mémoires partagées sont "mappés" vers des blocs de mémoires internes à chaque processus.
ainsi, la "shared adress 17" peut être à l'adresse 134 pour process1 et 812 pour process2;

&"shared adress 17" = 134 dans process1 et &"shared adress 17" = 812 dans process2

dans process1, stoquer l'adresse 134 dans un pointeur partagé ne le traduit pas pour process2.
15/05/2013, 15h17
Emmanuel Deloget

Citation:

Envoyé par Neckara

Si des pointeurs dans la mémoire partagée pointent vers une zone de cette même mémoire partagée est-ce qu'il y a vraiment un problème ?
Je pense que non mais je commence à avoir un doute :aie:

Pas possible. La zone mémoire peut être mappée à deux adresses différentes (0x7000a000 et 0x7000b000 par exemple) dans deux process différents. Du coup, un pointeur 0x7000a110 dans la zone de mémoire partagée ne pourra pas être utilisée dans la seconde.

offset_ptr<> dans boost.interprocess stocke l'offset entre l'objet offset_ptr<> et la cible - donc, dans le cas des deux exemple, si (p = this = 0x700a100 = 0x10), offset. Le déréférencement de offset_ptr<> effectue l'opération inverse. Sur la seconde zone, (p = this = 0x7000b100, donc *p = (0x7000b100+offset) = 0x7000b110.

Il y a des petites astuces sur la copie, le move... pour que l'offset reste toujours valide quelque soit l'instance de offset_ptr<> considérée.

C'est la seule manière de procéder (manière à laquelle je n'avais pas pensé, d'ailleurs).