Fibonacci-Folge / Benchmarks

Pascal, Basic und andere nicht aufgelistete
Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8502
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Fibonacci-Folge / Benchmarks

Beitrag von Xin » Mi Okt 03, 2018 10:40 am

So... nachdem das Jahr programmiertechnisch eigentlich ereignislos war (bis auf die Tatsache, dass wir proggen.org nach endlosen Vorbereitungen quasi neugeschrieben und umgezogen haben ^^) habe ich mich am Sonntag erstmals wieder an den Computer gesetzt, einfach um mal wieder etwas Spaß zu haben. Und damit auch an dieses Projekt, mich wieder eingelesen, ein paar Bugs entfernt und heute den erstmals seit Ewigkeiten wieder eine Kleinigkeit hinzugefügt: Eine kleine, aber feine Optimierung zum Addieren und Subtrahieren von Werten: Inc und Dec, bzw. Werte können direkt mit add und sub addiert werden. Vorher konnte der Renderer nur Register addieren und subtrahieren, der Wert musste also erst in ein Register geladen werden und dann wurde der geladene Wert aus dem Register verrechnet.
Das wirkt sich aus: von 0,029 Sekunden geht's runter auf 0,024 Sekunden.

Das sind nur 0,005 Sekunden. Oder eben 17%. 17% ist heftig. ^^

Womit die Konkurrenz zu Java wieder interessant wird...

Code: Alles auswählen

          Java       Genesys     C (optimiert)
fib(30):   0,170s     0,024s     0,013s
fib(35):   0,262s     0,137s     0,079s
fib(40):   1,181s     1,383s     0,767s
fib(45):  10,657s    13,708s     7,649s
Was interessant ist... ich bekomme die ursprüngliche Zeit von fib(30) mit 0,139s mit Java nicht mehr bestätigt!? Hatten wir ein Java-Update bzw. Downgrade?

Anyway, ich vermute, ich habe möglicherweise noch eine größere Bremse im JIT-Compiler. 30% müssten also auch noch zu machen sein, C zeigt schließlich an, wo die Meßlatte am Ende zu hängen hat. ^^
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

koshamo
Beiträge: 13
Registriert: Sa Aug 11, 2018 5:38 pm
Wohnort: Heidelberg

Re: Fibonacci-Folge / Benchmarks

Beitrag von koshamo » Fr Okt 05, 2018 9:53 pm

Welche Java-Version hattest du denn die ganze Zeit und welche jetzt? Die schrauben nämlich ständig an der JVM und am JIT rum und haben mit Java 9 einen neuen GC eingeführt, der andere Schwerpunkte setzt.
Optimierung ist halt immer so ein Problem: für welche Anwendungssituation soll optimiert werden? Optimierung in die eine Richtung bedeutet meist Verschlechterung in der anderen Richtung....
Nur an einer einzigen Problemstellung Performance zu testen zeigt auch nur die Leistungsfähigkeit der Sprachen / Compiler an dieser einzigen Stelle. Leider.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8502
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Fibonacci-Folge / Benchmarks

Beitrag von Xin » Sa Okt 06, 2018 10:13 am

koshamo hat geschrieben:
Fr Okt 05, 2018 9:53 pm
Welche Java-Version hattest du denn die ganze Zeit und welche jetzt? Die schrauben nämlich ständig an der JVM und am JIT rum und haben mit Java 9 einen neuen GC eingeführt, der andere Schwerpunkte setzt.
Gute Frage...
Aktuell war es die 10.0.2. Vor einem Jahr wird es entsprechend eine 9er gewesen sein.

Da Fibonacci aber nur rekursiv sich selbst aufruft und darin nur Vergleiche und Schleifen ablaufen, dürfte der GC gar nicht zum Zuge kommen. Es werden ja keine Objekte erzeugt.
koshamo hat geschrieben:
Fr Okt 05, 2018 9:53 pm
Optimierung ist halt immer so ein Problem: für welche Anwendungssituation soll optimiert werden? Optimierung in die eine Richtung bedeutet meist Verschlechterung in der anderen Richtung....
Nur an einer einzigen Problemstellung Performance zu testen zeigt auch nur die Leistungsfähigkeit der Sprachen / Compiler an dieser einzigen Stelle. Leider.
Zweifelsohne.
Für mich bedeutet dieser Benchmark vorrangig erstmal: Es funktioniert. Ich hatte eigentlich überhaupt nicht vor in Konkurrenz mit Java oder gar C zu treten. Erstmal wollte ich mit meiner Sprache leichtere Ziele angreifen. Ich wollte einfach nur an PHP und Python vorbei. Und da bin ich "versehentlich" derart dran vorbeigeschossen, dass die beiden Sprachen für mich komplett aus dem Fokus gerutscht sind.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

koshamo
Beiträge: 13
Registriert: Sa Aug 11, 2018 5:38 pm
Wohnort: Heidelberg

Re: Fibonacci-Folge / Benchmarks

Beitrag von koshamo » So Okt 07, 2018 9:00 am

Du hattest irgendwo vorne nach Beispielen in weiteren Sprachen gefragt, u.a. Haskell. Hier kommen Codebeispiele:

Code: Alles auswählen

fib :: Int -> Int
fib n 
    | n <= 1 = 1
    | otherwise = fib (n-1) + fib (n-2)

main = do
    let x = [fib x | x <- [1..30]]
    print x
Da aber gerade funktionale Sprachen in aller Regel eine Endrekursionsoptimierung mitbringen (jede endrekursive Funktion lässt sich als while-Schleife darstellen), sollte man da natürlich auch eine endrekursive Variante anbieten. Wenn schon, dann echter und sprachtypischer Benchmark :P

Code: Alles auswählen

fib :: Int -> Int -> Int -> Int
fib n acc prev
    | n <= 1 = prev
    | otherwise = fib (n-1) prev (acc+prev)

main = do
    let x = [fib x 1 0 | x <- [1..30]]
    print x

mfro
Beiträge: 311
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Fibonacci-Folge / Benchmarks

Beitrag von mfro » Do Aug 22, 2019 4:50 pm

... zum Thema Fibonacci-Folgen auf exotisch: wie wär's mit einer Implementierung in Hardware?

VHDL:

Code: Alles auswählen

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity recursive is
    port
    (
        clk     : in std_ulogic;
        n       : in natural;
        o       : out natural
    );
end recursive;

architecture Behavioral of recursive is
    function fib(n : natural) return natural is
    begin
        if n = 0 then
            return 0;
        elsif n = 1 or n = 2 then
            return 1;
        else
            return fib(n - 1) + fib(n - 2);
        end if;
    end function fib;
begin
    p_calc : process
    begin
        wait until rising_edge(clk);
        o <= fib(n);
        report("fib(" & integer'image(n) & ") = " & integer'image(fib(n))) severity note;
    end process;
end Behavioral;

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity tb is
end entity tb;

architecture sim of tb is
    signal clk          : std_ulogic := '0';
    signal n            : natural;
begin
    p_clk : process
    begin
        wait for 10 ns;
        clk <= not clk;
    end process p_clk;
    
    p_stim : process
        variable num : natural := 0;
    begin
        wait until rising_edge(clk);
        n <= num;
        num := num + 1;
    end process p_stim;
    
    i_uut : entity work.recursive
        port map (clk => clk, n => n);
end architecture sim;
Laufzeiten habe ich nicht anzubieten, aber das Ergebnis eines Simulationslaufs. Heißt, wenn die Hardware das mit 50 MHz abarbeiten könnte (meine kann's nicht), wäre das Ergebnis von fib(30) nach 630 ns da.
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3091
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Fibonacci-Folge / Benchmarks

Beitrag von cloidnerux » Fr Aug 23, 2019 10:30 am

... zum Thema Fibonacci-Folgen auf exotisch: wie wär's mit einer Implementierung in Hardware?
Ich hab es mal versucht in mein IC Tool zu importieren, um daraus mal ein Layout zu basteln. Aber der import schlägt fehl, weil es anscheinend nicht implementierbar ist.

Wenn ich lust und Zeit finde könnte ich es aber mal auf einem Spartan 3E ausprobieren.
Redundanz macht wiederholen unnötig.
quod erat expectandum

mfro
Beiträge: 311
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Fibonacci-Folge / Benchmarks

Beitrag von mfro » So Aug 25, 2019 10:07 am

cloidnerux hat geschrieben:
Fr Aug 23, 2019 10:30 am
... zum Thema Fibonacci-Folgen auf exotisch: wie wär's mit einer Implementierung in Hardware?
Ich hab es mal versucht in mein IC Tool zu importieren, um daraus mal ein Layout zu basteln. Aber der import schlägt fehl, weil es anscheinend nicht implementierbar ist.

Wenn ich lust und Zeit finde könnte ich es aber mal auf einem Spartan 3E ausprobieren.
Die meisten Synthesetools kommen ohne Hilfe mit (nicht trivialer) Rekursion nicht zurecht (weil sie versuchen werden, die Rekursion für alle möglichen Eingabewerte auszurollen). Wenn man eine Hilfestellung gibt (max. Rekursionstiefe mitgeben und abprüfen, wenn überschritten abbrechen), funktioniert's:

Code: Alles auswählen

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity recursive is
    generic
    (
        MAX_RECURSION_DEPTH  : natural
    );
    port
    (
        clk     : in std_ulogic;
        n       : in natural;
        o       : out natural
    );
end recursive;

architecture Behavioral of recursive is
    function fib(max_depth : natural; n : natural) return natural is
        variable res : natural;
    begin
        if max_depth <= 1 then
            res := 0;
            return res;
        end if;
        if n = 0 then
            res := 0;
        elsif n = 1 or n = 2 then
            res := 1;
        else
            res := fib(max_depth - 1, n - 1) + fib(max_depth - 1, n - 2);
        end if;
        return res;
    end function fib;
    
    signal result   : natural;
begin
    p_calc : process
    begin
        wait until rising_edge(clk);
        result <= fib(MAX_RECURSION_DEPTH, n); 
        o <= result;
    end process;
end Behavioral;
Das läuft durch, braucht aber bei einer Rekursionstiefe (MAX_RECURSION_DEPTH) von 21 für die Synthese bereits > 32 GB Hauptspeicher. Das Ergebnis ist ein Stück "Fibonacci-Hardware", das tatsächlich alle 20 ns (50 MHz) eine neue (durch die Beschränkung allerdings maximal 19 Bit lange) Fibonacci-Zahl ausspuckt.
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8502
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Fibonacci-Folge / Benchmarks

Beitrag von Xin » Mo Aug 26, 2019 9:48 am

koshamo hat geschrieben:
So Okt 07, 2018 9:00 am
Du hattest irgendwo vorne nach Beispielen in weiteren Sprachen gefragt, u.a. Haskell.
Ja, Haskell sollte ich mal in den Benchmark mit aufnehmen. Viele Dank!
mfro hat geschrieben:
Do Aug 22, 2019 4:50 pm
... zum Thema Fibonacci-Folgen auf exotisch: wie wär's mit einer Implementierung in Hardware?
Hier kenne ich mich quasi gar nicht aus.
VHDL sieht für mich erstmal nach seeeehr viel Text aus. :D
mfro hat geschrieben:
Do Aug 22, 2019 4:50 pm
Laufzeiten habe ich nicht anzubieten, aber das Ergebnis eines Simulationslaufs. Heißt, wenn die Hardware das mit 50 MHz abarbeiten könnte (meine kann's nicht), wäre das Ergebnis von fib(30) nach 630 ns da.
Dazu hättei ich zwei Fragen. Erstens: Womit simulierst Du und zweitens: Wie kommt das in die Hardware?
mfro hat geschrieben:
So Aug 25, 2019 10:07 am
Das läuft durch, braucht aber bei einer Rekursionstiefe (MAX_RECURSION_DEPTH) von 21 für die Synthese bereits > 32 GB Hauptspeicher. Das Ergebnis ist ein Stück "Fibonacci-Hardware", das tatsächlich alle 20 ns (50 MHz) eine neue (durch die Beschränkung allerdings maximal 19 Bit lange) Fibonacci-Zahl ausspuckt.
Okay, für Hardware wäre es wohl sinnvoller eine vernünftige Software Implementierung zu bauen. :D
Oder im Falle von einer Rekursionstiefe von 21 einfach eine Tabelle zu nutzen. :D
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

mfro
Beiträge: 311
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Fibonacci-Folge / Benchmarks

Beitrag von mfro » Mo Aug 26, 2019 7:23 pm

Xin hat geschrieben:
Mo Aug 26, 2019 9:48 am
mfro hat geschrieben:
So Aug 25, 2019 10:07 am
Das läuft durch, braucht aber bei einer Rekursionstiefe (MAX_RECURSION_DEPTH) von 21 für die Synthese bereits > 32 GB Hauptspeicher. Das Ergebnis ist ein Stück "Fibonacci-Hardware", das tatsächlich alle 20 ns (50 MHz) eine neue (durch die Beschränkung allerdings maximal 19 Bit lange) Fibonacci-Zahl ausspuckt.
Okay, für Hardware wäre es wohl sinnvoller eine vernünftige Software Implementierung zu bauen. :D
Oder im Falle von einer Rekursionstiefe von 21 einfach eine Tabelle zu nutzen. :D
Es ging mir hier nur darum auszuprobieren, ob "rekursive Hardware" überhaupt möglich ist und erstaunlicherweise ist sie das - mit der Einschränkung, dass man eben die Rekursionstiefe beschränken muss. Der Hauptspeicherverbrauch des Synthesetools beim "Bauen" ist für das Ergebnis einigermassen unerheblich: das belegt nämlich tatsächlich locker auch im kleinsten verfügbaren FPGA weniger als 10%.

Auf meiner SSD waren leider keine 128 Gig mehr frei, sonst hätte ich - zugunsten von mehr Ergebnisbits - noch ein wenig Swapspace nachgeschoben.
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

mfro
Beiträge: 311
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Fibonacci-Folge / Benchmarks

Beitrag von mfro » Mo Aug 26, 2019 7:47 pm

Xin hat geschrieben:
Mo Aug 26, 2019 9:48 am
Dazu hättei ich zwei Fragen. Erstens: Womit simulierst Du und zweitens: Wie kommt das in die Hardware?
Simuliert wird das im Simulator ;). Gibt es - im Gegensatz zu den Synthesetools, die immer vom jeweiligen Hardwarehersteller kommen - auch (und zwar in einer Qualität, die sich absolut nicht verstecken muß) als freie Software: https://ghdl.readthedocs.io/en/latest/

VHDL ist eine vollwertige Programmiersprache (die unverkennbar von Ada abstammt), mit Packages, Funktionen, Prozeduren, Records und Pointern (wollte man, könnte man damit auch einen Editor schreiben), aber nur ein Subset davon lässt sich tatsächlich in Hardware (Flipflops und kombinatorische Logik als Netzliste) umsetzen (man muss sich also einschränken, wenn Hardware draus werden soll). Aus der Netzliste baut der Fitter (ähnlich des Autorouters bei einem Platinenlayoutprogramm), das Ergebnis kann man auf ein FPGA laden oder - wenn man sich's leisten kann - in der nächsten Chipschmiede um die Ecke in Silikon "giessen" lassen.
Features, die bei C++ erst kürzlich erfunden wurden (wie constexpr und TMP - das heisst hier verwirrenderweise 'static') sind in VHDL schon seit Jahrzehnten drin.
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

Antworten