Not Having A Class For Every Combination Of Features

[adamnovak]

I've been thinking of adding an OrderedHandleGraph type. However, that would double the size of our class hierarchy again, based on whether ordering is supported.

What I want to do is have a HandleGraph<Feature1, Feature2, Feature3, ...> syntax. So I could write:

void do_the_thing(const HandleGraph<Ordered>& ordered_graph);

void do_another_thing(HandleGraph<Paths, Ordered, Mutable>& g1, HandleGraph<Mutable, Ordered>& g2);

class SomeImplementation : public HandleGraph<Mutable, Deletable, Paths, Ordered> {
};

Problems to be overcome:

• Ordering: HandleGraph<Mutable, Ordered> is a different type than HandleGraph<Ordered, Mutable>, and they can't both inherit from each other. We might be able to solve this by using int flags as template parameters: HandleGraph<feature::MUTABLE | feature::ORDERED>. We could also maybe solve this with Fancy Metaprogramming and a template<typename... Ts> using HandleGraph<Ts...> = SortStuff<Ts...>::type and have it give you a canonical type.

• Subsets: HandleGraph<Mutable, Ordered, Paths> has to inherit from HandleGraph<Mutable, Paths>, HandleGraph<Ordered, Paths>, and HandleGraph<Mutable, Ordered>, even if we ignore template argument ordering. Really we're still making our class hierarchy explode, we're just making the compiler do it for us.

[jeizenga]

So with whatever the inheritance is doing in the background, could we still split up the interface to have it be "multi-level" like we have been?

[adamnovak]

@jeizenga I'm trying to have it work that way.

Now I have something that in theory works. But in practice it's so slow that I gave up waiting for vg to build; each file was taking > 10 minutes. I think this comes from the sheer number of internal base classes that need to be searched over for every method. I'm generating a whole stack of base classes per combination of traits you implement, and then some more glue classes to hold them together.

I'm going to see if there's a way this can become sufficiently fast to actually use.

[adamnovak]

OK, I don't think an inheritance-based design like this is ever going to work efficiently in C++, if the compiler isn't fast enough to deal with it the way I did it. I think I could maybe make it build twice as fast by cutting out layers, which is still too slow.

In Scala this would be trivial; it's just with. But the C++ type system does not really want to allow this to happen.

The fundamental problem is that you do have to inherit from all combinations of the traits, if you want to have a base class with each combination of the traits for users to match on as an argument pointer/reference type. If you can't efficiently generate and inherit from all those combinations, you can't do it.

We could pre-generate all the combinations, or generate them with a macro, but I'm not convinced that would be appreciably faster.

We could also try an entity component system? And/or some kind of implicitly-constructible type checking class with a templated constructor?

[glennhickey]

I'm just curious, can you explain why doing pure inheritance (without traits) doesn't apply here? Can't you just add an OrderedHandleGraph interface class an either inherit (with virtual inhertiance) from it or not depending on the implementation (at the cost of one additional class)? The client then uses dynamic cast to see if the HandleGraph pointer you're working with supports the ordered interface or not?

On Mon, May 13, 2019 at 9:08 PM Adam Novak notifications@github.com wrote:

OK, I don't think an inheritance-based design like this is ever going to work efficiently in C++, if the compiler isn't fast enough to deal with it the way I did it. I think I could maybe make it build twice as fast by cutting out layers, which is still too slow.

In Scala this would be trivial; it's just with. But the C++ type system does not really want to allow this to happen.

The fundamental problem is that you do have to inherit from all combinations of the traits, if you want to have a base class with each combination of the traits for users to match on as an argument pointer/reference type. If you can't efficiently generate and inherit from all those combinations, you can't do it.

We could pre-generate all the combinations, or generate them with a macro, but I'm not convinced that would be appreciably faster.

We could also try an entity component system? And/or some kind of implicitly-constructible type checking class with a default constructor?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/vgteam/libhandlegraph/issues/16?email_source=notifications&email_token=AAG373SNNKCDQCEEAFRMTWLPVIGKDA5CNFSM4HMG3L32YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODVJ7DVA#issuecomment-492040660, or mute the thread https://github.com/notifications/unsubscribe-auth/AAG373TXAYNQEZ7DUU4CCBDPVIGKDANCNFSM4HMG3L3Q .

[adamnovak]

If you require the client to use dynamic_cast you can definitely do something similar: just add the features you want to each implementation, and use dynamic_cast on a HandleGraph* to get at each set of features, or throw a runtime error.

What I'm trying to do is preserve type safety: you want your algorithm's function signature to say what features it requires of its arguments, and you want the compiler to work out if you ever use it in a place where you can't guarantee those features are available. If there's a runtime failure, I want it to be at load time, because you couldn't load a graph implementation with the right features from the input given.

I think we might have to continue along the path we have been going down, just manually adding classes for combinations of features that we provide in implementations or require in algorithms. Do we ever need to specify that an algorithm takes a handle graph that is serializable, mutable, and has paths, but which doesn't necessarily have an ordering, node deletion, or path modification? I suspect not.

So for adding in serializability and ordering support, we pull them in at the top of the inheritance hierarchy to start, with the implementation using multiple inheritance to pull in each of them on top of the other HandleGraph classes it derives from. Then if we ever have an algorithm that requires, say, an OrderedMutableHandleGraph, we create that class at that time, add in all the inheritance links, and update the implementations that ought to implement it.

[glennhickey]

Thanks, I get it now. We only have so many graph implementations on the horizon, so hopefully the number of these "combination" classes stay in check. If not, it could be a sign that the hierarchy is overly complex, or perhaps the algorithms aren't modular enough.

On Tue, May 14, 2019 at 12:48 PM Adam Novak notifications@github.com wrote:

If you require the client to use dynamic_cast you can definitely do something similar: just add the features you want to each implementation, and use dynamic_cast on a HandleGraph* to get at each set of features, or throw a runtime error.

What I'm trying to do is preserve type safety: you want your algorithm's function signature to say what features it requires of its arguments, and you want the compiler to work out if you ever use it in a place where you can't guarantee those features are available. If there's a runtime failure, I want it to be at load time, because you couldn't load a graph implementation with the right features from the input given.

I think we might have to continue along the path we have been going down, just manually adding classes for combinations of features that we provide in implementations or require in algorithms. Do we ever need to specify that an algorithm takes a handle graph that is serializable, mutable, and has paths, but which doesn't necessarily have an ordering, node deletion, or path modification? I suspect not.

So for adding in serializability and ordering support, we pull them in at the top of the inheritance hierarchy to start, with the implementation using multiple inheritance to pull in each of them on top of the other HandleGraph classes it derives from. Then if we ever have an algorithm that requires, say, an OrderedMutableHandleGraph, we create that class at that time, add in all the inheritance links, and update the implementations that ought to implement it.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/vgteam/libhandlegraph/issues/16?email_source=notifications&email_token=AAG373S3UKJQVWW3FQFFLDLPVLUPVA5CNFSM4HMG3L32YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODVMC5FI#issuecomment-492318357, or mute the thread https://github.com/notifications/unsubscribe-auth/AAG373RSTXQEIUUM5IT5QO3PVLUPVANCNFSM4HMG3L3Q .