Is it better to use an array of pointers to members or a switch?

Question

In my school we're highly encouraged to use arrays of pointers to members instead of switch (or multiple else if) in C++ (and C).

As I don't see any point of using such arrays (I actually use maps of pointers to members) instead of a switch statement, I'd like to know if there's really any kind of optimization that would recommend pointers to functions.

Here's what's making me think that It'd be better to use switch :

• Arrays (especially maps) of pointers to members are memory heavy (an std::string as key and a pointer as value) and need to be stored either in the class (doesn't make any sense since it's not an object property...) or re-created everytime in the function using them if declared statically :

  std::map<std::string, void (MyClass::*)(...)>   operations;
  

• They're a pain to instantiate and get ready to use :

  operations.insert(std::map<std::string, void (Parser::*)(std::vector<std::string> const &)>::value_type("push", &Parser::push));
  operations.insert(std::map<std::string, void (Parser::*)(std::vector<std::string> const &)>::value_type("pop", &Parser::pop));
  operations.insert(std::map<std::string, void (Parser::*)(std::vector<std::string> const &)>::value_type("dump", &Parser::dump));
  operations.insert(std::map<std::string, void (Parser::*)(std::vector<std::string> const &)>::value_type("assert", &Parser::assert));
  operations.insert(std::map<std::string, void (Parser::*)(std::vector<std::string> const &)>::value_type("add", &Parser::add));
  operations.insert(std::map<std::string, void (Parser::*)(std::vector<std::string> const &)>::value_type("sub", &Parser::sub));
  operations.insert(std::map<std::string, void (Parser::*)(std::vector<std::string> const &)>::value_type("mul", &Parser::mul));
  operations.insert(std::map<std::string, void (Parser::*)(std::vector<std::string> const &)>::value_type("div", &Parser::div));
  operations.insert(std::map<std::string, void (Parser::*)(std::vector<std::string> const &)>::value_type("mod", &Parser::pop));
  operations.insert(std::map<std::string, void (Parser::*)(std::vector<std::string> const &)>::value_type("print", &Parser::print));
  operations.insert(std::map<std::string, void (Parser::*)(std::vector<std::string> const &)>::value_type("exit", &Parser::exit));
  

• It forces you to have useless parameters in some functions and to have non-const members that could've been const. For exemple, in my previous piece of code, "print" and "assert" could have been const if they were not used in the map, and most of the functions aren't using the parameter, but "push" and "assert" are...

• You have to verify that the pointer you want to use exists in the map, instead of just letting the "default" case handle it, and the call is hard to read :

  if (operations.find(myOperation) != operations.end())
      (this->*(operations.find(myOperation)->second))(myParameter);
  

So why are we forced to use pointers to members instead of just a clear switch statement, or even else-ifs ?

Thanks.

Answer 1

It depends. Switch-case with multiple, not connected choices is effectively the same as big if-else - slow. Good optimization is to perform desired operation using offset table (or jump table), that you were advised to implement.

Curious thing is, that compilers can usually perform this kind of optimization automatically - if switch-case is well written.

But what well written means?

It means, that you must design entries indexing, so it will be easy and fast to compute location of the one, that needs to be executed. Consider following code:

int n = 0;
std::cin >> n;

if(n == 1) printf("1\n");
else if(n == 2) printf("2\n");
else if(n == 3) printf("3\n");
else if(n == 4) printf("4\n");

This is possible output (an actual one, on VC11, compiled with /O2):

011AA799  mov         eax,dword ptr [n]  
011AA79C  cmp         eax,1 //is n equal to 1?
011AA79F  jne         main+34h (011AA7B4h) //if yes, continue, if not, jump... [J1]
011AA7A1  push        1262658h  
011AA7A6  call        printf (011E1540h) // print 1
011AA7AB  add         esp,4  
011AA7AE  xor         eax,eax  
011AA7B0  mov         esp,ebp  
011AA7B2  pop         ebp  
011AA7B3  ret  
011AA7B4  cmp         eax,2 // [J1] ...here. Is n equal to 2?
011AA7B7  jne         main+4Ch (011AA7CCh) //If yes, continue, if not, jump... [J2]
011AA7B9  push        126265Ch  
011AA7BE  call        printf (011E1540h) // print 2
011AA7C3  add         esp,4  
011AA7C6  xor         eax,eax  
011AA7C8  mov         esp,ebp  
011AA7CA  pop         ebp  
011AA7CB  ret  
011AA7CC  cmp         eax,3 // [J2] ...here. Is n equal to 3? (and so on...)
011AA7CF  jne         main+64h (011AA7E4h)  
011AA7D1  push        1262660h  
011AA7D6  call        printf (011E1540h)
[...]

Basically - an if-else. Now, let's change our code:

int n = 0;
std::cin >> n;

switch(n)
{
case  1: printf("1\n"); break;
case  2: printf("2\n"); break;
case  3: printf("3\n"); break;
case  4: printf("4\n"); break;
}

Possible output:

011BA799  mov         eax,dword ptr [n]  // switch case will run if n is 1-4
011BA79C  dec         eax //decrement by one, now it should be in 0-3
011BA79D  cmp         eax,3 // compare with 3
011BA7A0  ja          $LN4+46h (011BA7EFh) //if greater than 3, skip switch
011BA7A2  jmp         dword ptr [eax*4+11BA7F8h] //otherwise compute offset of instrcution and jump there

I didn't post calls to printf - essentially the same, but without any cmp or jump instructions.

This output is of course only one of many possible, but the point is: well designed applications with smart optimizations on conditional sections, can perform much more efficient. Here, compiler is able to make direct jump to proper instruction, because it is possible to easily compute its offset - all cases are labelled with numbers, that grows by one.

And to answer to your question more directly: suggestion you were given is technically correct, but instead of complicated code (that may or may not give significant speed improvement), I would focus on compiler-friendly optimizations, than everyone can understand and rely on (as far as compiler is smart enough to take this advantage and generate optimized code).

Answer 2

Your analysis about pros and cons of array of pointers to member functions compared to switch instructions is already very good.

But it all depends on the context:

• Of course technically speaking, you are fully right : such arrays are very cumbersome if you just want to replace a switch. Not speaking of the compiler who can optimize switches by using jump tables which use one less indirection than your array.

• But your example code implements a kind of command design pattern. From the design point of view this can have substantial adantages in terms of evolutivity and maintenability that outweights the technical drawbacks. It can for example easily be used in an application to implement undo/redo functions. It also eases the cases where several simulteneous user interfaces allow to trigger these commands on an object (example: a command line window, and a GUI)

Answer 3

The context is important.

If you work with a PC, i think is prefered the array because getting the result is very fast compared to very comparations, buy you paid with memory this. This is expensive in memory, but fast with arrays very large.

If the context is a microcontroller, the memory is very expensive and you can't waste to save all the array. especially if the array is almost not used. But the switch can be prefered because there is not use of memory, and the assembler is very fast in microcontrollers.

• If you have so much memory, and a high level programming language, maybe better is array.
• If you have so few memory, and low level programming language as assembler, or C in micros, better is switch (or rom tables)