Non polymorphic containers during runtime

Question

I'm trying to store objects in one of several container types, the type of the container is known during run-time. The interface of the containers is the same, but the containers are not polymorphic.

What I am trying to do is avoid the extra jump a vtable forces during runtime - by having a variable that should be of the concrete container type.

Consider that I have the containers:

class Vector1<T>
{
     T get();
}
class Vector2<T>
{
     T get();
}

And I want to have a container that is either Vector1 or Vector2 depending on some run-time parameter.

So my class should be:

Class VectorWrapper
{
      Vector1<SomeType> v1; 
      Vector2<Sometype> v2;

      inline Sometype get()
      {
          **how do I choose between v1 and v2, without the extra jump?**
      }
}

Answer 1

Your question is vague. So all I can provide are vague solutions.

The first technique worth considering is a manual vtable. This removes a memory indirection compared to an automatic vtable. Basically you store a function pointer to the right implementation of the method, and you follow that function pointer directly.

A second approach is hoisting the branch out of a loop. Your code, to matter, must be run repeatedly. If the decision asto which branch to take is made before the repeats, you can move the branch out there.

Imagine you had

void foo() {
  bool which_branch = decide();
  VectorWrapper wrap( decide );
  wrap.populate();
  for (auto x : some_loop_domain) {
    x.set( wrap.get() );
  }
}

notice that the decision is made outside of the loop, but the price may be paid within the loop.

If we can move the branch outside the loop, the cost is paid once instead of once per element in some_loop_domain.

One way to make this work is to provide the compiler with an easier to optimize constant. So we avoid storing the state for which vector is in use within the wrapper, and instead pass it in. The value we pass down is arranged to be "obviously constant" in the context where it is used, or even a compile time constant.

To use a compile time constant, the code using it must be templetized. However, this templetization need only be at the "above the loop" point, as a branch there is usually cheap enough to not care.

To rely on the optimizer being reasonable, you similarly populate an obvious constant there and pass it down as a value. This can be less reliable in my experience.

void foo() {
  bool which_branch = decide();

  auto body = [&](auto which_branch) {
    VectorWrapper wrap( which_branch );
    wrap.populate();
    for (auto x : some_loop_domain) {
      x.set( wrap.get() );
    }
  };
  if (which_branch) {
    body( std::true_type{} );
  } else {
    body( std::false_type{} );
  }
}

now within body, which_branch is a compile-time constant. All by itself this may result in the branch being hoisted, but it may require:

  auto body = [&](auto which_branch) {
    static_assert( decltype(which_branch){} || !decltype(which_branch){} );
    VectorWrapper<decltype(which_branch)> wrap;
    wrap.populate();
    for (auto x : some_loop_domain) {
      x.set( wrap.get() );
    }
  };

where we make VectorWrapper a template on a class that when instantiated and read in a bool context returns true or false as a constexpr.

The code within VectorWrapper remains similar, except it reads the compile time constant instead of a method to decide which branch to take.

This technique can be very intrusive or not at all. It can take seemingly branch-filled code and hoist the branches out.

You can do a cartesian product of many low-level branches in a similar way, where you can generate 2^10 different low-level routines, pick between them before entering the loop, then running one of the 1024 loops.

Answer 2

To avoid having to decide at runtime, you have to make the decision at compile time. That means using templates. And if you're so time-constrained that there really must be no non-essential jumps on the critical path, you have to keep pushing the tempaltedness higher and higher in your program until you reach a point where the extra jump can be made. Yes, this can theoretically mean having >= 90% of your code in templates, but if you really need to avoid the jumps, that's the price.

In other words, if VectorWrapper must not decide with an if, it must be a template as well. And so must be the code using it, etc., until you eventually reach a point where the if is not so expensive.

If you find that this templated part is too big, but can at least be isolated somehow, you could even do something like build several shared libraries (with different template arguments in each) and at runtime, load the one version containing the correct combination of template arguments.

Answer 3

Make the part of your program where those containers are used parameterized on the container type:

template<class Container>
void criticalPath()
{
    // Create and use Container objects a lot
}


void enterCriticalPath(bool useVector1) {
    if (useVector1) {
        criticalPath<Vector1<SomeType>>();
    } else {
        criticalPath<Vector2<SomeType>>();
    }
}