Defining interfaces in C++: concepts versus inheritance

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.

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

16 thoughts on “Defining interfaces in C++: concepts versus inheritance”

      1. 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.

  1. 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.

    1. Memory usage errors become difficult to make when your program has no visible pointers.

      Which would kind of take us back to Pascal 🙂

  2. If I mark the count_inheritance function as inline and pass to it an iter_base instance with a compile-time deducible type, will a modern optimizing compiler do the same (or similar) optimizations as for the concept-based approach?

    1. Sadly even with inline the compilers cannot inline the virtual method calls. Actually, it is even worse (at least with GCC): adding inheritance spoils the constexpr , now the compiler needs to make virtual function calls even in the context of templates.

      I had to add final to iterable_arry to recover optimizations.

      See the assembly for concept_count and inheritance_count functions with and without final:

      https://godbolt.org/z/6o1v7hEME

  3. taking a concept instance as a parameter

    No, no, no. The function template count takes a template type T parameter which satisfies the concept is_iterable. Concept is a set of constraints over types. One cannot really pass a concept as an argument — that’s just too much meta.

  4. 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.

  5. That passage about “Given an optimizing compiler…” leaves me puzzled. Why would compiler developers go as far as teaching it to reason about programers code to this extent? Optimizing “count(a)” to just returning the size of vector is not a kind of optimization I would like to get under the hood. Because it brings a side effect that can lead to errors in the program. Inner “index” value wouldn’t be changed, while it should.

Leave a Reply

Your email address will not be published.

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax

You may subscribe to this blog by email.