Fast polymorphic collections with devirtualization

The poly_collection template class we implemented for fast handling of polymorphic objects can be potentially speeded up in the case where some of the derived classes it manages are known to the compiler at the point of template instantiation. Let us use this auxiliary template class:

template<class Derived>
class poly_collection_static_segment
{
public:
  void insert(const Derived& x)
  {
    store.push_back(x);
  }
  
  template<typename F>
  void for_each(F& f)
  {
    std::for_each(store.begin(),store.end(),f);
  }
  
  template<typename F>
  void for_each(F& f)const
  {
    std::for_each(store.begin(),store.end(),f);
  }

private:
  std::vector<Derived> store;
};

We can add the ability for poly_collection to accept a variable number of derived class types:

template<class Base,class ...Derivedn>
class poly_collection
{
  ...
};

so that it includes poly_collection_static_segment<Derivedi> components taking care of objects whose types concide exactly with those specified, whereas for the rest the default dynamic handler is still used.

What does this gain us? Consider the example:

class base
{
  virtual void do_stuff()=0;
};

class derived1:public base{...};
...
poly_collection<base,derived1> c;
c.insert(derived1(0));
...
c.for_each([](base& x){
  x.do_stuff();
});

For the segment handling derived1, the code in for_each resolves to:

std::for_each(store.begin(),store.end(),[](base& x){
  x.do_stuff();
});

where store is of type std::vector<derived1>: so, the compiler can know that x.do_stuff() is invoked on objects with exact type derived1 and hence omit vtable lookup and even, if the definition of derived1::do_stuff is available at instantiation time, inline the call itself.

Now, the fact that the compiler can apply these optimizations does not mean it necessarily will do so: the static analysis needed to determine the optimization opportunity is certainly not trivial. There are a number of techniques we can implement to help the compiler in the process:

1. Make derived1::do_stuff final.
2. Use a polymorphic lambda [](auto& x){x.do_stuff();} to omit the cast from derived1& to base&.
3. Do both 1 and 2.

I have written a test program (Boost required) that implements this new version of poly_collection and measures its for_each performance for the following scenarios:

1. ⬛ poly_collection<base> (baseline)
2. ⬛ poly_collection<base,derived1>
3. ⬛ poly_collection<base,derived1,derived2>
4. ⬛ poly_collection<base,derived1,derived2,derived3>
5. ⬛ poly_collection<base,final_derived1>
6. ⬛ poly_collection<base,final_derived1,final_derived2>
7. ⬛ poly_collection<
     base,final_derived1,final_derived2,final_derived3>
8. ⬛ same as 1, with a polymorphic functor
9. ⬛ same as 2, with a polymorphic functor
10. ⬛ same as 3, with a polymorphic functor
11. ⬛ same as 4, with a polymorphic functor
12. ⬛ same as 5, with a polymorphic functor
13. ⬛ same as 6, with a polymorphic functor
14. ⬛ same as 7, with a polymorphic functor

with containers of several sizes ranging from n = 1,000 to 10⁷ elements (except where noted, results do not vary significantly across sizes). Values are the averages of execution times / number of elements for each scenario, normalized to the baseline = 1.

MSVC 2012

Microsoft Visual Studio 2012 using default release mode settings on a Windows box with an Intel Core i5-2520M CPU @2.50GHz.

Normalized execution times / number of elements.

Differences in performance are not significative and can be labeled as mostly noise: in fact, a visual inspection of the generated assembly code reveals that virtual calls are not optimized ever.

MSVC 2013

Results by Lars Schouw: MSVC 2013 with default release settings on an box with an Intel Core i7-920 @2.67GHz.

Normalized execution times / number of elements.

Unlike with MSVC 2012, here there is a modest but consistent improvement in performance as more derived classes are statically specified. This is probably due to tighter traversal loops rather than devirtualization, except when a polymorphic lambda is combined with final virtual functions, where reductions of up to 25% seem to indicate that inlining is taking place.

Clang on Arch Linux

Results by Theodoros Theodoridis: Clang 3.4 with settings -std=c++11 -O3, Arch Linux x64 with an Intel Core i7-950 @3.07GHz.

Normalized execution times / number of elements.

In most cases, specifying derived classes has no or a detrimental effect on performance (the reason for the degradation is not clear to me). For polymorphic lambda + final virtual functions, however, reductions in execution times are impressively large.

There is an odd effect that the aggregate figures of the graph do not show: in the last two scenarios, performance results when n = 10⁷ are still much better than the baseline but comparatively worse than for other container sizes.

Clang on Ubuntu 64

Results by plash: Compiler Clang 3.5.0 with settings -std=c++11 -stdlib=libc++ -lc++ -O3, system Ubuntu 13.04 x86_64 with an AMD Phenom II.

Normalized execution times / number of elements.

Specification of derived classes definitely improves execution times, although the resulting performance patterns and underlying factors are not easily interpretable. For polymorphic lambda + final virtual functions we have again massive reductions in execution time. Similarly to the case with Clang 3.4, we have comparatively poorer performance for  n = 10, although here the effect is seen across all scenarios.

GCC on Arch Linux

Results by Theodoros Theodoridis: GCC 4.9.0 with settings -std=c++11 -O3, Arch Linux x64 with an Intel Core i7-950 @3.07GHz.

Normalized execution times / number of elements.

For this compiler, passing a monomorphic or a polymorpic lambda to for_each makes all the difference, with the latter case achieving reductions in execution time of up to 60%. I do not have an explanation as to why using final virtual functions improves on the non-final case: in both situations inlining seems to be in effect, which should render final qualification irrelevant. Like with Clang, some cases of relative degradation when  n = 10⁷ are also seen for this compiler, here mostly concentrated on the last two scenarios.

(Update Aug 17, 2014) GCC 5 on Linux

Jan Hubička is working on integrating devirtualization capabilities in GCC, and the results on this area are improving accordingly. He ran the test benchmark against GCC mainline (as of Aug 15, 2014) with settings -O3 on a Linux machine with an Intel i5-4300U processor.

Normalized execution times / number of elements.

GCC's speculative devirtualization analysis is able to take full advantage of the optimization opportunities offered by static knowledge of the types involved, even to the point of rendering final decoration superfluous.

Conclusions

Allowing for the specification of a list of statically known derived class types as part of a poly_collection instantiation opens up possibilities for internal performance optimizations that do not impact the usage interface of this template class. The actual improvements achieved depend very much on the compiler being used, but in general are greater when passing polymorphic functors (such as generic lambdas) to for_each and qualifying virtual functions as final where possible.

Postscript: The observant reader might have noticed that poly_collection_static_segment<Derivedi> does not explicitly require that Derivedi be an actual derived class from Base, and in fact one can pass any type as long as we use a polymorphic functor with for_each that accepts it:

poly_collection<std::string,int,char> c;
c.insert(std::string("hello"));
c.insert(0);
c.insert('a');
c.for_each([](auto& x){
  std::cout<<x<<"\n";
});

Output:
hello
0
a

This comes more as a (easily fixable) happy accident than from a conscious design decision, but hints at an area of exploration away from the original purpose of poly_collection, focused on handling heterogeneous classes via visitor patterns in a manner reminiscent of the techniques used in Boost.Variant.

Update Jan 17, 2015

Fixed a serious bug in the code, that, fortunately, doesn't affect the test results.