Polymorphism and Performance

From Virtual Functions to Data Oriented Design

When developing software, one of the first Object Oriented Programming patterns that is taught is the inheritance pattern, or an is-a relationship. As a basic example, if we have some abstract class Shape, we might have classes like Square, Circle and Triangle that inherit from Shape, each of which has an area() function. Then when processing a collection of shapes, we don’t need to know what concrete type they are, just that they are Shapes, and therefore have an area function. We’ll show how we can implement a system like this in C++, as well as the performance of various implementations.

Virtual Functions

The traditional method of implementing polymorphic behavior at runtime in C++ is through the use of virtual functions. As such, a Shape class would be implemented as follows

class Shape
{
 public:
  virtual ~Shape() = default;
  virtual double area() const = 0;
};

We must first declare our destructor to be virtual¹, and can then declare the pure-virtual area function to return a double. The difference between a normal virtual function and a pure virtual function is that there is no implementation to be overridden in the base class, all children must provide an implementation in order to be instantiated. We’re then going to also create our first concrete Shape object, a square.

class Square : public Shape
{
 private:
  double _side;

 public:
  Square(const double side) : _side{side} {}
  double area() const override { return _side * _side; }
};

As you can see, we inherit from Shape, store a double for the square side length, and implement area() with the override keyword. To understand the mechanics of what’s actually going on here, it’s helpful to look at the compiled code of the following example

// Implemented in a different translation unit
Shape* get_shape();

int main(){
    get_shape()->area();
}

When we run the following code through Compiler Explorer, we have the following assembly generated.

main:
        push    rax
        call    get_shape()@PLT
        mov     rcx, qword ptr [rax]
        mov     rdi, rax
        call    qword ptr [rcx + 16]
        xor     eax, eax
        pop     rcx
        ret

In C++, classes with virtual functions are structured with the first data member of the class being a pointer to the virtual table, followed by the data members of the class instance. If we look at our Square/Shape example, we would expect our Square object to look something like this

Memory Layout for Two Squares

Each of our instances of square has a pointer to the vtable as the first element, and a data member of a single double as the second element. Then within the vtable, we have the base object destructor for deleting a Shape, as well as the deleting destructor for destroying the Square, and finally the address of the Square::area function. You can see this through the generated machine instructions if we add an instantiation of a square to force the compiler to generate the vtable.

With this layout in mind, our above assembly makes more sense. After we call to get_shape, rax holds the address of our newly returned object. We then load the value pointed to by rax into rcx, so the rcx register now holds the address of the base of the vtable. Then to invoke our area function, we call rcx + 16, since we want to invoke the third entry in the vtable which corresponds to the area function.

Benchmarking our Performance

From a performance perspective, a few things should stick out. First we need to load an address from memory, then jump to that address to invoke the function call. This means our function isn’t inlined, and depends on a separate memory load before we can invoke it. Let’s build a small benchmark to measure the performance of our Square implementation, summing up the area of all squares.

static std::vector<std::unique_ptr<Shape>> build_shapes(const int nSquares,
                                                        const int nTriangles,
                                                        const int nCircles)
{
  std::vector<std::unique_ptr<Shape>> result;
  result.reserve(nSquares + nTriangles + nCircles);
  for (int i = 0; i < nSquares; ++i)
  {
    result.emplace_back(std::make_unique<Square>(i));
  }
  for (int i = 0; i < nTriangles; ++i)
  {
    result.emplace_back(std::make_unique<Triangle>(i, i + 1));
  }
  for (int i = 0; i < nCircles; ++i)
  {
    result.emplace_back(std::make_unique<Circle>(i));
  }
  return result;
}

static void BM_shapes_all_squares(benchmark::State& state)
{
  const auto shapes = build_shapes(1000000, 0, 0);
  for (const auto& s : state)
  {
    double total_area = 0;
    for (const auto& shape : shapes)
    {
      total_area += shape->area();
    }
    benchmark::DoNotOptimize(total_area);
    benchmark::ClobberMemory();
  }
  state.SetItemsProcessed(shapes.size() * state.iterations());
}

Our benchmark is pretty straightforward, just build a vector of 1,000,000 Shapes, all squares, then sum the total area of all of these shapes. Running this on my hardware, the benchmark is able to process just shy of 300 million shapes per second.

Devirtualization

While this seems like a decent throughput, there are a few things holding us back. Namely, we’re forced to make a function call for every iteration of the loop, as we saw in the generated assembly. Because our function to calculate the area is so small, it would hugely benefit from being inlined, but this isn’t happening because the data we’re iterating over is a vector<Shape*>. While we know that we’re only putting in Squares, the compiler doesn’t have visibility into that and can’t optimize around it. What if we instead generated a vector<Square*> to sum up? With a few small tweaks, we have the following

static std::vector<std::unique_ptr<Square>> build_squares(const int nSquares)
{
  std::vector<std::unique_ptr<Square>> result;
  result.reserve(nSquares);
  for (int i = 0; i < nSquares; ++i)
  {
    result.emplace_back(std::make_unique<Square>(i));
  }
  return result;
}

static void BM_just_squares(benchmark::State& state)
{
  const auto shapes = build_squares(1000000);
  for (const auto& s : state)
  {
    double total_area = 0;
    for (const auto& square : shapes)
    {
      total_area += square->area();
    }
    benchmark::DoNotOptimize(total_area);
    benchmark::ClobberMemory();
  }
  state.SetItemsProcessed(shapes.size() * state.iterations());
}

When we run this benchmark, the compiler should be able to know that square→area() always calls Square::area since shape is always a Square. However, the performance results are disappointing.

We see we have essentially identical performance to our vector<Shape*> benchmark, despite knowing what the concrete type of our objects are. To understand why, we can look at the assembly of our small example if we replace our get_shape function to return a Square* instead of a Shape*

// Shape* get_shape();
Square* get_shape();

int main(){
    get_shape()->area();
}

With that change, we see our generated assembly is… exactly the same as when we returned a Shape*. This is happening because while we declared Square to be an implementation of Shape, we left it open for extension. That is to say, there could be another class that extends Square with its own implementation of area, such as the following

class ToggleableSquare : public Square
{
 private:
  bool _is_visible;

 public:
  ToggleableSquare(const double side, const bool is_visible) : Square{side}, _is_visible{is_visible} {}
  double area() const override { return _is_visible ? Square::area() : 0.0; }
};

Again, our compiler cannot know at compile time just by looking at a single function that the Square is the final, most derived function in the inheritance hierarchy. Unless, of course, we marked our square area as final instead of override. If we do that, we see that our generated assembly now fully omits the call to area, since the compiler knows Square’s implementation of area is the one that will be invoked, and since the result is entirely unused and has no side effects, it can eliminate the call altogether in our example.

We see a similar change if we mark Square’s call to area as final, with our benchmark on vector<Square*> nearly doubling in speed.

Polymorphism and Memory Layout

While these benchmarks have shown how our virtual functions perform as compared with a known-concrete implementation, we’ve left out a detail that makes our benchmark pretty unrepresentative of real-world scenarios. Because of the requirements that a virtual class must be held in an allocated piece of memory since the size of the class cannot be known at compile time (e.g. you cannot have a vector<Shape> since each shape may be a different concrete class with different sizes), our code is forced to interact with Shapes via a unique_ptr. However, the way that we allocated these pointers was within a fresh program, allocating all one million in a single shot. This means there was likely zero heap fragmentation and all of these objects were allocated more or less contiguously. We confirm this by printing the addresses for the first few objects.

0x5555555d6890
0x5555555d68b0
0x5555555d68d0
0x5555555d68f0
0x5555555d6910
0x5555555d6930
0x5555555d6950
0x5555555d6970
0x5555555d6990

We can see these are all allocated contiguously in memory, which is not representative of real-world programs. Our current layout is something like this

when in reality we want our heap to be shuffled and have our shapes pointing to disparate locations in memory, like this

To accomplish this, we’ll shuffle our vector to randomize where each individual pointer is pointing to. When we do this, our performance drops considerably as we’re no longer able to prefetch in a predictable manner. Our throughput drops to about 75 million items per second when processing Shape*, and 165 million items per second with Square* and final.

This is an unfortunate byproduct of implementing polymorphism with virtual functions. It essentially guarantees poor spatial locality by forcing objects to be dynamically allocated.

Mixing Up our Shapes

For all our benchmarks, we’ve dealt with only creating Squares and not actually using our polymorphic Shape to the extent of its abilities. To make this more realistic, we can now run our benchmark with a vector<Shape*> but have an even split of Square, Triangle and Circle. When we run this same benchmark, our performance degrades further, hitting just about 50 million items per second

It seems like the culprit here is branch prediction again. Running the benchmark with perf stat, we see that we’re hitting about 8% of all branches are mispredicted, compared with 0.75% when our vector is populated with all squares. While there isn’t a conditional branch here in the traditional sense, it may be that the call to area is being speculatively executed before the address is loaded from the vtable and this is being reported as a branch miss. For more about branch predictions and performance, check out this earlier post.

In any case, with the combination of the vtable indirection, the poor spatial locality and the randomized shape types, we’re operating at less than 1/10th of the performance of the vector<Square*> with final. We’ve reached the nadir of our performance and will now start heading the opposite direction and working to improve the throughput with various techniques.

Restoring Locality with std::variant

C++17 introduced a new way of handling runtime polymorphism without resorting to virtual function. Through the concept of std::variant, developers can generate a type-safe union of N types. In our case here, it allows us to create Square, Circle and Triangle as plain classes, then define a std::variant<Square, Circle, Triangle> to hold any of those classes.

class Square
{
 private:
  double _side;

 public:
  Square(const double side) : _side{side} {}
  double area() const { return _side * _side; }
};

class Circle
{
 private:
  double _radius;

 public:
  Circle(const double radius) : _radius{radius} {}
  double area() const { return _radius * _radius * M_PI; }
};

class Triangle
{
 private:
  double _base;
  double _height;

 public:
  Triangle(const double base, const double height)
      : _base{base}, _height{height}
  {
  }
  double area() const { return _base * _height * 0.5; }
};

using Shape = std::variant<Square, Circle, Triangle>;

// Variant is the size of the largest member type, plus 8 bytes of bookkeeping for the tag
static_assert(sizeof(Shape) ==
              std::max(sizeof(Square),
                       std::max(sizeof(Circle), sizeof(Triangle))) +
                  sizeof(std::size_t));

We see that our variant is the size of the largest of its possible constituent types, plus an 8 byte tag. This means we can store our variant in a container like a vector without resorting to indirection, and all our memory can be accessed in a flat, contiguous way.

Additionally, with the use of the std::visit function, a function or functor can be easily applied to all the possible types of a variant, with the visit function determining the correct function to call at runtime. As such, an area function on our Shape variant would look something like this

static double area(const variant::Shape& shape)
{
  // Correctly dispatches at runtime based on the type held in shape
  return std::visit([](const auto& s) { return s.area(); }, shape);
}

When we run our benchmark with a shuffled vector of Shape variants, we get back to a decent throughput of about 160 million objects per second.

While this is well below our original setup, those included somewhat unrealistic assumptions on memory layout and the types of shapes in our container. When compared to the vector<Shape*> with all types, we see we’re more than 3 times faster.

Branching Again

Running three times as fast is good, but ideally we’d be able to improve performance further here. When we run this latest benchmark with perf stat, we see we’re hitting about 21% of branches mispredicted.

 Performance counter stats for './build/polymorphism/polymorphic_shapes':

       430,039,717      branches                                                              
        90,952,554      branch-misses                    #   21.15% of all branches           

       0.910310649 seconds time elapsed

       0.875390000 seconds user
       0.034015000 seconds sys

This is a similar issue that we explored earlier with the branch misprediction penalty, but here there isn’t a clean solution to make this branchless. What we can do instead is help the branch predictor out by making our data more regular. We’ll sort our data based on the type, after doing the shuffle. This will ensure that all the Squares are contiguous, as well as the Circles and the Triangles.

When we add this sorting step in for the virtual function implementation, we get a modest improvement, hitting about 86 million items per second. This makes sense, as we’re roughly in line with our vector<Shape*> all squares implementation. The performance is still dominated however by the lack of spatial locality. When we run the same test with the vector<Shape Variant> though, we see a drastic improvement. Our branch miss rate goes all the way down to 0.5%, and our throughput hits over 600 million items per second.

From Polymorphism to Data Oriented Design

While we’ve gotten our performance up to over half a billion elements per second, we’re still not at the ideal for performance. While we’ve eliminated branch mispredictions and have ensured our data are stored contiguously in memory, we’re wasting bandwidth moving useless data into our cache hierarchy. If you haven’t seen Mike Acton’s excellent talk on Data Oriented Design I’d recommend adding it to the front of your queue. We’re going to apply some lessons from this design philosophy to our problem at hand.

First, we need to consider that data don’t move between memory hierarchies in single bytes, but flow in a larger granularity of a cache line, typically 64 bytes on modern hardware. This means that when we first load an address from memory, in addition to pulling in that value, we load the 64 bytes around the memory address as well. This can be hugely beneficial for spatial locality. If you’re loading a vector of longs, when the first element is loaded into cache, then next 7 longs will also be fetched in the same instruction, making it many times faster to load the following elements.

Loading Cache Line

However, if the following elements in the cache line are not of interest immediately, or aren’t useful data at all, both the cache space to store these and the bandwidth to fetch them are being wasted. One canonical example of this would be a boolean. While it only requires a single bit to represent its value, bools are 1 byte long.

Boolean Layout in Memory

Within a single bool, 87% of the bits are wasted. Even worse, fetching that single bool may have required loading a new cacheline that is not temporally useful. If that were the case, we’d load 512 bits into our cache, only to read a single bit, meaning 99.8% of the data taking up cache and memory bandwidth was wasted.

Let’s examine our variant using this lens. As mentioned above, the variant stores one 8 byte tag to specify which type it currently holds, plus memory enough to hold the largest of the possible variant types. In our case, that’s a triangle which holds both base and height. As such our memory layout would be as follows

It immediately sticks out that both Square and Circle are wasting 8 bytes since they only have a single data member, but the variant must be able to hold up to a triangle-sized object. This would be even worse if our variant was extended to hold a larger, but infrequently used object. Since the variant must have space to hold up to the largest possible object that it can contain, the more variation in the size of the variants, the worse the useful utilization of memory will be.

Additionally, we’re over-allocating space for the tag. While our tag uses 8 bytes to store the representation, in this case we only have 3 possible types held within the variant, which can be represented with just 2 bits. As such, the amount of useful data in a variant holding a square is 2 bits (tag) + 64 bits (side) = 66 bits. The size of our variant is 24 bytes = 192 bits though, so for every Square or Circle we load into memory, we’re effectively wasting 65% of our bandwidth.

Looking at this in terms of cache lines, we can fit about 2.67 shapes in a single cache line, meaning for our 1 million object benchmark, we’ll need to load about 375k cache lines.

The solution here is to take the sorting-by-type one step further. Rather than having a single container where all elements may be one of three types, we should have 3 containers, each just containing a single type of element. In our case here, we’d restructure to have something like the following.

struct ShapeSOA
{
  std::vector<Square> squares;
  std::vector<Circle> circles;
  std::vector<Triangle> triangles;
};

template <typename T>
static double area(const std::vector<T>& shapes)
{
  double total_area = 0;
  for (const auto& s : shapes)
  {
    total_area += s.area();
  }
  return total_area;
}

static double area(const ShapeSOA& shapes)
{
  double total_area = 0;
  total_area += area(shapes.squares);
  total_area += area(shapes.triangles);
  total_area += area(shapes.circles);
  return total_area;
}

Now we’ve gone beyond sorting and have fully separated each type out into its own container. Our memory layout benefits from this change as well. We no longer have a variant, so we no longer need the 8 bytes of a tag. The type is instead defined by our code and compile-time dispatch to the correct area function, rather than a runtime tag. Additionally, our vectors can be stored compactly since they’re each containing just a single type with no padding.

Data Oriented Design Layout

Since these can now be fully compact in memory, we have 0 wasted cachelines as every bit loaded in is meaningful for our computation. We can now fit 8 Squares or Circles, or 4 Triangles on a single cacheline, a marked improvement over the 2.67 with the variant approach. Now if we have 1/3 Squares, Triangles and Circles, we can load our million elements in 166k cachelines. This is also reflected in our updated performance when we run the benchmark with the struct of array implementation.

Takeaways and Tradeoffs

By shifting from traditional virtual polymorphism to runtime variants to a purely data-oriented-design with compile time polymorphism, we were able to push the performance of our shape area implementation up to nearly 1 million items per second. Like any change though, there are tradeoffs. The virtual function implementation still retains the most flexibility and least coupling, allowing new implementations without affecting the ABI or requiring a recompile. The variant removes some of this flexibility, since adding a new variant type breaks the ABI and the variant itself acts as a tight coupling of types. Finally with the data-oriented-design, we’re barely in the realm of polymorphism at all. All the types need to be known up-front, and need to be handled individually via compile-time dispatch. Any new type will require an intrusive change into both the ShapeSOA as well as the area calculation function. However with that in mind, there can be an overemphasis on designing for all platforms and for all possibilities. In our use case, perhaps we know there’s only likely to be a dozen or so shapes, so the unlimited flexibility of the virtual function polymorphism may be wasted in this case. Indeed in many places performance can be improved if knowledge of the domain is applied to understand how flexible or constrained a set of data or behaviors need to be.

We’ve discussed C++ polymorphism through various mechanisms, showing how the performance of a program can be significantly altered based on the choice of implementation. As always, the code for this can be found on my GitHub. Feel free to comment questions or feedback below, and if you found this useful please consider subscribing for more articles! Thank you for reading!

1. This is necessary since if we have the destructor as a regular method and attempt to delete a child class instance through a pointer to the base class, we’ll get undefined behavior and a likely resource leak. This StackOverflow post does a good job explaining the