Pourquoi vector fait-il appel au constructeur de copie lors d'un 'realloc' ?

Marc Boyer wrote:

suite au post de JM, je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.

Il doit le faire chaque fois qu'il a besoin d'agrandir la
capacité. Ce qui ne peut pas être à chaque push_back ; la norme
dit que push_back a une complexité amortie constante, ce qui
impose un algorithme exponentiel de croissance. (Selon
l'implémentation, typiquement, chaque fois que la capacité ne
suffit pas, il va la multiplier par 1,5 ou par 2 -- si je ne me
trompe pas, Stepanov utilisait 2, mais Andy Koenig a démontré
qu'avec un multiplicateur supérieur à sqrt(2), on ne pouvvait
jamais réutiliser la mémoire libérée.)

Si on connaît la taille finale, évidemment, rien n'empèche de
fair un coup de reserve au préalable, pour être sûr qu'il n'y a
pas de réallocation (avec les copies supplémentaires que cela
implique). Ça a aussi l'avantage que les insertions n'invalident
pas des itérateurs.

D'après le code expérimenté par JM, c'est le cas. Mais je
voudrais savoir si (et pourquoi) le vector ne peut pas
simplement faire un (pseudo) realloc, ie demander
de la mémoire brute, plus grande, et faire une copie
bit à bit des objets dejà stockés ?

D'abord, c'est intérdit avec l'allocator standard ; la norme
dit que cet allocator utilise la fonction ::operator new pour
obtenir de la mémoire (et si je remplace cette fonction, c'est
bien visible s'il le fait ou non).

Mais plus fondamentalement, le problème, c'est comment ? Il ne
peut pas faire un realloc tout court, parce que si realloc
déplace le bloc (chose qu'il fait souvent), on se retrouve
éventuellement avec des objets invalids. Et je ne connais pas de
fonction qui essaiera d'agrandir sur place, et si ce n'est pas
possible, renverra un code d'échec sans toucher à la mémoire
qu'on lui aurait passée.

La solution adoptée par la STL, alors, a été de limiter le
nombre de réallocations, en imposant un algorithme de croissance
exponentiel. Avec une fonction de reserve, qui te permet de
l'optimiser encore plus le cas échéant.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Marc Boyer <Marc.Boyer@enseeiht.yahoo.fr.invalid> writes:

suite au post de JM, je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.

Oui. J'ai pas le temps de chercher une référence, mais ne pas le faire
poserait un sérieux problème.

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

On Wed, 20 Sep 2006 08:01:59 +0000 (UTC), Marc Boyer :

je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.

Ben oui, faut bien, car vector<> ne connaît pas le contenu de la
classe.

struct C
{
int x;
int *ptr;
C() : ptr (&x) {}
};

Le 20-09-2006, kanze <kanze@gabi-soft.fr> a écrit :

suite au post de JM, je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.

Il doit le faire chaque fois qu'il a besoin d'agrandir la
capacité. Ce qui ne peut pas être à chaque push_back ; la norme
dit que push_back a une complexité amortie constante, ce qui
impose un algorithme exponentiel de croissance. (Selon
l'implémentation, typiquement, chaque fois que la capacité ne
suffit pas, il va la multiplier par 1,5 ou par 2 -- si je ne me
trompe pas, Stepanov utilisait 2, mais Andy Koenig a démontré
qu'avec un multiplicateur supérieur à sqrt(2), on ne pouvvait
jamais réutiliser la mémoire libérée.)

Tu as une ref sous la main pour le coup du coef supérieur
à sqrt(2) ? (sinon, je vais chercher tout seul).

Si on connaît la taille finale, évidemment, rien n'empèche de
fair un coup de reserve au préalable, pour être sûr qu'il n'y a
pas de réallocation (avec les copies supplémentaires que cela
implique). Ça a aussi l'avantage que les insertions n'invalident
pas des itérateurs.

oui

D'après le code expérimenté par JM, c'est le cas. Mais je
voudrais savoir si (et pourquoi) le vector ne peut pas
simplement faire un (pseudo) realloc, ie demander
de la mémoire brute, plus grande, et faire une copie
bit à bit des objets dejà stockés ?

D'abord, c'est intérdit avec l'allocator standard ; la norme
dit que cet allocator utilise la fonction ::operator new pour
obtenir de la mémoire (et si je remplace cette fonction, c'est
bien visible s'il le fait ou non).

Mais plus fondamentalement, le problème, c'est comment ? Il ne
peut pas faire un realloc tout court, parce que si realloc
déplace le bloc (chose qu'il fait souvent), on se retrouve
éventuellement avec des objets invalids.

Mais pourquoi un objet peut-il devenir invalide en
étant déplacé ? S'il possède des pointeurs sur lui même ?

Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. Paul Éluard)

Le 20-09-2006, Fabien LE LEZ <gramster@gramster.com> a écrit :

On Wed, 20 Sep 2006 08:01:59 +0000 (UTC), Marc Boyer :

je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.

Ben oui, faut bien, car vector<> ne connaît pas le contenu de la
classe.

struct C
{
int x;
int *ptr;
C() : ptr (&x) {}
};

Oui, une classe qui pointe sur/dans elle même.
Je ne vois pas trop l'intérêt, mais il faut le
permettre.

Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. Paul Éluard)

Marc Boyer <Marc.Boyer@enseeiht.yahoo.fr.invalid> writes:

Tu as une ref sous la main pour le coup du coef supérieur
à sqrt(2) ? (sinon, je vais chercher tout seul).

J'avais en mémoire le nombre d'or. Il faut que ce qui a été libéré est
supérieur en taille à ce qu'il faut allouer. Donc

sum_{i=0}^{N} x^i > x^{N+2}
over{x^{N+1}-1}{x-1} > x^{N+2}
x^{N+1}-1 > x^{N+3} - x^{N+2}
x^{N+2}+x^{N+1} > x^{N+3}-1

Vu la forme (ça fait penser à la suite de Fibonacci et la limite de 2
termes successifs de cette suite, c'est le nombre d'or), le nombre d'or me
semble un meilleur candidat que racine de 2, mais je ne vois plus comment
conclure formellement.

Mais pourquoi un objet peut-il devenir invalide en étant déplacé ?
S'il possède des pointeurs sur lui même ?

Par exemple, ou s'il est enregistré quelque part.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

On Wed, 20 Sep 2006 08:46:57 +0000 (UTC), Marc Boyer :

Oui, une classe qui pointe sur/dans elle même.
Je ne vois pas trop l'intérêt

J'ai fait récemment un truc dans ce goût-là :

class Machin;

class C
{
Machin* machin1;
Machin* machin2;
Machin* machin_en_cours;
};

avec "machin_en_cours" qui pointe vers machin1 ou machin2.
J'ai bien sûr simplifié le cas réel pour l'exemple.

Marc Boyer wrote:

suite au post de JM, je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.

Il doit le faire chaque fois qu'il a besoin d'agrandir la
capacité. Ce qui ne peut pas être à chaque push_back ; la norme
dit que push_back a une complexité amortie constante, ce qui
impose un algorithme exponentiel de croissance. (Selon
l'implémentation, typiquement, chaque fois que la capacité ne
suffit pas, il va la multiplier par 1,5 ou par 2 -- si je ne me
trompe pas, Stepanov utilisait 2, mais Andy Koenig a démontré
qu'avec un multiplicateur supérieur à sqrt(2), on ne pouvvait
jamais réutiliser la mémoire libérée.)

Tu as une ref sous la main pour le coup du coef supérieur
à sqrt(2) ? (sinon, je vais chercher tout seul).

Non. D'ailleurs, on me l'a raconté ; je n'ai pas vu la
référence moi-même. Mais la raisonement est simple : si tu vas
réutiliser la mémoire que tu as libérée, une condition
nécessaire, c'est que la taille totale libérée soit supérieur à
la taille que tu es en train de demander. C-à-d que si à la
n-ième demande, tu demandes x[n], il faut bien que
$Sigma_{i<n+1}x_i<=x_i$. Pour un algorithme exponentiel, où tu
as $x_i=kx_{i-1}$, je crois que la solution est bien sqrt(2).

Dans la pratique, évidemment, c'est un peu plus compliqué.
D'abord, parce que quand tu demandes n octets, il y aurait en
fait n+k d'allouer (ou plus -- certains algorithes de malloc
arrondient la demande à la puissance de 2 supérieur). Aussi,
même à 1,5, ce n'est pas dit que tu arrives à réutiliser ce que
tu as libéré très vite. Et puis, évidemment, il y a toujours le
clown qui vient allouer 8 octets chaque fois entre tes
libérations, et qui ne les libère jamais, de façon à ce que la
gestionnaire de la mémoire ne peut jamais coalise les blocs que
tu libères. Donc, sqrt(2) est une borne supérieur théorique, et
ne serait-ce qu'à cause du premier problème, il vaut mieux être
un peu plus petit. Comme, par exemple, 1,5, qui en plus se
laisse calculer de façon très simple avec l'arithmetique
entière.

Si on connaît la taille finale, évidemment, rien n'empèche de
fair un coup de reserve au préalable, pour être sûr qu'il n'y a
pas de réallocation (avec les copies supplémentaires que cela
implique). Ça a aussi l'avantage que les insertions n'invalident
pas des itérateurs.

oui

D'après le code expérimenté par JM, c'est le cas. Mais je
voudrais savoir si (et pourquoi) le vector ne peut pas
simplement faire un (pseudo) realloc, ie demander
de la mémoire brute, plus grande, et faire une copie
bit à bit des objets dejà stockés ?

D'abord, c'est intérdit avec l'allocator standard ; la norme
dit que cet allocator utilise la fonction ::operator new pour
obtenir de la mémoire (et si je remplace cette fonction, c'est
bien visible s'il le fait ou non).

Mais plus fondamentalement, le problème, c'est comment ? Il ne
peut pas faire un realloc tout court, parce que si realloc
déplace le bloc (chose qu'il fait souvent), on se retrouve
éventuellement avec des objets invalids.

Mais pourquoi un objet peut-il devenir invalide en
étant déplacé ? S'il possède des pointeurs sur lui même ?

Il peut. Dans la plupart des implémentations de l'héritage
virtuel, il l'aura, par exemple. Mais en général, la norme dit
que copier un object bit-à-bit a un comportement indéfini dans
le cas des types non POD. Que l'implémentation se sert de cette
possibilité ou non, tu ne le sais pas. (Note aussi que
l'implémentation la plus simple de la SSO pour basic_string
aurait aussi un pointeur sur lui-même dans le cas où
l'optimisation est effective, et que j'ai des classes à moi qui
en font pareil.)

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Jean-Marc Bourguet wrote:

Marc Boyer <Marc.Boyer@enseeiht.yahoo.fr.invalid> writes:

Tu as une ref sous la main pour le coup du coef supérieur
à sqrt(2) ? (sinon, je vais chercher tout seul).

J'avais en mémoire le nombre d'or. Il faut que ce qui a été
libéré est supérieur en taille à ce qu'il faut allouer. Donc

sum_{i=0}^{N} x^i > x^{N+2}
over{x^{N+1}-1}{x-1} > x^{N+2}
x^{N+1}-1 > x^{N+3} - x^{N+2}
x^{N+2}+x^{N+1} > x^{N+3}-1

Vu la forme (ça fait penser à la suite de Fibonacci et la
limite de 2 termes successifs de cette suite, c'est le nombre
d'or), le nombre d'or me semble un meilleur candidat que
racine de 2, mais je ne vois plus comment conclure
formellement.

En effet. En tout cas, c'était un nombre irrationnel un peu plus
grand que 1,5.

Mais pourquoi un objet peut-il devenir invalide en étant déplac é ?
S'il possède des pointeurs sur lui même ?

Par exemple, ou s'il est enregistré quelque part.

L'objet même rest valide. C'est le pointeur dans la registre qui
devient faux. Et ça peut être un problème même avec la copie
fait correctement ; typiquement (mais pas toujours), un objet
qui s'inscrit quelque part n'est pas copiable (et donc ne peut
pas se trouver dans une collection standard).

Évidemment, *si* l'objet supporte la copie, son constructeur
et son destructeur s'occuperont pour faire la nécessaire auprès
du registre. À condition qu'ils soient appelés ; c'est donc
effectivement le même problème que si l'objet se réfère à
lui-même.

Plus généralement : si j'ai fourni un constructeur de copie, je
l'ai bien fait pour une raison.

En fait, c'est un cas spécial, de déplacement, et il y en a des
classes qu'on peut déplacer plus efficacement qu'avec
copier/detruire, voire qu'on peut déplacer, mais pas copier.
Actuellement, le C++ ne prend pas ces possibilités en compte,
mais ça arrive. Et c'est probable que dans la prochaine version
de C++, tu aurais la possibilité de dire au compilateur que la
classe peut être déplacée, avec une sémantique autre que
copier/detruire.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Marc Boyer wrote:

On Wed, 20 Sep 2006 08:01:59 +0000 (UTC), Marc Boyer :

je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.

Ben oui, faut bien, car vector<> ne connaît pas le contenu de la
classe.

struct C
{
int x;
int *ptr;
C() : ptr (&x) {}
};

Oui, une classe qui pointe sur/dans elle même.
Je ne vois pas trop l'intérêt, mais il faut le
permettre.

template< typename charT, ... >
class basic_string
{
private:
size_type _M_capacity ;
size_type _M_size ;
charT* _M_buffer ;
charT _M_ssoBuf[ 8 ] ;

_M_insertData( charT const* source, size_type length )
{
if ( length <= 8 ) {
_M_capacity = 8 ;
_M_buffer = _M_ssoBuf ;
} else {
_M_capacity = length ;
_M_buffer = _M_allocate( length ) ;
}
// ...
}
} ;

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34