L'idée folle m'a prise de lancer un calcul pour 20 étages

Je présume que Sbire peut me faire une estimation pifométrique en se basant sur la vitesse du tachyon dans la soupe et le nombre de trous dans la passoire.

Tu enfonces ton propre record du monde ? A quand l'homologation ?

Et voilà l'heure de vérité.

World Of Warcraft a eu la curieuse idée de freezer sans que je puisse revenir au bureau

Après avoir lutté péniblement pour retrouver mon bureau windows quel ne fut pas ma surprise de découvrir une alarme console : kheopful_c avait (enfin!) trouvé quelque chose

le TSC de mon eeePC s'approche lentement de la barrière des 9 Péta.

Une fois arrivé au seuil psychologique des 9,5 Péta j'arrête tout

J'avais le secret espoir que Delphi 5 repasse devant le C grâce à de l'assembleur inline.

J'y ai travaillé plusieurs journées sur différentes parties du programme et même sur le programme en quasi-totalité. Écriture, benchmark, réécriture, re-benchmark, réécriture, re-benchmark ..

À aucun moment je n'ai approché la performance de gcc -Os.

Explications :

J'arrive à registeriser mieux que les compilateurs. Malheureusement ça ne sert pas à grand chose dans ce cas précis puisque la très grande majorité des boucles ne s'exécute que peu de fois. Si une boucle s'exécute 10 fois c'est qu'elle a trouvé une pyramide de hauteur 10 ce qui relève plus de l'exception que la règle.

Tant que je ne fais pas du 100% assembleur je dois sauvegarder 3 registres ce qui me pénalise de 6 cycles :

asm
  push esi
  push edi
  push ebx
  ... 
  pop ebx
  pop edi
  pop esi
end;

Depuis la génération des Pentiums il y a au moins 2 ALUs (Arithmetic & Logic Unit) par cœur d'exécution. Ça signifie que le cœur peut exécuter 2 instructions en 1 seul cycle si l'une ne dépend pas de l'autre. Or j'ai l'habitude d'écrire du code assembleur à l'ancienne, où chaque instruction dépend de l'instruction précédente. Conséquence: je n'utilise qu'une seule ALU au lieu de deux. Pour utiliser les deux ALUs il faut entrelacer les instructions : une instruction ne doit pas dépendre de la dernière instruction mais de l'avant dernière. Drôle de style, et à ce petit jeu de jonglage gcc est meilleur que moi.

Conclusion :  même si j'arrive à faire aussi bien que gcc -O3 il devient improbable que je fasse aussi bien ou mieux que  gcc -Os . Donc j'abandonne.

Je viens de remarquer que Kheopful a su tester plus de 101!* combinaisons en moins de 8 mois ! C'est à dire environ 98!  combinaisons éliminées chaque seconde, ce qui nous amène à un constat : L'algorithme est très efficace.

Maintenant, pour une pyramide de hauteur 12, si on prend une augmentation du nombre de trous comparable aux précédentes, disons 42 (ce qui minore assez bien le résultat), on a 120! combinaisons possibles, à grosse vue de pif, disons que l'algorithme pourra éliminer deux-mille milliards de milliards de fois plus de  combinaisons chaque seconde (environ 109!, peut-être je le sous-estime, je ne suis point spécialiste), et considérant un réseau de 5 ordinateurs quadricoeurs 6 fois plus puissants que le précédent record , on pourra espérer un résultat d'ici 16! années, ce qui reste raisonnable, seulement 1000 fois l'âge de l'univers.

Après, j'ai sans doute un peu sous-estimé la puissance de l'algorithme de Spiceguid, disons qu'il sera en pratique  18 milliards de fois plus rapide que ce que j'espère, ce qui devient plus rassurant : Seulement 23 ans de calcul pour y aboutir.

En fait, avec les méthodes qui SpiceGuid m'a montré, c'est sans doute encore plus performant ! Une progression de la quantité de calcul qui n'est sans doute pas linéaire... peut être que sa méthode sera non pas 18 mais 240000 milliards de fois plus rapide que mon estimation pessimiste de tout à l'heure... Ce qui ramènera le temps de calcul à seulement 20 petites journées de travail. Remarquez, si on veut utiliser nos ordinateurs durant ce temps de 20 jours, on devra sans doute brider la consommation à 25% des quatre coeurs pour rester confortables, ça porte le total de jours à 80.

Néanmoins, je rappelle que nous nous sommes basés sur un comptage des combinaisons à la base, ce qui fausse un peu les calculs... Disons que  nos calculs sont à 99% faux , on fera donc entre 30 heures et 80 jours de calculs pour 42 trous, et on est très optimistes, on prendra 30h comme valeur finale.

 On parie sur 30h pour arriver au record de 12 !

(Après, faut que le nombre de trous requis tombe sur 42, imaginez qu'il tombe sur 50, ça nous ferait entre 7 ans et 800 ans de calcul supplémentaire, au moins.)

Ces calculs se basent sur la méthode PifOMetric© Et ne sont pas à prendre en compte.

Cordialement,

Udo.

Toujours le même code en OCaml cette fois.

(*
 * ocamlopt -unsafe -o kheopful kheopful.ml
 *)

let n=ref 0 and p=ref 0 and s=ref 0 and t=ref 0

let rec pyramid q l m a b c =
  let r=ref 0 and d=ref 0 and i=ref 0 and j=ref 0 and u=ref 0 and v=ref 0 in
  if q <= !p then begin
    r := l+1;
    while !r <= !n do
      d := a.(!r); i := l; j := l-q+1;
      while b.(!d) > l && !i < m do
        incr i; incr j; d := abs (!d - a.(!j));
      done;
      if !i = m then begin
        d := a.(!r); i := l; j := l-q+1;
        while b.(!d) > !i && !i < m do
          incr i;
          v := a.(!i); u := b.(!d); c.(!i) <- !v;
          a.(!i) <- !d; a.(!u) <- !v;
          b.(!d) <- !i; b.(!v) <- !u;
          incr j; d := abs (!d - a.(!j));
        done;
        if !i = m then pyramid (q+1) m (m+q+1) a b c;
        while !i > l do
          v := a.(!i); d := c.(!i); u := b.(!d);
          a.(!i) <- !d; a.(!u) <- !v;
          b.(!d) <- !i; b.(!v) <- !u;
          decr i;
        done;
      end;
      incr r;
    done;
  end else begin
    print_char '\r';
    i := 1;
    while !i <= !p do
      print_int a.((!i * !i - !i+2)/2);
      print_char ' '; incr i;
    done;
    print_newline ();
    if !s > 0 then (print_char '\r'; print_int !t);
  end

let () =
  print_endline "Copyright© 2005 Damien Guichard";
  p := (print_string "How many levels? "; read_int ());
  if !p < 1 then exit 1;
  let x = print_string "How many holes ? "; read_int () in
  n := !p*(!p+1)/2+x;
  s := (print_string "What seed value? "; read_int ());
  if !s <= 0 or !s > !n then exit 1;
  let id i = i in
  let a = Array.init (!n+1) id
  and b = Array.init (!n+1) id
  and c = Array.init (!n+1) id
  in
  t := !s;
  while !t <= !n do
    print_char '\r'; print_int !t;
    a.(1) <- !t; b.(!t) <- 1;
    pyramid 1 0 1 a b c;
    incr t;
  done;
  print_string "\r    \r"

Pourquoi cette fièvre du benchmark ? Pourquoi ne pas envisager une structure distribuée ?

Dans le genre, tu développe une application serveur qui se charge d'attendre que tous les participants soient présents, qui ensuite découpe les combinaisons à traiter en blocs de diverses tailles en fonction de la puissance de chaque client, puis qui alloue à chaque client son bloc, le client les traites et si il trouve il renvoie une réponse que le serveur se fera un plaisir de tester.

Au lieu de perdre du temps à gagner 10% de vitesse sur un ordinateur, plutôt s'y mettre à plusieurs. Je suis prêt à mettre à disposition ma machine, carado sans doute, peut-être Aka et Ertaï, au pire j'ai du bon d'achat chez gandi, je peux te louer 48h une trentaine de clients (ou 96h une quinzaine), j'ai moi-même envie de savoir jusqu'où tu peux aller.

En plus, une infrastructure distribuée de calcul pour résoudre un problème combinatoire difficile, ça sera top sexy sur ton CV.

And the winner is...

Le benchmark se fait avec les paramètres 8 8 1 , le résultat est un triangle absolu à 8 étages.

Le temps est donné au cycle d'horloge près, même si bien entendu la précision de la mesure n'est pas aussi élevée. Le processeur utilisé est un Merom T5500 . L'activité est réduite pendant le benchmark. De plus même si activité il y a elle a tendance (j'espère) à utiliser le cœur n°2. J'estime que 100 milliards de cycles est un nombre raisonnable pour ce calcul.

Plus de 100 milliards de cycles : pouce rouge.

Moins de 100 milliards de cycles : pouce vert.

Delphi 5 (entiers Cardinal ) : 82 551 389 650

Delphi XE2 (entiers Cardinal ) : 81 711 650 550

OCaml 3.12.1 (entiers 31 bits ) : 119 256 268 720

GCC -O3 ( uint32_t ) : 80 931 256 300

GCC -Os ( uint32_t ) : 75 895 135 520

GCC -Os ( int32_t ) : 77 006 505 990

Le test confirme que, quelque soit le langage, les entiers non-signés sont légèrement plus rapides que les entiers signés. C'est aussi valable pour Delphi même si le benchmark avec Integer n'est pas présenté ici.

OCaml arrive bon dernier . Le calcul intensif n'est pas son domaine de prédilection. OCaml est fortement pénalisé par le fait qu'il utilise 1 bit pour le ramasse-miettes. Donc il perd du temps à faire du calcul sur des entiers signés en 31 bits .

Pour GCC l'option -Os est toujours meilleure que l'option -O3 . Sans doute qu'en compactant le code on lui permet d'être plus souvent présent dans le cache de niveau 1.

Les sources OCaml et C sont portables sur Linux + Windows98 et supérieurs (via Mingw32).

La source Delphi n'est portable que sous Windows ( désolé je n'ai pas testé la compatibilité avec freepascal ).

L'exécutable Delphi XE2 ne fonctionne pas sous Windows98 (le seul OS compatible avec LEGO Creator ). Toutefois le code Delphi est portable sous Windows98 jusqu'à Delphi 7 inclus.

edit: merci à carado qui m'a signalé un segfault tout à la fin du programme en C. Ce segfault a été corrigé depuis. N'empêche qu'il perturbait la mesure de performance. D'où un nouveau record pour la version C :

GCC -Os ( uint32_t ) : 71 104 007 900 cycles

À comparer aux 119 256 268 720 de la version originale en OCaml, on a quand même fait un progrès appréciable

Le même code traduit directement en C ( segfault)

Le même code traduit directement en C.

// gcc -Os -o kheopful kheopful.c
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

uint32_t *a,*b,*c;
uint32_t n,p,s,t;
uint32_t x;

void pyramid(const uint32_t q,const uint32_t l,const uint32_t m)
{
  uint32_t r,d,i,j,u,v;
  if (q <= p) {
    r = l+1;
    while (r <= n) {
      d = a[r]; i = l; j = l-q+1;
      while (b[d] > l && i < m) {
        i++; j++; d = abs (d - a[j]);
      };
      if (i == m) {
        d = a[r]; i = l; j = l-q+1;
        while (b[d] > i && i < m) {
          i++;
          v = a[i]; u = b[d]; c[i] = v;
          a[i] = d; a[u] = v;
          b[d] = i; b[v] = u;
          j++; d = abs (d - a[j]);
        };
        if (i == m) pyramid(q+1,m,m+q+1);
        while (i > l) {
          v = a[i]; d = c[i]; u = b[d];
          a[i] = d; a[u] = v;
          b[d] = i; b[v] = u;
          i--;
        };
      };
      r++;
    }
  } else {
    printf("\r");   
    for (i = 1; i <= p; i++) printf("%u ",a[(i*i-i+2)/2]);
    printf("\n");   
    if (s > 0) printf("\r%u",t);
  }
}

uint32_t* alloc(uint32_t max)
{
  uint32_t* result;
  uint32_t i;
  result = calloc(max+1,sizeof(uint32_t));
  for (i = 0; i <= max; i++) result[i] = i;
  return result;
}

int main(void)
{
  printf("Copyright© 2005 Damien Guichard\n");
  printf("How many levels? "); scanf("%u",&p);
  if (p < 1) exit(1);
  printf("How many holes ? "); scanf("%u",&x);
  n = p*(p+1)/2+x;
  printf("What seed value? "); scanf("%u",&s);
  if (s == 0 || s > n) exit(1);
  a = alloc(n);
  b = alloc(n);
  c = alloc(n);
  for (t = s; t <= n; t++) {
    printf("\r%u",t);   
    a[1] = t; b[t] = 1;
    pyramid(1,0,1);
  }; 
  printf("\r    \r"); 
  return 0;
}

Oh oh un programme de SpiceGuid que je serais capable de relire.

Pour ma part je possède Delphi XE2 soit une version extrêmement supérieure à Delphi 5, tu pourrais éventuellement profiter des améliorations du compilateur pour peut-être gagner en performance. Néanmoins si tu as déjà écrit une bonne partie du code en assembleur, je doute que ce soit le cas.

Bon alors c'est plus facile à dire qu'à faire

Le benchmark est réalisé au cycle d'horloge cpu près grâce à Printtsc .

Après réflexion mon langage de choix est Delphi 5 .

Motivations :

Delphi 5 génère du code win32 et Windows est mieux équipé que Linux en matière de drivers pour la gestion de l'alimentation.

Possibilité d'intégrer du code x86 en ligne avec un débogage asm interactif.

Au début, idée géniale (gros espoir). Résultat : hausse du temps de calcul de 25% :'(

Puis autre idée plus modeste. Résultat : baisse du temps de calcul de 4‰. Pas grand chose mais mieux que rien du tout

 Bon j'ai rien d'autre à faire alors je vais vous expliquer mon idée modeste :

À priori, et ça ne vous étonnera pas beaucoup, le programme passe une grande partie de son temps à calculer des valeurs absolues. C'est la raison pour laquelle j'utilisais le type Integer , parce qu'il est signé, contrairement à Cardinal .

Mais où sont ces nombres négatifs ? Vous en voyez vous des nombres négatifs En vérité il n'y en a aucun. D'où mon idée folle : utiliser Cardinal au lieu de Integer .

Alors vous allez me dire mais comment calculer une valeur absolue sans les nombres négatifs

Hé bien en fait ça ne pose aucun problème. Faites le test.

var c,ca,cb : Cardinal;
ca := 7; cb := 3;
c := Abs (cb - ca);    // oui ça fonctionne, même ici où ca > cb

Non seulement ça fonctionne mais c'est plus rapide car il n'y a jamais à faire un saut qui vide le pipeline du cpu

Si vous ne comprenez rien ni comment ni pourquoi ça n'est pas grave, dites vous que c'est une astuce de gosu .

Tout ça c'était pour gagner 4‰ La vache, je sens que ça va pas être facile

Je vais tenter d'améliorer mon programme et probablement tirer parti du multi-cœur pour battre mon record

Par contre je ne dévoilerai pas le résultat, seulement le nombre d'étages atteint et le plus grand entier de la ou des pyramide(s).

La motivation pour ce petit secret c'est que j'ai besoin de booster mon CV.

@xila Oui j'ai transféré le contenu de mon (ancien) blog (sur pagesperso-orange.fr) sur AG.

De cette façon je n'ai plus à en assurer la maintenance (merci Ertaï qui travaille pour nous tous).

@Azrock C'est bien moi l'auteur du programme Kheopful donc je suis capable de t'expliquer comment il fonctionne. Il n'y a pas de formule magique. Il essaye tous les arrangements A(n,m) sur la ligne de base de la pyramide puis il remplit le reste en vérifiant qu'aucun entier n'est utilisé plus d'une fois. Plus 1 ou 2 super-astuces trop compliquées à expliquer.

Les trois dernières pyramides à 11 étages ont quand même demandé 3 mois de calcul 24/24h sur un portable PentiumIII sous-cadencé à 500Mhz (la fréquence constructeur étant de 750Mhz mais pour le 24/24h j'ai préféré prendre mon temps plutôt que prendre un risque de surchauffe).

Azrock a écrit :

J'ai étendu la définition, sinon il serait impossible de trouver des triangles absolus avec n > 5.

Spiceguid je ne sais pas si tu as écrit l'article sur tuttisoft.pagesperso-orange.fr, mais je pense qu'il valait le coup d'être cité

Et tu as oublié un détail plutôt important, c'est que le triangle absolu, d'après ce que j'ai compris, doit comporter des entiers compris entre 1 et (n²+n)/2, où n représente le nombre d'étage

J'aimerai savoir s'il y a un moyen de calculer d'avance pour pas retomber plusieurs fois sur le même nombre, enfin de savoir par quels nombres commencer la pyramide? J'imagine que le logiciel ne fait pas qu'essayer jusqu'a ce que ça marche et qu'il y a une formule ou autre pour les faire, et elle aurait surement pas mal sa place dans l'article.