Repository files navigation

At this point, this library is experimental and it is a pure curiosity.No stability of interface or quality of implementation is guaranteed.Use at your own risks.

Dyno solves the problem of runtime polymorphism better than vanilla C++does. It provides a way to define interfaces that can be fulfillednon-intrusively, and it provides a fully customizable way of storingpolymorphic objects and dispatching to virtual methods. It does notrequire inheritance, heap allocation or leaving the comfortable worldof value semantics, and it can do so while outperforming vanilla C++.

Dyno is pure-library implementation of what's also known asRust traitobjects,Go interfaces,Haskell type classes, andvirtual concepts.Under the hood, it uses a C++ technique known astype erasure, which isthe idea behindstd::any,std::function and many other useful types.

#include<dyno.hpp>#include<iostream>usingnamespacedyno::literals;// Define the interface of something that can be drawnstructDrawable : decltype(dyno::requires_("draw"_s = dyno::method<void (std::ostream&)const>)) { };// Define how concrete types can fulfill that interfacetemplate<typename T>autoconst dyno::default_concept_map<Drawable, T> = dyno::make_concept_map("draw"_s = [](Tconst& self, std::ostream& out) { self.draw(out); });// Define an object that can hold anything that can be drawn.structdrawable {template<typename T>drawable(T x) : poly_{x} { }voiddraw(std::ostream& out)const  { poly_.virtual_("draw"_s)(out); }private:  dyno::poly<Drawable> poly_;};structSquare {voiddraw(std::ostream& out)const { out <<"Square"; }};structCircle {voiddraw(std::ostream& out)const { out <<"Circle"; }};voidf(drawableconst& d) {  d.draw(std::cout);}intmain() {f(Square{});// prints Squaref(Circle{});// prints Circle}

Alternatively, if you find this to be too much boilerplate and you can standusing a macro, the following is equivalent:

#include<dyno.hpp>#include<iostream>// Define the interface of something that can be drawnDYNO_INTERFACE(Drawable,  (draw,void (std::ostream&)const));structSquare {voiddraw(std::ostream& out)const { out <<"Square"; }};structCircle {voiddraw(std::ostream& out)const { out <<"Circle"; }};voidf(Drawableconst& d) {  d.draw(std::cout);}intmain() {f(Square{});// prints Squaref(Circle{});// prints Circle}

This is a C++17 library. No efforts will be made to support older compilers(sorry). The library is known to work with the following compilers:

The library depends onBoost.Hana andBoost.CallableTraits. The unittests depend onlibawful and the benchmarks depend onGoogle Benchmark,Boost.TypeErasure andMpark.Variant, but you don't need them to usethe library. For local development, thedependencies/install.sh script canbe used to install all the dependencies automatically.

Dyno is a header-only library, so there's nothing to build per-se. Justadd theinclude/ directory to your compiler's header search path (and makesure the dependencies are satisfied), and you're good to go. However, thereare unit tests, examples and benchmarks that can be built:

(cd dependencies&& ./install.sh)# Install dependencies; will print a path to add to CMAKE_PREFIX_PATHmkdir build(cd build&& cmake .. -DCMAKE_PREFIX_PATH="${PWD}/../dependencies/install")# Setup the build directorycmake --build build --target examples# Build and run the examplescmake --build build --target tests# Build and run the unit testscmake --build build --target check# Does both examples and testscmake --build build --target benchmarks# Build and run the benchmarks

In programming, the need for manipulating objects with a common interface butwith a different dynamic type arises very frequently. C++ solves this withinheritance:

structDrawable {virtualvoiddraw(std::ostream& out)const = 0;};structSquare : Drawable {virtualvoiddraw(std::ostream& out)constoverridefinal { ... }};structCircle : Drawable {virtualvoiddraw(std::ostream& out)constoverridefinal { ... }};voidf(Drawableconst* drawable) {  drawable->draw(std::cout);}

However, this approach has several drawbacks. It is

1. Intrusive
   In order forSquare andCircle to fulfill theDrawable interface, theyboth need to inherit from theDrawable base class. This requires havingthe license to modify those classes, which makes inheritance very inextensible.For example, how would you make astd::vector<int> fulfill theDrawableinterface? You simply can't.

2. Incompatible with value semantics
   Inheritance requires you to pass polymorphic pointers or references to objectsinstead of the objects themselves, which plays very badly with the rest ofthe language and the standard library. For example, how would you copy avector ofDrawables? You'd need to provide a virtualclone() method, butnow you've just messed up your interface.

3. Tightly coupled with dynamic storage
   Because of the lack of value semantics, we usually end up allocating thesepolymorphic objects on the heap. This is both horribly inefficient andsemantically wrong, since chances are we did not need the dynamic storageduration at all, and an object with automatic storage duration (e.g. onthe stack) would have been enough.

4. Prevents inlining
   95% of the time, we end up calling a virtual method through a polymorphicpointer or reference. That requires three indirections: one for loading thepointer to the vtable inside the object, one for loading the right entry inthe vtable, and one for the indirect call to the function pointer. All thisjumping around makes it difficult for the compiler to make good inliningdecisions. However, it turns out that all of these indirections except theindirect call can be avoided.

Unfortunately, this is the choice that C++ has made for us, and these are therules that we are bound to when we need dynamic polymorphism. Or is it really?

Dyno solves the problem of runtime polymorphism in C++ without any of thedrawbacks listed above, and many more goodies. It is:

1. Non-intrusive
   An interface can be fulfilled by a type without requiring any modificationto that type. Heck, a type can even fulfill the same interface in differentways! WithDyno, you can kiss ridiculous class hierarchies goodbye.

2. 100% based on value semantics
   Polymorphic objects can be passed as-is, with their natural value semantics.You need to copy your polymorphic objects? Sure, just make sure they havea copy constructor. You want to make sure they don't get copied? Sure, markit as deleted. WithDyno, sillyclone() methods and the proliferationof pointers in APIs are things of the past.

3. Not coupled with any specific storage strategy
   The way a polymorphic object is stored is really an implementation detail,and it should not interfere with the way you use that object.Dyno givesyou complete control over the way your objects are stored. You have a lot ofsmall polymorphic objects? Sure, let's store them in a local buffer andavoid any allocation. Or maybe it makes sense for you to store things onthe heap? Sure, go ahead.

4. Flexible dispatch mechanism to achieve best possible performance
   Storing a pointer to a vtable is just one of many different implementationstrategies for performing dynamic dispatch.Dyno gives you completecontrol over how dynamic dispatch happens, and can in fact beat vtablesin some cases. If you have a function that's called in a hot loop, you canfor example store it directly in the object and skip the vtable indirection.You can also use application-specific knowledge the compiler could neverhave to optimize some dynamic calls — library-level devirtualization.

First, you start by defining a generic interface and giving it a name.Dyno provides a simple domain specific language to do that. For example,let's define an interfaceDrawable that describes types that can be drawn:

#include<dyno.hpp>usingnamespacedyno::literals;structDrawable : decltype(dyno::requires_("draw"_s = dyno::method<void (std::ostream&)const>)) { };

This definesDrawable as representing an interface for anything that has amethod calleddraw taking a reference to astd::ostream.Dyno callsthese interfacesdynamic concepts, since they describe sets of requirementsto be fulfilled by a type (like C++ concepts). However, unlike C++ concepts,thesedynamic concepts are used to generate runtime interfaces, hence thenamedynamic. The above definition is basically equivalent to the following:

structDrawable {virtualvoiddraw(std::ostream&)const = 0;};

Once the interface is defined, the next step is to actually create a type thatsatisfies this interface. With inheritance, you would write something like this:

structSquare : Drawable {virtualvoiddraw(std::ostream& out)constoverridefinal {    out <<"square" << std::endl;  }};

WithDyno, the polymorphism is non-intrusive and it is instead providedvia what is called aconcept map (afterC++0x Concept Maps):

structSquare {/* ...*/ };template<>autoconst dyno::concept_map<Drawable, Square> = dyno::make_concept_map("draw"_s = [](Squareconst& square, std::ostream& out) {    out <<"square" << std::endl;  });

This construct is the specialization of a C++14 variable template namedconcept_map defined in thedyno:: namespace. We then initialize thatspecialization withdyno::make_concept_map(...).

The first parameter of the lambda is the implicit*this parameter that isimplied when we declareddraw as a method above. It's also possible toerase non-member functions (seethe relevant section).

Thisconcept map defines how the typeSquare satisfies theDrawableconcept. In a sense, itmaps the typeSquare to its implementation ofthe concept, which motivates the appellation. When a type satisfies therequirements of a concept, we say that the typemodels (or is a model of)that concept. Now thatSquare is a model of theDrawable concept, we'dlike to use aSquare polymorphically as aDrawable. With traditionalinheritance, we would use a pointer to a base class like this:

voidf(Drawableconst* d) {  d->draw(std::cout);}f(new Square{});

WithDyno, polymorphism and value semantics are compatible, and the waypolymorphic types are passed around can be highly customized. To do this,we'll need to define a type that can hold anything that'sDrawable. It isthat type, instead of aDrawable*, that we'll be passing around to and frompolymorphic functions. To help define this wrapper,Dyno provides thedyno::poly container, which can hold an arbitrary object satisfying a givenconcept. As you will see,dyno::poly has a dual role: it stores the polymorphicobject and takes care of the dynamic dispatching of methods. All you need to dois write a thin wrapper overdyno::poly to give it exactly the desired interface:

structdrawable {template<typename T>drawable(T x) : poly_{x} { }voiddraw(std::ostream& out)const  { poly_.virtual_("draw"_s)(out); }private:  dyno::poly<Drawable> poly_;};

Note: You could technically usedyno::poly directly in your interfaces.However, it is much more convenient to use a wrapper with real methodsthandyno::poly, and so writing a wrapper is recommended.

Let's break this down. First, we define a memberpoly_ that is a polymorphiccontainer for anything that models theDrawable concept:

dyno::poly<Drawable> poly_;

Then, we define a constructor that allows constructing this container from anarbitrary typeT:

template<typename T>drawable(T x) : poly_{x} { }

The unsaid assumption here is thatT actually models theDrawable concept.Indeed, when you create adyno::poly from an object of typeT,Dynowill go and look at the concept map defined forDrawable andT, if any. Ifthere's no such concept map, the library will report that we're trying to createadyno::poly from a type that does not support it, and your program won't compile.

Finally, the strangest and most important part of the definition above is thatof thedraw method:

voiddraw(std::ostream& out)const{ poly_.virtual_("draw"_s)(out); }

What happens here is that when.draw is called on ourdrawable object,we'll actually perform a dynamic dispatch to the implementation of the"draw"function for the object currently stored in thedyno::poly, and call that.Now, to create a function that accepts anything that'sDrawable, no needto worry about pointers and ownership in your interface anymore:

voidf(drawable d) {  d.draw(std::cout);}f(Square{});

By the way, if you're thinking that this is all stupid and you should have beenusing a template, you're right. However, consider the following, where you reallydo needruntime polymorphism:

drawableget_drawable() {if (some_user_input())return Square{};elsereturn Circle{};}f(get_drawable());

Strictly speaking, you don't need to wrapdyno::poly, but doing so puts a nicebarrier betweenDyno and the rest of your code, which never has to worryabout how your polymorphic layer is implemented. Also, we largely ignored howdyno::poly was implemented in the above definition. However,dyno::poly isa very powerful policy-based container for polymorphic objects that can becustomized to one's needs for performance. Creating adrawable wrapper makesit easy to tweak the implementation strategy used bydyno::poly for performancewithout impacting the rest of your code.

The first aspect that can be customized in adyno::poly is the way the objectis stored inside the container. By default, we simply store a pointer to theactual object, like one would do with inheritance-based polymorphism. However,this is often not the most efficient implementation, and that's whydyno::polyallows customizing it. To do so, simply pass a storage policy todyno::poly.For example, let's define ourdrawable wrapper so that it tries to storeobjects up to16 bytes in a local buffer, but then falls back to the heapif the object is larger:

structdrawable {template<typename T>drawable(T x) : poly_{x} { }voiddraw(std::ostream& out)const  { poly_.virtual_("draw"_s)(out); }private:  dyno::poly<Drawable, dyno::sbo_storage<16>> poly_;//                   ^^^^^^^^^^^^^^^^^^^^^ storage policy};

Notice that nothing except the policy changed in our definition. That is onevery important tenet ofDyno; these policies are implementationdetails, and they should not change the way you write your code. With theabove definition, you can now createdrawables just like you did before,and no allocation will happen when the object you're creating thedrawablefrom fits in16 bytes. When it does not fit, however,dyno::poly will allocatea large enough buffer on the heap.

Let's say you actually never want to do an allocation. No problem, just changethe policy todyno::local_storage<16>. If you try to construct adrawablefrom an object that's too large to fit in the local storage, your programwon't compile. Not only are we saving an allocation, but we're also saving apointer indirection every time we access the polymorphic object if we compareto the traditional inheritance-based approach. By tweaking these (important)implementation details for you specific use case, you can make your programmuch more efficient than with classic inheritance.

Other storage policies are also provided, likedyno::remote_storage anddyno::non_owning_storage.dyno::remote_storage is the default one, whichalways stores a pointer to a heap-allocated object.dyno::non_owning_storagestores a pointer to an object that already exists, without worrying aboutthe lifetime of that object. It allows implementing non-owning polymorphicviews over objects, which is very useful.

Custom storage policies can also be created quite easily. See<dyno/storage.hpp>for details.

When we introduceddyno::poly, we mentioned that it had two roles; the firstis to store the polymorphic object, and the second one is to perform dynamicdispatch. Just like the storage can be customized, the way dynamic dispatchingis performed can also be customized using policies. For example, let's defineourdrawable wrapper so that instead of storing a pointer to the vtable, itinstead stores the vtable in thedrawable object itself. This way, we'llavoid one indirection each time we access a virtual function:

structdrawable {template<typename T>drawable(T x) : poly_{x} { }voiddraw(std::ostream& out)const  { poly_.virtual_("draw"_s)(out); }private:using Storage = dyno::sbo_storage<16>;// storage policyusing VTable = dyno::vtable<dyno::local<dyno::everything>>;// vtable policy  dyno::poly<Drawable, Storage, VTable> poly_;};

Notice that nothing besides the vtable policy needs to change in the definitionof ourdrawable type. Furthermore, if we wanted, we could change the storagepolicy independently from the vtable policy. With the above, even though we aresaving all indirections, we are paying for it by making ourdrawable objectlarger (since it needs to hold the vtable locally). This could be prohibitiveif we had many functions in the vtable. Instead, it would make more sense tostore most of the vtable remotely, but only inline those few functions that wecall heavily.Dyno makes it very easy to do so by usingSelectors, whichcan be used to customize what functions a policy applies to:

structdrawable {template<typename T>drawable(T x) : poly_{x} { }voiddraw(std::ostream& out)const  { poly_.virtual_("draw"_s)(out); }private:using Storage = dyno::sbo_storage<16>;using VTable = dyno::vtable<    dyno::local<dyno::only<decltype("draw"_s)>>,    dyno::remote<dyno::everything_else>  >;  dyno::poly<Drawable, Storage, VTable> poly_;};

Given this definition, the vtable is actually split in two. The first part islocal to thedrawable object and contains only thedraw method. The secondpart is a pointer to a vtable in static storage that holds the remaining methods(the destructor, for example).

Dyno provides two vtable policies,dyno::local<> anddyno::remote<>.Both of these policies must be customized using aSelector. The selectorssupported by the library aredyno::only<functions...>,dyno::except<...>,anddyno::everything_else (which can also be spelleddyno::everything).

When defining a concept, it is often the case that one can provide a defaultdefinition for at least some functions associated to the concept. For example,by default, it would probably make sense to use a member function nameddraw(if any) to implement the abstract"draw" method of theDrawable concept.For this, one can usedyno::default_concept_map:

template<typename T>autoconst dyno::default_concept_map<Drawable, T> = dyno::make_concept_map("draw"_s = [](autoconst& self, std::ostream& out) { self.draw(out); });

Now, whenever we try to look at how some typeT fulfills theDrawableconcept, we'll fall back to the default concept map if no concept map wasdefined. For example, we can create a new typeCircle:

structCircle {voiddraw(std::ostream& out)const {    out <<"circle" << std::endl;  }};f(Circle{});// prints "circle"

Circle is automatically a model ofDrawable, even though we did notexplicitly define a concept map forCircle. On the other hand, if wewere to define such a concept map, it would have precedence over thedefault one:

template<>auto dyno::concept_map<Drawable, Circle> = dyno::make_concept_map("draw"_s = [](Circleconst& circle, std::ostream& out) {    out <<"triangle" << std::endl;  });f(Circle{});// prints "triangle"

It is sometimes useful to define a concept map for a complete family of typesall at once. For example, we might want to makestd::vector<T> a model ofDrawable, but only whenT can be printed to a stream. This is easilyachieved by using this (not so) secret trick:

template<typename T>autoconst dyno::concept_map<Drawable, std::vector<T>, std::void_t<decltype(  std::cout << std::declval<T>())>> = dyno::make_concept_map("draw"_s = [](std::vector<T>const& v, std::ostream& out) {for (autoconst& x : v)      out << x <<'';  });f(std::vector<int>{1,2,3})// prints "1 2 3 "

Notice how we do not have to modifystd::vector at all. How could we dothis with classic polymorphism? Answer: no can do.

Dyno allows erasing non-member functions and functions that are dispatchedon an arbitrary argument (but only one argument) too. To do this, simply definethe concept usingdyno::function instead ofdyno::method, and use thedyno::T placeholder to denote the argument being erased:

// Define the interface of something that can be drawnstructDrawable : decltype(dyno::requires_("draw"_s = dyno::function<void (dyno::Tconst&, std::ostream&)>)) { };

Thedyno::T const& parameter used above represents the type of the objecton which the function is being called. However, it does not have to be thefirst parameter:

structDrawable : decltype(dyno::requires_("draw"_s = dyno::function<void (std::ostream&, dyno::Tconst&)>)) { };

The fulfillment of the concept does not change whether the concept uses amethod or a function, but make sure that the parameters of your functionimplementation match that of the function declared in the concept:

// Define how concrete types can fulfill that interfacetemplate<typename T>autoconst dyno::default_concept_map<Drawable, T> = dyno::make_concept_map("draw"_s = [](std::ostream& out, Tconst& self) { self.draw(out); }//            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ matches the concept definition);

Finally, when calling afunction on adyno::poly, you'll have to pass inall the parameters explicitly, sinceDyno can't guess which one you wantto dispatch on. The parameter that was declared with adyno::T placeholderin the concept should be passed thedyno::poly itself:

// Define an object that can hold anything that can be drawn.structdrawable {template<typename T>drawable(T x) : poly_{x} { }voiddraw(std::ostream& out)const  { poly_.virtual_("draw"_s)(out, poly_); }//                              ^^^^^ passing the poly explicitlyprivate:  dyno::poly<Drawable> poly_;};