Seite 3 von 5

Re: Fibonacci-Folge / Benchmarks

Verfasst: Do Okt 12, 2017 6:48 am
von mfro
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

Re: Fibonacci-Folge / Benchmarks

Verfasst: Fr Okt 13, 2017 1:05 am
von Xin
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

Re: Fibonacci-Folge / Benchmarks

Verfasst: Fr Okt 13, 2017 5:42 am
von mfro
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?

Re: Fibonacci-Folge / Benchmarks

Verfasst: Mi Nov 15, 2017 1:27 am
von arB
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

Re: Fibonacci-Folge / Benchmarks

Verfasst: Mi Nov 15, 2017 7:15 am
von mfro
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 ;)

Re: Fibonacci-Folge / Benchmarks

Verfasst: Mi Nov 15, 2017 7:49 pm
von arB
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!)

Re: Fibonacci-Folge / Benchmarks

Verfasst: Mi Nov 15, 2017 7:56 pm
von mfro
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:

Re: Fibonacci-Folge / Benchmarks

Verfasst: Do Nov 16, 2017 10:47 am
von Xin
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. :-)

Re: Fibonacci-Folge / Benchmarks

Verfasst: So Nov 19, 2017 8:10 pm
von Xin
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.

Re: Fibonacci-Folge / Benchmarks

Verfasst: So Jan 14, 2018 8:57 pm
von bbbl
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.