GCC réimplémenté en C++

[Hinault Romaric]

GCC réimplémenté en C++
les développeurs du compilateur andonnent le C pour garder son code facilement maintenable et compréhensible

Le développement du compilateur GCC (GNU Compiler Collection) passe du langage C au C++.

La communauté en charge du développement de la suite de compilateurs libre GCC vient d’annoncer que son code a été réimplémenté avec le langage orienté objet C++.

Avant cette adoption définitive du C++, le code utilisé dans l’étape un du processus de construction de GCC a été mis en œuvre avec le langage C. Le code des étapes deux et trois de ce processus a été développé pendant un certain temps en C++ avant d’être abandonné.

L’idée d’utiliser le C++ en lieu et place du C avait germé dans la tête des développeurs de GCC en mai 2010, qui estimaient que le C++ était acceptable pour développer le compilateur.

Selon les explications sur le Wiki du projet, le passage du C au C++ a pour objectif de maintenir le code du GCC compréhensible et facilement maintenable. Les développeurs du projet notent néanmoins que l’utilisation imprudente de C++ peut être lourde de conséquences. Un point qui cependant n’est pas qualitativement différent des problèmes rencontrés actuellement.

Les modifications du code de GCC ont été planifiées et mises en œuvre dans le cadre du projet « GCC in Cxx ». Certaines structures de données ont déjà été réimplémentées en C++ et, actuellement, les développeurs sont en train de travailler sur les changements qui ont été intégrés à la branche 4.7.

GCC est à sa version 4.7.1 depuis juin 2012. La suite de compilateurs permet de transformer le code source en langage machine pour plusieurs langages de programmation dont C, C++, Java, Objective-C, Ada et même Fortran 95.



Source : Wiki conversion GCC vers C++


Et vous ?

Bonne ou mauvaise idée ? Pourquoi ?

[Freem]

Envoyé par Hinault Romaric

Bonne ou mauvaise idée ? Pourquoi ?

Bonne... question.

D'un côté, C++ permet d'utiliser plus de paradigmes de développement, mais cet ajout implique pour moi une certaine nécessité de re-réfléchir à la conception.
Je ne suis pas du tout persuadé que la migration d'un langage à un autre soit une bonne idée.

D'un autre côté, C++ permet de compiler du C. Le fait qu'il soit multi-paradigme permet tout simplement une refonte en douceur, très progressive, via divers refactoring très légers.
Donc la stabilité ne devrait pas trop en souffrir.

Après... Quels sont les avantages de C++ contre C?
_ la possibilité d'utiliser des outils pour générer des diagrammes de classes UML afin de comprendre nettement plus rapidement la structure de code. Diagrammes UML qui sont quand même de plus en plus connus par les développeurs, je pense. L'intérêt de ce point, c'est de pouvoir amener facilement de nouveaux contributeurs: plus un projet est simple a appréhender, moins ça coûte cher en formation et motivation, plus rapidement les nouveaux contributeurs peuvent contribuer. Donc, plus vite le projet peut lui-même évoluer.
Bien sûr, ce n'est pas parce qu'un projet est écrit en C qu'il est mal documenté, mais je n'ai jamais entendu parler d'outils qui extraient la structure d'un projet écrit en langage non objet.

_ utilisation des templates. Ca allonge la durée de compilation, mais ça permet de réduire la base de code de façon parfois drastique. Je doute fortement que ça aie un impact en terme de performances, en revanche, niveau maintenance, c'est une évidence. Bon... tant qu'il n'y a pas besoin d'aller lire le code source des templates fournis par G++, parce que bon, ces bouts de code n'ont pas grand chose de simple à lire... Voire de lisible...

Donc, pour moi, le seul gain potentiel sera un gain en terme de maintenance, une certaine partie du code sera fusionnée via les templates, une autre sera plus lisible grâce aux fonctions inline, et une doc pourra être générée à partir du source via les diagrammes de classe.

Peut-être même de légères pertes de performances dans l'absolu, parce que migrer du langage C au langage C++ est truffé de subtilités, mais s'ils gèrent bien (ce qui est probable, on parle de gens qui écrivent des compilateurs, dont un compilateur C++ hein), la différence ne sera pas perceptible (voire inexistante?):
Utiliser les méthodes et fonctions inline à bon escient et ne pas abuser du code virtuel (héritages et méthodes) permet de n'avoir que peu voire pas du tout d'impact.
Vu que la base de code est en C, je doute qu'il y ait de l'héritage de structures autre que "manuel" et du coup, il ne devrait pas y avoir trop de virtuel. De ce côté, il est même possible qu'il y ait un gain de performances occupation mémoire et/où utilisation CPU).
Pour l'inlining, le compilateur fait bien le boulot lui-même, je pense.

D'ailleurs, cette nouvelle amène une question:
C++, oui, mais C++11?
Parce que si ce n'est pas le cas, ils vont se priver de certains mécanismes qui peuvent considérablement simplifier leur vie: move semantic, intégration des instructions multi-thread, et ce genre de choses. Choses qui pour certaines sont fournies avec le C11, mais ça n'aurait été "qu'une simple mise à jour" du code, avec de probables oublis réguliers (je n'ose imaginer la taille en LOC du projet!). Ici, le changement de langage va probablement impliquer un travail avec plus d'attention, qui pourrait permettre d'intégrer les avancées de C11 et C++11, et la, je suis certain qu'on aura des améliorations de performances.

Quant à la question du fait que ça empêcherait que ça fonctionne sur certaines architecture d'utiliser du code trop récent: je suis sûr à 95% qu'ils utilisent GCC pour compiler, du coup, ça implique qu'au moins un compilateur pourra compiler leur compilateur: le leur. Et donc, il pourra le faire sur toutes les plate-formes déjà supportées, non?

[edit]
J'ai vu juste, le gain qu'ils semblent attendre est effectivement axé sur la maintenance:

Background

What matters for GCC going forward is that it continue to be comprehensible and maintainable. That is a struggle that GCC has faced for its entire existence as a free software project. It is certainly true that using C++ unwisely can make that struggle more difficult. But this issue is not qualitatively different from the issues we face today.

Whether we use C or C++, we need to try to ensure that interfaces are easy to understand, that the code is reasonably modular, that the internal documentation corresponds to the code, that it is possible for new developers to write new passes and to fix bugs. Those are the important issues for us to consider. The C++ features which are not present in C -- features which are well documented in many books and many web sites -- are not an important issue.

For additional background information on this effort and its scope, please check out http://airs.com/ian/cxx-slides.pdf .

==>
Ce qui importe est que GCC reste compréhensible et maintenable[...]que nous utilisions C ou C++ nous devons nous assurer que les interfaces soient simples à comprendre, que le code soit raisonnablement modulaire, que la documentation interne corresponde au code, qu'il soit possible pour de nouveaux développeurs d'écrire de nouvelles passes et de corriger les bugs.

==>
Les fonctionnalités de C++ qui ne sont pas présentes en C -- fonctionnalités qui sont très bien documentées [...] -- ne sont pas importantes.

Du coup, j'en déduis qu'ils ne vont pas utiliser les fonctionnalités des nouveaux standards, ce qui répond(?) à ma question précédente.

[jmnicolas]

GCC réimplémenté en C++ ?

Les signes avant-coureurs sont bien là, les Mayas avaient raison : 2012 c'est la fin du monde

[gbdivers]

Pourquoi pas ? Mais perso, je suis plus intéressé par les nouvelles fonctionnalités qui seront implémentées : support complet de la norme (il doit manquer des choses je crois), proposition de nouvelles fonctionnalités pour le prochaine TR ou C++1x (SG1 et SG5 en particulier), amélioration des temps de compilation et des messages d'erreurs de template (clang en mieux). Si cette évolution permet de faciliter l'ajout de ces fonctionnalités, je prend

[Freem]

Envoyé par jmnicolas

GCC réimplémenté en C++ ?

Les signes avant-coureurs sont bien là, les Mayas avaient raison : 2012 c'est la fin du monde

Post très argumenté s'il en est.

J'ai lu un peu plus en détail le contenu de cette source et des documents qui y sont cités...

D'ailleurs, j'ai l'impression que le titre de cet article fait dans la sensation.

Le C n'est pas abandonné, pas totalement du moins, puisque "GCC generates temporary garbage which is only freed by ggc collect", GCC étant écrit en C. D'un autre côté "C++ permits reference counting smart pointers." et donc "We may want to use a mixture of reference counting and garbage collection."

En gros, le C++ va être utilisé, oui, mais uniquement quand il présente un avantage par rapport au C.
Basiquement, je suppose qu'ils ne vont pas utiliser les stream (et je ne pourrait leur en vouloir, personnellement je ne les apprécie pas du tout)

Pendant que j'y suis, j'ai juste adoré le PDF que j'ai cité, notamment un passage:

The FSF doesn’t like it!
◮ The FSF is not writing the code.

Je salue la justesse du raisonnement de l'auteur

Ce PDF attaque aussi d'autres idées reçues, telles que:
_ C++ trop lent
_ C++ trop compliqué
_ C++ pas portable
Et surtout, les exemples de code sont très instructifs.

Bon... n'empêche, il précise aussi que ce n'est pas la panacée, juste une amélioration.
Pour le coup, je me demande ce qu'en pense ce cher Linus.

Au sujet de la source elle-même, il semble qu'ils attendent un véritable gain en mémoire, et donc en durée de compilation.
Gain dû au fait que le C++ aie des destructeurs, et que donc, dès que l'on sors d'une portée, on libère de la mémoire. La ou l'implémentation C utilisais un gargage collector, une implémentation C++ économise la mémoire grâce à la RAII.
Quand je vois qu'en 2-3 threads je monte vite à 1Gio, qui est la limite de mon netbook, c'est plutôt une bonne nouvelle qu'ils espèrent ce type d'amélioration.
Divers autres passages parlent aussi de diminution du nombre de cast dynamiques, et donc d'optimisation de la vitesse également.

En tout cas, je pense que ce projet permettra de montrer clairement si oui ou non, C++ est une amélioration par rapport au C, et dans quelle mesure l'efficacité est améliorée.
A noter tout de même, qu'ils ne semblent pas vouloir tout convertir, mais juste quelques modules.

En tout cas, ils n'y parlent pas d'implémenter les fonctionnalités restantes des standards.
Ce qui paraît logique: je pense qu'ils vont commencer par migrer les parties stables, pour faciliter le travail.
Migrer une partie stable, ça veut dire qu'il est possible qu'il existe des tests unitaires pour cette partie, donc que le code migré sera bien testé, plutôt que de devoir à la fois lutter contre les bugs de migration et ceux d'implémentation.
Donc, pour moi, a court et moyen terme, on ne peux s'attendre qu'a une amélioration en terme de mémoire et de vitesse à la compilation (pour les raisons déjà évoquées)

[gbdivers]

Pour le coup, je me demande ce qu'en pense ce cher Linus.

On connait déjà sa position sur le C++ et ce n'est pas non plus lui qui écrit le code de gcc

Pour les idées reçues, le pdf date de 2008. Si les gens ont encore ce genre d'idées 4 ans après, faudrait peut être qu'ils se remettent en question

Dans http://gcc.gnu.org/gcc-4.8/changes.html :

GCC now uses C++ as its implementation language. This means that to build GCC from sources, you will need a C++ compiler that understands C++ 2003.

Donc pas de C++11

[Freem]

Envoyé par gbdivers

On connait déjà sa position sur le C++ et ce n'est pas non plus lui qui écrit le code de gcc

Ce n'était pas une phrase sérieuse en même temps

Envoyé par gbdivers

Pour les idées reçues, le pdf date de 2008. Si les gens ont encore ce genre d'idées 4 ans après, faudrait peut être qu'ils se remettent en question

En même temps, si j'avais confiance dans la capacité des gens (y compris moi-même hein) à se remettre en question ou à changer d'idées quand la raison l'impose, je pense que j'aurai préféré un métier avec plus de contact humain. Le fait que mon contact se limite à des rapports de bugs et des demandes de fonctionnalités me suffit amplement.

Envoyé par gbdivers

Dans http://gcc.gnu.org/gcc-4.8/changes.html :

Donc pas de C++11

La source indique également que le compilateur version N doit pouvoir être compilée par le compilateur version N-1, donc effectivement, C++11 ne sera pas utilisé de sitôt.
Je suppose qu'il faudrait déjà qu'il soit complètement implémenté et surtout débogué pour ça... Un compilateur qui utilise une techno qui n'est pas nécessairement stable risquerait d'introduire pas mal de bugs dans les binaires par effet de cascade.
Je suis tout de même assez content de voir qu'ils n'y vont pas comme des brutes. En tout cas, je me demande combien de temps ça va mettre pour qu'ils sortent un truc en bêta, et je me demande quel sera le résultat niveau améliorations de perfs.

D'ailleurs, vu que mingw est basé sur GCC, peut-être qu'on aura aussi des améliorations de ce côté-ci? Histoire de pouvoir concurrencer un peu VS, ce serait pas mal.

[PINGOUIN_GEANT]

Envoyé par gbdivers

Donc pas de C++11

Tu posais une question sur les nouvelles fonctionnalités supportées par gcc, mais il me semble que la version de langage pour développer gcc est quelque chose différent de l'actuel support d'un langage. J'ai peut-être raté quelque chose.
Passer de C a C++, qu'est ce que cela veut dire sur l'optimisation des 2 versions de gcc pour compiler du C et du C++ ? Est-ce que la variante pour compiler du C++ est maintenant plus mature que la variante pour le C ? A-t-on des indices pour le savoir (aussi en comparaison des variantes pour Java, FORTRAN 95, etc.) ?

[guillaume07]

c'est pas trop tôt !!

[gbdivers]

Envoyé par Freem

La source indique également que le compilateur version N doit pouvoir être compilée par le compilateur version N-1, donc effectivement, C++11 ne sera pas utilisé de sitôt.

Je suppose que c'est le numéro de version mineur de gcc, j'espère qu'ils compilent pas gcc avec la version 3
Dans ce cas, la version N-1 (gcc 4.7) supporte déjà une très grande partie du C++11, donc ils pourraient l'utiliser sans problème pour gcc 4.8

Envoyé par PINGOUIN_GEANT

Tu posais une question sur les nouvelles fonctionnalités supportées par gcc, mais il me semble que la version de langage pour développer gcc est quelque chose différent de l'actuel support d'un langage. J'ai peut-être raté quelque chose.

Pas compris. On parle du langage pour écrire gcc et non du langage pris en charge par gcc

Envoyé par PINGOUIN_GEANT

Passer de C a C++, qu'est ce que cela veut dire sur l'optimisation des 2 versions de gcc pour compiler du C et du C++ ? Est-ce que la variante pour compiler du C++ est maintenant plus mature que la variante pour le C ? A-t-on des indices pour le savoir (aussi en comparaison des variantes pour Java, FORTRAN 95, etc.) ?

Il n'y a pas plusieurs variantes de gcc, il y a une version de gcc en cours de dev et la prise en charge des langages dépend : 1. de l'évolution des langages (le C et le C++ ont eu des nouvelles normes récentes) 2. de la disponibilité des équipes de dev
Bref, pas trop compris la question

[Freem]

Je pense aussi que c'est le numéro mineur, parce que sinon, la compilation qui met déjà 50 plombes quand on joue avec quantité de template mettrait probablement 50 siècles

Pour le reste, je suppose que PINGOUIN_GEANT demande si un compilateur GCC est écrit dans le langage qu'il est censé compiler... Mais en fait, je suis presque sûr de ne pas trop avoir compris non plus.

Mais bon...
GCC, pour ce que j'en sais, est conçu de façon modulaire, quand on écrit un compilateur GCC pour un nouveau langage, on écrit un nouveau module. Précédemment, GCC était écrit 100% en C, mais il semble qu'ils aient décidé de commencer à utiliser le langage C++ pour continuer certains modules.

Pour ce qui est de l'intérêt d'utiliser C++ au lieu de C, ce n'est pas tant une question de maturité du compilateur (puisqu'on pourrait vouloir compiler GCC avec VS, pour ce que j'en sais), mais de techniques utilisables dans les langages.
C++ offre plus de possibilités que C pour implémenter les choses, entres autres parce que C++ est multi-paradigme, alors que C n'en utilise qu'un.
Et, selon l'auteur du PDF que j'ai cité, C++ permet d'écrire du code plus lisible, et donc plus simple à maintenir, que s'il était écrit en C. Cette personne estime aussi que le gain de performance obtenu en écrivant en C est négligeable voire inexistant. Elle estime d'ailleurs que sur certains points, le C++ est plus performant.
Cette performance serait par exemple due au fait que, si je me souviens bien, le C nécessite de déclarer toutes les variables en début de fonction, contrairement au C++.
L'intérêt de ceci pour le C++, est que l'on peut par exemple écrire cela:

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
int main()
{
  //code divers
  {
     Foo f;
     //code exploitant f
  }
  // encore un peu de code
  {
     Bar b;
     // code exploitant b
  }
  //autre code divers
}

Alors qu'en C il eut fallut écrire:

Code :

1
2
3
4
5
6
7
8
9
10
 
int main()
{
  Foo f;
  Bar b;
  //code divers
  //code exploitant f
  //code exploitant b
  //autre code divers
}

La différence provenant du fait que dans le code C++ la mémoire utilisée par f n'est pas allouée avant que f ne serve, et est vidée quand il ne sert plus à rien. Idem pour b. Selon le programme, ces trucs peuvent prendre plus ou moins de mémoire, entres autres.

Autre point sur lequel C++ est meilleur en terme de performance, c'est le support de la RTTI, qui, bien que lourde, est plus rapide que d'effectuer deux fois la conversion d'un type à un sous-type, afin de vérifier que le type est le bon.

Et il semble que ces technologies aient un potentiel non négligeable d'optimisation de GCC, dont la réputation de lenteur et de lourdeur doit être connue de la plupart des gens ici. (je ne sais pas si elle est avérée, je ne me suis jamais amusé à faire de comparaison réelle, mais c'est à coup sûr un reproche que l'on voit souvent sur le web)

j'ai lu le PDF et a la page 3 il dit

Code :

1
2
3
4
typedef std::vector<struct loop, gcallocator> loopvec;
loopvec *superloops;
superloops->reserve (depth);
superloops[depth];

un pointeur sur un vecteur... c'est peut etre pas si bien barré que ca

[Tryph]

Envoyé par Freem

[...]je n'ai jamais entendu parler d'outils qui extraient la structure d'un projet écrit en langage non objet.

Doxygen est capable d'analyser du code C, de décrire les structures, de les lier entre elles et même de faire des diagrammes pour synthétiser tout ça.

bon c'est pas de l'UML, mais c'est déjà bien pratique.

[gbdivers]

@screetch
Aie, en effet, si on ce genre de code, ça fait mal

Envoyé par Freem

Et il semble que ces technologies aient un potentiel non négligeable d'optimisation de GCC, dont la réputation de lenteur et de lourdeur doit être connue de la plupart des gens ici. (je ne sais pas si elle est avérée, je ne me suis jamais amusé à faire de comparaison réelle, mais c'est à coup sûr un reproche que l'on voit souvent sur le web)

Je crois pas que l'optimisation de gcc (qui en a effectivement bien besoin) puisse venir de quelques fonctionnalités du langage C++
Le problème de gcc est plus profond, c'est un problème d'algorithmie (en particulier, on lui reproche de parser plusieurs fois les fichiers d'en-tête et de ne pas garder en mémoire ce qu'il a déjà analysé, d'où la perte de temps)
A voir si c'est toujours le cas. Mais si oui, on pourrait tout réécrire en assembleur (voir en langage machine ou en micro code processeur) que cela ne changerait rien

Très clairement pour moi, si ça avait été un débutant qui proposerait de recoder gcc en C++ pour diminuer les temps de compilation, je lui aurait répondu que c'est de la premature optimization, qu'il teste d'abord le temps passer dans les algos et dans les appels de fonctions et ne réécrire que s'il montre que c'est nécessaire.
Bon mais là, c'est les devs de gcc, je vais rien dire...

Pour moi, le principal intérêt reste le gain en évolutivité, qui lui permettra d'implémenter plus facilement de nouvelles méthodes de compilation qui vont faire gagner du temps (et l'ajout des nouvelles fonctionnalités aux langages, ce qui est encore mieux)

[rt15]

Envoyé par Freem

Cette performance serait par exemple due au fait que, si je me souviens bien, le C nécessite de déclarer toutes les variables en début de fonction, contrairement au C++.
L'intérêt de ceci pour le C++, est que l'on peut par exemple écrire cela:

Code :

Alors qu'en C il eut fallut écrire:

Code :

La différence provenant du fait que dans le code C++ la mémoire utilisée par f n'est pas allouée avant que f ne serve, et est vidée quand il ne sert plus à rien. Idem pour b. Selon le programme, ces trucs peuvent prendre plus ou moins de mémoire, entres autres.

Ce code montre aussi beaucoup plus pourquoi le C++ peut être plus lent que le C.

Mais parlons donc mémoire tout d'abord. Déjà, le mot "allocation", pour des variables locales ferais presque bondir certaines personnes, assez peu il est vrai. Elle réservent ce terme aux allocations dynamiques, à base de malloc ou new par exemple. Pour une variable locales, ces personnes parlent plus de "réservation dans la pile".
Car ces deux méthode pour obtenir de la mémoire sont très différentes. Dans un cas, on ne change que la valeur d'un registre du processeur pour déplacer la tête de pile, dans l'autre on appelle toute une machinerie qui gère un tas.
(C'est a nuancer car il y a toute une gestion de la pile par l'OS derrière : taille initiale, taille maximale, ajout de pages lors des défauts de pages. Mais dans la grande majorité des cas, la pile est prête).

Bref, que représente donc l'"allocation" de f et b dans le code C ci-dessus ? Une misérable instruction sub esp, XXX ou XXX correspond (Au moins à peu près, dépend de la gestion de l'alignement) à la taille d'une instance de Foo + une instance de Bar. Il y aurait 200 variables, il n'y aurait quand même qu'une instruction. Pour un coût à l'exécution quasi nul. Effectivement, il y a de la mémoire consommée, mais dans la pile donc c'est carrément anecdotique -> Par défaut, la taille max de la pile est de 1 ou 2 Mo (Précisée dans le .exe par le linker). Malgré ça, pour faire un dépassement de pile, il faut souvent mettre un bon gros tableau en variable locale, ou faire un récursivité qui ne s'arrête pas.

Bref, le code C ci-dessus ne coute quasi rien en CPU et pas grand chose en mémoire.

Pouvoir donner une portée en interne aux variables réduirait potentiellement un peu la consommation mémoire, mais ralentirait l'exécution (1 sub esp, XXX par portée, et pourquoi pas un add esp à la fin des portées).

En fait, pouvoir limiter la portée des variables comme ci-dessus sert surtout au C++. Non pas pour limiter la consommation mémoire, d'ailleurs, mais la consommation CPU !

Et c'est là tout le piège du C++ en ce qui concerne les performances !

Le code C ci-dessus est quasi instantané. Il ne PEUT PAS prendre de temps.
Mais le code C++ ci-dessus prend un temps... Inconnu ! Peut être plusieurs secondes ! Peut être des heures... Avec juste ce bout de code, on ne sait pas ce que le processeur va devoir exécuter.

Tout dépend en effet des constructeurs de Foo et Bar ! Et c'est pour ça que la portée limitée est bien plus intéressante en C++ qu'en C, par exemple pour ne pas exécuter de constructeurs d'instances dont on a pas besoin.

Et c'est une des raisons pour laquelle une implémentation en C est souvent plus rapide. Car le C colle au comportement du processeur, là ou le C++ permet d'ajouter de l'abstraction qui nous cache des instructions.

[gbdivers]

C'est quoi cette argumentation ??? Surtout la dernière phrase

Si tes variables f ou b ont besoin d'être initialisé, que ce soit dans le constructeur des classes (C++) ou dans une fonction d'initialisation (C), ça sera pareil en terme de temps d’exécution. Si tu n'as pas besoin de les initialiser, ça te coûtera pas plus en C++ qu'en C.
De plus, en C++ comme en C, les variables seront sur la pile, il n'y aura pas de différence sur le code généré et les performances


Il faudrait comprendre un jour que le C++ et le C ont les mêmes performances pour les mêmes fonctionnalités (et les fonctionnalités du C++ qui n'existent pas en C, comme par exemple les fonctions virtuelles, nécessiteront du code supplémentaire en C, ce qui donnera les mêmes performances au final)

[rt15]

Effectivement, le message est assez fin, et est presque plus philosophique que technique. Mais prenons par exemple le code C++ suivant :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <vector>
 
#define VECTOR_SIZE 10000000
 
int main()
{
  std::vector<int> my_vector(VECTOR_SIZE);
 
  for (int i = 0; i < VECTOR_SIZE; i++)
    my_vector[i] = i;
 
  return 0;
}

On construit un vecteur de int avec chaque élément qui est égale à son indice.
Bien sûr, un vector n'est pas très adapté, mais c'est pour l'exemple.

La question est : combien de fois les éléments du vecteurs sont ils parcourus et affectés ?

Ne lisez pas la suite avant de vous être posé la question !

On comprend bien qu'un seul parcourt devrait suffire pour réaliser cette tâche. Pourtant le code ci-dessus en fait deux. Les éléments sont initialisés à zéro dans le constructeur, et ce quel que soit le niveau d'optimisation donné au compilo.

Encore une fois, ce n'est pas tranchant comme argument. Mais en lisant le code, on a quand même bien l'impression de voire une complexité en n, pas en 2n. Tout ça à cause d'un constructeur qui exécute du code dans notre dos, sans que ça ait d'intérêt pour nous. C'est donc quand même très vite fait d'écrire un code deux fois plus lent qu'il ne devrait, sans que ça saute aux yeux.

Pour en revenir à la philosophie, on peut remarquer que ce genre de "détail" à une fâcheuse tendance à être plus repéré par des développeurs C que des développeur C++. Nan mais franchement, vous imagineriez une double initialisation d'une liste dans le noyau linux ? Ça ferait pas très sérieux quand même...

[gbdivers]

Ok donc ça confirme ce que je dis

Envoyé par gbdivers

Il faudrait comprendre un jour que le C++ et le C ont les mêmes performances pour les mêmes fonctionnalités (et les fonctionnalités du C++ qui n'existent pas en C, comme par exemple les fonctions virtuelles, nécessiteront du code supplémentaire en C, ce qui donnera les mêmes performances au final)

Là tu compares avec une classe qui encapsule un tableau avec RAII en C++ et un tableau sans initialisation en C. Deux fonctionnalités différentes, deux résultats différents.
En C++, tu n'as pas en effet de séparation allocation et initialisation pour un vector, donc on pourrait oublier (ou ne pas savoir) que l'on parcours deux fois le tableau dans ton code. Mais :
- on trouve plus souvent l'erreur d'utilisation d'un tableau C non initialisé qu'un problème de performance d'un tableau C++
- on trouve plus souvent des problèmes d'algorithme sur la gestion des ressources que des problèmes de performance d'un tableau C++ (typiquement des tableaux qui sont alloué et libéré plusieurs fois dans un algo)
- la différence de temps d'allocation d'un tableau C ou C++ est en général ridicule sur la durée total d'un programme (si on s'amuse pas à allouer et libérer les tableaux tout le temps)
- le C++ autorise d'autres types de tableaux qui ne présente pas la sécurité du RAII (new[], malloc) ou de fournir d'autres allocateurs

Bien sûr, un vector n'est pas très adapté, mais c'est pour l'exemple.

C'est claire qu'en prenant des outils non adaptés, on arrive aux conclusions que l'on veut

de voire une complexité en n, pas en 2n

Jusqu'au dernière nouvelle, O(n) = O(2n)

C'est donc quand même très vite fait d'écrire un code deux fois plus lent qu'il ne devrait, sans que ça saute aux yeux.

Tu l'as testé ton code pour dire qu'il est deux fois plus lent ?


Bref, ton argument est basé sur une méconnaissance du C++

HS :

Effectivement, le message est assez fin, et est presque plus philosophique que technique.

Merci de ne pas prendre les gens de haut

[transgohan]

Envoyé par gbdivers

Jusqu'au dernière nouvelle, O(n) = O(2n)

Seulement après simplification (qu'on effectue dans 99% des cas je te l'accorde, mais si on veut parler bien, parlons bien !).
Certains chercheurs travaillent dans des domaines où ils ne peuvent se permettre de dire que O(10n) est négligeable et équivalent à O(n).

mathematiquement, O(2n) est equivalent a O(n)
programmatiquement, le code philosophique de rt15 n'est pas equivalent a son pendant vector, le code equivalent est:

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <vector>
 
#define VECTOR_SIZE 10000000
 
int main()
{
  std::vector<int> my_vector;
  my_vector.reserve(VECTOR_SIZE);
 
  for (int i = 0; i < VECTOR_SIZE; i++)
    my_vector.push_back(i);
 
  return 0;
}

ou il n'y a qu'un seul parcours (le O(1N) philosophique)
pour en revenir au sujet sur GCC, nul doute que les erreurs sur la page 3 du PDF sont simplement de l'inattention (un copie/colle vite fait) puisque il cumule 4 erreurs en 3 lignes (1 - pointeur sur vecteur, 2 - operateur [] sur le pointeur et non sur le vecteur, 3 - acces hors borne puisque il y a depth elements donc le dernier est depth-1, 4 - reserve ne grandit pas le vecteur, donc il y a toujours 0 element dans le vecteur).

meme un programmeur C qui n'a jamais code C++ aurait fait mieux, je suppose donc une simple slide fait a la va-vite.