Fibonacci-Benchmark

[drohne235]

Mal eine Frage: Muss der Fibonacci-Benchmark rekusiv sein? Iterativ ist es doch viel schneller. Irgendwo muss es doch aber vergleichbar bleiben!? Hab mal google befragt, aber oft werden beide Versionen angegeben.

In Forth sieht die iterative Version so aus:

Code: Alles auswählen

\ ( n -- f ) berechnet die nte fibonacci-zahl
: fib 
  0 1 rot 0 do over + swap loop drop ;

\ benchmark über n fibonacci-zahlen
: fibo-bench
  1+ 1 do
    i ." fibo(" . ." ) = "
    i cnt COG@ swap fib cnt COG@ swap .
    swap - ." , ticks : " . 
    cr 
  loop ;

Und das Ergebnis:

Code: Alles auswählen

Prop0 Cog2 ok
decimal 40 fibo-bench hex
fibo(1 ) = 1 , ticks : 2416
fibo(2 ) = 1 , ticks : 3232
fibo(3 ) = 2 , ticks : 4048
fibo(4 ) = 3 , ticks : 4864
fibo(5 ) = 5 , ticks : 5680
fibo(6 ) = 8 , ticks : 6496
fibo(7 ) = 13 , ticks : 7312
fibo(8 ) = 21 , ticks : 8128
fibo(9 ) = 34 , ticks : 8944
fibo(10 ) = 55 , ticks : 9760
fibo(11 ) = 89 , ticks : 10576
fibo(12 ) = 144 , ticks : 11392
fibo(13 ) = 233 , ticks : 12208
fibo(14 ) = 377 , ticks : 13024
fibo(15 ) = 610 , ticks : 13840
fibo(16 ) = 987 , ticks : 14656
fibo(17 ) = 1597 , ticks : 15472
fibo(18 ) = 2584 , ticks : 16288
fibo(19 ) = 4181 , ticks : 17104
fibo(20 ) = 6765 , ticks : 17920
fibo(21 ) = 10946 , ticks : 18736
fibo(22 ) = 17711 , ticks : 19552
fibo(23 ) = 28657 , ticks : 20368
fibo(24 ) = 46368 , ticks : 21184
fibo(25 ) = 75025 , ticks : 22000
fibo(26 ) = 121393 , ticks : 22816
fibo(27 ) = 196418 , ticks : 23632
fibo(28 ) = 317811 , ticks : 24448
fibo(29 ) = 514229 , ticks : 25264
fibo(30 ) = 832040 , ticks : 26080
fibo(31 ) = 1346269 , ticks : 26896
fibo(32 ) = 2178309 , ticks : 27712
fibo(33 ) = 3524578 , ticks : 28528
fibo(34 ) = 5702887 , ticks : 29344
fibo(35 ) = 9227465 , ticks : 30160
fibo(36 ) = 14930352 , ticks : 30976
fibo(37 ) = 24157817 , ticks : 31792
fibo(38 ) = 39088169 , ticks : 32608
fibo(39 ) = 63245986 , ticks : 33424
fibo(40 ) = 102334155 , ticks : 34240
Prop0 Cog2 ok

Ist da irgendwas falsch dran?

[quix]

Die Ahnung hab ich nicht, aber die Ergebnisse stimmen. Da es aber ein Benchmark-Test ist, ist ja die Zeit relevant, in der der Test durchgeführt wird. Wie misst Du die?

[drohne235]

Die Ahnung hab ich nicht, aber die Ergebnisse stimmen. Da es aber ein Benchmark-Test ist, ist ja die Zeit relevant, in der der Test durchgeführt wird. Wie misst Du die?

In der folgenden Zeile wird vor und nach dem Aufruf des Wortes zur Berechnung der entsprechenden Fibonacci Zahl der Systemcounter ausgelesen und auf den Stack gelegt. Im folgenden wird von beiden Werten die Differenz gebildet, was die Anzahl der entsprechenden Systemticks ergibt.

Code: Alles auswählen

    i cnt COG@ swap fib cnt COG@ swap .

[josto]

Mal eine Frage: Muss der Fibonacci-Benchmark rekusiv sein? Iterativ ist es doch viel schneller.

Ich denke nicht, dass dies rekursiv sein muss. Nur wenn man Ergebnisse vergleicht, sollte der selbe Algorithmus verwendet werden.
Wenn ich den Benchmark bei SmallC in einer while-Schleife ausführe, sind die Ergebnisse auch deutlich besser (fibo(10 ) war bei ca. 10400). Die rekursive Variante zeigt eher, wie gut/schlecht ein System mit dem Stack klarkommt.
Deshalb knoble ich zur Zeit auch über eine andere VM, welche weniger Platz benötigt, so dass auch der Stack im COG Platz hätte (kleines Speicher Modell). Damit wären die Ergebnisse deutlich besser.

[josto]

Auch ein nettes Programm: Türme von Hanoi

Code: Alles auswählen

/*
 * The Towers Of Hanoi
 * C
 * Copyright (C) 1998 Amit Singh. All Rights Reserved.
 *
 * Tested with, ah well ... :)
 */

#include <P8X32A.h>
#include <stdio.h>

#define FROM	1
#define TO	3
#define USING	2

dohanoi(N, from, to, using)
int N, from, to, using;
{
  if (N > 0) {
    dohanoi(N-1, from, using, to);
    /* printf ("move %d --> %d\n", from, to); */
    dohanoi(N-1, using, to, from);
  }
}

main()
{
  int i, t1, t2;

  sleep(CLKFREQ);
  printf("Towers of Hanoi\n");
  for(i=3; i<20; i++)
  {
    t1 = clock();
    dohanoi(i, FROM, TO, USING);
    t2 = clock();
    printf("hanoi(%u) = %u ms, (%u)\n", i, (t2-t1)/(CLKFREQ/1000), t2-t1);
  }
  printf("Habe fertig.");
}

Ist auch massiv rekursiv.

PS: Ha'noi heißt übrigens im Schwäbischen: "Nein"

[yeti]

Ist da irgendwas falsch dran?

Ich antworte mal mit einem entschiedenen "VIELLEICHT!".

Benchmarken ist eine Kunst für sich.
Man muß sich genau dessen bewußt sein was man denn wirklich messen will.

Willst Du die reinen Rechenoperationen der Fibonacci-Berechnung ohne die I/O-Zeit messen?

Mit I/O-Zeit ist die Programmlaufzeit extrem durch eventuelle Trägheiten der die Ausgabe aufbereitenden Routinen (printf, term.dec() und Verwandschaft) und von der Geschwindigkeit der (nennen wir es mal:) Terminalschnittstelle.
Manch Simpel-Benchmark rennt um Dimensionen schneller als ein an einer langsamen Ausgabeleitung angeschlossenes Terminal die Ergebnisse auszugeben in der Lage ist oder die Umrechnung binärer Zeit-"Meß"-Werte in ausgebbare dezimale Zahlen-Strings braucht durch mehrere Divisionen in einer Schleife über die Stellenanzahl der auszugebenden Zahl schnell deutlich länger als die paar Additionen die Fibonacci ausmachen.

Gut... das kann man Alles berücksichtigen oder wieder rausrechnen...

Berücksichtigt man es, muß man genau hinschauen mit welcher I/O-Software man arbeitet und mit welchem I/O-Gerät. All dies muß dann sauber erfaßt werden und man bekommt Probleme wenn es mit anderen Sprachen, anderen Bibliotheken auf anderen rechnenden Geräten, ausgebend auf andere I/O-Geräten verglichen werden soll.

Der schnellst-rechnende Fibonacci-Variante kann am 110 Baud-Fernschreiber hängend das schlechteste Laufzeitergebnis liefern weil... (((der Rest des Gedankenganges ist wohl nun klar...)))

Also: Was will man messen und wie sorgt man dafür daß vergleichbare Werte entstehen?

...und sind die paar Additionen, Zuweisungen und die Schleife drumrum die den Fibonacci-Benchmark ausmachen wirklich ein messenswürdiges Konstrukt?

[josto]

Ich habe zwar den Forth Code nicht wirklich verstanden, aber ich glaube, dass auch hier die Ausgaben nicht im Messzyklus stattfinden. Von da her sind die Ergebnisse durchaus vergleichbar. Oder habe ich dich hier jetzt falsch verstanden?

...und sind die paar Additionen, Zuweisungen und die Schleife drumrum die den Fibonacci-Benchmark ausmachen wirklich ein messenswürdiges Konstrukt?

In wie weit der Fibonacci als Benchark Sinn macht, ist eine andere Geschichte...
Ich habe das Thema nur aufgegriffen, weil du mich auf den ProgGCC Benchmark aufmerksam gemacht hast:

http://code.google.com/p/propgcc/wiki/PropGccLoader zeigt unter Anderem Timimg-Angaben einer Demo in verschiedenen Speichermodi...

Du bist daher quasi selbst schuld an der ganzen Diskussion

[yeti]

http://code.google.com/p/propgcc/wiki/PropGccLoader zeigt unter Anderem Timimg-Angaben einer Demo in verschiedenen Speichermodi...

Du bist daher quasi selbst schuld an der ganzen Diskussion

Quasi...

Beim zitierten PropGCC-Zeuchs war es dasselbe Programm in verschiedenen Speichermodellen in derselben Sprache auf derselben Hardware...

Nimmt man den Fibonacci in 'ner anderen Sprache und eventuëll auf anderer Hardware daher muß man halt hingucken inwieweit man tatsächlich vergleichbare Situationen schafft...

...mehr als das wollt' ich doch garnicht ausdrücken...

...aber ich finde halt jedes Fettnäpfchen... dafür bin ich bekannt... ist schon fast mein Alleinstellungsmerklmal!