title: Performance hit of vtable lookup in C++
body: <p>I'm evaluating to rewrite a piece of real-time software from C/assembly language to C++/assembly language (for reasons not relevant to the question parts of the code are absolutely necessary to do in assembly).</p>
  
  <p>An interrupt comes with a 3&nbsp;kHz frequency, and for each interrupt around 200 different things are to be done in a sequence. The processor runs with 300&nbsp;MHz, giving us 100,000 cycles to do the job. This has been solved in C with an array of function pointers:</p>
  
  <pre><code>// Each function does a different thing, all take one parameter being a pointer
  // to a struct, each struct also being different.
  void (*todolist[200])(void *parameters);
  
  // Array of pointers to structs containing each function's parameters.
  void *paramlist[200];
  
  void realtime(void)
  {
    int i;
    for (i = 0; i &lt; 200; i++)
      (*todolist[i])(paramlist[i]);
  }
  </code></pre>
  
  <p>Speed is important. The above 200 iterations are done 3,000 times per second, so practically we do 600,000 iterations per second. The above for loop compiles to five cycles per iteration, yielding a total cost of 3,000,000 cycles per second, i.e. 1% CPU load. Assembler optimization <em>might</em> bring that down to four instructions, however I fear we might get some extra delay due to memory accesses close to each other, etc. In short, I believe those five cycles are pretty optimal.</p>
  
  <p>Now to the C++ rewrite. Those 200 things we do are sort of related to each other. There is a subset of parameters that they all need and use, and have in their respective structs. In a C++ implementation they could thus neatly be regarded as inheriting from a common base class:</p>
  
  <pre><code>class Base
  {
    virtual void Execute();
    int something_all_things_need;
  }
  class Derived1 : Base
  {
    void Execute() { /* Do something */ }
    int own_parameter;
    // Other own parameters
  }
  class Derived2 : Base { /* Etc. */ }
  
  Base *todolist[200];
  
  void realtime(void)
  {
    for (int i = 0; i &lt; 200; i++)
      todolist[i]-&gt;Execute(); // vtable look-up! 20+ cycles.
  }
  </code></pre>
  
  <p>My problem is the vtable lookup. I cannot do 600,000 lookups per second; this would account for more than 4% of wasted CPU load. Moreover the todolist never changes during run-time, it is only set up once at start-up, so the effort of looking up what function to call is truly wasted. Upon asking myself the question "what is the most optimal end result possible", I look at the assembler code given by the C solution, and refind an array of function pointers...</p>
  
  <p>What is the clean and proper way to do this in C++? Making a nice base class, derived classes and so on feels pretty pointless when in the end one again picks out function pointers for performance reasons.</p>
  
  <p>Update (including correction of where the loop starts):</p>
  
  <p>The processor is an ADSP-214xx, and the compiler is VisualDSP++ 5.0. When enabling <code>#pragma optimize_for_speed</code>, the C loop is 9 cycles. Assembly-optimizing it in my mind yields 4 cycles, however I didn't test it so it's not guaranteed. The C++ loop is 14 cycles. I'm aware of the compiler could do a better job, however I did not want to dismiss this as a compiler issue - getting by without polymorphism is still preferable in an embedded context, and the design choice still interests me. For reference, here the resulting assembly:</p>
  
  <p>C:</p>
  
  <pre><code>i3=0xb27ba;
  i5=0xb28e6;
  r15=0xc8;
  </code></pre>
  
  <p>Here's the actual loop:</p>
  
  <pre><code>r4=dm(i5,m6);
  i12=dm(i3,m6);
  r2=i6;
  i6=i7;
  jump (m13,i12) (db);
  dm(i7,m7)=r2;
  dm(i7,m7)=0x1279de;
  r15=r15-1;
  if ne jump (pc, 0xfffffff2);
  </code></pre>
  
  <p>C++ :</p>
  
  <pre><code>i5=0xb279a;
  r15=0xc8;
  </code></pre>
  
  <p>Here's the actual loop:</p>
  
  <pre><code>i5=modify(i5,m6);
  i4=dm(m7,i5);
  r2=i4;
  i4=dm(m6,i4);
  r1=dm(0x3,i4);
  r4=r2+r1;
  i12=dm(0x5,i4);
  r2=i6;
  i6=i7;
  jump (m13,i12) (db);
  dm(i7,m7)=r2;
  dm(i7,m7)=0x1279e2;
  r15=r15-1;
  if ne jump (pc, 0xffffffe7);
  </code></pre>
  
  <p>In the meanwhile, I think I have found sort of an answer. The lowest amount of cycles is achieved by doing the very least possible. I have to fetch a data pointer, fetch a function pointer, and call the function with the data pointer as parameter. When fetching a pointer the index register is automatically modified by a constant, and one can just as well let this constant equal 1. So once again one finds oneself with an array of function pointers, and an array of data pointers.</p>
  
  <p>Naturally, the limit is what can be done in assembly, and that has now been explored. Having this in mind, I now understand that even though it comes natural to one to introduce a base class, it was not really what fit the bill. So I guess the answer is that if one wants an array of function pointers, one should make oneself an array of function pointers...</p>