In a previous blog post, I showed how you could define ‘an interface’ in C++ using concepts. For example, I can specify that a type should have the methods has_next, next and reset:
template <typename T> concept is_iterable = requires(T v) { { v.has_next() } -> std::convertible_to<bool>; { v.next() } -> std::same_as<uint32_t>; { v.reset() }; };
I can then define a function template, taking a concept instance as a parameter:
template <is_iterable T> size_t count(T &t) { t.reset(); size_t count = 0; while (t.has_next()) { t.next(); count++; } return count; }
In that blog post, I stated that I did not take into account inheritance as a strategy. Let us do so. We can define a generic base class and a corresponding generic function:
class iter_base { public: virtual bool has_next() = 0; virtual uint32_t next() = 0; virtual void reset() = 0; virtual ~iter_base() = default; }; size_t count_inheritance(iter_base &t) { t.reset(); size_t count = 0; while (t.has_next()) { t.next(); count++; } return count; }
I can define a class that is suitable for both functions, as it satisfies the inheritance condition, as well as the concept:
struct iterable_array : iter_base { std::vector<uint32_t> array{}; size_t index = 0; void reset() { index = 0; } bool has_next() { return index < array.size(); } uint32_t next() { index++; return array[index - 1]; } };
So far so good. But what is the difference between these two expressions given that a is an instance of iterable_array?
- count(a),
- count_inheritance(a).
Given an optimizing compiler, the first function (count(a)) is likely to just immediately return the size of the backing vector. The function is nearly free.
The second function (count_inheritance(a)) does not know anything about the iterable_array type so it will iterate through the content naively, and might be hundreds of times more expensive.
Should the inheritance not be public? C++ defaults to private inheritance.
Why would that be a concern?
Private inheritance means you don’t get the base class interface as your own in the derived class. It is not an “is a” relation. It’s more of a “has a” relation.
Ah but you had a strict! My mistake!
“Struct”
In the example,
iterable_arrayis defined as astruct, which defaults to public inheritance.Moreso: when things are decided at runtime, bugs are not detected without a test that tickles them. With things decided at compile time, you often get to have the compiler refuse to compile the bugs.
It is a daily occurrence for modern C++ code, as with Rust code, to run correctly on the first try. Memory usage errors become difficult to make when your program has no visible pointers. Concurrency errors become difficult to make when you have no visible threads or thread synchronization.
Which would kind of take us back to Pascal 🙂
It’s nice seeing someone discovering Alex Stepanov ideas of from 90s.
Can you please explain that in more detail?
If I mark the
count_inheritancefunction asinlineand pass to it aniter_baseinstance with a compile-time deducible type, will a modern optimizing compiler do the same (or similar) optimizations as for the concept-based approach?In theory, I suppose it could, but I have not observed this behaviour in the scenario outlined in the blog post.
Sadly even with
inlinethe compilers cannot inline the virtual method calls. Actually, it is even worse (at least with GCC): adding inheritance spoils theconstexpr, now the compiler needs to make virtual function calls even in the context of templates.I had to add
finaltoiterable_arryto recover optimizations.See the assembly for
concept_countandinheritance_countfunctions with and withoutfinal:https://godbolt.org/z/6o1v7hEME
taking a concept instance as a parameter
No, no, no. The function template
counttakes a template typeTparameter which satisfies the conceptis_iterable. Concept is a set of constraints over types. One cannot really pass a concept as an argument — that’s just too much meta.You see this sentiment echoed a lot and while in practice, it is mostly true, it’s not because virtualisation is inherently evil, it’s that optimisers are not very good at devirtualisation. In this example, it’s trivial to devirtualise iterable_array with lto or wpo and if it’s marked final it’ll even work across a dynamic boundary.
Saying that concepts are still simpler and more expressive, easier to use and harder to misuse and in practice generate better code.