Not a virtual interface? (Requires very effective low-level abstraction)

Question

I am trying to micro-optimize my code at a very low level in the application architecture. So here is my specific scenario:

• I have a parser class that parses a graph file (nodes, edges, adjacency records, etc.).
• The file format has a version, so for each version there are parsers that are implemented as separate classes (ParserV1, ParserV2, ...).
• Parsers provide the same functionality for some top level in the application. Thus, they implement the same “ interface ”.
• In C ++, I would implement such an interface as an abstract class, while all functions would be pure virtual .
• Since virtual functions need a different memory lookup and cannot be statically linked at compile time and - more importantly - will not allow embedding of small methods in parser classes using the classic sub-class idiom will not lead to the maximum performance that I can achieve.

[Before describing my possible solutions, I want to explain why I am doing micro-optimization here (you can skip this section): the parser class has many small methods, where “small” means, I do a lot. Most of them read only one or two bytes or even one bit from the cached stream of bits. Thus, it should be possible to implement them in a very efficient way when a function call, when it is built-in, requires only a few machine instructions. These methods are often called in the application, as they look for node attributes on a very large graph (worldwide network of roads) that can happen about a million times for each user request, and such a request should be the same as soon as possible.]

What is the way here? I can see the following solutions to the problem:

• Write an interface using virtual methods and a subclass. Performance will suffer.
• Do not write such an interface. Each parser defines the same methods independently. At the top level (which the parser uses) there are pointers (as members) for each version subclass. First, create an instance of the specific parser to be used. Use the switch block and throw the parser instance into an explicit subclass when calling the function. Will performance be better? (if / switch block vs. virtual table lookup).
• Mix the two solutions 1. + 2: Write an interface using virtual methods for rarely used methods where performance is not very important. If this is important, do not provide a virtual method, but use the second method.
• Improvement 2: Providing non-virtual methods in an abstract class; save the version number as a member variable in an abstract class (a type of proprietary information such as runtime) and implement if and switch blocks in these methods; then call the methods in the subclass. This provides both inline and static binding.

Are there any better ways to solve this problem? Is there an idiom for this?

To clarify, I have many functions that are version independent (at least so far) and thus are great for some superclasses. For most functions, I will use the standard design of the subclass, while this question only discusses the solution for version-optimized functions that will be optimized. (Some of them are not called very often, and I can, of course, use virtual methods in these cases.) In addition, I do not like the idea of ​​making the parser class decide which methods should be performative and which should not, (Although it could be to do.)

Answer 1

Firstly, from couse you should profile your code to find out how much this is related to vcalls performance in your specific case (in addition to potentially weaker optimizations).

Putting aside the optimization topic, I’m pretty sure that you won’t get any significant performance boost by replacing the call to a virtual function (or calling a function with a pointer variable that is almost the same) with a switch that calls compilation - time-aware functions in different cases.

If you really want a significant improvement, these are the most promising IMHO options:

• Try changing the interface to include more advanced features. For example, if you have a function that reads one vertex, change it to immediately read (up to) N vertices. And so on.

• You can make all of your parsing code (which your parser uses) a template class / function that will use the template parameter to create the required parser. Here you need neither an interface nor virtual functions. At the very beginning (where you define the version) - put a switch , for each recognized version, call this function with the corresponding template parameter.

The latter is likely to exceed performance point of view, OTOH increases code size

EDIT:

Here's an example (2):

 template <class Parser> void MyApplication::HandleSomeRequest(Parser& p) { int n = p.GetVertexCount(); for (iVertex = 0; iVertex < n; iVertex++) { // ... p.GetVertexEdges(iVertex, /* ... */); // ... } } void MyApplication::HandleSomeRequest(/* .. */) { int iVersion = /* ... */; switch (iVersion) { case 1: { ParserV1 p(/* ... */); HandleSomeRequest(p); } break; case 2: { ParserV2 p(/* ... */); HandleSomeRequest(p); } break; // ... } } 

Classes ParserV1 , ParserV2 , etc. have no virtual functions. They also do not inherit any interface. They simply implement some features, such as GetVertexCount .

Answer 2

One option that may work well is the following: each parser class defines methods with the same signatures, but does it completely independently of each other's class. Then enter the hierarchy of the secondary class, which actually implements all these functions, then redirects the call of each method to a specific parser object. Thus, the implementation of the analyzer receives all the advantages of inlining, since from the point of view of the class all calls can be solved statically, while the client receives the benefits of polymorphism, since any method call will dynamically decide the correct type.

The trick here is that you use additional memory (the wrapper object takes up a space), and you will also probably have at least one additional indirect action when you call the parser functions, since the call goes

client -> wrapper -> implementation

Depending on how rarely you call methods from the client, this implementation may work very well.

Using templates, you can implement a shell layer extremely concisely. The idea is this. Suppose you have methods fA, fB and fC. Start by defining a base class as follows:

 class WrapperBase { public: virtual ~WrapperBase() = 0; virtual void fA() = 0; virtual void fB() = 0; virtual void fC() = 0; }; 

Now define the following template type as a subclass:

 template <typename Implementation> class WrapperDerived: public WrapperBase { private: Implementation impl; public: virtual void fA() { impl.fA(); } virtual void fB() { impl.fB(); } virtual void fC() { impl.fC(); } }; 

Now you can do something like this:

 WrapperBase* wrapper = new WrapperDerived<MyFirstImplementation>(); wrapper->fA(); delete wrapper; wrapper = new WrapperDerived<MySecondImplementation>(); wrapper->fB(); delete wrapper; 

In other words, all the shell code can be generated for you by the compiler, simply by creating an instance of the WrapperDerived template.

Hope this helps!