Problème avec les allocateurs

Version imprimable

07/10/2015, 21h01
bountykiler

Problème avec les allocateurs

Bonjour à tous,

j'essaie actuellement d'implémenter une classe shared_vector, qui serait un mix entre un std::vector et un std::shared_ptr, l'idée étant que que lorsque je fais une copie de mon vector je ne fais qu'incrémenter un compteur de référence, et lorsque mon vector est détruit je décrémente ce compteur. Une fois que celui-ci atteint 0, les elements de mon vector sont alors détruit. (Rien de méchant jusqu'ici).
J'aimerai pouvoir passer en paramètre template un type d'allocateur à utiliser pour effectuer les allocations de mémoire. Le hic, c'est que quand j'alloue de la mémoire, je dois pouvoir réserver de la mémoire pour stocker les éléments dans mon tableau + mon compteur de références. Or, l'interface des allocateurs ne permet que de reserver de la mémoire pour X éléments d'un type donné, mais ne permet pas de spécifier une quantité précise de mémoire à allouer.:?

Qqun a une idée de comment je peux faire?
08/10/2015, 08h56
ternel

tu ne peux pas juste faire un vector de shared_ptr?
08/10/2015, 10h50
Astraya
Citation:

tu ne peux pas juste faire un vector de shared_ptr?

ou plutôt un shared_ptr<std::vector<Element>> :)

Citation:

Or, l'interface des allocateurs ne permet que de reserver de la mémoire pour X éléments d'un type donné, mais ne permet pas de spécifier une quantité précise de mémoire à allouer.

Il est facile de passer de l'un à l'autre:
X*Element => X*sizeof(Element)
Si tu veux que ton allocateur alloue de la mémoire disons 10octets... C'est simple
Code:

1 2 3 4 struct Memory { unsigned char [10]; };
Tu passe ça en élément dans ton vector. Puis quand tu veux l'utiliser comme un autre élément tu le cast (Element*)MemoryPtr;Si tu veux que tes 10 octets soit aligné selon Element alors tu passes alignement en alignof(Element) et élément a alloué Memory
Tu pourrais même : shared_ptr<std::vector<shared_ptr<Element>>>
08/10/2015, 20h43
bountykiler

Citation:

Envoyé par Astraya

ou plutôt un shared_ptr<std::vector<Element>> :)

Je pourrai, mais avoir un shared_vector est plus simple à l'utilisation. (En plus c'est potentiellement + performant)

Citation:

Il est facile de passer de l'un à l'autre:
X*Element => X*sizeof(Element)

Sauf qu'a ces X*sizeof(Element), je dois ajouter sizeof(ref_counter), et c'est bien là le problème.
08/10/2015, 22h12
Astraya

Code:

Je pourrai, mais avoir un shared_vector est plus simple à l'utilisation. (En plus c'est potentiellement + performant)

Laisse moi douter du fait que tu puisses faire plus performant sans y passé des mois ;)

Code:

Sauf qu'a ces X*sizeof(Element), je dois ajouter sizeof(ref_counter), et c'est bien là le problème.

Donc shared_ptr<std::vector<Element>>
09/10/2015, 20h36
bountykiler

Citation:

Envoyé par Astraya

Code:

Je pourrai, mais avoir un shared_vector est plus simple à l'utilisation. (En plus c'est potentiellement + performant)

Laisse moi douter du fait que tu puisses faire plus performant sans y passé des mois ;)

Fais gaffe, je serai capable d'en faire le pari :mouarf:

Citation:

Code:

Sauf qu'a ces X*sizeof(Element), je dois ajouter sizeof(ref_counter), et c'est bien là le problème.

Donc shared_ptr<std::vector<Element>>

Précisemment ce que je veux éviter.

Petite remarque au passage:
J'ai besoin de cela pour un projet perso, donc je ne cherche pas une solution rapide.
Et si je pose la question, c'est aussi parce que je la trouve intéressante car elle mets en évidence une limitation des allocateurs actuels.

Deuxième remarque:
Hier je suis tombé là-dessus:
http://en.cppreference.com/w/cpp/exp...emory_resource
A priori c'est quelque chose de prévu pour C++17, aussi je me demande si ce n'est finalement pas là la solution à mon problème.
12/10/2015, 11h31
Astraya

Tu n'as pas l'air de te rendre compte de la complexité d'un simple sharde_ptr et d'un vector... Les dépendences cycliques, la gestion mémoire, la copie/move des éléments d'un vector ( car il faut considérer le meilleur car pour tout 'T'), l'alignement mémoire...
Bref, shared_ptr<std::vector<Element>> ou fait le toi même mais t'étonne pas d'y être encore fin 2016. Sauf si tu te base sur du code opensource comme Boost ou autre..

Citation:

Envoyé par Astraya

Tu n'as pas l'air de te rendre compte de la complexité d'un simple sharde_ptr et d'un vector... Les dépendences cycliques, la gestion mémoire, la copie/move des éléments d'un vector ( car il faut considérer le meilleur car pour tout 'T'), l'alignement mémoire...
Bref, shared_ptr<std::vector<Element>> ou fait le toi même mais t'étonne pas d'y être encore fin 2016. Sauf si tu te base sur du code opensource comme Boost ou autre..

:plusser: et je ne vois pas ce qu'une classe maison peut apporter de plus ... si ce n'est qu'un sucre syntaxique.
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 template<class Element> class shared_vector { std::shared_ptr<std::vector<Element> > _data; public: shared_vector() : _data(std::make_shared<std::vector<Element> >()) {} shared_vector(const shared_vector<Element>& other) : _data(other._data) {} shared_vector(shared_vector<Element>&& other) : _data(other._data) { other.reset(nullptr); } virtual ~shared_vector() {} shared_vector<Element> operator=(const shared_vector<Element>& other) { _data.reset(other._data); } shared_vector<Element> operator=(shared_vector<Element>&& other) { _data.reset(other._data); other.reset(nullptr); } const Element& operator[](std::size_t n) { return (*_data)[n]; } Element& operator[](std::size_t n) { return (*_data)[n]; } // autres méthodes de std::vector que l'on veut exposer... };
Sous réserve de compilation.

17/10/2015, 20h25
bountykiler

Citation:

Envoyé par Astraya

Tu n'as pas l'air de te rendre compte de la complexité d'un simple sharde_ptr et d'un vector... Les dépendences cycliques, la gestion mémoire, la copie/move des éléments d'un vector ( car il faut considérer le meilleur car pour tout 'T'), l'alignement mémoire...
Bref, shared_ptr<std::vector<Element>> ou fait le toi même mais t'étonne pas d'y être encore fin 2016. Sauf si tu te base sur du code opensource comme Boost ou autre..

Ben si, je comprends bien toutes ces problématiques...:weird:
Et puis si je dois bosser là-dessus jusque fin 2016 (mais j'en doute), pq pas? Après tout comme dit plus haut c'est pour un projet perso sans réel but et au final tout ce que je risque c'est d'apprendre des choses, donc je vois pas ou est le problème.
Après, la raison pour laquelle le fait d'avoir un shared_vector<T> doit permettre d'aller plus vite est que cela permet d'accéder aux éléments en ne déréférençant qu'un seul pointeur, là ou un shared_ptr<vector<T>> va nécessiter d'en déréférencer 2.

Citation:

Envoyé par prgasp77

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
template<class Element>
class shared_vector
{
    std::shared_ptr<std::vector<Element> > _data;
public:
    shared_vector() : _data(std::make_shared<std::vector<Element> >()) {}
    shared_vector(const shared_vector<Element>& other) : _data(other._data) {}
    shared_vector(shared_vector<Element>&& other) : _data(other._data)
    {
        other.reset(nullptr);
    }
    virtual ~shared_vector() {}
    shared_vector<Element> operator=(const shared_vector<Element>& other)
    {
        _data.reset(other._data);
    }
    shared_vector<Element> operator=(shared_vector<Element>&& other)
    {
        _data.reset(other._data);
        other.reset(nullptr);
    }
    const Element& operator[](std::size_t n) { return (*_data)[n]; }
    Element& operator[](std::size_t n) { return (*_data)[n]; }
    // autres méthodes de std::vector que l'on veut exposer...
};

Sous réserve de compilation.

Bon allez, un p'tit correctif pour la route:

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
 
template<class Element>
class shared_vector final
{
    std::shared_ptr<std::vector<Element> > _data;
public:
    //Ici, le ctor par défaut devrait suffire.
    shared_vector() : _data() {}
    shared_vector(const shared_vector<Element>& other) : _data(other._data) {}
    //Tant qu'à faire, autant utiliser le ctor de déplacement de shared_ptr. 
    shared_vector(shared_vector<Element>&& other) : _data(std::move(other._data))
    {
    }
    // pas la peine de mettre un dtor virtuel, vu que cette classe n'est pas censé etre héritée (j'ai d'ailleurs ajouté un "final" à cet effet)
    ~shared_vector() {}
    //Autant utiliser l'opérateur directement. Et au passage, renvoyer une ref plutot qu'une copie ;)
    shared_vector<Element>& operator=(const shared_vector<Element>& other)
    {
        _data = other._data;
        return *this;
    }
    // pareil.
    shared_vector<Element>& operator=(shared_vector<Element>&& other)
    {
        _data = std::move(other._data);
        return *this.
    }
    const Element& operator[](std::size_t n) { return (*_data)[n]; }
    Element& operator[](std::size_t n) { return (*_data)[n]; }
    // autres méthodes de std::vector que l'on veut exposer...
};

sous réserve de compilation, j' avoue ne pas avoir testé.
;)

17/10/2015, 20h53
Iradrille

Citation:

Envoyé par bountykiler

Ben si, je comprends bien toutes ces problématiques...:weird:
Et puis si je dois bosser là-dessus jusque fin 2016 (mais j'en doute), pq pas? Après tout comme dit plus haut c'est pour un projet perso sans réel but et au final tout ce que je risque c'est d'apprendre des choses, donc je vois pas ou est le problème.

Rien, ni personne ne t'en empêche, mais tu risques de te confronter à des difficultés auxquelles tu ne penses pas encore. Tu maitriseras le fonctionnement de std::vector et std::shared_ptr (si fait correctement :aie:) mais ça va te prendre du temps.

Citation:

Envoyé par bountykiler

Après, la raison pour laquelle le fait d'avoir un shared_vector<T> doit permettre d'aller plus vite est que cela permet d'accéder aux éléments en ne déréférençant qu'un seul pointeur, là ou un shared_ptr<vector<T>> va nécessiter d'en déréférencer 2.

Si les accès sont séquentiels, un déréférencement de pointeur ça à un coût très faible. Ce qui coûte cher, c'est les caches misses.

J'ai pas les nombres exacts, mais je suis prêt à parier que déréférencer un std::shared_ptr à un cout au moins 10 fois supérieur au déréférencement d'un pointeur nu, tout comme déréférencer un pointeur nu lors d'accès séquentiels doit être 50 à 100 fois plus rapide que lors d'accès aléatoires.

Tant que tu n'as pas profilé ton code, l'optimisation à l'aveugle est inutile. ;)