Discussion :

[Jean-Marc.Bourguet]

J'ai toujours le meme ordre, en optimise comme en debug, sur xeon (gcc), core 2 duo (gcc), sparc (sun cc), Alpha (gcc). Sur power pc (IBM xlc) en debug la methode de fearyourself est meilleure que la tienne, en optimise c'est l'inverse. Les rapports varient suivant l'architecture et le degre d'optimisation.

[stephl]

OK, merci. Je ne pensais pas qu'il pouvait y avoir de telles différences.

[Jean-Marc.Bourguet]

Une idee, c'est quoi RAND_MAX chez toi? Ta methode est la seule qui va dependre largement de la valeur des donnees. Si tu as un RAND_MAX a 2^15-1, elle est plus rapide qu'avec un RAND_MAX a 2^31-1 (comme sur les machines ou j'ai regarde)

[stephl]

Une idee, c'est quoi RAND_MAX chez toi? Ta methode est la seule qui va dependre largement de la valeur des donnees. Si tu as un RAND_MAX a 2^15-1, elle est plus rapide qu'avec un RAND_MAX a 2^31-1 (comme sur les machines ou j'ai regarde)

Bien vu:

Code :

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

#define RAND_MAX 0x7FFFU

Serait-ce donc l'explication?

[Jean-Marc.Bourguet]

Bien vu:

Code :

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

#define RAND_MAX 0x7FFFU

Serait-ce donc l'explication?

Adapate nos codes en fonction des valeurs maximales reelles, et mesure... Il n'est pas impossible que meme adapte ils soient plus lents. Puisque ton code depend des valeurs, si tu veux faire une vraie mesure, il faut aussi te definir une distribution (si ca tombe, la distribution lineraire que rand() correspond a celle de l'application, si ca tombe ce n'est pas le cas...) Le code par dicotomie est celui qui a le moins de variation, ce qui peut etre un avantage aussi.

Je l'aurais ecrit autrement (non teste comme a chaque fois -- au fait tu as verifie que les codes faisaient bien le meme calcul?):

Code :

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

1
2
3
4
5
6
7
8
9
10
11
  min = 0;
  max = 32;
  while (min+1 != max) {
      int mid = (min + max) / 2;
      if (nbr >= (1UL << mid)) {
          min = mid;
      } else {
          max = mid;
      }
  }
  return min;

Mais c'est une autre histoire.

[stephl]

J'ai déjà vérifié et nos 3 fonctions donnent les mêmes résultats.

[stephl]

Je pense que votre explication (RAND_MAX) était la bonne. Plutôt qu'adapter vos codes à une plage de valeurs sur 15 bits, j'ai changé de générateur aléatoire, le nouveau pouvant produire sur 31 bits selon une loi uniforme. Les résultats sont maintenant conformes aux vôtres. Donc, même avec (seulement) 32 bits, vos méthodes surpassent largement la mienne.

Code :

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

1
2
3
MÚthode fearyourself: 77.296 s
MÚthode Jean-Marc Bourguet: 54.500 s
MÚthode stephl: 102.641 s

[NiamorH]

Et si maintenant vous interchangez l'ordre des tests, trouvez vous une différence ? Parce que, souvent les tests de vitesse que j'ai pu faire se sont parfois avérés inversés selon l'ordre dans lesquels je les faisais. J'ai pas d'exemple sous la main mais ça m'est arrivé plusieurs fois.
Je ne suis pas un expert non plus en matiere de benchmark et de comment on doit s'y prendre.

[stephl]

Et si maintenant vous interchangez l'ordre des tests, trouvez vous une différence ?

Logiquement, tel que le code est écrit, il ne devrait pas y en avoir. J'ai d'ailleurs fait le test et il n'y en a pas.

Parce que, souvent les tests de vitesse que j'ai pu faire se sont parfois avérés inversés selon l'ordre dans lesquels je les faisais.

Cela signifie qu'il y a quelque chose dans votre code dépendant de l'ordre d'exécution. Ici, ce qui est comptabilisé dans le temps d'exécution n'est que du temps de calcul. Le problème que vous suggérez peut se manifester si votre code comptabilise aussi un chargement en mémoire ou quelque chose dans ce genre.

[Jean-Marc.Bourguet]

Donc, même avec (seulement) 32 bits, vos méthodes surpassent largement la mienne.

Il me semble que le demandeur savait que normalement les donnees etaient limitees a 12 bits. On peut facilement biaiser la recherche dicothomique pour mieux traiter ces cas; ma methode est moins sujette a une telle manoeuvre.

[stephl]

Il me semble que le demandeur savait que normalement les donnees etaient limitees a 12 bits. On peut facilement biaiser la recherche dicothomique pour mieux traiter ces cas; ma methode est moins sujette a une telle manoeuvre.

En tout cas, merci pour votre explication qui - me semble-t-il - était la bonne.