07-26-10 - Virtual Functions

Previous post on x86/PPC made me think about virtual functions.

First of all, let's be clear than any serious game code base must have *some* type of dynamic dispatch (that is, data-dependent function calls). When people say "avoid virtual functions" it just makes me roll my eyes. Okay, assume I'm not just over-abstracting and I'm doing the dynamic dispatch for a good reason, because I actually need to do different things on different objects. The issue is just how you implement it.

How C++ virtual functions are implemented on most compilers :

There's a "vtable" of function pointers associated with each class type. Individual objects have a pointer to their vtable. The advantage of this is that vtables are shared, but the disadvantage is that you get an extra cache miss. What actually happens when you make a virtual call? (multiple and virtual inheritance ignored here for now).

vtable pointer = obj->vtable;

func_pointer = vtable->func

jump func_pointer

Why does this hurt ?

vtable pointer = obj->vtable;

The load of vtable pointer may be a cache miss, but that doesn't count against us since you are working on obj anyway you have to have one cache miss there.

func_pointer = vtable->func

Then you fetch the func pointer, which is maybe a cache miss (if this type of object has not been used recently).

jump func_pointer

Then you jump to variable, which may or may not be able to use branch prediction or fuck up your CPU's pipelining.

How can virtual calls be removed ?

• A good practice is to never expose virtuals directly. In the base class you should have something like :

  
  void DoStuff(int x);
  
  

  as the public interface, and then hidden lower down, something like :

  
  virtual void v_DoStuff(int x) = 0;
  void DoStuff(int x) { v_DoStuff(x); }
  
  

  this gives you a single controlled call-through point which you can then make non-virtual or whatever at some point. (though, this screws up the next issue:)

• The compiler can do it better than you (in theory anyway). Virtual functions that aren't actually overriden anywhere can obviously replaced with direct calls. But it's better than that - if you hold a pointer to some type, as long as nothing *derived* from that type override the virtual, it can be called direct. Even if sibling or cousin or parent classes override that virtual, by holding it by a derived type you can know that you are in a leaf part of the virtual call.

  No C++ compiler that I know of actually does this, because it requires knowledge of the class heirarchy in the whole program. But Java and C# are doing this now, so hopefully we will get it in C++ soon.

  When/if we get this, it is a very powerful optimization, because you can make then make functions that take concrete types and get joint-dispatch where you turn many virtual calls into just one. An example to be clear :

  
  class Base { virtual int Func() { return 0; } };
  
  class A : public Base { virtual int Func() { return 1; } };
  
  class B : public A { int m_data; };
  
  class C : public Base { virtual int Func() { return 2; } };
  
  void Test(A * obj)
  {
    obj->Func();
  }
  
  

  in this case the virtual call to Func() can be replaced with the direct call A::Func() by the compiler because no child of A overrides Func.

• Don't use the method of virtual calls to hide implementation from interface. Some C++ coders will make a naked pure virtual interface class for their D3DHardware or ResourceManager or whatever, and then make a concrete class that impelements those virtuals. This is pretty nice for code cleanliness, but gives you virtual calls all over that are unnecessary. Note that if we had compiler-virtual-elimination this method would be fine since all those virtuals could be eliminated as there is only one implementation of that interface in the program.

• Large/rare classes could use in-object vtables. In some cases, the space savings of sharing the vtable for all instances of a given class is not a huge win, and in that case you'd rather have the vtable directly in line in the object, because it gives you one less cache miss. There's no way to make the compiler do this for you, but you can do it reasonably easily with function pointers.

• They can be converted into normal branches. In the DoStuff() example, instead of calling v_DoStuff, you could just branch on object type and call some concrete functions. Like :

  
  void DoStuff(int x)
  {
      if ( this is Actor ) Actor::DoStuff(x);
      else Base::DoStuff(x);
  }
  
  

  the advantage of this is that you avoid a cache miss for the vtable, and you use a normal branch which can be predicted even on shitty chips.

  This is only practical if you have only a few overrides for the function. The shitty thing about this (and many of these patterns) is that it pushes knowledge of the derived class up to the base. One nice variant of this is :

• Rare overrides can use a test. If DoStuff() usually calls the default implementation, but once in a rare while needs an override, you can do that more efficiently with a pattern like :

  
  void DoStuff(int x)
  {
      if ( base is okay ) Base::DoStuff(x);
      else v_DoStuff(x);
  }
  
  

  so we check a bool (could be in a bitfield) and if so we use direct call, else we call the virtual.

• Pushing data up to parent instead of calling down to child. A good method is simply to eliminate the virtual through code flow redesign.

  For example, a lot of bad game engines might have something like "virtual GetPosition()" on the base object. This at first seems like a good idea - not all objects have positions, and they might want to implement different ways of reporting it. In fact it is a bad idea, and you should just store m_position as public data, then have the different object types push their different position into m_position. (For example silly people implement attachments by making GetPosition() query the parent position then add some offset; instead you should do that computation only once in your object update and store it into the shared m_position).

  Most good games have a chunk of the most common data stored directly in the base object type so it can be accessed without virtuals.

• Specialize for common cases. I sort of noted about this before, but when you're calling a bunch of virtuals from something, you can change many virtuals into one by dispatching to a func that calls them concretely. eg. Say you have a function like :

  
  void func(obj * o)
  {
    o->v1();
    o->v2();
    o->v3();
  }
  
  

  that does a bunch of virtual calls. Instead make a concrete call version t_func which does no virtuals :

  
  template < typename T >
  void t_func(T * o)
  {
    o->T::v1();
    o->T::v2();
    o->T::v3();
  }
  
  void func(obj * o)
  {
      dispatch to actual type of obj :
         t_func < typeof(o) >( o );
  }
  
  

  the difficulty is the dispatching from func to t_func. C++ has no mechanism to do type-dependent dispatch other than the vtable mechanism, which is annoying when you want to write a helper function and not add it to your class definition. There are general solutions to this (see for example in cblib the PrefDispatcher which does this by creating a separate but parallel class heirarchy to do dispatch) but they are all a bit ugly. A better solution for most games is to either add func() to the vtable or to just to know what concrete types you have and do manual dispatch.
• Note that just flattening your hierarchy is not generally a great solution. For example, rather than have a bunch of different types of Crate (ExplodingCrate, FlammableCreate) you might decide to just make one single UberCrate that can be any type of crate. This eliminates virtual calls when you are working on UberCrate since it is just one concrete type, but it adds a lot of branches (if (crate.isExploding)) , and often makes the classes fatter in memory, etc. Making objects data-polymorphic instead of type-polymorphic may or may not be a win depending on the details.
• In general it's good practice to make queries as fast and non-virtual as possible, and push the virtuals to the updates.