AeriesGuard Le Refuge des Créateurs Minecraftiens !

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;
}