Fibonacci-Folge / Benchmarks

Pascal, Basic und andere nicht aufgelistete
mfro
Beiträge: 346
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Fibonacci-Folge / Benchmarks

Beitrag von mfro » Do Okt 12, 2017 6:48 am

ansonsten hätte ich noch das hier anzubieten:

Code: Alles auswählen

mfro@thinkpad:~/Dokumente/Development/scratch$ time ./tst101 
30: 832040

real	0m0,004s
user	0m0,000s
sys	0m0,000s




Code: Alles auswählen

#include <iostream>

template <int N> struct Fib_t {
        enum { value = Fib_t<N-1>::value + Fib_t<N-2>::value };
        Fib_t() { std::cout << N << ": " << value << std::endl; }
};

// Explicitly specialized for N==2
template <> struct Fib_t<2> {
        enum { value = 1 }; 
        Fib_t() { std::cout << 2 << ": " << value << std::endl; }
};

// Explicitly specialized for N==1
template <> struct Fib_t<1> {
        enum { value = 1 }; 
        Fib_t() { std::cout << 1 << ": " << value << std::endl; }
};

int main(void)
{
       Fib_t<30> f;
}
... aber das lässt Du bestimmt nicht gelten... :D
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

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

Re: Fibonacci-Folge / Benchmarks

Beitrag von Xin » Fr Okt 13, 2017 1:05 am

Sorry, dass ich das hier gerade etwas schleifen lasse, da kommt noch eine Antwort drauf.
Aber da brauche ich Ruhe und Zeit zum experimentieren für und die fehlt mir in der Woche etwas.

Die template-Geschichte lasse ich natürlich gelten. Das ist schlussendlich ja auch mein Ziel - aber eher in der Syntax der const expr. :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: 346
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Fibonacci-Folge / Benchmarks

Beitrag von mfro » Fr Okt 13, 2017 5:42 am

Xin hat geschrieben:Aber da brauche ich Ruhe und Zeit zum experimentieren für und die fehlt mir in der Woche etwas.
Das ist doch o.k. Als Anregung zum Nachdenken zwei Dinge, die mir selber nicht klar sind (C++ ist nicht meine Leib- und Magensprache, aber solcherlei Funktionalität macht einem den Mund wässrig):
  1. warum hat die constexpr-Variante nicht dieselbe (Nicht-) Laufzeit wie die Template-Variante? constexpr sagt doch eigentlich, daß die Geschichte zur Compilezeit auszurechnen ist?
  2. warum werden bei der Template-Variante die Konstruktoren der rekursiven Template-Instanzierungen (einschließlich der Spezialisierungen) anscheinend nicht aufgerufen?
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

arB
Beiträge: 2
Registriert: Mi Nov 15, 2017 12:52 am

Re: Fibonacci-Folge / Benchmarks

Beitrag von arB » Mi Nov 15, 2017 1:27 am

mfro hat geschrieben: 1. warum hat die constexpr-Variante nicht dieselbe (Nicht-) Laufzeit wie die Template-Variante? constexpr sagt doch eigentlich, daß die Geschichte zur Compilezeit auszurechnen ist?
Der Compiler kann nicht durch die Rekursive Funktion schauen. Bei einer Tiefe von 30 ist dass zu aufwendig.
Zudem wird die Funktion in einer Schleife aufgerufen. Der Optimizer gibt daher noch schneller auf.
mfro hat geschrieben: 2. warum werden bei der Template-Variante die Konstruktoren der rekursiven Template-Instanzierungen (einschließlich der Spezialisierungen) anscheinend nicht aufgerufen?
Du erzeugst nur eine Instanz des Typen `Fib_t` in `main()`. Deine Rekursion läuft ja über den Scope `::` und nicht über Instanzen.

Und ich hab mir mal die Mühe gemacht alles mit `constexpr` in C++14 zu implementieren.
Die gesamte Ausgabe wird zur Compile-Zeit generiert, so dass zur Laufzeit nur noch ausgegeben werden muss.
Zusätzlich wird das Programm mit `exit(0)` beendet, damit keine unnötigen Aufräum-Arbeiten die Laufzeit verzögern.

https://godbolt.org/g/XMKcFe

MSVS 2017.4 kann den Code auch kompilieren. Godbolt hat den leider noch nicht.

Code: Alles auswählen

#include <iostream>

namespace {

template<class T, T V>
struct val {
    T data{V}; // not needed but VS crashes without this
};
template<char C>
using chr = val<char, C>;
template<size_t S>
using idx = val<size_t, S>;

// constexpr sequence type
template<class T, T... V>
struct seq {
    T data[sizeof...(V)]{V...};
};
template<char... C>
using str = seq<char, C...>;

// allow val + val
template<class T, T V, T V2>
constexpr auto operator+(val<T, V>, val<T, V2>) {
    return val<T, V + V2>{};
}

// allow str + val
template<class T, T... V, T V2>
constexpr auto operator+(seq<T, V...>, val<T, V2>) {
    return seq<T, V..., V2>{};
}
// allow str + str
template<class T, T... V, T... V2>
constexpr auto operator+(seq<T, V...>, seq<T, V2...>) {
    return seq<T, V..., V2...>{};
}

// std::to_string is not constexpr yet
template<size_t V>
constexpr static auto to_str(idx<V> = {}) {
    if constexpr (V < 10)
        return str<'0' + V>();
    else
        return to_str<V / 10>() + str<'0' + (V % 10)>();
}

// use constexpr template to prevent recursion limit
template<int n>
constexpr auto fib = fib<n - 1> + fib<n - 2>;
template<>
constexpr auto fib<1> = idx<1>{};
template<>
constexpr auto fib<2> = idx<1>{};

// recursive constexpr because the type expands on each iteration
template<size_t N>
constexpr auto gen() {
    auto b = to_str<N>() + chr<' '>() + to_str(fib<N>) + chr<'\n'>();
    if constexpr (1 == N)
        return b;
    else
        return gen<N - 1>() + b;
}

} // namespace

[[noreturn]] int main() {
    constexpr static const auto d = gen<30>(); // ensure all is evaluated at compile time
    std::cout.write(d.data, sizeof(d.data));
    std::exit(0); // prevent any destructor
}
Selbst mit `gen<100>` sollte die Ausführungszeit kaum messbar sein. Ab `gen<80>` steigt MSVC aus.

Code: Alles auswählen

PS R:\build> (1..500 | % { (Measure-Command {.\ConstexprFib.exe}).TotalMilliseconds } | Measure-Object -Minimum).Minimum
3,7382

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

Re: Fibonacci-Folge / Benchmarks

Beitrag von mfro » Mi Nov 15, 2017 7:15 am

arB hat geschrieben:... Selbst mit `gen<100>` sollte die Ausführungszeit kaum messbar sein. Ab `gen<80>` steigt MSVC aus.
...
Aha, schön! Danke!


gcc spielt auch bei gen<100> noch mit (hab' ich eben schnell ausprobiert).

Allerdings ist das Ergebnis ab 94 falsch (int Überlauf?).

Ansonsten muss ich mir das erst mal zu Gemüte führen, da fällt mir sicher noch 'ne dumme Frage ein ;)
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

arB
Beiträge: 2
Registriert: Mi Nov 15, 2017 12:52 am

Re: Fibonacci-Folge / Benchmarks

Beitrag von arB » Mi Nov 15, 2017 7:49 pm

mfro hat geschrieben:Allerdings ist das Ergebnis ab 94 falsch (int Überlauf?).
Ich hab es bis dahin nicht nachgeprüft. Danke :D

Hier noch der Code für D.

Code: Alles auswählen

import std.stdio : writeln;

void main() {	
	import std.range : iota, array, enumerate;
	import std.algorithm : map, each;
	import std.array : appender, join;
	import std.conv : to;

	// faster compile time without recursion
	auto fibs(int n) {
		ulong[] arr = [1,1];
		iota(2,n) // 2, 3, 4 … n
			.each!(v => arr ~= (arr[v-1] + arr[v-2]));
		return arr;
	}

	// enum enforces a compile time constant
	enum a = fibs(100)
		.enumerate(1) // create tuple with index (1…) and value
		.map!(e => e.index.to!string ~ ' ' ~ e.value.to!string)
		.array.join('\n');
	writeln(a);
}
https://godbolt.org/g/dKjHLY

Deutlich kürzer und einfacher zu verstehen. Performance müsste die gleiche sein wie bei C++. (aktuellen ldc compiler benutzen!)

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

Re: Fibonacci-Folge / Benchmarks

Beitrag von mfro » Mi Nov 15, 2017 7:56 pm

arB hat geschrieben: ... Deutlich kürzer und einfacher zu verstehen. Performance müsste die gleiche sein wie bei C++. (aktuellen ldc compiler benutzen!)
Rekursion eliminieren gilt nicht!

Oder doch? :mrgreen:
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

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

Re: Fibonacci-Folge / Benchmarks

Beitrag von Xin » Do Nov 16, 2017 10:47 am

Nur kurz zur Info: ich bin die letzte Zeit laufend unterwegs, derentwicklungsrechner ist seit 2 Wochen nicht an gewesen ;-)

Aber ich lese mit, ab Samstag bin ich dann auch mal wieder in Ruhe am richtigen Rechner.

Ich habe die constexpr Variante gestern mal am Laptop ausprobiert: sie ist. Ei mir mit gcc 7.2 scheinbar etwas schneller. Es geht um etwa 5%. Wieso weshalb warum weiß ich noch nicht, aber die Rekursion zieht er definitiv nicht raus. ;-)

Mir ist klar dass iterative Verfahren schneller sind. Mir geht's bei dem Benchmsrk darum auch erste Tests mit der Sprache zu fahren. Der Funktionsaufruf ist für mich hier wichtig, weil ich hiermit auch dessen Korrektheit und dessen Speed messen kann.

In dem Sinne ist ein Benchmark nicht der schnellste Fib,sondern die schnellste Möglichkeit ihn genau so zu implementieren, dass ich all diese Funktionalität testen kann. Rekursion entfernen gilt also nicht. ;-)

Es kommen weitere Benchmarks ohne Rekursion. :-)

Weitere Benchmarks werden kommen. :-)
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.

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

Re: Fibonacci-Folge / Benchmarks

Beitrag von Xin » So Nov 19, 2017 8:10 pm

So, der Entwicklungsrechner ist am 24. Oktober zuletzt hochgefahren und heute komme ich endlich mal wieder zu was...
Zeug nachholen, was im letzten Monat liegen blieb. ^^
mfro hat geschrieben:Ich nehme übrigens stark an, dass Du mit C/C++ lediglich die Geschwindigkeit der Konsolen-Ausgabe misst.

ich habe nämlich gerade das hier probiert (c++ 11):

Code: Alles auswählen

constexpr int fib(int f) { return f <= 2 ? 1 : fib(f - 1) + fib(f - 2); }
und das ist keinen Deut schneller. D.h. der Compiler hat bereits ganz ohne constexpr aus deinem Benchmark eine Konstante gemacht.
Dann dauert die Ausgabe von fib(45) bei mir rund 31,8 Sekunden - unabhängig davon, ob constexpr oder ohne. Ich denke, der Compiler könnte da eine hübschere Konstante draus machen ;)
Interessanterweise lassen sich hier nicht die 5% realisieren, wie beim i5 in meinem Laptop!?
arB hat geschrieben:Und ich hab mir mal die Mühe gemacht alles mit `constexpr` in C++14 zu implementieren.
Die gesamte Ausgabe wird zur Compile-Zeit generiert, so dass zur Laufzeit nur noch ausgegeben werden muss.
Zusätzlich wird das Programm mit `exit(0)` beendet, damit keine unnötigen Aufräum-Arbeiten die Laufzeit verzögern.
...
Selbst mit `gen<100>` sollte die Ausführungszeit kaum messbar sein. Ab `gen<80>` steigt MSVC aus.
Das zeigt, wie awesome C++14 ist, hat aber leider nichts mit dem Laufzeit-Benchmark zu tun, der natürlich auch zur Laufzeit laufen muss.

Diese Variante wird irgendwann mal interessant, wenn ich solche Sachen zur Compilezeit ausrechnen lassen will, aber soweit bin ich noch nicht.
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.

Benutzeravatar
bbbl
Beiträge: 80
Registriert: So Jul 19, 2009 12:04 am

Re: Fibonacci-Folge / Benchmarks

Beitrag von bbbl » So Jan 14, 2018 8:57 pm

Ich kann auch noch was beisteuern:

JavaScript (ES6): https://nodejs.org/en/

Code: Alles auswählen

// fib.js

const fib = f => (f <= 2) ? 1 : fib(f-1) + fib(f-2)

for (let value = 1; value <= 30; value++)
    console.log('%d: %d', value, fib(value))
Julia: https://julialang.org/

Code: Alles auswählen

# fib.jl

fib(f) = f <= 2 ? 1 : fib(f-1) + fib(f-2)

for value = 1:30
    @printf "%d: %d\n" value fib(value)
end
Julia ist noch eine recht junge Sprache und nutzt ebenfalls JIT.

Apropos JIT, vielleicht sollte man die Python-Variante auch mal mit PyPy (http://pypy.org/) laufen lassen.

Antworten