Type-Erased Ranges

cooky451

Das aktuelle System ist zwar blöd, aber bei dem Thema würde ich ungern Performance verlieren. Okay, für dein Beispiel mag das nicht ganz so relevant sein, aber bei sort etc. sieht das u.U. anders aus. Ich hoffe da eher auf Module + Concepts, die würden dieses Problem z.B. gleich mit lösen.

Nexus

boost::any_iterator kannte ich nicht, danke. Die Vorteile der Type Erasure habe ich ja beschrieben...

Ja, Performance ist auch meine grösste Sorge. Eine High-Level-Range könnte vielleicht Optimierungen wie Cachen des dereferenzierten Zeigers erlauben, allerdings wirds dann mühsam mit Proxies.

Module verringern Kompilierzeit, aber wie genau helfen Concepts bei der Sache?

cooky451

Nexus schrieb:

Module verringern Kompilierzeit, aber wie genau helfen Concepts bei der Sache?

1. Sobald Module da sind, ist es egal ob etwas ein Template ist oder nicht. (Man hat das Header Problem ja nicht mehr.)
2. Sobald Concepts da sind, kann man einfach ein IntContainer, FooContainer oder was man auch immer haben will erwarten. Damit ist der Typ auch eindeutig, und man verliert 0% Performance.

Nexus

cooky451 schrieb:

1. Sobald Module da sind, ist es egal ob etwas ein Template ist oder nicht. (Man hat das Header Problem ja nicht mehr.)

Man sollte nicht vergessen, dass Templates auch weitere Nachteile haben (Fehlerüberprüfung erst bei Instantiierung, Code-Bloat, komplexer/langsamer zu parsen, Code kann nicht in Bibliotheken ausgelagert werden). Okay, ich kenne Module zu wenig, eventuell lösen die weitere Probleme.

cooky451 schrieb:

2. Sobald Concepts da sind, kann man einfach ein IntContainer, FooContainer oder was man auch immer haben will erwarten. Damit ist der Typ auch eindeutig, und man verliert 0% Performance.

Wie könnte das z.B. aussehen? Müsste man dafür erst ein Concept definieren, oder gehst du davon aus, dass man eines wie std::Container<Foo> gleich benutzen könnte?

Aber wir reden momentan über Science Fiction, da kann ich ja gleich auf die Bugfixes in Boost.Range warten :p
Nein im Ernst, Concepts und Module sind langfristig sicher zu berücksichtigen, aber was denkt ihr über eine halbwegs portable Implementierung heute? Visual Studio unterstützt ja leider vieles in C++11 noch nicht.

cooky451

Nexus schrieb:

Man sollte nicht vergessen, dass Templates auch weitere Nachteile haben

Fehlerüberprüfung wird ja durch Concepts gelöst, Rest kann man vernachlässigen denke ich.

Nexus schrieb:

Wie könnte das z.B. aussehen? Müsste man dafür erst ein Concept definieren, oder gehst du davon aus, dass man eines wie std::Container<Foo> gleich benutzen könnte?

Ich gehe tatsächlich von std::Container<Foo> aus, aber in jedem Fall ist es ziemlich simpel.

Nexus schrieb:

Aber wir reden momentan über Science Fiction,

Jo, leider.

Nexus schrieb:

was denkt ihr über eine halbwegs portable Implementierung heute? Visual Studio unterstützt ja leider vieles in C++11 noch nicht.

Wie gesagt, ganz einfach aufgrund der Performance würde ich es wohl nicht benutzen. Wobei man das testen müsste, aber ich fürchte das ist dann so ein Fall, wo es tatsächlich einen Unterschied macht.

Nexus

cooky451 schrieb:

Rest kann man vernachlässigen denke ich.

Würde ich so pauschal nicht sagen, hängt wohl vom Fall ab.

cooky451 schrieb:

Wie gesagt, ganz einfach aufgrund der Performance würde ich es wohl nicht benutzen. Wobei man das testen müsste, aber ich fürchte das ist dann so ein Fall, wo es tatsächlich einen Unterschied macht.

Wenn die Aufgaben pro Element teuer sind, wird der Iteratoroverhead vernachlässigbar. In solchen Fällen könnte man von der Type-Erased Range profitieren.

Ich glaube, ich schreibe mir einmal so eine Implementierung und schaue, wie stark die Performance tatsächlich beeinträchtigt wird und ob man eventuell was optimieren kann...

headmyshoulder

Hast Du die Diskussion http://thread.gmane.org/gmane.comp.lib.boost.devel/231052 mitbekommen? Ich glaube das ist genau das was Du suchst. Man definiert sich Anforderungen an seinen Typen via

typedef boost::type_erase::any< requirements > my_any;

und kann dann davon beliebige Container erstellen:

std::vector< my_any > vec;

Nexus

Dann gehören die any<X> -Objekte aber dem Container, bei Ranges handelt es sich nur um Verweise (View auf Container). Und ich brauche keinen vollständigen Container wie std::vector , eine Range bietet nur einen Teil der Operationen an.

Ausserdem fürchte ich, dass die Type-Erasure-Library mit dem exzessiven Einsatz von Boost.MPL und impliziten Concepts für den 0815-Benutzer viel zu kompliziert ist. Aber danke trotzdem für den Hinweis auf die Bibliothek!

headmyshoulder

Nexus schrieb:

Dann gehören die any<X> -Objekte aber dem Container, bei Ranges handelt es sich nur um Verweise (View auf Container). Und ich brauche keinen vollständigen Container wie std::vector , eine Range bietet nur einen Teil der Operationen an.

Das verstehe ich nicht. Irgendwo müssen die Objekte ja liegen. Und ein vector ist per Definition eine Range. Was meinst Du mit Range. make_pair( vec.begin(),vec.end() ) liefert Dir auch eine View auf den vector.

Du kannst natürlich die any Types in jede beliebte Struktur packen und Dir eine Range dafür definieren.

Nexus schrieb:

Ausserdem fürchte ich, dass die Type-Erasure-Library mit dem exzessiven Einsatz von Boost.MPL und impliziten Concepts für den 0815-Benutzer viel zu kompliziert ist. Aber danke trotzdem für den Hinweis auf die Bibliothek!

Das kann sein, man kann einen any Type aber auch relativ einfach selber implementieren.

Nexus

Wozu brauch ich überhaupt any ? Der Elementtyp selbst soll ja nicht type-erased sein, nur die Iteratoren bzw. die Range.

Shade Of Mine

Nexus schrieb:

Wozu brauch ich überhaupt any ? Der Elementtyp selbst soll ja nicht type-erased sein, nur die Iteratoren bzw. die Range.

Weil wenn du type erasure betreibst du so oder so alle kosten zahlst, egal wieviel zu erased. also erased man einfach alles und hat wenigstens maximale flexibilitaet.

Nexus

Die Flexibilität ist aber nicht gratis, man bezahlt sie teuer mit Typsicherheit (und Typinferenz). Das zeigt sich dann in

auto elem = any_cast<MyType>(*range);
// Todo: Fehlerbehandlung

statt

auto elem = *range;

Ich sehe den Vorteil echt nicht, im Endeffekt ist man dauernd am casten. Wie will man überhaupt von der "Flexibilität" mehrerer Typen Gebrauch machen, ohne explizite If-Else-Fallunterscheidungen einzusetzen?

hustbaer

Naja...

Die range<T> könnte ja von einer any_range ableiten.

any_range könnte dabei sämtliche Funktionen anbieten die nicht das aktuelle Element zurückgeben, also alles bis auf die front/back Funktionen. Bzw. man könnte sogar front_ptr/back_ptr Funktionen anbieten, die einfach void-Zeiger zurückgeben.

Wenn man es schlau anstellt, sollte das mMn. auch möglich sein ohne dass man dabei zusätzliche Performance-Einbussen hat.

Die zusätzliche Type-Erasure liesse sich verwenden um dem Template-Bloat in diversen Algorithmen entgegenzuwirken.
Natürlich würde man an der Stelle dann erneut für die Type-Erasure im Algorithmus zahlen, mit einem virtual-call bzw. function-pointer-call überall wo man auf ein Element zugreifen muss.

Ob das jetzt Sinn macht oder nicht sei mal dahingestellt, aber wenn man es gratis oder quasi-gratis anbieten kann, dann könnte das bei sowas allgemeinem wie einer Range-Implementierung schon Sinn machen.

----

Was mMn. gar keinen Sinn macht ist der Weg über any. Denn ich traue mich wetten, dass man mit any so überhaupt keine Chance hat es vergleichbar schnell wie ohne die 2. Type-Erasure hinzubekommen. Wenn überhaupt, dann über void-Zeiger. void-Zeiger sind nicht böse

Nexus

Die Any-Range klingt interessant, allerdings kommt beim Elementzugriff (der in STL-Style-Algorithmen oft vorkommt, z.B. für swap() ) wieder ein any ins Spiel.

Bei meiner Range bin ich vor allem von Anwendungsfällen wie im ControlUnits() -Beispiel ausgegangen, wo es um konkrete Elementtypen geht. Wenn sich diese als Spezialfall der Any-Range performant implementieren liesse, wäre das durchaus eine Überlegung wert. Möglicherweise kann man durch die zusätzliche Typsicherheit in der konkreten Range schnell casten.

Mal schauen, ich habe inzwischen mit der Implementierung begonnen.

hustbaer

BTW: willst du die Iteratoren-Variante bauen (also dass man von der Range wieder Iteratoren bekommen kann wenn man will), oder eine "reine" Range?

Und was ist das ControlUnits() -Beispiel? - kann ich grad nicht zuordnen...

Kellerautomat

Hab mal bisschen was gebastelt.

#include <cstddef>
#include <memory>

template <typename T>
struct default_iterator_traits
{
	typedef std::size_t size_type;
	typedef std::ptrdiff_t difference_type;

	typedef T value_type;

	typedef T& reference;
	typedef T const& const_reference;

	typedef T* pointer;
	typedef T const* const_pointer;
};

template <typename T, typename Traits>
struct forward_iterator;

template <typename T, typename Traits>
bool operator == (forward_iterator<T, Traits> const& first, forward_iterator<T, Traits> const& second);

template <typename T, typename Traits = default_iterator_traits<T>>
struct forward_iterator
{
	typedef typename Traits::size_type size_type;
	typedef typename Traits::difference_type difference_type;

	typedef typename Traits::value_type value_type;

	typedef typename Traits::reference reference;
	typedef typename Traits::const_reference const_reference;

	typedef typename Traits::pointer pointer;
	typedef typename Traits::const_pointer const_pointer;

	forward_iterator(forward_iterator const& other)
		: wrapper_(other.wrapper_->clone())
	{}

	template <typename ForwardIterator>
	forward_iterator(ForwardIterator const& iter)
		: wrapper_(new wrapper<ForwardIterator>(iter))
	{}

	forward_iterator& operator = (forward_iterator const& other)
	{
		if(&other != this)
			wrapper_.reset(other.wrapper_->clone());

		return *this;
	}

	forward_iterator& operator ++ ()    { ++*wrapper_; return *this; }
	forward_iterator  operator ++ (int) { forward_iterator iter(*this); ++iter; return iter; }

	reference operator *  () const { return **wrapper_; }
	pointer   operator -> () const { return (*wrapper_).operator -> (); }

	friend bool operator == <>(forward_iterator const& first, forward_iterator const& second);

private:
	struct wrapper_base
	{
		virtual void operator ++ () = 0;

		virtual reference operator *  () const = 0;
		virtual pointer   operator -> () const = 0;

		virtual bool operator == (wrapper_base& other) const = 0;

		virtual wrapper_base* clone() const = 0;
		virtual ~wrapper_base() {}
	};

	template <typename ForwardIterator>
	struct wrapper : wrapper_base
	{
		wrapper(ForwardIterator const& iter)
			: iter_(iter)
		{}

		virtual void operator ++ () override { ++iter_; }

		virtual reference operator *  () const override { return *iter_; }
		virtual pointer   operator -> () const override { return iter_.operator -> (); }

		virtual bool operator == (wrapper_base& other) const override
		{
			wrapper* w = dynamic_cast<wrapper*>(&other);
			return w && iter_ == w->iter_;
		}

		virtual wrapper_base* clone() const override { return new wrapper(iter_); }

	private:
		ForwardIterator iter_;
	};

	std::unique_ptr<wrapper_base> wrapper_;
};

template <typename T, typename Traits>
bool operator == (forward_iterator<T, Traits> const& first, forward_iterator<T, Traits> const& second)
{
#pragma GCC diagnostic ignored "-Wparentheses" // icanhaz no warning plox
	return !first.wrapper_ && !second.wrapper_ || *first.wrapper_ == *second.wrapper_;
#pragma GCC diagnostic warning "-Wparentheses"
}

template <typename T, typename Traits>
bool operator != (forward_iterator<T, Traits> const& first, forward_iterator<T, Traits> const& second)
{
	return !(first == second);
}

template <typename T, typename IteratorTraits = default_iterator_traits<T>>
struct forward_range
{
	typedef typename IteratorTraits::size_type size_type;
	typedef typename IteratorTraits::difference_type difference_type;

	typedef typename IteratorTraits::value_type value_type;

	typedef typename IteratorTraits::reference reference;
	typedef typename IteratorTraits::const_reference const_reference;

	typedef typename IteratorTraits::pointer pointer;
	typedef typename IteratorTraits::const_pointer const_pointer;

	typedef forward_iterator<T, IteratorTraits> iterator;

	template <typename ForwardIterator>
	forward_range(ForwardIterator const& begin, ForwardIterator const& end)
		: begin_(begin), end_(end)
	{}

	iterator begin() { return begin_; }
	iterator   end() { return   end_; }

private:
	iterator begin_, end_;
};

//////////////////////////////////

#include <iostream>
#include <vector>

void foo(forward_range<int> r)
{
	for(int i : r)
		std::cout << i << '\n';
}

int main()
{
	std::vector<int> v{ 1, 2, 3, 4, 5 };
	foo({ v.begin(), v.end() });
}

So ungefaehr?

Nexus

Ja, meine Implementierung sieht recht ähnlich aus. Nur ein paar Punkte:

Ich habe in der Basisklasse benannte Funktionen statt Operatoren. Für die Dereferenzierung sollte eigentlich eine Funktion reichen, oder?
Generalisierungen wie Traits implementiere ich normalerweise erst später (warum nicht std::iterator_traits ?). Optimierungen und Debugging werden so einfacher. Auch verschiedene Iteratorkategorien und Const-Iteratoren wären ein Thema...
Auf diverse C++11-Features muss ich wegen Visual Studio verzichten.
Bei operator== würde ich im Release-Modus wohl static_cast statt dynamic_cast nehmen. Verschiedene wrapper -Instantiierungen deuten auf inkompatible Iteratoren hin, da sollte UB zugunsten der Geschwindigkeit vertretbar sein.
Die Range hat weitere Methoden, sodass man sie nicht nur über Iteratoren ansprechen kann.

Kellerautomat

Nexus schrieb:

Ich habe in der Basisklasse benannte Funktionen statt Operatoren. Für die Dereferenzierung sollte eigentlich eine Funktion reichen, oder?

Der Typ von &*iter muss ja nicht gleich dem von iter.operator->() sein, oder?

Nexus schrieb:

Generalisierungen wie Traits implementiere ich normalerweise erst später (warum nicht std::iterator_traits ?). Optimierungen und Debugging werden so einfacher. Auch verschiedene Iteratorkategorien und Const-Iteratoren wären ein Thema...

Auf die Kategorien und const Iteratoren hatte ich gerade keine lust :p

Nexus schrieb:

Bei operator== würde ich im Release-Modus wohl static_cast statt dynamic_cast nehmen. Verschiedene wrapper -Instantiierungen deuten auf inkompatible Iteratoren hin, da sollte UB zugunsten der Geschwindigkeit vertretbar sein.

Das ist eine Designfrage, ueber die ich sicherlich schon ein paar Stunden philosophiert habe. Momentan ist meine favorisierte Loesung hier, statisch Typ-IDs zu vergeben, um dem dynamic_cast auszuweichen und im Falle einer ungleichen ID eine Exception zu schmeissen. Ist ja schliesslich ein Fehler im User-Code, den zu verschleiern war eine dumme Idee.

Nexus schrieb:

Die Range hat weitere Methoden, sodass man sie nicht nur über Iteratoren ansprechen kann.

Welche waeren das denn?
Ich habe nicht wirklich viel Ahnung von Ranges, hast du mir nen Link?

Nexus

@hustbaer: ich hatte deinen Post nicht gesehen... Ich denke, eine Iteratoren-Variante ist von daher gut, dass man sie mit bestehenden Algorithmen und Range-Based For verwenden kann. Hat eine reine Range mehr Optimierungspotential, oder was meinst du dazu?

Das Beispiel bezog sich auf meinen 2. Post im Thread.

@Kellerautomat: kennst du gerade ein Beispiel, wo -> und &* verschieden sind?

Eine Range kann z.B. Methoden anbieten, um sich selbst zu verkleinern oder eine Referenz auf das vorderste Element zurückzugeben. Auch eine Methode, die angibt, ob eine Range leer ist, ist nicht unüblich. So kann man direkt durch die Range iterieren, ohne Iteratoren. Du könntest mal Boost.Range oder die STLSoft RangeLib anschauen. Vielleicht kennt jemand weitere Bibliotheken...

hustbaer

Nexus schrieb:

@hustbaer: ich hatte deinen Post nicht gesehen... Ich denke, eine Iteratoren-Variante ist von daher gut, dass man sie mit bestehenden Algorithmen und Range-Based For verwenden kann. Hat eine reine Range mehr Optimierungspotential, oder was meinst du dazu?

Ich denke vermutlich ja, eine reine Range sollte in dem Fall schneller sein.
Kommt natürlich auch auf die Verwendung drauf an. Wenn die Range an genau so viel Stellen rumkopiert wird wie sonst die Iteratoren dann wird der Unterschied wohl nicht so gross sein.