Journal Recherche de valeur dans un tableau et l'écosystème des compilateurs C++

Posté par Julien Jorge (site web personnel) le 03 octobre 2021 à 22:37. Licence CC By‑SA.

Étiquettes :

oct.

2021

Bonjour 'nal,

GCC, Clang, MSVC, sont tous des compilateurs très performants, ayant de nombreuses heuristiques pour émettre des instructions terriblement efficaces, à défaut d'être optimales. De même pour ICC, le compilateur d'Intel, réputé pour enterrer tous les autres en termes de performance du code généré. On en parle pas beaucoup mais il est là. (Tiens, d'ailleurs, savais-tu qu'Intel migrait son compilateur vers LLVM ? Le nouveau compilateur se nomme ICX pour le C, et ICPX pour le C++.)

Il est de plus en plus difficile d'écrire de l'assembleur plus efficace que celui généré par un de ces compilateurs. Pour illustrer leurs performances, prenons par exemple cet algorithme qui cherche un entier dans un tableau, demi-finaliste dans la catégorie « Algorithme Le Plus Bête Qui Soit » aux championnat du monde d'algorithmes de Limoges en 2019 :

// Retourne la position de la première occurrence de k dans les n entiers
// pointés par v, ou n si la valeur n'y est pas.
size_t find_int_c(int k, const int* v, size_t n)
{
  for (size_t i = 0; i != n; ++i)
    if (v[i] == k)
      return i;

  return n;
}

Simple et direct, un bon vieil algorithme en C. Voyons un peu comment les compilateurs s'en sortent. Pour les comparer j'utilise Google Benchmark et je mesure la recherche du dernier élément d'un tableau de valeurs distinctes (i.e. je mesure le pire cas) pour des tailles jusqu'à 16 millions d'éléments. La machine qui fait tourner cela est un MacBook pro de 2014, avec un CPU 4 cœurs i5-3210M à 2.5 GHz. Le système est Ubuntu 21.04, GCC version 11.1, Clang version 12, ICC et ICPX version 2021.3.0. Les tests sont compilés avec -O3 -DNDEBUG bien entendu.

Sans surprise, les compilateurs sont tous aussi efficaces les uns que les autres. Il faut dire que l'algo n'est pas compliqué, ça doit fuser au niveau des heuristiques d'optimisation. Mais bon, nous sommes en 2021 et tu vas me dire : « qu'est-ce qui te prend d'écrire une boucle, tu te prends pour un programmeur oh ? » Allez, essayons de cacher cette boucle avec un algo idiomatique du C++ :

// Retourne la position de la première occurrence de k dans les n entiers
// pointés par v, ou n si la valeur n'y est pas.
size_t find_int_cpp(int k, const int* v, size_t n)
{
  return std::find(v, v + n, k) - v;
}

Je t'épargne la version ranges de ~~even more moderner~~ C++20 parce ça ne change rien aux performances. Observons juste que le fait de passer --std=c++20 au compilateur a multiplié le temps de compilation par 1,55 (sur une base de 1,35 secondes), contre un facteur de 1,17 pour C++17 et de 1,02 pour C++14. D'autre part, ICPC et ICPX 2021 ne gèrent pas le C++20.

Je relance le benchmark histoire de dire, mais bon on se doute bien que ça ne va rien changer.

Euh… bon, ben… C'est inattendu.

On voit deux choses ici : d'une part tout est beaucoup plus rapide qu'avec la boucle en C (note que l'axe des ordonnées est le même que sur le graphique précédent), d'autre part la version d'ICC se démarque en étant encore plus rapide que les autres. On parle d'une réduction du temps d'exécution de 35-40% pour les premiers, et 70-75% pour ICC.

Sur une bête boucle comme ici, nous pouvons facilement imaginer que le compilateur applique un bon vieux déroulage de boucle. Confirmons par exemple en testant huit entrées par itération :

// Retourne la position de la première occurrence de k dans les n entiers
// pointés par v, ou n si la valeur n'y est pas.
size_t find_int_c_unrolled_8(int k, const int* v, size_t n)
{
  size_t i = 0;

  for (; n - i >= 8; i += 8)
    {
      if (v[i] == k)
        return i;
      if (v[i + 1] == k)
        return i + 1;
      if (v[i + 2] == k)
        return i + 2;
      if (v[i + 3] == k)
        return i + 3;
      if (v[i + 4] == k)
        return i + 4;
      if (v[i + 5] == k)
        return i + 5;
      if (v[i + 6] == k)
        return i + 6;
      if (v[i + 7] == k)
        return i + 7;
    }

  for (; i != n; ++i)
    if (v[i] == k)
      return i;

  return n;
}

Ça a l'air de se valoir, mais bizarrement c'est quand même plus rapide que l'implémentation de std::find(). En fait on peut directement aller voir le code de libstdc++ pour constater qu'ils traitent quatre entrées du tableau à chaque itération. Observons aussi que ICPC est revenu au niveau des autres compilateurs, ce qui signifie qu'il y a quelque chose de particulier derrière std::find() chez lui.

As-tu une idée de ce que pourrait être cette particularité ? Retourne ton écran pour vérifier ta réponse : sǝןןǝı̣ɹoʇɔǝʌ suoı̣ʇɔnɹʇsuı̣,p ǝƃɐsn ʇı̣ɐɟ ƆԀƆI,p ()puı̣ɟ::pʇs uoı̣ʇɔuoɟ ɐן. Évidemment je n'ai pas accès au code de la bibliothèque standard utilisée par ICPC, alors je te propose cette implémentation qui fait usage du jeu d'instructions SSE2 :

// Retourne la position de la première occurrence de k dans les n entiers
// pointés par v, ou n si la valeur n'y est pas.
size_t find_int_sse2(int k, const int* v, size_t n)
{
  // Nous allons tester les valeurs de v quatre par quatre.

  // Cette instruction copie la valeur recherchée k dans chaque segment
  // de 32-bits d'un un registre de 128 bits. Si k…k représente les 32 bits
  // de k, le registre ressemble à ce qui suit:
  //
  // [ k…k | k…k | k…k | k…k ]
  //
  const __m128i needle = _mm_set1_epi32(k);

  // Là on réinterprète juste le pointeur v comme un pointeur vers des
  // vecteurs de 128 bits, comme ça on prendra les entiers quatre par
  // quatre. Et ouais, je caste à la C comme une brute.
  const __m128i* p = (const __m128i*)v;

  // Une division ! Est-ce que le compilateur émettra un décalage à la place ?
  const size_t iterations = n / 4;
  const size_t tail = n % 4;

  for (size_t i(0); i != iterations; ++i, ++p)
    {
      const __m128i haystack = *p;

      // Ceci compare les quatre valeurs 32 bits de needle (donc
      // quatre fois la valeur recherchée) avec quatre entiers pointés
      // par p, en un seul cycle. Tous les bits d'un segment de 32 bits
      // sont mis à un si les valeurs sur celui-ci sont égales.
      // L'opération ressemble à ceci :
      //
      //       [ k…k | k…k | k…k | k…k ]
      // cmpeq [ a…a | b…b | k…k | c…c ]
      //     = [ 0…0 | 0…0 | 1…1 | 0…0 ]
      //
      const __m128i mask = _mm_cmpeq_epi32(needle, haystack);

      // On ne peut pas directement comparer la valeur mask avec zéro
      // mais il existe une instruction qui va nous aider à tester les
      // bits de mask.

      // Cette instruction prend les bits de poids fort de chaque
      // segment de 8 bits d'un registre 128 bits et les copie dans les
      // bits de poids faible d'un entier (32-bits).
      //
      // Par conséquent, puisqu'il y a quatre fois 8 bits dans un
      // entier, si k a été trouvé dans haystack, nous devrions avoir un
      // 0b1111 dans eq. Autrement eq sera zéro. Autrement dit (les 16
      // bits de poids forts sont toujours nuls) :
      //
      // movemask                     [ 0…0 | 0…0 | 1…1 | 0…0 ]
      //        = 0000 0000 0000 0000  0000  0000  1111  0000
      //
      const uint32_t eq = _mm_movemask_epi8(mask);

      // Puisque nous avons de nouveau affaire à un scalaire, nous
      // pouvons le tester directement.
      if (eq == 0)
        continue;

      // Il ne reste plus qu'à trouver l'offset du premier bit de
      // poids faible égal à 1. Mon ordinateur ne gère pas l'instruction
      // tzcnt donc j'utilise l'équivalent des fonctions de GCC.
      const unsigned zero_bits_count = __builtin_ctz(eq);

      // Chaque groupe de 4 bits dans eq correspond à une valeur 32
      // bits dans mask, donc on divise par 4.
      return i * 4 + zero_bits_count / 4;
    }

  // On teste quand même les dernières valeurs du tableau à l'ancienne
  // au cas où le nombre d'éléments n'est pas un multiple de 4.
  for (size_t i(iterations * 4); i != n; ++i)
    if (v[i] == k)
      return i;

  return n;
}

Mesurons ça:

Et voilà, maintenant tous les compilateurs génèrent un code équivalent à l'implémentation de std::find() utilisée par ICC.

Conclusion

Cette aventure a été assez surprenante finalement. Tout à commencé alors que je m'entraînais à utiliser des intrinsics, et que je tentais de valider mon implémentation — tant du point de vue résultats que de perfs — avec le binaire produit par GCC pour la boucle C. Quelle surprise de voir mon code sortir le résultat quatre fois plus rapidement !

Au fond ce résultat me déçoit un peu. Cela fait plus de vingt ans que j'entends que le temps d'ingénierie coûte cher, qu'il vaut mieux acheter du CPU et de la mémoire, et que la loi de Moore fera le taf' ; et quasiment aussi longtemps que j'entends que les compilateurs « d'aujourd'hui » sont performants, etc. Pour au final constater que seul un compilateur sur les quatre me sort du code optimisé. Et encore, si je prends la version la plus moderne de ce compilateur, ICPX versus ICPC donc, je perds cette optimisation ! Juste pour le fun, je te mets un extrait de l'annonce d'Intel :

The latest Intel C/C++ compilers, using LLVM, deliver faster compiler times, better optimizations, enhanced standards support, and support for GPU and FPGA offloading.

Better.

Optimizations.

Du coup j'ai tendance à penser maintenant que ceux qui tiennent ce discours (« les compilateurs d'aujourd'hui sont performants etc. ») ont surtout la flemme de regarder comment leur code est traduit et répètent cette doctrine pour éviter d'avoir à se poser la question.

Évidemment il n'est pas question de tout optimiser, mais la vraie raison pour laquelle nous écrivons du code de haut niveau n'est pas que les compilateurs sont très performants ; c'est plutôt un compromis du temps de mise en œuvre. En d'autres termes, nous acceptons du code sous optimal au profit d'une écriture et d'une maintenance simplifiée.

Au passage, je suis aussi un peu déçu de voir toute la variété des compilateurs doucement s'éteindre au profit d'une seule implémentation, LLVM. J'ai l'impression de revoir l'effet Chrome : au début c'est tout frais, tout jeune et performant, ça met un coup de fouet à l'ancêtre (Firefox/GCC) et puis au final ça grossit, ça bouffe tout et il n'y a plus de choix (Internet Explorer est mort au profit de Edge, toute appli récente est codée en Electron, tout compilateur récent est basé sur LLVM).

Je ne dis pas que LLVM est aussi problématique que Chrome, il y a plein de chouettes outils qui viennent de LLVM (clang-format, clang-tidy, FileCheck…), mais de là à abandonner toute variété, personnalité, créativité, au profit d'un seul et unique modèle, c'est déprimant.

Pour lutter contre tout cela et garder le moral, je t'invite à mettre à l'épreuve les outils que tu utilises, à les confronter à d'autres outils et à ce que tu saurais faire de toi-même. Au final la décision sera probablement toujours « bah on va prendre X, c'est moins bien mais tout le monde l'utilise et ça sera vite intégré », parce quand il y a des sous ou de la popularité en jeu, c'est l'efficacité de production qui compte ; mais peut être qu'en s'intéressant aux détails on pourra petit à petit subrepticement pousser une culture de curiosité, de défi et d'optimisation même dans les processus les plus « bottom line ». Et puis même si ça ne change rien, on apprendra des choses ; et ça c'est cool :)

Le code du benchmark.

# -march

Posté par Clément V le 04 octobre 2021 à 00:53. Évalué à 5.

Je me demandais quelle était l'influence de -march=... pour ce genre d'algo. J'ai testé ton benchmark chez moi (i5-9600k) avec g++ seulement (la flemme d'installer d'autres compilateurs). Sans changer les options, je trouve des résultats similaires aux tiens sauf que benchmark_cpp est plus rapide que benchmark_c_unrolled.

Avec -march=native ou -march=skylake, benchmark_c devient aussi bon que benchmark_c_unrolled. benchmark_c_unrolled et benchmark_cpp ne bougent pas. benchmark_sse2 devient plus lent ! (plus lent que benchmark_cpp mais toujours plus rapide que benchmark_c_unrolled)

Avec -march=core2, benchmark_c est tout autant accéléré, benchmark_c_unrolled va encore un peu plus vite, benchmark_cpp et benchmark_sse2 sont aussi rapide que sans l'option.

Donc -march est bien important, mais g++ ne semble pas très bon pour les architectures récentes et sabote même l'algo sse2.
- [^] # Re: -march
  
  Posté par Julien Jorge (site web personnel) le 04 octobre 2021 à 07:51. Évalué à 2.
  
  Il me semble que par défaut GCC cible la plateforme hôte, comme si on passait -march=native. Chez moi si je mets ça, et même -mtune=native, les résultats ne changement pas. Par contre je ne peux pas utiliser -march=skylake puisque ça ne correspond pas à ma machine. Peut-être que cela active de l'AVX2, qui rendrait l'algo plus rapide que du SSE2 ? Auquel cas je me demande pourquoi il optimise pour AVX2 mais pas SSE2.
  - [^] # Re: -march
    
    Posté par Clément V le 04 octobre 2021 à 11:31. Évalué à 2.
    Il me semble que par défaut GCC cible la plateforme hôte, comme si on passait -march=native.
    
    Chez moi la valeur par défaut est x86-64 (amd64 avec extensions jusqu'à sse2 si j'ai bien compris).
    
    Mes résultats plus détaillés sont :
```
            c       c_unr   cpp     sse2
default     8.56    5.49    4.39    3.91
core2       5.42    5.16    4.38    3.89
sandybridge 5.45    5.51    4.34    3.93
haswell     5.42    5.47    4.35    3.89
broadwell   5.42    5.47    4.35    3.86
skylake     5.39    5.47    4.31    4.70
```
    Je regarde le code désassemblé avec objdump et je n'y comprends rien. Pour find_int_c le code machine est exactement le même entre default et core2, à partir de haswell add $0x1,%rcx est remplacé par inc %rcx mais ce n'est pas ce qui fait la différence. Pareil pour find_int_sse2, à partir de sandybridge les instructions SSE2 sont remplacées par leurs équivalents AVX, mais il n'y a aucune différence entre broadwell et skylake. Des idées sur ce qui peut se passer ?
    
    Pour la boucle déroulée sur core2, au moins je vois des différences : des instructions sont réordonnées par rapports aux autres architectures.
- [^] # Re: -march
  
  Posté par KuroLightning le 04 octobre 2021 à 11:33. Évalué à 2.
  
  Une autre option qui peut avoir de l'influence, c'est pour GCC frename-registers. D'expérience, dire au compilateur qu'il peut utiliser l'ensemble des registres [xyz]mm[0-9]+ permet d'obtenir des gains de perf significatifs.
  
  Par contre, je n'ai pas testé sur ce cas ci.

# Sans SSE

Posté par YBoy360 (site web personnel) le 04 octobre 2021 à 06:11. Évalué à 8.

Il faut utiliser objdump pour observer le code compilé, ensuite, il faut fournir la commande de compilation.

Sans forcer, je divise par 2.6 le temps de la boucle original (j'ai eu la flemme de calculer le résultat exacte).

size_t find_int_c2(const int k, const int* v, const size_t n)
{
      int index = 0;
      size_t i = 0;
      for (; i < n - 8;) {
        int r0 = v[i++] - k;
        index = r0 == 0 ? 1 : index;
        int r1 = v[i++] - k;
        index = r1 == 0 ? 2 & index : index;
        int r2 = v[i++] - k;
        index = r2 == 0 ? 4 & index : index;
        int r3 = v[i++] - k;
        index = r3 == 0 ? 8 & index : index;
        int r4 = v[i++] - k;
        index = r4 == 0 ? 16 & index : index;
        int r5 = v[i++] - k;
        index = r5 == 0 ? 32 & index : index;
        int r6 = v[i++] - k;
        index = r6 == 0 ? 64 & index : index;
        int r7 = v[i++] - k;
        index = r7 == 0 ? 128 & index : index;
        if (index != 0) i += n;
        __builtin_prefetch(v + i + 512, 0, 1);
    }

  return index != -1 ? i + index : n;
}

Voila l'idée, supprimer les Jumps. Je pense que ça peut s'améliorer d'un facteur 2 ou 3.

$ gcc -march=native -O3 -g test.c -o test.x
$ objdump -dS test.x
$ ./test.x 
C1 = 228117 (499999984), C2 = 85911 (999999993)

Le main:

int main() {
    int* tab = malloc(SIZE * 4);
    for (int i = 0; i < SIZE; i++) {
        tab[i] = i;
    }
    clock_t c1 = clock();
    size_t r1 = find_int_c(SIZE - 16, tab, SIZE);
    clock_t c1end = clock();

    clock_t c2 = clock();
    size_t r2 = find_int_c2(SIZE - 16, tab, SIZE);
    clock_t c2end = clock();

    printf("C1 = %ld (%ld), C2 = %ld (%ld)\n", c1end - c1, r1, c2end - c2, r2);
}

[^] # Re: Sans SSE

Posté par YBoy360 (site web personnel) le 04 octobre 2021 à 07:32. Évalué à 4.
Je viens de corriger la boucle, il est difficile d'éviter les jumps (dans le code ci-dessus, il aurait fallu utiliser "|" au lieu de "&").

J'ai également ajouté les options de compilation suggérées au-dessus, et le prefetch sur le premier algo :
```
$ gcc -march=native -funroll-all-loops -O3 -g test.c -o test.x
$ ./test.x 
C1 = 138643 (499999984), C2 = 89029 (499999984)
```
```
size_t find_int_c(int k, const int* v, size_t n)
{
  for (size_t i = 0; i != n; ++i) {
    if (v[i] == k) {
      return i;
    }
    __builtin_prefetch(v + i + 512, 0, 1);
  }
  return n;
}

size_t find_int_c2(const int k, const int* v, const size_t n) {
      int index = 0;
      size_t i = 0;
      for (; i < n - 8;) {
        index = 0;
        if (v[i] == k) index = 1;
        else if (v[i + 1] == k) index = 2;
        else if (v[i + 2] == k) index = 3;
        else if (v[i + 3] == k) index = 4;
        else if (v[i + 4] == k) index = 5;
        else if (v[i + 5] == k) index = 6;
        else if (v[i + 6] == k) index = 7;
        else if (v[i + 7] == k) index = 8;
        if (index != 0) i += n;
        i += 8;
        __builtin_prefetch(v + i + 512, 0, 1);
    }

    i -= n + 8;
    if (index == 0) return n;
    if (index == 1) return i;
    if (index == 2) return i + 1;
    if (index == 4) return i + 2;
    if (index == 8) return i + 3;
    if (index == 16) return i + 4;
    if (index == 32) return i + 5;
    if (index == 64) return i + 6;
    if (index == 128) return i + 7;
}
```
Les gains sont bien moins importants dans ce cas. On peut cela dit avoir envie d'éviter de dérouler toutes les boucles.. Puisque cela fait grossir la section code. Bref. On gagne quand même 40 % avec le déroulage manuel.
- [^] # Re: Sans SSE
  
  Posté par Julien Jorge (site web personnel) le 04 octobre 2021 à 08:26. Évalué à 3.
  
  Je pense qu'il reste un souci avec ton algo car il ne passe pas les tests que j'ai mis dans le benchmark. Je n'ai pas eu le temps d'approfondir mais il y a déjà la condition de la boucle qui ne gère pas les cas n < 8 (il y a underflow et on entre toujours dans la boucle).
  
  Par contre j'ai ajouté -funroll-all-loops et ça fait gagner sur tous les algos, ce qui est déjà pas mal :)
  - [^] # Re: Sans SSE
    
    Posté par YBoy360 (site web personnel) le 04 octobre 2021 à 09:11. Évalué à 1.
    
    Je n'ai pas fait le cas n < 8, j'ai considéré que la recherche se faisait sur un grand tableau.
    
    As-tu essayé avec le prefetch placé à la main ? même si ce n'est pas "conseillé", car lié au HW, pour les grands tableaux, même pour des accès contiguë, on y gagne.. Pour les accès aléatoire un peu complexe, calculer l'adresse à précharger peut être coûteux.
    
    Le combo SSE + prefetch doit être intéressant dans ton cas, puisque plus on optimise, plus le prefetch devrait agir, car son effet est constant.
    - [^] # Re: Sans SSE
      
      Posté par calandoa le 06 octobre 2021 à 14:51. Évalué à 3.
      
      Je confirme que find_int_c2() est bugué : comment index pourrait-il être égal à 2ⁿ alors qu'il est mis à n dans la boucle ?
      - [^] # Re: Sans SSE
        
        Posté par YBoy360 (site web personnel) le 08 octobre 2021 à 01:40. Évalué à 2.
        
        Oui, il faut ajouter le code pour les n non multiple de 8, j'aurais dû le préciser. Dans le main, n >> 8, n % 8 == 0, et k est positionné en fin de tableau. Normalement, on regarde d'abord les données, ensuite on fait un profile sur des benchmarks typiques, puis on envisage quoi optimiser. L'avantage de ces hypothèses, c'est que l'on sait ce que l'on test.
        
        Si k a de forte chance d'être présent dans le tableau (par exemple plus de 1/8 des valeurs sont k) ou que les tableaux sont très petits, il faut considérer d'autres méthodes, évidement.
        
        J'essaierai de comparer les résultats de ce main sur un M1 ou un Raspberry PI. Sur Intel, le remplacement des jumps par les cmov (conditional mov) ne semble pas si interesante que cela, car dans l'hypothèse "k a peu de chance d'être rencontré" rend la prédiction de branchement efficace (par rapport au cmov), puisque c'est toujour le même chemin qui est emprunté par le code.

[^] # Re: Sans SSE

Posté par gUI (Mastodon) le 04 octobre 2021 à 07:51. Évalué à 2.

Voila l'idée, supprimer les Jumps.

Est-ce que ça voudrait dire que sur ces jumps là la prédicition de branchement se vautre systématiquement ? Y aurait-il un moyen de l'aider manuellement ?

En théorie, la théorie et la pratique c'est pareil. En pratique c'est pas vrai.

[^] # Re: Sans SSE

Posté par Nicolas Boulay (site web personnel) le 04 octobre 2021 à 10:09. Évalué à 6.

C'est une erreur de croire ça. Les jumps se prédisent, pas les valeurs. Le seul cas ou virer les jumps est bien, c'est dans le cas ou la prédiction se vautre tout le temps (parsing JSON, par exemple).

De mémoire, la règle c'est "forward taken, backward not taken", si l'adresse n'est pas déjà connue. Ici, le test est toujours faux, donc la prédiction marche à fond.

Par contre, si vous voulez un code déroulage de boucle, il faut regarder le code RAID soft de Linux. Typiquement, il utilise V+=8 dans la boucle for et ensuite v[0] v[1] v[2]… dans le corps de boucle, l'usage de valeur fixe permet d'économiser des instructions.

"La première sécurité est la liberté"

[^] # Re: Sans SSE

Posté par YBoy360 (site web personnel) le 08 octobre 2021 à 01:56. Évalué à 2.

C'est ce que j'ai constaté (l'efficacité de la prédiction de branchement, dans le cas ou k n'est présent qu'une fois en fin de tableau), ça doit être lié aux architectures cependant.

Mais, même dans ce cas très favorable à la prédiction, le temps mis est pratiquement égal à la version cmov. Donc prédiction OK == cmov en temps dans ce cas. La version cmov est constante en temps, alors que si pour un algo la prédiction n'est pas bonne 1 fois de temps en temps, tu es très pénalisé.

Il faudrait faire un autre journal ou on compte les occurrences de k…

[^] # Re: Sans SSE

Posté par Nicolas Boulay (site web personnel) le 08 octobre 2021 à 10:34. Évalué à 4. Dernière modification le 08 octobre 2021 à 10:35.

La version cmov est constante en temps, alors que si pour un algo la prédiction n'est pas bonne 1 fois de temps en temps, tu es très pénalisé.

Sauf que tu es pénalisé en permanence avec CMOV car tu as une dépendance de plus. A l'époque au Linus travaillait pour Transmeta, il avait écrit un long texte sur sa détestation de CMOV qui impliquait de la prédiction de valeur, ce qui est bien plus difficile que la prédiction de branchement. (cf https://yarchive.net/comp/linux/cmov.html par exemple)

tu as vu la dernière version de mon code :
https://linuxfr.org/users/julien_jorge/journaux/recherche-de-valeur-dans-un-tableau-et-l-ecosysteme-des-compilateurs-c#comment-1868353 ?

"La première sécurité est la liberté"

[^] # Re: Sans SSE

Posté par YBoy360 (site web personnel) le 08 octobre 2021 à 14:40. Évalué à 1. Dernière modification le 08 octobre 2021 à 14:40.

Sur ARM (un chromebook avec Debian dessus), j'obtiens de meilleurs score pour la version "CMOV" sur le main que j'ai mis au-dessus, les valeurs sont loader bien avant le CMOV, donc pas besoin de prédiction de valeur, elles sont dispo lors du cmov (il faudrait faire du profiling, j'ai la flème).

$ ./test.x
C1 = 928197 (499999984), C2 = 605687 (499999984), C3 = 538721 (499999984), C4 = 539927 (499999984), C5 = 545717 (499999984)

C3 et C4 sont 2 versions CMOV, les autres utilisent les branchements. C5, c'est le code que tu as mis dans l'autre commentaire.

$ cat /proc/cpuinfo 
processor       : 0
BogoMIPS        : 26.00
Features        : fp asimd evtstrm aes pmull sha1 sha2 crc32 cpuid
CPU implementer : 0x41
CPU architecture: 8
CPU variant     : 0x0
CPU part        : 0xd03
CPU revision    : 4
[ . . . 8 cores qui semblent identiques ]

size_t find_int_c3(const int k, const int* v, const size_t n) {
    unsigned int mask = 0;
    size_t i = 0;
    for (; i < n - 8;) {
        mask = v[i] != k ? mask : 1;
        mask = v[i+1] != k ? mask : 2;
        mask = v[i+2] != k ? mask : 4;
        mask = v[i+3] != k ? mask : 8;
        mask = v[i+4] != k ? mask : 16;
        mask = v[i+5] != k ? mask : 32;
        mask = v[i+6] != k ? mask : 64;
        mask = v[i+7] != k ? mask : 128;
        i += 8;
        if (mask != 0) i += n;
        __builtin_prefetch(v + i + 512, 0, 1);
    }

    i -= n + 8;
    if (mask == 0) return n;
    if (mask == 1) return i;
    if (mask == 2) return i + 1;
    if (mask == 4) return i + 2;
    if (mask == 8) return i + 3;
    if (mask == 16) return i + 4;
    if (mask == 32) return i + 5;
    if (mask == 64) return i + 6;
    if (mask == 128) return i + 7;
}

size_t find_int_c4(const int k, const int* v, const size_t n) {
    size_t i = 0;
//  size_t n2 = n >> 1;
//  const long* vl = (const long*)v;
//  const long kl = (long)(((long)k>>32) + k);
    unsigned int index = 0;

    for (; i <= n; i += 8, v += 8) {
        index = 0;
        __builtin_prefetch(v + 256);
        index = v[0] != k ? index : 1;
        index = v[1] != k ? index : 1;
        index = v[2] != k ? index : 1;
        index = v[3] != k ? index : 1;
        index = v[4] != k ? index : 1;
        index = v[5] != k ? index : 1;
        index = v[6] != k ? index : 1;
        index = v[7] != k ? index : 1;
        if (index == 1) {
            break;
        }
    }
    if (index == 0) return i;
    else
        for (int j = 0; i < 8; j++) {
            if (v[j] == k) return i + j;
        }
}

size_t find_int_c5(const int k, const int* v, const size_t n) {
      size_t i = 0;
       for (; n - i >= 8; i += 8,v+=8)
         {
          __builtin_prefetch(v+256); //54/148
          if (v[0] == k) return i;
          if (v[1] == k) return i + 1;
          if (v[2] == k) return i + 2;
          if (v[3] == k) return i + 3;
          if (v[4] == k) return i + 4;
          if (v[5] == k) return i + 5;
          if (v[6] == k) return i + 6;
          if (v[7] == k) return i + 7;
        }

       for (; i != n; i++,v++)
        if (v[0] == k)
          return i;
       return n;
}

Le fait que C3 soit plus rapide que C4 est contre-intuitif, mais le prefetch n'est pas placé aux mêmes endroits. Je m'attendais à de plus de différences…

Perso j'adore ce Chromebook, pour 250 EUR t'as un Linux sur ARM (certes, ça ne vaut pas un RPi). Mais il y a un très bon écran.

[^] # Re: Sans SSE

Posté par YBoy360 (site web personnel) le 08 octobre 2021 à 15:26. Évalué à 2.

Pour info, la version utilisant des long est presque encore 2 fois plus rapide sur ARM que la version int …

Par contre ça impose des contraintes d'alignement.

size_t find_int_c4l(const int k, const int* v, const size_t n) {
    size_t i = 0;
    size_t n2 = n >> 1;
    const long* vl = (const long*)v;
    const long kl = (long)(((long)k>>32) + k);
    unsigned int index = 0;

    for (; i <= n2; i += 8, vl += 8) {
        index = 0;
        __builtin_prefetch(vl + 256, 0, 1);
        index = vl[0] != kl ? index : 1;
        index = vl[1] != kl ? index : 1;
        index = vl[2] != kl ? index : 1;
        index = vl[3] != kl ? index : 1;
        index = vl[4] != kl ? index : 1;
        index = vl[5] != kl ? index : 1;
        index = vl[6] != kl ? index : 1;
        index = vl[7] != kl ? index : 1;
        if (index == 1) {
            break;
        }
    }
    if (index == 0) return i;
    else
        for (int j = 0; i < 8; j++) {
            if (vl[j] == kl) return i + j; 
                        //Attention, il == 2 * i...
        }
}

[^] # Re: Sans SSE

Posté par YBoy360 (site web personnel) le 08 octobre 2021 à 16:16. Évalué à 1.

Je me suis emballé, il faut 2 comparaisons et appliquer 2 masks. Par contre, autant on perd sur de l'AMD sur cette boucle par rapport à la version non long, mais on divise par 2 sur mon ARM (Mediatek je crois…).

Si après correction j'obtiens des gains, je te les communiquerai.

[^] # Re: Sans SSE

Posté par YBoy360 (site web personnel) le 08 octobre 2021 à 17:00. Évalué à 2.

La version utilisant des long corrigée présente un gains de 10 % sur ARM, mais grand chose sur Intel, par rapport à la version entière… Il y a peut-être encore de marge en regardant le code généré, mais l'épilogue de la fonction est déjà compliqué à écrire (ou les cas non aligné, pour des tableaux de n'importe quelle taille).

Donc sur cette tablette / Chromebook, le meilleur résultat est pour la boucle suivante (sans optimisation du prefetch) :

size_t find_int_c4l(const int k, const int* v, const size_t n) {
    size_t i = 0;
    size_t n2 = n >> 1;
    const unsigned long* vl  = (const unsigned long*)v;
    const unsigned long klow = (unsigned long)k;
    const unsigned long khi  = (unsigned long)k << 32;
    const unsigned long maskLow = 0xffffffff;
    const unsigned long maskHi  = maskLow << 32;
    unsigned int index = 0;

    for (; i <= n2; i += 8, vl += 8) {
        index = 0;
        __builtin_prefetch(vl + 256, 0, 1);

        index = ((vl[0] & maskLow) != klow && (vl[0] & maskHi) != khi) ? index : 1;
        index = ((vl[1] & maskLow) != klow && (vl[1] & maskHi) != khi) ? index : 1;
        index = ((vl[2] & maskLow) != klow && (vl[2] & maskHi) != khi) ? index : 1;
        index = ((vl[3] & maskLow) != klow && (vl[3] & maskHi) != khi) ? index : 1;
        index = ((vl[4] & maskLow) != klow && (vl[4] & maskHi) != khi) ? index : 1;
        index = ((vl[5] & maskLow) != klow && (vl[5] & maskHi) != khi) ? index : 1;
        index = ((vl[6] & maskLow) != klow && (vl[6] & maskHi) != khi) ? index : 1;
        index = ((vl[7] & maskLow) != klow && (vl[7] & maskHi) != khi) ? index : 1;
        if (index == 1) {
            break;
        }
    }
    return i; // i n/2 -8 si ok dans mon cas...
}

Résultat :
bash C1 = 2850253 (499999984), C2 = 1233600 (499999984), C3 = 575797 (499999984), C4 = 547523 (499999984), C4l = 494092 (249999992), C5 = 556564 (499999984)

Par rapport à la version originale, dans mon test sur ARM, la boucle C4l est 5,77 fois plus rapide.

[^] # Re: Sans SSE

Posté par Ontologia (site web personnel) le 09 octobre 2021 à 11:51. Évalué à 3.

Il faut voir qu'il y a un point particulier dans la critique de Linus : le P4 avait un pipeline particulièrement long et donc un vidage du pipeline était particulièrement couteux. Ce qui est moins le cas dans des architectures actuelles.

« Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker

# Typo ?

Posté par gUI (Mastodon) le 04 octobre 2021 à 07:50. Évalué à 5.

Cela fait plus de vingt temps que j'entends

"Vingt ans" ? Ou j'ai râté qqchose ?

En théorie, la théorie et la pratique c'est pareil. En pratique c'est pas vrai.
- [^] # Re: Typo ?
  
  Posté par Julien Jorge (site web personnel) le 04 octobre 2021 à 07:54. Évalué à 6.
  
  C'est parce que j'écris en phonétique et je tiens à ce que les lecteurs fassent les liaisons…
  
  C'est corrigé, merci :)
- [^] # Re: Typo ?
  
  Posté par groumly le 04 octobre 2021 à 21:26. Évalué à 5.
  
  Non, c’est juste le premier temps de la valse.
  
  Linuxfr, le portail francais du logiciel libre et du neo nazisme.
# J'veux pas faire le relou mais...

Posté par Joël le 04 octobre 2021 à 07:58. Évalué à 9.

… du coup, j'ai l'impression que tu confonds compilateur et bibliothèque standard. Si je comprends bien ton article, c'est pas vraiment que le compilateur de Intel est mieux que les autres, c'est surtout que la bibliothèque standard qu'il utilise est potentiellement plus optimisée. En d'autres termes, si tu compiles avec GCC mais en utilisant le code de la biblio standard de chez Intel, t'auras les mêmes perfs avec le compilo d'Intel.

J'ai loupé qque chose ?
- [^] # Re: J'veux pas faire le relou mais...
  
  Posté par Julien Jorge (site web personnel) le 04 octobre 2021 à 09:13. Évalué à 4. Dernière modification le 04 octobre 2021 à 09:13.
  
  Effectivement si on utilise la lib standard d'Intel avec GCC on risque d'avoir les même perfs, mais le fond n'est pas là :)
  
  Le message que j'essaye de faire passer est que, à mon avis, nous nous appuyons trop sur une supposée efficacité des compilateurs pour obtenir des binaires efficaces.
  
  Ici aucun des compilateurs n'a été capable de sortir ne serait-ce que quelque chose d'équivalent à un déroulage de boucle pour la fonction initiale (une simple boucle de recherche), et aucun ne sait vectoriser l'algorithme de lui-même. Par conséquent il faut utiliser une bibliothèque dédiée pour avoir l'algo SSE2, mais là ce n'est plus le résultat du travail du compilateur, c'est le travail des développeurs de la bibliothèque.
  - [^] # Re: J'veux pas faire le relou mais...
    
    Posté par Nicolas Boulay (site web personnel) le 04 octobre 2021 à 10:11. Évalué à 4.
    
    Le déroulage de boucle est fait depuis longtemps par GCC. Je suis assez étonné de ce que tu écris. Vers 2000, j'avais écrit un code de multiplication de matrice, et GCC déroulait 16 fois tout seul.
    
    "La première sécurité est la liberté"
    - [^] # Re: J'veux pas faire le relou mais...
      
      Posté par Julien Jorge (site web personnel) le 04 octobre 2021 à 13:22. Évalué à 2. Dernière modification le 04 octobre 2021 à 18:03.
      
      J'en étais convaincu aussi, mais Compiler Explorer confirme que la boucle n'est pas déroulée si je ne mets pas -funroll-loops. Donc il le fait, mais c'est en plus du lot d'optimisations de O3 :)
      - [^] # Re: J'veux pas faire le relou mais...
        
        Posté par groumly le 04 octobre 2021 à 21:35. Évalué à 4.
        
        Le problème des micro benchmarks, c’est qu’ils ne sont pas forcément super réalistes.
        
        Est ce que t’as essayé de relancer le code en question sur des tableaux triés ou aléatoirement triés?
        Je suppute que les mecs qui écrivent la lib std c++ savent dérouler une boucle, et s’ils l’ont pas fait, ils ont potentiellement de bonnes raisons. En l’occurrence, un bon compromis pour les cas les plus courants, la ou Intel recherche la vitesse pure en partant du principe que les inges comprennent ce qu’il se passe.
        
        Linuxfr, le portail francais du logiciel libre et du neo nazisme.
        
        [^] # Re: J'veux pas faire le relou mais...
        
        Posté par Julien Jorge (site web personnel) le 04 octobre 2021 à 22:23. Évalué à 2.
        
        Oui j'ai essayé sur des tableaux aléatoirement triés et ça n'avait rien changé. Je ne m'attends pas à ce que ça change quelque chose puisque les valeurs c'est pas l'important (ici) : elles sont toutes distinctes et on cherche la dernière. Je suppose que le prédicteur de branche va vite comprendre que la condition dans la boucle est plutôt jamais vérifiée.
        
        Je me dis aussi qu'il y a une raison pour ne pas dérouler, d'autant plus que la boucle de std::find() est bien déroulée, elle. Peut-être est-ce une politique générale du genre « tu ne me dis pas -funroll-loops alors je ne déroule pas parce que ça ferait grossir le binaire ».
        
        [^] # Re: J'veux pas faire le relou mais...
        
        Posté par groumly le 05 octobre 2021 à 06:39. Évalué à 6.
        
        Ce que je voulais dire, c’est tester des cas ou la valeur est pas à la fin du tableau, justement.
        
        ‘fin, tes graphes sont pas très réalistes. Qui va en pratique se trimballer des tableaux de 2 millions d’entrées en premier lieu, et lancer un linear scan sur un tableau de cette taille?
        Applique à des objets/structs pas forcément très gros en premier lieu, tu vas commencer à te trimballer plusieurs centaines de Mo juste pour le tableau. Personne ne va faire ça.
        
        Tes résultats pour des tailles de tableaux réalistes sont tellement agglutinées qu’on en sort pas grand chose (surtout avec une échelle en nano secondes), sans compter que ça tourne sur un tromblon vieux de 7 ans.
        
        C’est un peu la ou je voulais en venir, les auteurs de compilos ont très probablement considéré les optimizations dont tu parles. Mais une fois benchmarké sur des cas réalistes, les gains potentiels (a supposer qu’il y’en avait vraiment) ne valent pas le coup.
        Les mecs, ils recherchent des optimisations qui améliorent des cas concret.
        
        Linuxfr, le portail francais du logiciel libre et du neo nazisme.
        
        [^] # Re: J'veux pas faire le relou mais...
        
        Posté par jyes le 06 octobre 2021 à 14:26. Évalué à 6.
        
        Peut-être est-ce une politique générale du genre « tu ne me dis pas -funroll-loops alors je ne déroule pas parce que ça ferait grossir le binaire
        
        La taille du binaire n’est pas le seul critère. J’ai participé à une formation de chez Intel où les formateurs nous expliquaient qu’au gré des versions (récentes) ils avaient fait le choix d’être de moins en moins agressifs sur la vectorisation automatique, car elle n’est pas aussi performante que la vectorisation manuelle (ou assistée par des instructions manuelles). Il ne suggéraient pas de dérouler les boucles à la main, mais d’utiliser des directives OpenMP pour indiquer quelles boucles pouvaient/devaient être déroulées et optimisées avec des instructions SIMD etc. C’est possible que l’argument ait aussi été entendu (et appliqué) chez GCC qui attend donc (sauf options contraire sur la ligne de commande) des directives du développeur pour dérouler/vectoriser les boucles.
        
        Ça me contrarie à titre personnel car il va falloir repasser sur tout mon code pour ajouter les directives OpenMP idoines, mais si à la fin c’est vraiment la bonne solution, ce travail ne sera pas vain et me fera peut-être gagner davantage que la vectorisation automatique (qui repose sur des heuristiques très pifométriques). Chez OpenMP, ils ont beaucoup bossé sur la question, et si ~~tout le monde a~~ les experts ont l’air de tomber d’accord, je suis prêt à me fier à ce consensus.
        
        [^] # Re: J'veux pas faire le relou mais...
        
        Posté par barmic 🦦 le 06 octobre 2021 à 15:25. Évalué à 2.
        
        Les compilateurs n'éditent pas de document pour donner des grands principes d'état de l'art comme ça ? Que ce soit des règles de codage ou des options de compilation qu'ils n'activent pas par défaut car cassant la norme mais qui devraient être l'usage selon eux.
        
        Je comprends qu'Intel vend des formations, mais gcc/llvm me paraissent plus ouverts.
        
        https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll
        
        [^] # Re: J'veux pas faire le relou mais...
        
        Posté par SpaceFox (site web personnel, Mastodon) le 06 octobre 2021 à 16:08. Évalué à 3. Dernière modification le 06 octobre 2021 à 16:09.
        
        Parfois, les documents existent mais sont peu connues et difficiles d’accès.
        
        Dans un autre domaine mais qui s’en rapproche, la compilation JIT de la JVM IBM s’appuie elle aussi sur des heuristiques pour savoir quoi compiler et quand, et ils ont fait les heuristiques ont été créées avec le code qu’avaient ses concepteurs à disposition comme « code représentatif à optimiser ». La conséquence et à moins que la situation ait changé depuis la dernière fois que j’ai vérifié, c’est que pour garantir que ton code Java sera compilé le plus tôt et le plus efficacement avec la JVM IBM, il faut qu’il ressemble au maximum… à du veux code Java IBM. Ce qui, quand tu fais du Java 8+, n’est pas très motivant. L’information était disponible, mais à condition d’aller chercher les détails d’implémentation du JIT dans les docs non publiques (compte IBM nécessaire).
        
        PS : dans ce cas c’est « ouvert » dans le sens où l’info était disponible dès que tu avais accès au compilateur IBM (c’était avant qu’il ne soit refilé à la fondation Eclipse, qui est un peu la poubelle du Libre par certains aspects), et IBM ne vendait pas à ma connaissance de formations spécifiques sur ce point.
        
        La connaissance libre : https://zestedesavoir.com
        
        [^] # Re: J'veux pas faire le relou mais...
        
        Posté par barmic 🦦 le 06 octobre 2021 à 16:15. Évalué à 3. Dernière modification le 06 octobre 2021 à 16:15.
        
        OpenJDK a une liste de projets libres qui leur servent entre autre à ça. Tu peux aussi activer des logs pour qu'hotspot indique les choix qu'il fait. Ça n'en fait pas quelque chose de génial (les projets ont une certaine latence pour passer aux nouveautés à des fins de compatibilité et lire ces logs, bien que compréhensibles, ne vaut pas une doc qui donne des règles) mais c'est déjà ça.
        
        Note qu'en plus les heuristiques d'un jit dépendent d'informations runtime, tu peux avoir des optimisations différentes selon l'état de la jvm ce qui peut rendre assez complexe les benchmark.
        
        https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll
- [^] # Re: J'veux pas faire le relou mais...
  
  Posté par David Demelier (site web personnel) le 04 octobre 2021 à 09:23. Évalué à 5.
  
  Tu as raison sur le fond, mais dans la réalité c'est tout autre. La bibliothèque standard et le compilateur sont fortement liés. Il y a des choses dans la bibliothèque standard qui ne peuvent tout simplement pas être implémentés avec du C++ pur et donc il y a forcément un moment où on doit appeler des extensions et builtins du compilateur
  
  Je pense par exemple à tout ce qui est relatif à RTTI, certaines choses dans <type_traits>, etc. GCC et Clang sont assez interchangeables (clang peut utiliser libstdc++ come libc++). Mais on ne pourra probablement pas utiliser ICC/MSVC avec libstdc++.
  
  Donc au final, ça reste acceptable de comparer un « ensemble » d'outils : donc MSVC avec sa bibliothèque C++, clang avec libc++, tu vois le topo. Il ne faut pas oublier que développer en C++ nécessite beaucoup d'autres outils (linker, preprocesseur, libc, …).
  
  git is great because linus did it, mercurial is better because he didn't
# Code de haut niveau

Posté par barmic 🦦 le 04 octobre 2021 à 09:48. Évalué à 10.

Évidemment il n'est pas question de tout optimiser, mais la vraie raison pour laquelle nous écrivons du code de haut niveau n'est pas que les compilateurs sont très performants ; c'est plutôt un compromis du temps de mise en œuvre. En d'autres termes, nous acceptons du code sous optimal au profit d'une écriture et d'une maintenance simplifiée.

Il me semble que ton journal démontre l'inverse. std::find permet à la toolchain (que ce soit le compilateur ou la bibliothèque standard) d'implémenter simplement des optimisations. Là où les heuristiques qui vont dérouler des boucles peuvent être fragiles (être appliquées ou non par faux positif/négatif) et même être cassé dans le code (parce que boucle toute propre, tu peux repasser dessus 1 ans plus tard et y ajouter un 'tit traitement qui va invalider l’heuristique).

Ensuite il semble effectivement que les toolchains ne sont pas forcément aussi optimisées qu'on l'espérerais. Il me semble néanmoins qu'il est préférable de s'appuyer dessus et que tenter d'optimiser sois-même et d'arriver assez vite à du code bugué et très difficile à maintenir comme on le voit dans d'autres commentaires. Sincèrement avoir un code qui recherche une valeur dans un tableau qui contiens une erreur suffisamment non trivial pour ne pas sauter aux yeux, je préfère avoir un code un peu plus lent. Je place la correction du code comme une qualité qui est tout de même devant toutes les autres en terme de qualité logiciel.

https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll
- [^] # Re: Code de haut niveau
  
  Posté par Nicolas Boulay (site web personnel) le 04 octobre 2021 à 10:14. Évalué à 7.
  
  On pourrait aussi optimiser find.
  
  En fait, je pense que find est déjà optimisé mais pour des tailles de l'ordre de la centaine. Personne ne doit faire de recherche linéaire sur 1 millions d'élément.
  
  Souvent les codes rapides ont un "startup time" important qui les invalident pour les petites tailles qui sont les plus utilisé.
  
  "La première sécurité est la liberté"
  - [^] # Re: Code de haut niveau
    
    Posté par barmic 🦦 le 04 octobre 2021 à 10:41. Évalué à 3.
    Tout à fait, de la même manière que des structures de données plus complexes (comme les map) n'ont pas la même implémentation optimales selon si elles sont petites ou grande.
    
    En fait, je pense que find est déjà optimisé mais pour des tailles de l'ordre de la centaine.
    
    En soit elle pourrait faire un test au runtime pour ça.
    
    Personne ne doit faire de recherche linéaire sur 1 millions d'élément.
    
    Entièrement d'accord et si l'exercice de regarder comment marchent les optimisations de la toolchain est intéressant et pratiques sur des cas triviaux, il faut :
    1. s'assurer que ce que l'on observe à petite échelle garde du sens à grande échelle
    2. s'assurer que l'ont est entrain de regarder quelque chose de pertinent (quel est l'impact de ce que l'on regarde sur la performance globale du programme ?). Il me semble que dans biens des cas le problème est moins dans la performance CPU que dans les IO par exemple. Utiliser de manière pertinentes les mmap/io_uring/etc me semble amplement plus important.
    https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll
- [^] # Re: Code de haut niveau
  
  Posté par Julien Jorge (site web personnel) le 04 octobre 2021 à 22:28. Évalué à 4.
  
  Sincèrement avoir un code qui recherche une valeur dans un tableau qui contiens une erreur suffisamment non trivial pour ne pas sauter aux yeux, je préfère avoir un code un peu plus lent. Je place la correction du code comme une qualité qui est tout de même devant toutes les autres en terme de qualité logiciel.
  
  Là dessus je te rejoins complètement. Idéalement je préfère que les algos optimisés viennent de bibliothèques bien rodées ou soient directement fournies par le vendeur du compilateur.
  - [^] # Re: Code de haut niveau
    
    Posté par gouttegd le 04 octobre 2021 à 23:30. Évalué à 10.
    
    Ça me rappelle qu’un jour j’étais allé voir l’implémentation de memchr dans la GNUlib (impossible de me rappeler pourquoi…). J’en avais conclu que j’admirais les développeurs capable d’imaginer et d’écrire ce genre de code (sincèrement), mais que je ne voulais pas voir ça dans mes propres projets… Je n’ai pas changé d’avis !
    
    J’aime beaucoup cette phrase de Brian Kernighan :
    
    Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as you can, you are, by definition, not smart enough to debug it.
    
    J’essaie de la garder en tête chaque fois que l’envie me prend de jouer au plus malin avec mon code…
    - [^] # Re: Code de haut niveau
      
      Posté par Zenitram (site web personnel) le 05 octobre 2021 à 14:38. Évalué à 2.
      
      mais que je ne voulais pas voir ça dans mes propres projets
      
      De mon point de vue bien subjectif, j'aime quand même bien accélérer les choses, on arrive parfois à des trucs qui sont super lent sur des machines de guerre parce que personne ne veut optimiser…
      Comme souvent, c'est le coût de dev et maintenance contre le gain de performance et le nombre d'utilisateurs, et il faut trouver le juste milieu (rien de simple!)
      
      Donc c'est bien que GNUlib ai ça (c'est très utilisé), et c'est bien de ne pas le vouloir dans ses propres projets (moins utilisé à priori).
      - [^] # Re: Code de haut niveau
        
        Posté par fearan le 05 octobre 2021 à 15:40. Évalué à 10.
        
        on arrive parfois à des trucs qui sont super lent sur des machines de guerre parce que personne ne veut optimiser…
        
        Ce n'est généralement pas une question d'optimisation, mais à un mauvais codage; typiquement
        
        si tu cherches systématiquement une valeur pour savoir quel est l'indice dans un tableau ou si une valeur est dans une collection, tu as le choix entre une map ou un set;
        
        si tu décides de faire un systématiquement à chaque itération de boucle, alors que tu as le même résultat si tu fais une fois le calcul après la boucle, c'est qu'il y'a encore eu un soucis dans le codage.
        
        si tu te contente de quelques appels jpa pour aller chercher des données arborescente dans une db SQL, tu va aussi morfler dès que les données seront un minimum conséquente, et tu vas devoir revoir ta copie (requête récursive, ou ajouter un champ permettant de tout récupérer en une requête), de même, le choix des index en bdd est essentiel.
        
        Bref ça m'est arriver en corrigeant le code de gagner plusieurs fois d'un facteur 2 ou 3, et parfois même de plus d'une minutes, a moins d'une seconde, et cela sans aller chercher dans l'optimisation fine que sont les déroulage de boucle.
        
        Mais utiliser les structure de données adaptés, faire les calculs au bon moment, c'est pas de l'optimisation, mais de l'hygiène de code!
        
        Il ne faut pas décorner les boeufs avant d'avoir semé le vent
      - [^] # Re: Code de haut niveau
        
        Posté par gouttegd le 05 octobre 2021 à 23:00. Évalué à 6.
        
        Donc c'est bien que GNUlib ai ça
        
        Ah mais tout-à-fait, je ne voulais pas insinuer le contraire ! Et je n’aurais aucune hésitation à utiliser une bibliothèque codée ainsi. Par contre, je me garderai bien d’essayer d’écrire du code comme ça moi-même, et je pense que je serai même réticent à accepter un patch écrit comme ça, quand bien même l’auteur me démontrerait que ça rend mon programme 76 fois plus rapide…
        
        En gros, en tant que programmeur du dimanche et conscient de l’être, je n’ai aucun problème avec ce genre de code, tant que je ne me retrouve pas à le maintenir moi-même. :D
- [^] # Re: Code de haut niveau
  
  Posté par Ontologia (site web personnel) le 06 octobre 2021 à 15:52. Évalué à 7.
  
  C'est encore une fois tout le débat auquel avait simplement répondu Donald Knuth : "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%."
  
  Si on a le temps de détecter ces 3% (j'ai passé 3 ans à écrire un logiciel qui le fait pour du Java, en static), ça peut être intéressant, en commentant les optimisations pour qu'elles soient compréhensibles pour celui qui passe derrière.
  Par experience, en Java, même l'optimisation de 0,5% de code peut faire gagner 10% de performances, en général c'est juste quelques centaines de lignes de code, au plus (et souvent moins)
  
  « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
  - [^] # Re: Code de haut niveau
    
    Posté par barmic 🦦 le 06 octobre 2021 à 16:06. Évalué à 3.
    
    Si on a le temps de détecter ces 3%
    
    Oui mais la détection est importante justement. Avant d'en arriver à dérouler des boucles à la main, c'est intéressant de vérifier les IO, les algo et structures de données et une fois que toutes ses choses sont faites, on peut aller vers des optimisations qui vont commencer à prendre le pas sur la lisibilité et la maintenabilité.
    
    Et oui quelques lignes de code peuvent drastiquement changer la donne. Prends le bug de GTA sur le parsing de fichier json : How I cut GTA Online loading times by 70%. On parle de quelques dizaines de lignes.
    
    https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll
    - [^] # Re: Code de haut niveau
      
      Posté par Gil Cot ✔ (site web personnel, Mastodon) le 06 octobre 2021 à 16:51. Évalué à 2.
      
      Je te rejoins en repensant à l'époque où je tatais un peu d'assembleur (mais je retrouve un peu ça en faisant du scripting) : il est très important d'avoir de bon algorithmes (d'où l'intérêt de comprendre la notion d'ordre de complexité) et les structures de données adéquates, cela résout la majorité des soucis de lenteur que l'on rencontre.
      
      “It is seldom that liberty of any kind is lost all at once.” ― David Hume
# Vectorisation illégale

Posté par SChauveau le 04 octobre 2021 à 11:09. Évalué à 8.

Je n'ai pas regardé dans les compilateurs actuels, mais en règle général, la vectorisation n'est pas possible dans les boucles non-pures, c'est à dire contenant un break ou un return conditionnel. Je ne dis pas que c'est toujours impossible mais c'est rarement intéressant donc les compilateurs n'essayent même pas.

Je tiens aussi à signaler que strictement parlant, la vectorisation SSE proposée ici est illégale. Le problème est que les données sont lues par blocs de 4 int (donc 16 octets). En pratique, cela signifie que la boucle vectorisée peut lire 1, 2 ou 3 int supplémentaire. Cela pourrait causer un dépassement de tableau et donc un 'segfault'. Un bon compilateur ne fera pas cela.

Remarque: Le fait que les indices lus soient tous inférieurs à n n'a pas d'importance car, du point de vue du compilateur, l'argument n n'indique pas la taille du taille du tableau. Par exemple, si l'utilisateur est certain que son tableau contient au moins une fois la valeur, il pourrait décider d'utiliser n=INT_MAX.

J'imagine qu'ICC fait quelques tests supplémentaires sur les alignements des pointeurs dans son implémentation de std::find(). Cela entraîne évidemment un petit surcoût qui peut ne pas être négligeable quand n est petit. C'est une information que le compilateur ne possède généralement pas (sauf inlining ou analyse inter-procedurale).

Il ne faut pas non plus oublier que pour respecter les conventions d'appels, les codes vectorisés doivent aussi sauver et restaurer plus de registres (push/pop dans la pile). C'est un autre surcoût qu'il faut prendre en compte pour décider si la vectorisation est intéressante.

PS: Dans ton benchmark, toutes les fonctions sont dans le même fichier. Il n'est pas impossible qu'ICC réussisse à optimiser std::find en inlinant systématiquement tout les appels de fonctions (donc potentiellement plus d'info sur n et sur l'alignement des données). Obtiens tu les même perfs quand find_int_cpp() est compilé dans un fichier séparé?
- [^] # Re: Vectorisation illégale
  
  Posté par Julien Jorge (site web personnel) le 04 octobre 2021 à 22:50. Évalué à 3.
  
  Je tiens aussi à signaler que strictement parlant, la vectorisation SSE proposée ici est illégale. Le problème est que les données sont lues par blocs de 4 int (donc 16 octets). En pratique, cela signifie que la boucle vectorisée peut lire 1, 2 ou 3 int supplémentaire. Cela pourrait causer un dépassement de tableau et donc un 'segfault'. Un bon compilateur ne fera pas cela.
  
  Remarque: Le fait que les indices lus soient tous inférieurs à n n'a pas d'importance car, du point de vue du compilateur, l'argument n n'indique pas la taille du taille du tableau. Par exemple, si l'utilisateur est certain que son tableau contient au moins une fois la valeur, il pourrait décider d'utiliser n=INT_MAX.
  
  Très intéressante observation :) En fait, par le standard C++, un appel à std::find() doit forcément passer deux itérateurs sur le même conteneur (car comparer deux itérateurs qui ne pointent pas sur la même séquence est undefined behavior). Du coup le compilateur pourrait se permettre d'utiliser la vectorisation pour l'implémenter, mais pas pour une boucle ad-hoc de l'utilisateur qui, elle, peut effectivement être appelée avec n'importe quoi.
  
  Après il pourrait aussi prendre cela dans l'autre sens : considérer que la boucle lit potentiellement n éléments à partir de v, et si elle lisait une zone non autorisée le programme serait invalide, donc les n éléments sont forcément valides (i.e. n est bien inférieur ou égal à la taille allouée pour v).
  
  PS: Dans ton benchmark, toutes les fonctions sont dans le même fichier. Il n'est pas impossible qu'ICC réussisse à optimiser std::find en inlinant systématiquement tout les appels de fonctions (donc potentiellement plus d'info sur n et sur l'alignement des données). Obtiens tu les même perfs quand find_int_cpp() est compilé dans un fichier séparé?
  
  Je viens de séparer les fichiers (c'est poussé dans le dépôt) et les résultats sont les mêmes :)
  - [^] # Re: Vectorisation illégale
    
    Posté par SChauveau le 07 octobre 2021 à 17:46. Évalué à 3.
    
    Je doute fort que les 2 itérateurs de std::find puissent être utiles au compilateur.
    
    L'itérateur est un concept de haut niveau qui est probablement inconnu du compilateur. Il faut bien différencier les règles définies dans les APIs et celles définies dans le langage lui même (et la lib std de c++ est une api). Le compilateur C++ n'a normalement aucune idée de la sémantique associée aux std::iterator, std::string, std::vector, etc. Il ne voit que des classes et ne peux faire aucune hypothèse sur la sémantique. Si demain, je renomme tout les 'iterator' en 'foobar' cela devrait fonctionner pareil.
    
    C'est différent dans d'autre langages tels que Fortran où de nombreuses fonctions sont intrinsèques au langage et ont donc une sémantique connue du compilateur.
    
    Cela ne signifie pas que le compilateur C++ ne peut jamais exploiter ce genre d'information. En général, il faut que le programmeur fournisse l'information explicitement, par exemple, sous la forme d'un pragma ou d'un attribut.
    - [^] # Re: Vectorisation illégale
      
      Posté par Thomas Douillard le 07 octobre 2021 à 20:02. Évalué à 2.
      
      Potentiellement, on est dans le cadre de la norme, donc en écrivant un compilateur pourrait considérer qu’il a accès à toutes les informations sémantiques du langage, y compris la norme de la bibliothèque standard. Et l’implémenter lui même. Mais c’est plus de travail, forcément.
      - [^] # Re: Vectorisation illégale
        
        Posté par Ontologia (site web personnel) le 07 octobre 2021 à 21:38. Évalué à 3. Dernière modification le 07 octobre 2021 à 21:38.
        
        Bon courage à celui qui va coder la détection de pattern à partir de la grammaire de C++. Je n'imagine pas le nombre de cas et leur complexité à gérer…
        
        « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
        
        [^] # Re: Vectorisation illégale
        
        Posté par Thomas Douillard le 08 octobre 2021 à 10:27. Évalué à 1.
        
        Je comprend pas trop pourquoi tu parles de grammaires du langage lorsqu’on parle d’exploiter la sémantique de l’API
        
        [^] # Re: Vectorisation illégale
        
        Posté par Ontologia (site web personnel) le 09 octobre 2021 à 12:54. Évalué à 2.
        
        Parce que tu penses que le compilateur travaille à partir d'autre chose qu'un AST ?
        
        « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
        
        [^] # Re: Vectorisation illégale
        
        Posté par Julien Jorge (site web personnel) le 09 octobre 2021 à 19:42. Évalué à 2.
        
        La détection de pattern se fait bien après avoir parsé le code C++, au niveau d'un langage intermédiaire. Chez LLVM par exemple ça se fait au niveau de l'IR, mais aussi lors du codegen, i.e. la partie qui tiens compte de l'architecture cible. Je ne suis pas sûr qu'on parle encore d'AST à ce niveau là.
    - [^] # Re: Vectorisation illégale
      
      Posté par pulkomandy (site web personnel, Mastodon) le 07 octobre 2021 à 23:51. Évalué à 7.
      Gcc fait des optimisations auxquelles on ne s'attend pas forcément. Quelques cas auxquels je pense:
      
      Il optimise printf("chaine\n") en puts("chaine")
      
      Dans Haiku, dans notre libc on teste dans nos fonctions de manipulations de chaîne (strcpy, strlen, …) si un pointeur null est passé en paramètre. Dans le standard C, l'appel de ces fonctions avec un paramètre null est un comportement indéfini. Gcc optimise notre implémentation en enlevant le test qu'on avait ajouté. Il peut aussi décider de ne pas du tout appeler la fonction et d'utiliser sa propre implémentation.
      
      Les compilateurs font usage de tout ce qui est dit dans la spécification, et la spécification est architecturée pour ça. Par exemple la spécification du C décrit un mode "hosted" et un mode "freestanding", dans le deuxième, la plupart des fonctions de la librairie standard ne sont plus définies. Ce qui permet au compilateur de savoir qu'il doit désactiver les optimisations correspondantes.
      
      L'idée qu'on se fait d'une architecture bien découpée en couches indépendantes ne tient en fait pas la route quand on regarde les détails d'implémentation.
# Parfois l'homme est meilleur que la machine

Posté par KuroLightning le 04 octobre 2021 à 11:31. Évalué à 2. Dernière modification le 04 octobre 2021 à 11:57.

Par expérience, il y a des cas où faire les optimisations à la main (via les intrinsics ou directement en asm) est, à l'heure actuelle, toujours supérieure aux compilateurs.

#MyLife
Durant ma thèse (2017), j'ai développé un code de simulation multifluide de décharges plasmas. Et l'un des solveurs utilisés pour résoudre calculer le potentiel électrique devait calculer alternativement les indices pairs puis les indices impairs. Ecrit correctement et avec les bons optimisations, le compilateur produisait un code sympathique. Mais une analyse de l'assembleur a révelé qu'il y avait possibilité de faire mieux.
Avec l'aide des intrinsics (et d'un peu d'assembleur pour forcer GCC), j'ai pu gagner un gain d'un facteur ~ 4 en monocoeurs. (Evidemment, la grille de calcul était séparé sur les différents coeurs).
#MyLife

Bref, il existe encore des cas concrets où l'humain surpasse le compilateur.
# le plus rapide en code simple

Posté par Nicolas Boulay (site web personnel) le 04 octobre 2021 à 19:01. Évalué à 4.

sans utilisé de SSE, c'est le code le plus rapide que j'arrive à faire. Je triche un peu avec le v[16] comme prefetch.
```
size_t find_int_c_unrolled_8(const int k, const int* v, size_t n)
{
size_t i = 0;
int t=0;
for (; n - i >= 8; i += 8,v+=8)
{
t |= v[16];
if (v[0] == k) return i;
if (v[1] == k) return i + 1;
if (v[2] == k) return i + 2;
if (v[3] == k) return i + 3;
if (v[4] == k) return i + 4;
if (v[5] == k) return i + 5;
if (v[6] == k) return i + 6;
if (v[7] == k) return i + 7;
}
volatile int tt =t;
for (; i != n; i++,v++)
if (v[0] == k)
return i;

return n;
}
```

"La première sécurité est la liberté"
- [^] # Re: le plus rapide en code simple
  
  Posté par sjub le 05 octobre 2021 à 09:24. Évalué à 2.
  
  Il est possible de faire de la vecto sans unité vectorielle ! En manipulant des types de taille inférieure à 64 bits, par exemple des int, on peut "caster" le tableau en (int64_t*) donc charger deux int à la fois et faire une seule instruction de comparaison avec un registre contenant deux fois l'int recherché. Cela permet de diviser par deux le nombre d'instructions de comparaison et de chargement, même si on charge finalement la même quantité de données. Pour des opérations simples on doit pouvoir gagner, par contre j'avais testé il y a longtemps pour des instructions arithmétiques pour du traitement d'images, donc en manipulant 8 octets dans un registre 64-bit, mais il faut gérer les risques de dépassement en évitant la propagation des retenues entre les octets et c'était finalement pas efficace. En plus le code était illisible, mais ça peut être bien pour de l'obfuscation !
  - [^] # Re: le plus rapide en code simple
    
    Posté par pulkomandy (site web personnel, Mastodon) le 05 octobre 2021 à 11:51. Évalué à 3.
    
    Je ne vois pas comment on peut tester l'égalité de chaque moitié d'un registre 64bit séparément avec une seule instruction de comparaison non vectorisée.
    
    Au mieux on peut faire un XOR bit à bit, et ensuite il faut regarder si les 32 premiers ou les 32 derniers bits sont tous à 0. Ce qui fait toujours 2 comparaisons.
    - [^] # Re: le plus rapide en code simple
      
      Posté par sjub le 05 octobre 2021 à 14:48. Évalué à 1.
      
      Effectivement, le plus pratique est de faire un XOR avec deux comparaisons. Si on veut quand même supprimer une comparaison il faut ajouter pas mal d'opérations logiques et des masques donc ce n'est plus rentable. Une idée : "replier" les sous parties 32-bit sur elles-mêmes avec des OR et des masques de manières à tout accumuler dans le bit 0 et le bit 32, puis décaler le bit 32 vers la position 1 et on obtient soit 0 si pas trouvé, soit 1 si trouvé en position basse, soit 2 si trouvé en position haute, il ne reste qu'à comparer avec 0 et retourner i+lavaleurcalculée-1. Bon là on n'est plus dans l'optimisation du tout !
    - [^] # Re: le plus rapide en code simple
      
      Posté par Chuck #1 le 09 octobre 2021 à 10:39. Évalué à 2.
      
      En fait, c'est possible de tester avec une seule comparaison non vectorisée. Cf. l'excellent commentaire de gouttegd un peu plus haut et les commentaires dans le code de memchr auquel il fait référence.
      
      Cette signature est publiée sous licence WTFPL
      - [^] # Re: le plus rapide en code simple
        
        Posté par pulkomandy (site web personnel, Mastodon) le 09 octobre 2021 à 23:23. Évalué à 2.
        
        En effet. J'ai trouvé un benchmark qui conclut que ça marche plutôt bien, 3 fois plus rapide que l'implémentation qui teste les octets un par un: https://gist.github.com/nico/2624336
  - [^] # Re: le plus rapide en code simple
    
    Posté par Nicolas Boulay (site web personnel) le 05 octobre 2021 à 13:31. Évalué à 4.
    
    Je devrais tenter, mais je n'y crois pas trop. C'est tout de même un algo totalement memory bound à la base. J'arrive à faire mieux avec __builtin_prefetch(v+i+256).
    
    Il faudrait tester le 64 bits.
    
    "La première sécurité est la liberté"
    - [^] # Re: le plus rapide en code simple
      
      Posté par sjub le 05 octobre 2021 à 15:04. Évalué à 3.
      
      Je n'y crois pas trop moi-même ! Il vaut mieux passer par l'unité SIMD dispo qui est plus large et possède les bonnes instructions.
      
      En plus on peut aussi optimiser les loads : comme on ne fait que lire et qu'on ne réutilise pas les données on va vite remplir le cache pour des tableaux assez grands et donc il faut trouver des lignes dispos pour mettre les nouvelles données ce qui peut prendre un peu de temps. On peut dans ce cas utiliser les loads non temporels via les intrinsics streams (movntdq), c'est à dire qu'on indique au cache qu'il peut évincer sans pitié la ligne de cache que l'on vient juste d'utiliser et ça va un peu plus vite pour trouver de la place dans le cache pour charger de nouvelles données. On retrouve ces instructions notamment dans le code de memcpy.
- [^] # Re: le plus rapide en code simple
  
  Posté par Nicolas Boulay (site web personnel) le 06 octobre 2021 à 20:50. Évalué à 5.
  Je n'arrive pas à faire mieux. __builtin_prefetch(v+256,0,0) qui est le prefetchnta n'est pas plus rapide.
```
    size_t find_int_c_unrolled_8(const int k, const int* v, size_t n)
    {
      size_t i = 0;
       for (; n - i >= 8; i += 8,v+=8)
         {
          __builtin_prefetch(v+256); //54/148
          if (v[0] == k) return i;
          if (v[1] == k) return i + 1;
          if (v[2] == k) return i + 2;
          if (v[3] == k) return i + 3;
          if (v[4] == k) return i + 4;
          if (v[5] == k) return i + 5;
          if (v[6] == k) return i + 6;
          if (v[7] == k) return i + 7;
        }

       for (; i != n; i++,v++)
        if (v[0] == k)
          return i;
       return n;
     }
```
  "La première sécurité est la liberté"
# Les compilateurs et l'optimisation

Posté par sjub le 04 octobre 2021 à 19:36. Évalué à 10.
Bonjour,
Merci pour cette petite expérience. Je travaille pas mal sur l'optimisation de codes/parallélisation et je me méfie toujours de ce que fait le compilateur suite à de nombreuses déconvenues. Mes conclusions (en partie suite aux résultats dans ce papier https://hal.archives-ouvertes.fr/hal-01915529, je recommande le tableau page 8!) :
1. le compilateur n'apporte aucune garantie sur les optimisations : parfois avec -O2 c'est plus rapide qu'avec -O3, parfois c'est avec -Ofast, parfois avec un -march qui ne correspond pas à l'archi de la machine sur laquelle tourne le code, …
2. le compilateur casse parfois les optimisations qu'on essaie de mettre en place -> assembleur…
3. l'autovectorisation ne vectorise pas des cas triviaux mais vectorise des cas complexes sans doute par identification de motifs et remplacement par du code optimisé (un peu comme la boucle for pour copier qui est remplacée par un memcpy), mais dès qu'on modifie un peu le motif, plus personne…
4. l'autovectorisation quand elle produit du code vectorisé ne garantit pas que le code vectorisé soit plus efficace, par exemple sur un traitement d'image, le code "vectorisé" va passer son temps à faire des instructions shuffle/unpack/permute pour réorganiser les données avant de faire quelques calculs puis refaire tout le chemin inverse et parfois c'est plus lent que du code scalaire… mais si on le fait correctement à la main avec des intrinsics on va 3x plus vite ! C'est ce qui a motivé la désactivation de la vecto pour AVX-512, le gain de perf dans de nombreux cas n'était pas suffisant pour contrecarrer la baisse de fréquence.
5. l'autovectorisation n'est pas portable entre architectures (je sais que ce ne sont pas les mêmes instructions mais le processus devrait être un peu indépendant de l'archi), le même compilo va arriver à vectoriser sur x86 en SSE, mais pas en NEON sur Arm, sans utiliser des instructions spécifiques.
6. sur Arm 32-bit j'ai eu une surprise avec une ancienne version de GCC : mes intrinsics étaient convertis en code scalaire mais ça allait 20-30% plus vite que le code scalaire parce que du coup la boucle était déroulée de 4 !
7. parfois l'ajout d'une directive #pragma omp simd bloque l'autovectorisation qui est pourtant faite avec juste -O3.
8. il y a des optimisations qui cassent si on ajoute une petite couche de templates, même juste en utilisant std::vector à la place d'un tableau à la C.
9. j'ai vu des personnes passer énormément de temps à modifier leur code et à espérer que le compilo daigne enfin vectoriser tout seul. Le code ne ressemble plus à rien, on peut espérer gagner 20%, alors qu'en passant par des intrinsics et avec la surcharge des opérateurs on peut vectoriser sans modifier la structure du code et on a un x2 à x5 suivant les archis.
Vivement que Facebook vienne révolutionner tout ça… ou pas ! https://ai.facebook.com/blog/compilergym-making-compiler-optimizations-accessible-to-all/
- [^] # Re: Les compilateurs et l'optimisation
  
  Posté par Philippe F (site web personnel) le 06 octobre 2021 à 15:28. Évalué à 2.
  
  Et il faut ajouter:
  
  10- Des optimisations qui marchent super bien sur une version donnée du compilateur peuvent ne plus marcher du tout sur la version suivante.
# Efficacité - Borne sup

Posté par sjub le 05 octobre 2021 à 10:11. Évalué à 2.

Dans le cas du find, on peut raisonnablement se dire que la performance est limitée par la bande passante mémoire, on est dans un scénario memory-bound, car le processeur doit charger beaucoup de données et ne fait que peu de calcul dessus, en tout cas pas suffisamment pour recouvrir le temps d'attente de la donnée. Du coup est-ce qu'on pourrait avoir des infos sur la mémoire utilisée sur la machine pour déterminer une bande passante max ?

D'après les données, le tableau fait 16M de int donc 64Mo, l'élément à trouver est en dernière position donc on traverse tout, et le temps pour la version optimisée SSE est d'environ 5ms, ce qui donne environ un débit de 12,8Go/s. Le i5-3210M ça doit être du Sandy Bridge avec de la DDR3 12800, donc on attendrait la perf max ! mais c'est en simple canal et il faudrait vérifier la config mémoire pour voir si c'est pas du double canal.
- [^] # Re: Efficacité - Borne sup
  
  Posté par Julien Jorge (site web personnel) le 05 octobre 2021 à 21:08. Évalué à 2.
  
  La machine est celle-ci, encore plus vieille que je ne le pensais !
  
  Donc niveau RAM on a de la DDR3L SDRAM à 1600 MHz, mais je n'ai aucune idée du débit correspondant.
  - [^] # Re: Efficacité - Borne sup
    
    Posté par sjub le 05 octobre 2021 à 22:22. Évalué à 3.
    
    En fait c'est pas 1,6GHz mais 1,6G transactions de 64 bits donc 8 octets (la fréquence réelle est 800MHz mais on peut faire 2 transactions par cycle), ce qui donne le débit de 12,8Go/s, plus de détails ici : https://en.wikipedia.org/wiki/DDR3_SDRAM.
    Comme la mémoire de 8Go est soudée je pense que ce n'est qu'une barrette, on a un seul canal, donc on arrive bien à la bande passante maximale avec le code optimisé. Pas la peine d'essayer de trafiquer encore le code pour gagner des perfs ! Bon après en passant en AVX on peut faire moins d'instructions et donc sans doute pouvoir réduire la fréquence et baisser la conso (j'ai fait des expériences sur Arm et le passage d'un code scalaire à NEON permet de réduire pas mal la conso en baissant la fréquence tout en gardant les performances) ou avoir plus de ressources disponibles pour d'autres processus.
    - [^] # Re: Efficacité - Borne sup
      
      Posté par gUI (Mastodon) le 06 octobre 2021 à 08:22. Évalué à 2. Dernière modification le 06 octobre 2021 à 08:23.
      
      Du coup on peut essayer de jouer avec le cache ? Lancer 1000x le test par exemple (pour noyer dans l'épaisseur du trait la moindre perfo du 1er jet) ?
      
      En théorie, la théorie et la pratique c'est pareil. En pratique c'est pas vrai.
      - [^] # Re: Efficacité - Borne sup
        
        Posté par sjub le 06 octobre 2021 à 09:31. Évalué à 4.
        
        Ça dépend ce que l'on veut mesurer : si le jeu de données ne tient pas dans le cache on va de toute façon se heurter au coût de l'éviction du cache avec un "mov" standard, qui sera plus faible si on fait un "movntdq" et on peut mesurer la bande passante mémoire max, sinon si le jeu de données tient dans le cache et qu'on fait plusieurs itérations dessus on va mesurer le débit des caches et là il vaut mieux utiliser un "mov" pour que les données soient laissées en cache, sinon avec "movntdq" certaines pages auront tendance à être évincées et le débit va baisser.
        
        Au passage j'ai une petite remarque sur la bande passante du processeur M1 : en lecture je mesure environ 60Go/s (c'est énorme !) et en écriture "seulement" 30Go/s, donc c'est pas symétrique contrairement aux systèmes habituels. Je n'ai pas trouvé de détails sur le pourquoi du comment (et Apple n'est pas très bavard sur son processeur) donc si quelqu'un a une info là dessus je prends !
        
        [^] # Re: Efficacité - Borne sup
        
        Posté par Nicolas Boulay (site web personnel) le 06 octobre 2021 à 10:47. Évalué à 4.
        
        Je pense que la mémoire utilisé pour le cache à simplement 2 ports de lecture pour un seul port d'écriture. Dans un ASIC, les 2 ports sont séparés. Dupliquer les ports de lecture est plus facile que pour l'écriture.
        
        "La première sécurité est la liberté"
# Un autre benchmark

Posté par pulkomandy (site web personnel, Mastodon) le 05 octobre 2021 à 11:58. Évalué à 6.

Celui-ci ajoute d'autres implémentations: la fonction memchr en C est équivamente, et il y a différentes implémentations dans différentes biblothèque C. Certaines plus lentes et certaines plus rapides que l'implemenation "naive" avec une simple boucle.

https://gms.tf/stdfind-and-memchr-optimizations.html

Cela a donné lieu à une discussion sur la mailing list du musl: https://www.openwall.com/lists/musl/2016/09/18/3 avec des liens supplémentaires vers d'autres cas ou des libraries C proposent une implémentation "optimisée" qui est en fait plus lente que l'implémentation triviale en C. D'ou la conclusion: on peut faire confiance au compilateur pour optimiser le code simple et lisible de façon pas trop mauvaise. Même si le compilateur n'est pas parfait et que les fonctions de la glibc sont très génériques, et souvent on peut écrire du code plus efficace, ce n'est pas la peine d'essayer de le faire systématiquement.
- [^] # Re: Un autre benchmark
  
  Posté par fearan le 05 octobre 2021 à 13:54. Évalué à 8.
  
  De toutes façons, tenter d'optimiser manuellement le code 'à priori' n'est que rarement utile;
  
  Autant il faut bien sélectionner la structure de donnée, et la façon d'y accéder, faire attention à pas recalculer systématiquement des valeurs ou faire des allocations dynamiques, utiliser les bons algorithme, mais aller manuellement dérouler des boucles, va plus desservir qu'autre chose.
  
  Une fois que le code tourne, on peut regarder les goulots d'étranglement et remédier au cas par cas (si nécessaire, car l'optimisation nuit généralement à la maintenabilité et à l'évolutivité du code).
  
  Il ne faut pas décorner les boeufs avant d'avoir semé le vent

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.