Type-Erased Ranges

Nexus

Hallo zusammen

Was denkt ihr über Ranges, in denen der Iteratortyp wegabstrahiert wird? Zum Beispiel soll Range<int> eine abstrakte Ansicht von Containern mit int als Elementtyp ermöglichen.

Implementierungen kenne ich bisher nur boost::any_range , aber die kommt meiner Meinung nach mit dem typischen Boost-Overengineering, ausserdem gibt es einige Bugs und übelste Fehlermeldungen (beides teilweise als Resultat der Generizität). Entwicklungen in der C++-Community scheinen vor allem in Richtung Iterator-Range zu gehen, z.B. in diesem Paper. Sowas wie std::range<Iterator> wäre der direkt nächste Schritt von heutigen Iteratoren und als solcher ein sehr nützliches Tool.

Jedoch habe ich persönlich schon einige Male eine Range vermisst, die noch abstrakter ist und direkt auf Elementtypen eingeht. Eventuell könnte man die konkreten (erased) Typen sogar mit einer herkömmlichen Iterator-Range umsetzen. Eine abstrahierte Range könnte abstrahierte Iteratoren anbieten, um Kompatibilität zu STL-Algorithmen oder Range Based For zu gewährleisten.

Vorteile einer Range-Klasse mit Type Erasure wären:

Der Iteratortyp muss bei der Deklaration nicht bekannt sein. Man spart sich Compiletime-Abhängigkeiten, ausserdem kann man Range-Algorithmen für ein konkretes T als Nicht-Template-Funktionen schreiben.
Die Range ist flexibler und kann aus verschiedenen Iteratortypen bestehen. Dadurch ist es möglich, Elemente aus mehreren Containertypen in eine einzelne Range zusammenzufassen.
Code wird einfacher, da mit dem Elementtyp direkt die relevante Information dort steht und der Iteratortyp als Implementierungsdetail versteckt wird. Denn selbst wenn durch Typinferenz einiges dem Compiler überlassen werden kann, müsste der Iteratortyp (sei er nur ein typedef ) doch als Parameter und Member jeweils hingeschrieben werden. Mit Type-Erased Ranges werden zudem Fehlermeldungen freundlicher.

Nachteile dieses Ansatzes:

Recht teuer, da Operationen auf Iteratoren indirekt angesprochen werden, z.B. über virtuelle Funktionen. Auch ist mehr Speicheroverhead als ein begin-end-Paar notwendig.
Man müsste sich überlegen, wie man verschiedene Iteratorkategorien (Traversal und evtl. Access im Boost-Sinne) umsetzt. Möglichkeiten wären z.B. zusätzliche Templateparameter oder spezialisierte Klassen, mit entsprechenden Konvertierungen untereinander.

Was meint ihr dazu?

knivil

Was meint ihr dazu?

Nichts. Wozu soll das gut sein bzw. welches Problem soll geloest werden.?

persönlich schon einige Male eine Range vermisst

Beispiele?

die noch abstrakter

Also doch kein echtes Problem.

Ansonsten ist http://www.artima.com/cppsource/type_erasure.html wahrscheinlich auch auf Ranges anwendbar.

Nexus

knivil schrieb:

die noch abstrakter

Also doch kein echtes Problem.

Interessante Schlussfolgerung

knivil schrieb:

Nichts. Wozu soll das gut sein bzw. welches Problem soll geloest werden.?

Ich habe ja relativ genau beschrieben, in welchen Fällen man gegenüber einer herkömmlichen Range (wie das std::range -Proposal) profitiert, und die Anwendungsfälle von Ranges brauche ich wohl nicht zu erläutern.

Konkretes Beispiel:

void Ai::ControlUnits(FwdRange<Unit> units);

// anstelle von

void Ai::ControlUnits(boost::ptr_vector<Unit>& units);

void Ai::ControlUnits(boost::iterator_range<boost::ptr_vector<Unit>::iterator> units);

template <typename FwdItr>
void Ai::ControlUnits(FwdItr begin, FwdItr end);

knivil schrieb:

Ansonsten ist http://www.artima.com/cppsource/type_erasure.html wahrscheinlich auch auf Ranges anwendbar.

Ich weiss, das ist nicht das Problem. Mich interessiert es, ob die Anwendungsfälle nachvollziehbar sind, oder ob man das Gleiche auf eine bessere Art erreichen könnte. Bzw. was ihr generell davon hält, wenn möglich mit Argumenten. Und vielleicht auch -- was ich mich bei vielen Dingen frage -- warum sowas nicht populärer ist (nur Performance?)

Shade Of Mine

Ich sehe da nur eine andere Schreibweise.
Wenn du eh Typlose Iteratoren aktzeptierst kannst du ja auch
void foo(iterator_range<T>)
erlauben.

Nexus

Ich verstehe nicht ganz, was du damit sagen willst... Bei

template <typename T>
void Foo(boost::iterator_range<T> r);

müsste ich ja wieder die Funktion als Template schreiben, ausserdem ist das Interface weniger aussagekräftig (Range mit was für Elementen?).

Kellerautomat

Ich habe selbst schon desoefteren darueber nachgedacht. IMO waere so eine Range aufgrund des klaren Interfaces einem Template vorzuziehen, die Kosten halte ich nicht fuer so schlimm. Wir verwenden schließlich auch std::vector wenn wir oft nur < 100 Elemente brauchen, und der alloziert auch auf dem Heap.

Shade Of Mine

Nexus schrieb:

Ich verstehe nicht ganz, was du damit sagen willst... Bei
template <typename T>
void Foo(boost::iterator_range<T> r);
müsste ich ja wieder die Funktion als Template schreiben, ausserdem ist das Interface weniger aussagekräftig (Range mit was für Elementen?).

Ah du willst das Template wegbringen? wie wäre es mit iterator_range<any_iterator> oder any_range?
type erasure kostet halt und es gibt ja eh any_iterator.

Du willst aber den Typ drinnen haben im Interface aber den Container type erasen, richtig?
Welchen Vorteil siehst du dabei?

PS:
Kellerautomat:
Doof nur dass man iteratoren öfters kopiert als vectoren

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