[C++] Copy-On-Write benchmark

Hello,

on n'a pas mal argumenté le pour et contre le COW dans Qt,

http://blogs.qtdeveloper.net/archive...it-2/#more-158

Qu'en pensez-vous ?

http://blog.developpez.com/index.php...&c=1&tb=1&pb=1
Je suis content qu'il ait démontré que la méthode de Trolltech soit plus rapide. Après les tests de Sutter, j'avais un doute, mais les optimisations de Qt ont fait le travail + les QString ne sont pas les plus critiques pour ce genre de choses - imaginez les benchmarks sur des QList ! -

Je me pose la question d'inclure un pointeur Qt plutôt qu'un pointeur Boost dans ma bibliothèque matricielle...

tu revises donc ta position ? :)
qu'entends-tu par les benchmarks sur les lists ?

Les QList sont aussi partagées implicitement.

En fait, je n'avais jamais eu de position fixe ;)

oui c'est clair, les Qlist ca evite beaucoup de recopie et permet un design plus propre en retournant la liste.

mais tu n'etais pas pour la stl a tout pris ? ;)

enfin tout le monde peut changer d'avis hein ? :D

Comme l'a dit je ne sais plus qui : Il ne faut jamais croire un benchmark que l'on n'a pas truqué soit-même ;)

En l'occurence, je n'ai pas eu l'occasion de le tester sur ma machine, de jouer avec... Je ne dis pas que je j'y crois, ni que je n'y crois pas.

Par contre, en jettant un oeil rapide sur le code, je ne vois pas en quoi les chaînes sont partagées entre les différent thread ?

Le comportement de std::string dépend de l'implémentation, cellede libstdc++ utilise déjà du copy-on-write et pas vraiment de manière optimisée pour le multithreadé d'après ce que je sais.

Et en regardant les résultats des benchmarks je ne vois rien qui explicite que les solutions de Qt sont mieux.

J'ai survolé les benchs.

Comme je disais par mail à Aurélien. La pertinence du COW m'échappe toujours.
Je veux bien volontier admettre un intérêt à des chaînes non mutables partagées. Mais pas à des COW partagées dans divers threads.

Mes scénarios de manipulation de chaines consistent généralement à construire ces chaines et à ensuite les figer. Après éventuellement elles sont dans des tâches (ace) partagées entre plusieurs threads, ou expédiées d'une tâche à l'autre. Et si j'avais des modifs à faire, cela correspondrait à des reset, mais pas à des utilisations de [] ou de quoique ce soit qui active une copie sur écriture.

Du coup les benchs qui me semblent les plus pertinents (je ne les ai plus en tête) sont ceux:
- de construction (et encore)
- ceux d'accès "globaux" pour quand on veut sérialiser vers une autre structure ; on utilise alors directement le pointeur sous-jascent ; ne devrait pas couter grand chose, même avec du COW
- ceux d'accès "atomique" pour ceux qui ecrivent des boucles avec [] sur tous les éléments des chaines ; là le COW ne devrait pas être si bon je pense.

Le coût de la copie de type chaine à type chaîne ? Est-ce si pertinent ?
Mes paramètres sont pris par référence constante (ce qui n'est pas le cas d'un de leurs benchs :?). Je ne fais pas de copies pour le plaisir de faire des copies -- à la limite pour un nouvel object qui recopie la chaine reçue lors de sa construction, ici OK pour des non-mutables partagées et réinitialisables.
Mes retours vont utiliser RVO et RNVO (quand possible), un jour les lvalue reference (je l'espère). Là effectivement, on n'a pas de sémantique de déplacement native... OK pour cet avantage là. Bien que la non-mutable partagée est très bien aussi, voire carrément que le comptage non protégé contre le multithread. (*)

(*) Dans le genre il aurait fallu un constructeur à std::list qui prenne un std::auto_ptr<std::list> et qu'il s'implémente par un swap. Bon, c'est sale et cela fait plus de types, et cela empêche les R*VO, c'est vrai.

Pour les concaténations, il existent d'autres techniques qui torchent (cf les concatenators présentés par Matthew Wilson dans Imperfect C++ et donc présents dans stl_soft -- bien que je serais plus parti sur une approche de meta-prog plutôt que l'approche dynamique qu'il a choisie)

Pour revenir à QT, vu qu'ils utilisent un proxy, cela mérite de ressortir le MEC++ pour voir si il n'y aurait pas des effets de bord bizarres.

Je suis aussi très surpris des résultats de GCC. Je savais pour le COW, mais je vois rien qui justifie les écarts. A part une très mauvaise implémentation du comptage atomique, ou d'autre chose.

A propos de RVO/RNVO je me demande qu'elle sont les options de compils retenues dans les bench vu les coûts de certains appels. Bref, il faudra que je remesure tout cela chez moi.

Je ne vois pas pourquoi les pointeurs intelligents de QT seraient plus efficaces que ceux de boost qui reposent aussi sur des compteurs atomiques (ou non dans le cas de boost compilé en mono-thread). Sans parler de la richesse de l'interface qui fait que les boost::shared_ptr sont en fait des shared_ressource.

PS: dès que j'ai un moment je m'occupe sérieusement de ces transcripts :-(

Pou Qt, il faut aussi voir ça de manière plus générale que juste pour les string. Ils partagent ainsi les données de toutes leurs classes qui ont un minimum de données - P_IMPL idiome pour assurer une compatibilité binaire entre les versions de Qt -.
Pour des caînes partagées entre les threads, dans Qt3, ce n'était pas le cas, et apparemment ils ont eu un retour négatif sur ce problème car on devait forcer la copie complète. Maintenant, on peut s'en passer, c'est plus transparent. De plus, leur comptage atomique est efficace, du moins plus efficace qu'une recopie, et leurs mutex qui utilisent aussi leur classe atomique est plus rapide qu'un mutex traditionnel.

Voir aussi:
http://blogs.qtdeveloper.net/archive...the-benchmark/

Pour info, l'auteur de ce benchmark a été interviewé par developpez.com quelques jours avant de publier ses résultats. On va bientôt publier tout ça... (ben oui je fais du teasing :D)

Citation:

---

un jour les lvalue reference (je l'espère)

---

rvalue references plutôt non ?

Citation:

---

Pour les concaténations, il existent d'autres techniques qui torchent

---

De manière dynamique, une structure comme sgi rope devrait aussi fournir de bons résultats pour la concaténation.

Citation:

---

Envoyé par Miles

leurs mutex qui utilisent aussi leur classe atomique est plus rapide qu'un mutex traditionnel.

---

Il y a un truc que je trouve louche là.
Si on pouvait implémenter des mutex avec des compteurs atomiques, pourquoi est-ce que les autres implémentations de mutex ne procèderaient pas aussi de la sorte pour avoir un truc plus efficace ?
(ceci n'est pas une question comme dans "je connais la réponse, mais pose toi aussi la question". Mais comme dans "je n'en sais strictement rien". Je ne me suis jamais posée cette question)

Citation:

---

Envoyé par loufoque

rvalue references plutôt non ?

---

arf. Oui au temps pour moi. Je me plante toujours.

Citation:

---

Envoyé par Luc Hermitte

Si on pouvait implémenter des mutex avec des compteurs atomiques, pourquoi est-ce que les autres implémentations de mutex ne procèderaient pas aussi de la sorte pour avoir un truc plus efficace ?

---

Note: je suis quelqu'un de très atypique en ce qui concerne la programmation multithread. Je joue encore avec, mais mon expérience est essentiellement dans le cadre de programmation en Ada, il y a une dizaine d'année. Je peux être complètement à côté de la plaque.

Un mutex doit nécessairement recourir à l'OS s'il ne peut pas se contenter d'être du polling sur une variable, consommant du CPU pour rien. Une possibilité est que les mutex de QT fasse un peu de polling avec des algo lock-free (éventuellement un seul passage peut être un gain) puis prennent un lock via l'OS. On a un gain si la lib n'utilise pas déjà ce truc (ce qui m'étonnerait un peu, je le connais et je suis plutôt rouillé en la matière) et que le lock est généralement soit libre soit pris par un process tournant sur un autre processeur qui le libère rapidement.

vous etes vraiment sure que les mutexes dans Qt sont implementés avec des compteurs atomiques ?

moi je ne pense pas du tout.

Citation:

---

Envoyé par Jean-Marc.Bourguet

Un mutex doit nécessairement recourir à l'OS s'il ne peut pas se contenter d'être du polling sur une variable, consommant du CPU pour rien. Une possibilité est que les mutex de QT fasse un peu de polling avec des algo lock-free (éventuellement un seul passage peut être un gain) puis prennent un lock via l'OS. On a un gain si la lib n'utilise pas déjà ce truc (ce qui m'étonnerait un peu, je le connais et je suis plutôt rouillé en la matière) et que le lock est généralement soit libre soit pris par un process tournant sur un autre processeur qui le libère rapidement.

---

C'est ça, je crois. En tout cas, s'ils l'utilisent, c'est après avoir vérifié dans la doc et dans les benchs qu'un mutex traditionnel comporte beaucoup d'aller-et-venues, et avoir une opération atomique pour tenter d'avoir un lock est plus rapide tout de même.

Je pense serieusement que les compteurs atomiques sont seulement utilisés pour le implicit sharing.

... atomic counting n'est pas de la mise en attente du thread sur une resource protégé

Dans les opérateurs atomiques, il n'y a pas que l'incrémentation, il y a aussi le set and test, et ça, ça sert pour les mutex. Et c'est certain qu'ils s'en servent cf un article dans qqs jours sur "Qt in depth".

Citation:

---

Envoyé par Luc Hermitte

Il y a un truc que je trouve louche là.
Si on pouvait implémenter des mutex avec des compteurs atomiques, pourquoi est-ce que les autres implémentations de mutex ne procèderaient pas aussi de la sorte pour avoir un truc plus efficace ?

---

Parce qu'on veut dans certains cas en avoir plus ? Par exemple, sous windows, un mutex est partageable entre processus. Il y existe aussi un objet (mal) nommé CriticalSection, qui est en fait un mutex non partageable entre processus, et qui a de bien meilleures perfs.

a priori qt se sert du comptage atomique pour faire des mutexes recursifs.
mais le wait et le wakeup utilise bien un mutex pthread (sous macos)

a+

Oui, il utilise un mutex standard après. Mais au départ, pour accélerer, il utilise un test and set atomique - j'ai l'info directement du concepteur du système... -

tu en as de la chance toi !!!
moi je l'ai vu dans le code :)

La vidéo de la présentation devrait être dispo le mois prochain :D

Si longtemps :aie: ?

Après la conférence de San Jose... (c'est la video de Trolltech).

Il faudra que je reregarde comment ils procèdent dans ACE -- ils ont quantités de mutex, locks et gardes différents. Sans parler des diverses polices pour paramétrer tout cela.

Sinon, dans ce dernier "thême" je suis tombé sur ça aujourd'hui. http://www.artima.com/cppsource/threads_meeting.html (compte rendu de la dernière réunion du commité de standardisation au sujet du support du multi-threading dans le C++0x)
Très intéressant.

En ce qui concerne les critical sections sous Windows:
http://support.microsoft.com/kb/105678/en-us
Il y a aussi les fonctions InterlockedXXX
http://msdn.microsoft.com/library/en...ronization.asp

Citation:

---

Envoyé par Luc Hermitte

http://www.artima.com/cppsource/threads_meeting.html (compte rendu de la dernière réunion du commité de standardisation au sujet du support du multi-threading dans le C++0x)

---

Ce n'est pas la dernière... La dernière est en cours actuellement.. ;)

A part ça, j'ai découvert ce doc, qui a l'air assez sympa aussi http://www.cs.utah.edu/~wilson/compi...04-michael.pdf. Faudra que je le lise au calme.

donc en fait Qt a fait le bon choix ... ?
je dis cela parce que j'observe un revirement assez impressionnant sur le COW ...

mais ca me rassure croyez moi :lol:

C'est pas qu'ils on fait le bon choix, c'est simplement qu'ils ont ajouté un refcounting plus optimisé pour le multi-threadé.
Pas de quoi casser trois pattes à un canard...

Sans cette optimisation, en faisant des copies à chaque fois dans leurs programmes, le CPU grimperait de 50% d'après des tests qu'ils ont fait.

Je crois que c'est le gain mémoire qui est de 50% dans le designer, + un gain visible en terme de vitesse d'exécution (difficile à quantifier).

Citation:

---

Envoyé par Aurelien.Regat-Barrel

Je crois que c'est le gain mémoire qui est de 50% dans le designer, + un gain visible en terme de vitesse d'exécution (difficile à quantifier).

---

Ah ? JE croyais que c'était le temps CPU... De toute manière, on verra vite :D

Yep :D Il me semble que c'est les 2 (tant qu'à faire).

Quel revirement de situation quand meme ! ;)

En même temps, il y a sûrement moyen d'éviter cette dégradation en utilisant moisn de copies, ...

Citation:

---

Envoyé par Miles

Sans cette optimisation, en faisant des copies à chaque fois dans leurs programmes, le CPU grimperait de 50% d'après des tests qu'ils ont fait.

---

C'est un cercle vicieux ! Ils ont le COW. Des développeurs décident alors de passer par copie au lieu de passer par référence. Donc, dans ces programmes, les perfs baissent notablement si on n'utilise plus le COW. Donc on prétend que le COW fait gagner du temps.

Si on me dit qu'un programme typique fait par une personne un minimum compétente sans COW, puis porté dans un environnement COW se comporte XX% plus vite pourquoi pas. Mais là, j'ai quelques doutes.

J'ai pas fait trop de tests, mais je n'ai clairement pas l'impression que mes programment passent une partie mesurable de leur temps dans des copies de chaînes inutiles.

pas seulement de chaines mais de collection, set, map etc...
et sans compter un design clair et une relecture facile.

C'est surtout par rapport à la valeur de retours dans les fonctions je crois. Avec la STL, tu es obligés "d'optimiser à la main" en jouant avec swap:

Code:

---

1 2 3 4 5

std::vector<int> get_vect();   std::vector<int> v; v.swap( get_vect() );

---

Avec l'approche de Qt l'écriture est allégée. Y'a du pour et y'a du contre...

Citation:

---

Envoyé par JolyLoic

C'est un cercle vicieux ! Ils ont le COW. Des développeurs décident alors de passer par copie au lieu de passer par référence. Donc, dans ces programmes, les perfs baissent notablement si on n'utilise plus le COW. Donc on prétend que le COW fait gagner du temps.

---

Tout à fait d'accord avec toi, un test sur un programme plus neutre serait plus approprié, sans nul doute.