Rekursion in Templates

Bashar

Einfach schrieb:

Das ist klar, aber das schützt nicht per se vor rekursiven Aufrufen.

Das ist technisch gesehen überhaupt keine Rekursion. Die Funktion ruft sich ja nicht selbst auf, sondern eine andere Instanz desselben Templates. Endrekursionsauflösung kommt daher nicht in Frage, aber wohl Inlining der kompletten Aufrufhierarchie.

Bashar schrieb:

Das ist technisch gesehen überhaupt keine Rekursion. Die Funktion ruft sich ja nicht selbst auf, sondern eine andere Instanz desselben Templates.

Versteh ich nicht. Gibt es pro Aufruf einer Funktion in einem Template eine neue Funktions-Instanz?

Wenn du das template mit zb

f(1, 2, 3);

aufrufst wird das doch zu (etwas wie)

f_3(int i3) { ; }
f_2(int i2, int i3) { f_3(i3); }
f_1(int i1, int i2, int i3) { f_2(i2, i3); }
//...
f_1(1, 2, 3);

kompiliert. Du hast hier also gar keine Rekursion, sondern nur n (hier: 3) verschiedene funktionsaufrufe.

@f<>: Mag sein, aber ich habe damit dieselben Nachteile wie bei Rekusion --> Langsam und Risiko eines Stackoverflows. Es sei denn, es wird geinlined. Kann ich davon ausgehen, dass das gemacht wird?!

camper

Einfach schrieb:

Aus The C++ Programming Language habe ich folgendes Beispiel entdeckt:

template<typename T>
void g(T x)
{
    cout << x << " ";
}

template<typename T, typename... Tail>

void f(T head, Tail... tail)
{
    g(head); // Do something with head
    f(tail...); // try again with tail
}

void f() { } // Do nothing

Das steht da so drin? Gleich mal schauen ob es dafür schon ein Erratum gibt...

@camper: Also ich musste, damit das kompiliert, oben einen void f(); Prototypen einbauen. Meinst du das?

Columbo

Genau. Da kein ADL stattfinden kann muss eine parameterlose Version von f vor der Definition des Templates deklariert sein.

TNA

Einfach schrieb:

@f<>: Mag sein, aber ich habe damit dieselben Nachteile wie bei Rekusion --> Langsam und Risiko eines Stackoverflows. Es sei denn, es wird geinlined. Kann ich davon ausgehen, dass das gemacht wird?!

Jeder gängige Kompiler macht das, wenn die Optimierungen an sind. Ansonsten wären die ganzen schönen C++11-varadic-argument-Funktionstemplates wie std::make_shared in der Tat kaum zu gebrauchen. Allerdings machen die Kompiler das nicht, wenn optimierungen ausgeschaltet sind was dazu führt das ein std::make_shared mit vielen argumenten einige Kilobyte an Stack-Speicher verbraucht, was bei uns schon öfter zu Stackoverflows bei DEBUG-Builds geführt hat.

TNA schrieb:

Einfach schrieb:

@f<>: Mag sein, aber ich habe damit dieselben Nachteile wie bei Rekusion --> Langsam und Risiko eines Stackoverflows. Es sei denn, es wird geinlined. Kann ich davon ausgehen, dass das gemacht wird?!

Jeder gängige Kompiler macht das, wenn die Optimierungen an sind.

Bedeutet das nicht im Umkehrschluss, dass, wenn ich eine "Rekursionstiefe" von eine Millionen habe, dass da ganz schön großer Code erzeugt wird?! In dem Fall wäre Endrekursionsoptimierung besser.

Bashar

Wenn du Funktionen mit einer Million Argumenten aufrufst und eine Million Templates instanziierst, hast du ganz andere Probleme als einen möglichen Stacküberlauf.

Bashar schrieb:

Wenn du Funktionen mit einer Million Argumenten aufrufst und eine Million Templates instanziierst, hast du ganz andere Probleme als einen möglichen Stacküberlauf.

Wieso? Es kann doch sein, dass ich über eine Millionen Elemente iterieren möchte. Für einen Stackoverflow dürften 10.000 auch ausreichend sein.

Bzw. bei Inlining wird das ja nicht passieren. Dann wird der Code entsprechend groß. Auch bei 10.000 Elementen.

Einfach schrieb:

Bashar schrieb:

Wenn du Funktionen mit einer Million Argumenten aufrufst und eine Million Templates instanziierst, hast du ganz andere Probleme als einen möglichen Stacküberlauf.

Wieso? Es kann doch sein, dass ich über eine Millionen Elemente iterieren möchte. Für einen Stackoverflow dürften 10.000 auch ausreichend sein.

Einfach schrieb:

Wieso? Es kann doch sein, dass ich über eine Millionen Elemente iterieren möchte. Für einen Stackoverflow dürften 10.000 auch ausreichend sein.

Dann stellt sich eher die frage was du tatsächlich machen willst. Denn ich denke nicht dass du eine funktion mit 1 mio. argumenten (auch nicht mit 10000, nichtmal mit 100) aufrufen willst.

cooky451

Einfach schrieb:

@f<>: Mag sein, aber ich habe damit dieselben Nachteile wie bei Rekusion --> Langsam und Risiko eines Stackoverflows.

Hast du nicht btw, da die Aufrufhierachie nicht von Laufzeitvariablen abhaengt ist es trivial fuer den Compiler alles zu inlinen, oder es so zu inlinen wie er es fuer richtig haelt.

f<> schrieb:

Dann stellt sich eher die frage was du tatsächlich machen willst. Denn ich denke nicht dass du eine funktion mit 1 mio. argumenten (auch nicht mit 10000, nichtmal mit 100) aufrufen willst.

Hm, Argumente, ok. Ich habe das mit Java verglichen. In Java sind die variablen Argumente einfach Arrays. D. h., dass ich einer Funktion mit variablen Argumenten einfach ein Array übergeben kann und es funktioniert genauso. Das scheint mit C++s variadic templates nicht zu funktionieren.
Danke, für die Aufklärung!

Einfach schrieb:

Hm, Argumente, ok. Ich habe das mit Java verglichen. In Java sind die variablen Argumente einfach Arrays. D. h., dass ich einer Funktion mit variablen Argumenten einfach ein Array übergeben kann und es funktioniert genauso. Das scheint mit C++s variadic templates nicht zu funktionieren.
Danke, für die Aufklärung!

Ok, mit Java kenn ich mich nicht aus, daher kann ich dazu nichts sagen. Außer dass das zwei grundlegend verschiedene mechanismn sind.

In C++ geht sowas ungefähr so:

#include <iostream>

template <typename Iterator>
void display(Iterator first, Iterator last)
{
	while (first != last)
	{
		std::cout << *first << '\n';
		++first;
	}
}

int main()
{
	std::vector<int> vec = { 1, 3, 4, 6, 2, 9 }; // beliebig viele elemente
	display(vec.begin(), vec.end());
}