GCC réimplémenté en C++

[Hibernatus34]

Envoyé par Freem

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.

Pardon, mais c'est pas pertinent du tout à mes yeux, la seule différence entre ces 2 codes est la portée des variables, mais le code compilé sera probablement le même, puisque l'allocation de toutes les variables d'une fonction se fait par une seule soustraction. Une variable peut être déclarée dans un while, le compilo ne sera pas assez stupide pour empiler/dépiler à chaque itération. La seule différence viendrait de la présence de constructeurs/destructeurs (c'est d'ailleurs la raison pour laquelle C++ devait permettre ces déclarations n'importe où), mais évidemment le C n'en a pas, donc il n'est pas question de comparer ça. Ce que fait le constructeur en C++, une fonction C peut le faire... n'importe où également.

(notez que je préfère de très loin le C++ au C)

screetch : Le code n'est pas 100% équivalent à un array (était-ce le but ?), parce qu'on incrémente le membre size du vector à chaque itération, ce qu'on ne ferait pas pour un array Perso je m'en fous

[rt15]

Pour le débat O(2n) est equivalent a O(n), c'est vrai pour les maths.
Maintenant, si les sprinters se mettaient à courir le 100m en 20 secondes, me semble que la différence vous sauterait aux yeux, non ? Un programme qui deviens deux fois plus lent, ça pique en général.

Pour ce qui est de l'utilisation de "reserve", en théorie c'est bien, ça ramène probablement à un parcourt de tableau... Sauf que compilé avec g++ (En -O2 ou -O3), le code avec reserve met un temps tout à fait similaire à mon code. Les deux mettant à peu près deux fois le temps passé sur un parcourt unique...

A vérifier, mais je suppose que c'est dû au fait que push_back a plus de boulot à faire que l'opérateur []. Bilan la complexité a beau être n, l'opération réalisée est deux fois plus complexe (Mise à jour de la size du vecteur probable par exemple).

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <vector>
#include <iostream>
#include <windows.h>
 
using namespace std;
 
#define VECTOR_SIZE 20000000
 
int array[VECTOR_SIZE];
 
void constructor()
{
  vector<int> my_vector(VECTOR_SIZE);
 
  for (int i = 0; i < VECTOR_SIZE; i++)
    my_vector[i] = i;
}
 
void browse()
{
  for (int i = 0; i < VECTOR_SIZE; i++)
    array[i] = i;
}
 
void reserve()
{
  std::vector<int> my_vector;
  my_vector.reserve(VECTOR_SIZE);
 
  for (int i = 0; i < VECTOR_SIZE; i++)
    my_vector.push_back(i);
}
 
int main()
{
  LARGE_INTEGER starting;
  LARGE_INTEGER end;
 
  for (int i = 0; i < 10; i++)
  {
    QueryPerformanceCounter(&starting);
    constructor();
    QueryPerformanceCounter(&end);
    cout << end.QuadPart - starting.QuadPart << endl;
 
    QueryPerformanceCounter(&starting);
    reserve();
    QueryPerformanceCounter(&end);
    cout << end.QuadPart - starting.QuadPart << endl;
 
    QueryPerformanceCounter(&starting);
    browse();
    QueryPerformanceCounter(&end);
    cout << end.QuadPart - starting.QuadPart << endl;
 
    cout << endl;
  }
 
  return 0;
}

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
233871239
232111922
161693399
 
236877116
232803109
115653265
 
237220459
234170832
114499161
 
237944784
237114185
115160248
 
239684284
233381540
114996329
 
238357294
232007671
114847537
 
246558018
231487116
120612464
 
267180473
244786381
103820297
 
272322960
238285341
116277903
 
243198732
232527302
115246334

Quand je dis "fin", c'est pour dire que c'est petit voire négligeable (En théorie on peut même tout à fait dire que les perfs C vs C++ sont comparables), pas pour dire qu'il faut être un super héro pour voir la différence.

Mais c'est juste que quand des gens commencent à écrire que passer du code C en C++ peut, notamment, améliorer les perfs... C'est comme dire que le java peut être plus rapide que l'assembleur. C'est vrai (Encore que je n'ai jamais eu la preuve montre en main ), mais c'est beaucoup plus rare que l'inverse.

[Hibernatus34]

rt15:
1. Le fait de mettre 2 fois plus de temps à alimenter un tableau est négligeable, le fait de pouvoir accéder à ce tableau aussi efficacement qu'en C, une fois ce tableau alimenté est beaucoup plus important pour la plupart des algorithmes. Tu ne développeras pas de programmes plus rapides avec des raisonnements aussi limités.

2. Certaines optimisations ne sont envisageables qu'à un certain niveau d'abstraction. Pour prendre un exemple qui te parlera je pense, imagine programmer tout Photoshop en assembleur en entrelaçant à la main les instructions pour bénéficier des fameuses optims du Pentium... Heureusement qu'il existe le compilo C capable de le faire à ta place.

L'exemple typique du C++ plus rapide que le C, c'est le qsort Vs. std::sort.

Envoyé par rt15

...

c'est gentil d'avoir retirer l'allocation dynamique du tableau pour favoriser le C.
en faisant l'allocation dynamique j'obtiens des resultats un peu plus proches deja.....

c'est deja pas facile de comparer du C et du C++, mais prendre une loupe pour regarder un element sans considerer un programme entier c'est tres contre-productif.

De mon experience, les deux ont la meme vitesse; le C++ perd par moment mais gagne par d'autres, et regarder individuellement c'est contre productif.

C'est comme mettre un exemple de 4 lignes en java qui va plus vite qu'en C++ sans regarder que eclipse qui est une vrai appli java cette fois, rame comme pas permis.

En plus, si on cherche bien, on trouve toujours des trucs mieux ou moins bien (plus ou moins rapide), ca n'a vraiment aucun interet...

[rt15]

Dommage que le code de photoshop ne soit pas libre.
D'après le web, photoshop utilise ou utilisait pas mal SSE2.
SSE2 n'est pas utilisable efficacement en C, tout du moins pas sans une bibliothèque. Une bibliothèque écrite partiellement en assembleur.
L'alternative est d'utiliser directement l'assembleur.

A ma connaissance, aucun compilateur C ou C++ à l'heure actuelle n'est tout simplement capable d'optimiser des calculs efficacement en utilisant SSE. Car il faut une compréhension profonde des dits calculs pour pouvoir les rendre parallèles et adaptés à SSE. Les compilos peuvent utiliser SSE pour des "détails", fonctions built-in ou autre, mais ils ne vont pas transformer nos propre code de calcul en du jolie code machine exploitant bien SSE.

Photoshop est précisément dans le cas où une optimisation très travaillée a été mise en place. Car pour certaines partie du code, la performance est critique. Et ils ont fait quoi ? Ils ont fait du C++ ???? Non, ils ont certainement fait de l'assembleur, ou utiliser une bibliothèque faite en assembleur.

Pour optimiser, on se rapproche de la machine. C++ -> C. C -> ASM. On ne fait pas du haut niveau. Ça marchera seulement quand les compilos seront plus intelligent que les hommes.

Merci pour qsort, vs sort, je vais voire ça.

[edit]
Mon code C++ ci-dessus n'est pas là pour comparer les temps C vs C++, surtout que c'est que du C++ lol. C'est plus pour comparer reserver et le constructeur et se donner une idée de ce que ça donne par rapport à un parcourt simple.

pour optimiser, on s'approche de la machine en C comme ne C++ comme en assembly, ca passe en premier lieu par une grosse optimisation du cache memoire qui est le bottleneck de toute application, surtout photoshop (on comprend bien que photoshop, c'est le processing d'image hein qu'il faut optimiser, pas l'interface utilisateur)

et on utilise SSE en C++ avec les "intrinsic", et on encapsule le tout dans des classes C++. Eh ouais, c'est comme ca qu'on fait, on ecrit pas de l'assembleur.

j'ai travaille sur d'autres codes ou la performance etait critique, il y avait pas une goutte d'assembleur, c'etait du C++ avec des intrinsic, et une tres tres grosse passe pour faire du traitement par batch (qui n'est as contraire au C++ mais la le C++ n'est pas forcement l'outil le plus adapte)

la meilleure preuve que photoshop ne doit pas contenir d'assembleur, c'est que sous visual studio en configuration 64bits on a plus le droit a l'assembleur.

[Hibernatus34]

Je suis d'accord rt15. Mais justement, si on peut combiner plusieurs langages c'est idéal.
L'assembleur tu l'utiliseras pour du code court et exécuté à haute fréquence.
Le C++ permet de faire de l'assembleur inline, mais aussi du C inline d'une certaine manière.

Et je suis sûr qu'un développeur avisé sur les questions de bas niveau tel que toi, probablement adepte aussi de code explicite et simple, ferait un très bon développeur C++, juste différent des développeurs C++ qui aiment développer des templates monstrueux, ou ceux qui veulent faire du Java en C++ etc. A chacun sa manière de profiter du C++, mais refuser en bloc le C++ n'a pas de sens.

PS. screetch : asm inline ou intrinsics, franchement quand tu vois la tête d'un code bourré d'intrinsics SSE2 c'est kif-kif
Et l'assembleur, même s'il est pas inline peut être linké à un projet C++, c'est pas tellement le problème (j'espère quand même que Microsoft va rétablir l'inline )

[grim7reaper]

Envoyé par screetch

programmatiquement, le code philosophique de rt15 n'est pas equivalent a son pendant vector, le code equivalent est:

Code :

Le véritable code C++ équivalent au code de rt15 serait l’utilisation de std::array.
Son code C utilise un tableau statique, le std::vector a une sémantique de tableau dynamique (avec ce que ça implique comme surcoût). Donc la comparaison est biaisée.
D’ailleurs, en utilisant std::array il n’y a pas de différence de perf’ entre le C et le C++ sur cet exemple (qui vaut ce qu’il vaut).

[Freem]

Envoyé par Hibernatus34

Je suis d'accord rt15. Mais justement, si on peut combiner plusieurs langages c'est idéal.
L'assembleur tu l'utiliseras pour du code court et exécuté à haute fréquence.
Le C++ permet de faire de l'assembleur inline, mais aussi du C inline d'une certaine manière.

Et je suis sûr qu'un développeur avisé sur les questions de bas niveau tel que toi, probablement adepte aussi de code explicite et simple, ferait un très bon développeur C++, juste différent des développeurs C++ qui aiment développer des templates monstrueux, ou ceux qui veulent faire du Java en C++ etc. A chacun sa manière de profiter du C++, mais refuser en bloc le C++ n'a pas de sens.

PS. screetch : asm inline ou intrinsics, franchement quand tu vois la tête d'un code bourré d'intrinsics SSE2 c'est kif-kif
Et l'assembleur, même s'il est pas inline peut être linké à un projet C++, c'est pas tellement le problème (j'espère quand même que Microsoft va rétablir l'inline )

Je n'ai pas l'impression qu'il refuse le C++ en bloc.
Il argumentait juste sur le fait que j'ai dit que le C++ pourrait optimiser le code, nuance.
Le souci ayant été que, comme lui avec son exemple du vector, j'aie pris un (très) mauvais exemple.

Personnellement, je pense que C et C++, bien utilisés, sont aussi rapides l'un que l'autre (C étant un sous-ensemble du langage C++, dans celui-ci).
0 différence, vu qu'au final, tous les langages natifs sont égaux face au code machine.
Le problème étant que, pour moi, et je crois ne pas être le seul à le penser, bien utiliser le C est plus complexe que bien utiliser le C++.

Par exemple, dans les documents de GCC, il est précisé qu'ils utilisent un garbage collector en C.
Bien.
Le problème des garbage collector, selon moi, c'est qu'ils ne libèrent pas la mémoire aussitôt qu'elle n'est plus nécessaire, contrairement à la RAII.
Sans compter que la mécanique interne du GC nécessite sûrement des variables, qui vont être modifiées par des calculs, ce qui consomme du temps processeur. Ensuite, le GC, si je ne suis pas dans le faux, va appeler la fonction qui permet de libérer l'objet en question.

Pourquoi avoir utilisé un GC?
Je pense que c'est parce que l'usage de la RAII est plus contraignant en C qu'en C++.
Niveau performance, il me semble évident que la RAII soit plus efficace dans l'absolu qu'un GC (mémoire libérée aussitôt => moins de swap et moins de changement de segment de données. Dans l'absolu, amélioration - faible pour les changement de segment - des perf. Et économie d'un mécanisme de GC, qui doit au final libérer quand même la mémoire, re amélioration probable des perf).

Le fait est qu'en C++ aussi, on peut avoir un GC. Mais que la RAII, est aussi nettement plus simple à utiliser en C++ qu'en C: pas besoin de penser tout le temps a appeler un faux destructeur ou un faux constructeur.

De ce changement de langage, ce qui va en résulter, c'est donc, pour moi, un changement naturel et progressif dans l'architecture du logiciel, qui devrait pouvoir permettre des améliorations de perf.

Effectivement, j'avais totalement tord en prenant le raccourcis C++ peut rendre le code plus rapide.
Mea culpa donc.

PS: je me permet tout de même de dire que l'exemple du vector m'a piqué les yeux, mais c'est de bonne guerre, mon exemple ayant aussi été mauvais: dans la pratique, je n'utilise pas le changement de scope de façon aussi laide, mais plutôt des fonctions, le compilo me les mettant je pense inline selon les options de compilation et la situation.
C'était pour l'exemple, mais il était très mauvais



Par rapport à votre débat "O(2n) est equivalent a O(n)" la réponse est très simple.
En maths, il ne me semble pas que équivalent soit égal. Donc, O(2n) équivaut toujours à O(n), mais O(2n) diffère de O(n). Me semble même me souvenir que les matheux ont un symbole spécial pour l'équivalence...
Mais bon, moi et les maths...

pourt les maths (et j'espere que ca clot le sujet car on comprend bien les intentions des uns et des autres)
la definition de O:

f est bornée, par le dessus, par g asymptotiquement
(à un facteur près)

la remarque importante, c'est "a un facteur pres". donc O(2n) = O(n) = O(5000n)
mais dans la plupart des cas si on a equivalence des O pour deux algorithmes (tous les deux en O(n) on cherchera a savoir par quel facteur.