Discussion :

[Guesset]

Bonjour Luc Hermitte,

...Pour le modulo, à nouveau ce que je cherche à montrer c'est que les compilateurs vont générer exactement le même asm si on utilise `%` ou si on calcule `a - (a/b) * b` depuis du C++...

Je vais un peu pinailler .

Cet exemple n'est pas complet. Le code a - (a/b) * b n'a jamais été intéressant. Dès le départ, la division (monde Intel) donnait le quotient et le reste (le modulo) dans des registres différents. Alors a % b générait 1 division tandis que a - (a/b) * b demandait 1 division, 1 multiplication et 1 soustraction.

En revanche, le code q = a / b; r = a % b; (alors 2 divisions) était effectivement remplacé par q = a/b; r = a - q*b (1 division, 1 multiplication et 1 soustraction - intéressant car la division est beaucoup plus coûteuse que la multiplication). Aujourd'hui, pour peu que les calculs de q et r ne soient pas trop distants l'un de l'autre, ces deux instructions ne génèrent que 1 division dont elles se partagent les résultats. Utiliser DivMod évite de prendre le risque de perdre cette optimisation du compilateur.

Salut

[Luc Hermitte]

Re,

Effectivement, quand je fais référence à ce que j'ai écrit, c'est en contexte que l'on a aussi calculé a/b en vue de l'exploiter également

Du coup, si on craint que le compilo ne sache pas optimiser (instructions dans des fonctions différentes?), le standard offre aussi `std::div`

[serge17]

# Luc Hermitte

Par curiosité, j'ai regardé les implémentations de libstdc++ et de libc++.

j'ai essayé mais je n'ai pas trouvé comment voir ces implémentations

# tous
J'ai utilisé un benchmark en ligne (Quick C++ Benchmark) pour comparer mon gcd binaire et std::gcd

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
#include <numeric>
 
uint64_t gcd64(uint64_t u, uint64_t v)
{
   if(u == 0) return(v);
   if(v == 0) return(u);
   int k = __builtin_ctzll(u | v);
   u >>= __builtin_ctzll(u);
   v >>= __builtin_ctzll(v);
   // now u and v are odd
   while( u != v ){
      if(u > v){
         u -= v;
         u >>=__builtin_ctzll(u);
      }else{
         v -= u;
         v >>= __builtin_ctzll(v);
      }
   }
   return(u << k);
}
 
static void std_gcd(benchmark::State& state) {
  uint64_t u, v, w;
  for (auto _ : state) {
    w = std::gcd(u,v);
    benchmark::DoNotOptimize(w);
  }
}
BENCHMARK(std_gcd);
 
static void bin_gcd(benchmark::State& state) {
 uint64_t u, v, w;
  for (auto _ : state) {
    w = gcd64(u,v);
    benchmark::DoNotOptimize(w);
  }
}
BENCHMARK(bin_gcd);

Sur ce benchmark, le binaire est 20% plus rapide que le std

Une bizarrerie avec Clang

Je n'ai pas testé nanobench ; il n'est pas en ligne apparemment.

Mes tests perso donnent des résultats très différents (option O3)
Avec des données en 16 bits, 32 bits et 64 bits le gcd binaire est respectivement
8.8 fois, 7.4 fois et 6.4 fois plus rapide que std
Pour calculer les temps, j'utilise __rdtsc(). Pour un couple de valeurs (u, v) donné, Je boucle 10000 fois pour obtenir une valeur stable (j'ai essayé avec 1000000, ça ne change rien) et je boucle avec 10000 couples aléatoires (on peut faire plus mais c'est plus long !). Bon c'est du bricolage mais on est loin des 20% !

[serge17]

Update : j'ai chargé la dernière version de Code::Blocks et j'en ai profité pour changer de compilateur (MinGW_w64). Mon bricolage est cette fois plus conforme aux 20% du benchmak.
Je passe ce fil en "Résolu".

Par contre, si ceux qui m'ont si gentiment répondu pouvait jeter un coup d'oeil à mon nouveu fil "Problème de compilation avec l'option O3" ce serait super.

Quoi qu'il en soit, grand merci à vous tous.