Une string très performante?

Pardon j'oubliais un détail important: je ne fais que insérer des
chaines de caractères au début (rarement) et à la fin (toujours). J'ai
aussi parfois besoin supprimer les n derniers caractères (ou de reculer
et de les overwriter ce qui revient au même).

Mel Higg wrote:

Bonjour à tous,

Jusqu'à présent, j'utilisais des c-string (un simple tableau de char)
plutot que des c++ string pour des raisons de performance (je n'ai que
récemment découvert les moultes réallocations(!!) des string c++).

Je trouve dommage d'avoir à préallouer à chaque fois ce tableau, car je
me retrouve à hardcoder ces valeurs et il est courant d'allouer bien
plus que nécessaire.

J'ai donc codé une solution intermédiaire à base de listes chaînées de
c-string, en ayant un proxy qui alloue de nouveaux blocks si nécessaire.
Le problème, c'est que je dois maintenir un contexte qui contient des
infos telles que la position du curseur courant du block courant,
l'adresse du block courant etc... Et ce maintient est couteux.

J'ai fait quelques recherches sur le WWW à la recherche de solutions
miracles, et j'ai peut etre trouvé mon bonheur dans les ropes
(http://www.sgi.com/tech/stl/Rope.html), dont l'implémentation GNU
semble être exactement reprise de SGI.

Déjà, pensez-vous que je suis sur une bonne piste?

Si oui, je me demande si je pourrai raisonnablement créer des iovecs à
partir des blocks internes des ropes pour éviter des copies inutiles..

Merci
Mel

On Sat, 03 Dec 2005 09:46:52 +0100, Mel Higg <mailf@free.fr>:

Jusqu'à présent, j'utilisais des c-string (un simple tableau de char)
plutot que des c++ string pour des raisons de performance (je n'ai que
récemment découvert les moultes réallocations(!!) des string c++).

Je ne suis pas sûr qu'il y ait une réelle différence dans les
performances, à cahier des charges égal.
Si tu connais à l'avance la taille de la chaîne (ou un majorant), un
std::string::reserve() évitera les réallocations.
Si tu ne connais pas la taille à l'avance, il y aura forcément des
réallocations.

ropes

C'est un concept assez différent de std::string (qui lui-même est
assez proche des C-string), avec des applications différentes. Si tu
as beaucoup d'insertions à faire, rope sera vraisemblablement
meilleur.
De toutes façons, pour connaître la méthode la plus rapide dans ton
contexte, la seule solution est de tester et chronométrer...

On Sat, 03 Dec 2005 09:52:04 +0100, Mel Higg <mailf@free.fr>:

Pardon j'oubliais un détail imp[...]au même).

Mel Higg wrote:

Bonjour à tous,

Oui mais non.
Est-ce que tu te rends compte de ce que tu viens de poster ?
Tu as écris une réponse (en fait, un complément à ton propre message),
_suivie_ de l'intégralité du message d'origine.

Ton message est non seulement inutilement long, ce qui résulte dans un
gaspillage de bande passante et de temps, mais en plus n'a aucune
structure logique, puisqu'il est écrit de bas en haut.

C'est exactement comme si tu écrivais :

int main()
{
n= i;
int n;
int i= 7;
}

Rappelle-toi qu'en français, on écrit de haut en bas (et donc une
réponse est toujours mise immédiatement en-dessous de la question).
Par voie de conséquence, aucune citation ne doit se trouver après le
point final de ton message.

Cf <http://www.giromini.org/usenet-fr/repondre.html> pour plus
d'infos.

Ton message est non seulement inutilement long, ce qui résulte dans un
gaspillage de bande passante et de temps, mais en plus n'a aucune
structure logique, puisqu'il est écrit de bas en haut.

Autant je suis d'accord avec la fin (bien que dans ce cas précis il s'agit selon
moi uniquement d'un article posté un peu trop vite) autant l'argument de la
bande passante date d'un autre âge : avec les débits actuels (même si tout le
monde n'a pas de l'ADSL2+), quelques dizaines de lignes ne vont pas faire
s'écrouler les performances du forum.
Sans quoi un simple "Attention danger" suivi du lien que tu donnes aurait suffit
et tout ton laïus (ainsi que le mien !) peuvent être vus comme ce qu'ils sont :
de la pollution inutile pour une faute minime dont il ne semble (a priori) pas
spécialement être coutumier.
Après on s'étonne que les informaticiens ont mauvaise réputation !
Pour précision, je critique surtout le ton qui m'apparait comme inutilement
réprobateur et moralisateur aux dépends de l'information qui serait
auto-suffisante et plus agréable. Les forums ne sont pas réservés aux
spécialistes des forums (je fais moi même de nombreuses erreurs), et il est
agréable d'être conseillé plutôt que réprimendé.
Ceci dit, ce n'est que mon avis et je sais bien que mon intervention va
entrainer une levée de boucliers indignés...
Cordialement,
Aurélien.

On Sat, 03 Dec 2005 11:56:33 +0100, Aurélien Barbier-Accary
<nospam_star-shoot_mapson@fr.st.invalid>:

autant l'argument de la
bande passante date d'un autre âge

Et la bande passante lecteur de news -> oeil ?

Bon, je veux bien reconnaître que l'argument est un peu spécieux.

faute minime

Non.

Sans quoi un simple "Attention danger" suivi du lien que tu donnes aurait suffit

Non. Quand je ne donne que le lien, il n'est pas lu.

et tout ton laïus (ainsi que le mien !) peuvent être vus comme ce qu'ils sont :
de la pollution inutile

Sans doute. Aurais-je dû me contenter d'un laconique
"Message illisible - plonk" ?

Bonjour Fabien,

Tout d'abord excuse ma méconnaissance du formalisme des posts newsgroup,
je suis encore novice en la matière. Quand au manque de "logique"
structurel, ca doit être une marque de mon passé en langages de
résolution de prédicat assaisonée d'une sémantique influencée par la NPI
de ma HP ;)

Fabien LE LEZ wrote:

On Sat, 03 Dec 2005 09:46:52 +0100, Mel Higg <mailf@free.fr>:

Jusqu'à présent, j'utilisais des c-string (un simple tableau de char)
plutot que des c++ string pour des raisons de performance (je n'ai que
récemment découvert les moultes réallocations(!!) des string c++).

Je ne suis pas sûr qu'il y ait une réelle différence dans les
performances, à cahier des charges égal.
Si tu connais à l'avance la taille de la chaîne (ou un majorant), un
std::string::reserve() évitera les réallocations.
Si tu ne connais pas la taille à l'avance, il y aura forcément des
réallocations.

Oui, mon pb c'est que je ne connais pas systématiquement la taille à

l'avance (pas plus qu'un majorant d'ailleurs). Et si je ne la connais
pas, dans le cas des string, il y aura forcément des réallocations mais
mon objectif c'est justement de pallier à cette limite des strings.

ropes

C'est un concept assez différent de std::string (qui lui-même est
assez proche des C-string), avec des applications différentes. Si tu
as beaucoup d'insertions à faire, rope sera vraisemblablement
meilleur.
De toutes façons, pour connaître la méthode la plus rapide dans ton
contexte, la seule solution est de tester et chronométrer...

Je suis d'accord avec toi sur ta vision empirique, mais il me semble que

l'intérêt des ropes n'est pas seulement son efficacité à l'insertion,
mais aussi justement son chainage interne de blocs évitant d'inutiles
réallocations.

Reste l'inconnue de la possibilité d'une interface iovec.. La structure
des ropes reste une inconnue pour moi, il semblerait à première vue
qu'il ne soit pas évident d'en extraire des iovecs.

Mel

Mel Higg wrote:

Jusqu'à présent, j'utilisais des c-string (un simple tableau
de char) plutot que des c++ string pour des raisons de
performance (je n'ai que récemment découvert les moultes
réallocations(!!) des string c++).

Grace au profiler, sans doute.

Ça dépend évidemment de l'implémentation de std::string, mais
dans certains cas extrème, c'est vrai qu'une implémentation
générale peut poser des problèmes de performance dans une
utilisation précise.

[...]

J'ai fait quelques recherches sur le WWW à la recherche de
solutions miracles, et j'ai peut etre trouvé mon bonheur dans
les ropes (http://www.sgi.com/tech/stl/Rope.html), dont
l'implémentation GNU semble être exactement reprise de SGI.

Déjà, pensez-vous que je suis sur une bonne piste?

Tout à fait. Rope est un essai d'optimiser l'interface de string
pour une utilisation différente que celle d'habitude. Elle
supporte par exemple de façon efficace l'insertion au plein
milieu d'une chaîne de quelque millions de caractères de long,
ainsi que la copie de telles chaînes. En revanche, l'itération
(et je crois l'opérateur []) est nettement moins rapide que dans
les implémentations classiques de std::string. C'est un
trade-off différent.

Si oui, je me demande si je pourrai raisonnablement créer des
iovecs à partir des blocks internes des ropes pour éviter des
copies inutiles..

Je ne suis pas sûr ce que tu veux dire par les iovecs -- si tu
parles des iovec du Posix readv et writev : il ne doit pas être
difficile à modifier rope pour y ajouter une interface qui
renvoie le iovec nécessaire pour writev. Pour readv, en
revanche, le problème est un peu plus ardu, parce qu'il faut
déterminer les longueurs par l'avance et en allouer la mémoire
dans les blocs.

En revanche, je crois que rope supporte plusieurs types de bloc,
dont les blocs mappés directement sur disque. (C-à-d qu'à la
lecture, tu ne crées que la liste des blocs ; la lecture n'aura
lieu que quand tu accèdes au bloc.)

--
James Kanze mailto: james.kanze@free.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34

Mel Higg wrote:

Fabien LE LEZ wrote:

On Sat, 03 Dec 2005 09:46:52 +0100, Mel Higg <mailf@free.fr>:

Jusqu'à présent, j'utilisais des c-string (un simple tableau
de char) plutot que des c++ string pour des raisons de
performance (je n'ai que récemment découvert les moultes
réallocations(!!) des string c++).

Je ne suis pas sûr qu'il y ait une réelle différence dans les
performances, à cahier des charges égal. Si tu connais à
l'avance la taille de la chaîne (ou un majorant), un
std::string::reserve() évitera les réallocations. Si tu ne
connais pas la taille à l'avance, il y aura forcément des
réallocations.

Oui, mon pb c'est que je ne connais pas systématiquement la
taille à l'avance (pas plus qu'un majorant d'ailleurs). Et si
je ne la connais pas, dans le cas des string, il y aura
forcément des réallocations mais mon objectif c'est justement
de pallier à cette limite des strings.

Si tu ne le connais pas, il y aura forcément des réallocations,
quelque soit l'implémentation. Ce que tu gagneras avec rope,
ce sont des copies.

Quand la taille des chaînes se mésure en millions, ça peut faire
une différence importante. Avant, je ne sais pas.

ropes

C'est un concept assez différent de std::string (qui lui-même
est assez proche des C-string), avec des applications
différentes. Si tu as beaucoup d'insertions à faire, rope sera
vraisemblablement meilleur. De toutes façons, pour connaître
la méthode la plus rapide dans ton contexte, la seule solution
est de tester et chronométrer...

Je suis d'accord avec toi sur ta vision empirique, mais il me
semble que l'intérêt des ropes n'est pas seulement son
efficacité à l'insertion, mais aussi justement son chainage
interne de blocs évitant d'inutiles réallocations.

Oui et non. Il faut allouer chaque bloc. Si tu n'ajoutes qu'à la
fin, il risque d'avoir plus d'allocations avec rope qu'avec une
bonne implémentation de std::string.

Reste l'inconnue de la possibilité d'une interface iovec.. La
structure des ropes reste une inconnue pour moi, il semblerait
à première vue qu'il ne soit pas évident d'en extraire des
iovecs.

Pour l'écriture (en supposant que tu veux dire les iovec de
writev de Posix -- chose qu'il vaut mieux dire, parce que tout
le monde ici ne connaît pas Posix dans tous les détails), je ne
crois pas que ça soit particulièrement difficile. Pour la
lecture, en revanche...

Peut-être si on savait plus de ce que tu essaies à faire...

--
James Kanze mailto: james.kanze@free.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34