J'ai toujours été surpris par la propriété d'ordonnancement de std::map. Mais c'est une vieille structure. Depuis, la norme d'implémentation est devenue les hash maps, que ce soit en Java ou en Perl ou les dict en Python (bien que ces derniers conservent l'ordre, après une n-ième implémentation).
J'ai presque envie de conseiller std::unordered_map comme std::map et de renommer std::map en std::ordrered_map ;) Quand à l'opérateur [] qui crée forcément un entrée, en appelant le constructeur par défaut, c'est un principe même du langage… qui est un sacré piège, surtout quand les valeurs de la map sont des objets complexes.
pour les conteneurs y'a at qui ne créent pas l'entrée, et qui font les vérifications qui vont bien (genre on dépasse pas pour les vecteurs) je trouverai particulièrement incongru qu'un [] me jette une exception
J'ai presque envie de conseiller std::unordered_map comme std::map et de renommer std::map en std::ordrered_map
y'a pleins de code qui vont planter, notamment tout ceux qui se basent justement sur le fait que le parcours est trié; sans compter que certains code vont perdre en perf. Ou tout simplement ne vont pas compiler (lower_bond/upper_bond)
J'ai toujours considéré qu'avant de choisir une structure de données il était important de regarder ce qui était disponible et de choisir en conséquence; c'était même une notion importante inculqué en IUT (list, tableau, file, pile, tas, tableau associatif…), ordonné ou non, avec la complexité des différents accesseurs.
Décider de changer une implémentation pour que les gens ne réfléchissent pas avant de coder me parait une mauvaise idée.
Il ne faut pas décorner les boeufs avant d'avoir semé le vent
Sauf que std::ordrered_map n'existe pas, et que std::unordrered_map a été ajouté par C++11 quand std::map existe depuis le début.
Pour des raisons de compatibilités tu ne peux pas revenir en arrière sur ces noms et leur implication si facilement. La base de code impactée serait trop importante.
Cela s'appelle l'héritage historique et ce n'est pas la première fois que cela arrive dans notre domaine.
Bien sûr, bien sûr. Mais ça ne change pas le problème. Le fait est que le langage a mis une implémentation de map en avant qui se retrouve celle utilisé par défaut de fait : elle est présente dans toutes les implémentations standards du langage sans nécessité de nouvelle dépendance.
J'avoue personnellement que pour un langage dont beaucoup de locuteur mettent la performance en première qualité et souhaitant éviter tout tests inutiles avoir comme unique implémentation une map "over featured" et surprenant.
Pour des raisons de compatibilités tu ne peux pas revenir en arrière sur ces noms et leur implication si facilement. La base de code impactée serait trop importante.
Je suis personnellement de plus en plus embêté par ce genre d'approche. Pour moi les ruptures de compatibilité doivent être gérées (ne pas arriver à n'importe quel moment, ne pas aller dans tous les sens, etc), mais il doit y avoir des ruptures de compatibilité sinon on risque l'ossification du langage voir du langage à plusieurs niveau avec toute une pile non standard qui tente de créer une norme au dessus de la norme.
J'avoue personnellement que pour un langage dont beaucoup de locuteur mettent la performance en première qualité et souhaitant éviter tout tests inutiles avoir comme unique implémentation une map "over featured" et surprenant.
Il existait d'autres moyens d'arriver à ses fins avant cette map standard, et ce n'est pas vraiment en contradiction avec les qualités mises en avant par ses locuteurs : cette implémentation standard se veut performante et sans tests inutiles pour un cas qui a été jugé courant (ordonné) et difficile…
Les versions normalisées mettent du temps et plusieurs acteurs (libres et propriétaires) sont impliqués. Du coup ça correspond bien aux besoins consensuels au moment de sa sortie. Fort de cela, pour ma part, je trouve dommage qu'il n'y ait pas eu std::ordrered_map et std::unordrered_map dès le début, avec std::map comme alias/synonyme du premier (puisque c'était le besoin/cas principal/courant.)
on risque l'ossification du langage voir du langage à plusieurs niveau avec toute une pile non standard qui tente de créer une norme au dessus de la norme.
Ce n'est pas un risque mais bien l'approche choisie (àmha) contrairement à d'autres (Go, Java, Rust, etc.) Mais il n'y a pas vraiment d'approche qui soit vraiment meilleure qu'une autre (àmha) car chacun a sa philosophie, sa cible, et divers paramètres.
Ceci dit, j'ai l'impression qu'il y a une certaine précipitation (ce que tu appelles "aller dans tous les sens" je pense) pour coller à une supposée concurrence (pourtant, les langages ne devraient s'opposer) & ne plus faire son âge vénérable…
“It is seldom that liberty of any kind is lost all at once.” ― David Hume
Je pense qu'il y a plusieurs raisons pour que le type « tableau associatif » du C++ soit un arbre binaire plutôt qu'une table de hachage. Entre autre choses il faut voir que cela date du début des années 90, quand il n'y avait même pas de standardisation du langage. Ensuite il faut voir qu'un arbre binaire c'est intellectuellement plaisant, et les gens qui ont produit la base du C++ à cette époque étaient plutôt intellos, du genre à considérer que tous les algos en O(n) se valent. À côté de ça une table de hachage c'est un peu bête : c'est juste un gros tableau. Et encore ça ne résout que la moitié du problème puisqu'il faut en plus lui donner une fonction de hachage rapide et avec peu de collisions. Pas simple. Dans le pire des cas on a une recherche en O(n) (toutes valeurs ont le même hash), là où l'arbre binaire est en O(log(n)) (qu'on va déguiser en O(1) en le qualifiant d'« amorti »).
Est-ce que les mesures faites avec perf prennent en compte uniquement le temps cpu utilisé? Il y a peut-être pas mal de performances à gagner sur les entrées/sorties, en particulier en utilisant de façon intelligente les buffers proposés par fstream. Mais pour ça il faut mesurer le temps "réel" et pas le temps "user". Il me semble que c'est faisable avec perf en changeant quelques options.
J'ai eu des gains très importants en creusant de ce côté sur un de mes projets, mais c'était sur un système embarqué avec du stockage eMMC et un système de fichier f2fs. Peut-être sur un PC portable, les IO sont beaucoup plus rapides?
(note: le lien est indiqué en français, mais il est en anglais)
Oui, par défaut ce sont les cycles CPU, mais dans l'article je n'ai pas vu de précision sur ce qui est fait avec perf (et c'est un outil qui peut faire beaucoup d'autres choses).
Justement, ma question est de savoir précisément ce qui est mesuré avec perf. Dans la commande "time" on a droit à 3 mesures:
Le temps "user": temps passé à exécuter du code utilisateur
Le temps "system": temps passé à exécuter du code du noyau (appels système)
Le temps "real": temps total de l'exécution
On peut soustraire les deux premiers au troisième pour avoir le temps passé à ne pas exécuter de code du processus concerné (autres tâches en cours d'exécution, attente sur les entrées-sorties, etc).
Avec le compteur "cycles" de perf, on mesure au mieux les deux premiers, mais pas le troisième. Et donc le temps passé à ne pas exécuter de code n'est pas identifié. Je n'ai pas trouvé dans l'article ni dans le dépôt git du benchmark si tu as regardé la commande "time" pour voir si le code passe surtout du temps à s'exécuter ou surtout du temps à attendre les entrées-sorties. Ça peut être pas mal de vérifier ça pour s'assurer qu'on optimise au bon endroit. Si le programme est limité par les entrées-sorties, les gains en utilisation CPU ne seront pas visibles sur le throughput ou le temps d'exécution total pour un test donné (mais ils seront visibles sur la charge CPU et la consommation électrique).
Pour mesurer le temps passé ailleurs que dans le code avec perf: par exemple, en utilisant les évènements "syscalls:sys_enter_" on peut profiler tous les endroits qui font des appels systèmes (ce qui est en général assez coûteux, ça se place quelque part entre un appel de fonction et un switch de contexte pour exécuter un autre processus). Les évènements "block:" peuvent aussi être utiles pour regarder les entrées-sorties sur disque. On s'éloigne vite du C++ pour entrer dans les détails de la programmation système UNIX, mais ça peut être intéressant.
Bonnes remarques, je vais ajouter les infos dans les posts. La commande perf mesure donc les cycles, sur l'ensemble du programme (y compris le chargement du fichier donc). Par contre le temps rapporté dans les tables et représenté sur les graphes correspond au temps de traitement de l'input après qu'il ait été entièrement copié dans une std::string. Il n'y a donc pas d'IO dans ces métriques.
# Héritage de std::map
Posté par Glandos . Évalué à 5.
J'ai toujours été surpris par la propriété d'ordonnancement de
std::map. Mais c'est une vieille structure. Depuis, la norme d'implémentation est devenue les hash maps, que ce soit en Java ou en Perl ou les dict en Python (bien que ces derniers conservent l'ordre, après une n-ième implémentation).J'ai presque envie de conseiller
std::unordered_mapcommestd::mapet de renommerstd::mapenstd::ordrered_map;) Quand à l'opérateur[]qui crée forcément un entrée, en appelant le constructeur par défaut, c'est un principe même du langage… qui est un sacré piège, surtout quand les valeurs de la map sont des objets complexes.[^] # Re: Héritage de std::map
Posté par fearan . Évalué à 8.
pour les conteneurs y'a at qui ne créent pas l'entrée, et qui font les vérifications qui vont bien (genre on dépasse pas pour les vecteurs) je trouverai particulièrement incongru qu'un [] me jette une exception
y'a pleins de code qui vont planter, notamment tout ceux qui se basent justement sur le fait que le parcours est trié; sans compter que certains code vont perdre en perf. Ou tout simplement ne vont pas compiler (lower_bond/upper_bond)
J'ai toujours considéré qu'avant de choisir une structure de données il était important de regarder ce qui était disponible et de choisir en conséquence; c'était même une notion importante inculqué en IUT (list, tableau, file, pile, tas, tableau associatif…), ordonné ou non, avec la complexité des différents accesseurs.
Décider de changer une implémentation pour que les gens ne réfléchissent pas avant de coder me parait une mauvaise idée.
Il ne faut pas décorner les boeufs avant d'avoir semé le vent
[^] # Re: Héritage de std::map
Posté par barmic 🦦 . Évalué à 2.
Le fait que
std::mapexiste montre que c'est pourtant prévu. Sinon il n'existerait questd::ordrered_mapetstd::unordrered_map.https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll
[^] # Re: Héritage de std::map
Posté par Renault (site web personnel) . Évalué à 6.
Sauf que
std::ordrered_mapn'existe pas, et questd::unordrered_mapa été ajouté par C++11 quandstd::mapexiste depuis le début.Pour des raisons de compatibilités tu ne peux pas revenir en arrière sur ces noms et leur implication si facilement. La base de code impactée serait trop importante.
Cela s'appelle l'héritage historique et ce n'est pas la première fois que cela arrive dans notre domaine.
[^] # Re: Héritage de std::map
Posté par barmic 🦦 . Évalué à 3.
Bien sûr, bien sûr. Mais ça ne change pas le problème. Le fait est que le langage a mis une implémentation de map en avant qui se retrouve celle utilisé par défaut de fait : elle est présente dans toutes les implémentations standards du langage sans nécessité de nouvelle dépendance.
J'avoue personnellement que pour un langage dont beaucoup de locuteur mettent la performance en première qualité et souhaitant éviter tout tests inutiles avoir comme unique implémentation une map "over featured" et surprenant.
Je suis personnellement de plus en plus embêté par ce genre d'approche. Pour moi les ruptures de compatibilité doivent être gérées (ne pas arriver à n'importe quel moment, ne pas aller dans tous les sens, etc), mais il doit y avoir des ruptures de compatibilité sinon on risque l'ossification du langage voir du langage à plusieurs niveau avec toute une pile non standard qui tente de créer une norme au dessus de la norme.
https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll
[^] # Re: Héritage de std::map
Posté par Gil Cot ✔ (site web personnel, Mastodon) . Évalué à 2.
Il existait d'autres moyens d'arriver à ses fins avant cette map standard, et ce n'est pas vraiment en contradiction avec les qualités mises en avant par ses locuteurs : cette implémentation standard se veut performante et sans tests inutiles pour un cas qui a été jugé courant (ordonné) et difficile…
Les versions normalisées mettent du temps et plusieurs acteurs (libres et propriétaires) sont impliqués. Du coup ça correspond bien aux besoins consensuels au moment de sa sortie. Fort de cela, pour ma part, je trouve dommage qu'il n'y ait pas eu
std::ordrered_mapetstd::unordrered_mapdès le début, avecstd::mapcomme alias/synonyme du premier (puisque c'était le besoin/cas principal/courant.)Ce n'est pas un risque mais bien l'approche choisie (àmha) contrairement à d'autres (Go, Java, Rust, etc.) Mais il n'y a pas vraiment d'approche qui soit vraiment meilleure qu'une autre (àmha) car chacun a sa philosophie, sa cible, et divers paramètres.
Ceci dit, j'ai l'impression qu'il y a une certaine précipitation (ce que tu appelles "aller dans tous les sens" je pense) pour coller à une supposée concurrence (pourtant, les langages ne devraient s'opposer) & ne plus faire son âge vénérable…
“It is seldom that liberty of any kind is lost all at once.” ― David Hume
[^] # Re: Héritage de std::map
Posté par Julien Jorge (site web personnel) . Évalué à 5.
Je pense qu'il y a plusieurs raisons pour que le type « tableau associatif » du C++ soit un arbre binaire plutôt qu'une table de hachage. Entre autre choses il faut voir que cela date du début des années 90, quand il n'y avait même pas de standardisation du langage. Ensuite il faut voir qu'un arbre binaire c'est intellectuellement plaisant, et les gens qui ont produit la base du C++ à cette époque étaient plutôt intellos, du genre à considérer que tous les algos en O(n) se valent. À côté de ça une table de hachage c'est un peu bête : c'est juste un gros tableau. Et encore ça ne résout que la moitié du problème puisqu'il faut en plus lui donner une fonction de hachage rapide et avec peu de collisions. Pas simple. Dans le pire des cas on a une recherche en O(n) (toutes valeurs ont le même hash), là où l'arbre binaire est en O(log(n)) (qu'on va déguiser en O(1) en le qualifiant d'« amorti »).
# Mesures avec perf
Posté par pulkomandy (site web personnel, Mastodon) . Évalué à 2.
Est-ce que les mesures faites avec perf prennent en compte uniquement le temps cpu utilisé? Il y a peut-être pas mal de performances à gagner sur les entrées/sorties, en particulier en utilisant de façon intelligente les buffers proposés par fstream. Mais pour ça il faut mesurer le temps "réel" et pas le temps "user". Il me semble que c'est faisable avec perf en changeant quelques options.
J'ai eu des gains très importants en creusant de ce côté sur un de mes projets, mais c'était sur un système embarqué avec du stockage eMMC et un système de fichier f2fs. Peut-être sur un PC portable, les IO sont beaucoup plus rapides?
(note: le lien est indiqué en français, mais il est en anglais)
[^] # Re: Mesures avec perf
Posté par Julien Jorge (site web personnel) . Évalué à 2.
Il me semble que perf compte juste des événements, sans notion de temps. Par défaut il compte les cycles CPU.
Il y a des trucs à gagner avec les streams oui. J'en parlerai dans un futur billet mais ce n'est pas encore dans le top des trucs coûteux.
C'est corrigé, merci :)
[^] # Re: Mesures avec perf
Posté par pulkomandy (site web personnel, Mastodon) . Évalué à 4.
Oui, par défaut ce sont les cycles CPU, mais dans l'article je n'ai pas vu de précision sur ce qui est fait avec perf (et c'est un outil qui peut faire beaucoup d'autres choses).
Justement, ma question est de savoir précisément ce qui est mesuré avec perf. Dans la commande "time" on a droit à 3 mesures:
On peut soustraire les deux premiers au troisième pour avoir le temps passé à ne pas exécuter de code du processus concerné (autres tâches en cours d'exécution, attente sur les entrées-sorties, etc).
Avec le compteur "cycles" de perf, on mesure au mieux les deux premiers, mais pas le troisième. Et donc le temps passé à ne pas exécuter de code n'est pas identifié. Je n'ai pas trouvé dans l'article ni dans le dépôt git du benchmark si tu as regardé la commande "time" pour voir si le code passe surtout du temps à s'exécuter ou surtout du temps à attendre les entrées-sorties. Ça peut être pas mal de vérifier ça pour s'assurer qu'on optimise au bon endroit. Si le programme est limité par les entrées-sorties, les gains en utilisation CPU ne seront pas visibles sur le throughput ou le temps d'exécution total pour un test donné (mais ils seront visibles sur la charge CPU et la consommation électrique).
Pour mesurer le temps passé ailleurs que dans le code avec perf: par exemple, en utilisant les évènements "syscalls:sys_enter_" on peut profiler tous les endroits qui font des appels systèmes (ce qui est en général assez coûteux, ça se place quelque part entre un appel de fonction et un switch de contexte pour exécuter un autre processus). Les évènements "block:" peuvent aussi être utiles pour regarder les entrées-sorties sur disque. On s'éloigne vite du C++ pour entrer dans les détails de la programmation système UNIX, mais ça peut être intéressant.
[^] # Re: Mesures avec perf
Posté par Julien Jorge (site web personnel) . Évalué à 3.
Bonnes remarques, je vais ajouter les infos dans les posts. La commande
perfmesure donc les cycles, sur l'ensemble du programme (y compris le chargement du fichier donc). Par contre le temps rapporté dans les tables et représenté sur les graphes correspond au temps de traitement de l'input après qu'il ait été entièrement copié dans unestd::string. Il n'y a donc pas d'IO dans ces métriques.Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.