Secrets to Optimization - Function Pointers

Let me present you with a bit of code which you might find quite commonly in a program:

void function_1(type a, type b)
{
  if (complex_formula())
  {
    method_a(a, b);
  }
  else
  {
    method_b(a, b);
  }
}
...
void function_2(type *a, type *b, size_t ab_len)
{
  while (ab_len--)
  {
    function_1(*a++, *b++);
  }
}

I see this quite often in all kinds of situations. Where some repetitive action keeps calling a function which uses a static calculation which in turn does one of two things. Since this action is making many calls to a function which is doing the exact same sub action on this set of data, it really is a waste to redetermine which sub action we're dealing with for every element of data.

Imagine if a program has an option to approximate fractions from floating point using algorithm A or algorithm B, if the program repeatedly has to check which algorithm it's supposed to be using on each floating point number in a set, it is wasting time that could be spent on actually working on these numbers.

The most obvious way to speed this process up is to setup a variable which contains the result of complex_formula(), so complex_formula() itself doesn't have to be recalculated again and again, and instead we just do something like "method = complex_formula()" once, and just check "method" each time. However if we have a case where we have multiple methods, we'd have to turn this into a switch(). Once we have several methods, we'll be wasting a bit of minor but cumulative CPU cycles for every time we need to perform this action.

In order to bypass any overhead, or make the overhead insignificant, we make use of a sometimes neglected feature - function pointers. Let's rewrite the prior example:

void (*function_1)(type a, type b) = method_a;
...
void function_2(type *a, type *b, size_t ab_len)
{
  while (ab_len--)
  {
    function_1(*a++, *b++);
  }
}

With this new bit of code, method_a will be used each time. If we want to recalculate which method to use because an option was changed. then we can do something like this when need be:

function_1 = complex_formula() ? method_a : method_b;

But this complex_formula() won't have to be rechecked for each element of an array, or even overhead for comparison and jumping if we did ifs/switch on a variable.

I've looked into the difference of calling a function directly or via a pointer, and on the CPUs I looked at, the overhead was 1 cycle or even 0, meaning the overhead is negligible if any. Either way, it's less than that of a comparison and jump, and surely several of them.

If you remember some posts back where I was talking about quick sorting, I setup a sorting testing frame work like so:

struct qsorters
{
  char *name;
  void (*func)(void *, size_t, size_t, int(*)(const void *, const void *));
};

static struct qsorters qsorters[] = {{"AT&T", qsort_att},
                                     {"BSD 1983", qsort_bsd2},
                                     {"BSD 1990", qsort_bsd3},
                                     {"BSD 1993", qsort_bsd},
                                     {"diet libc", qsort_dietc},
                                     {"DJGPP", qsort_djgpp},
                                     {"glibc", qsort_gnu},
                                     {"IBM", qsort_ibm},
                                     {"Linux", qsort_linux},
                                     {"Microsoft", qsort_microsoft},
                                     {"Sun", qsort_solaris},
                                     {"Syslinux", qsort_syslinux},
                                     {"uClibc", qsort_uclibc},
                                     {"insane", qsort_insane},
                                     {"Simple", qsort_simple},
                                    };

Now my sorting framework simply looped through the array and did the sorting tests on qsorters[i].func() instead of it needing to setup some kind of switch system to translate names into the function to call. If you want table driven methods to apply to functions, this is the way to do it. Imagine how much slower my testing framework would've been if I had to use a switch on this. This also makes the code simpler to read and write, just like arrays make more sense than x1. x2. x3. etc...

Function pointers are a wonderful thing to use whenever you have multiple functions which are the same black box, which when on the same input offer the same output, just use different methods internally.

This also extends well to when mixing with other kinds of optimizations. Quite often people try to optimize critical sections of their code using hand tuned assembly. Now on the x86 platform, there exists several instruction sets which can be used for optimization that not every CPU has, for example, MMX, 3DNow!, SSE, SSE2, etc...
If one wanted to offer good assembly optimizations for something, I all to often see scattered across programs code like this:

void func()
{
  if (detect_sse2())
  {
    func_sse2();
  }
  else if (detect_3dnow())
  {
    func_3dnow();
  }
  else if (detect_mmx())
  {
    func_mmx();
  }
  else
  {
    func_i386();
  }
}

If func() is called say 10,000 times a frame in a video processing program, it really lowers the overall FPS that could be processed if instead the following method was used:

void (*func) = func_i386;
void (*func2) = func2_i386;
etc...

void instructions_detect()
{
  if (detect_sse2())
  {
    func = func_sse2;
    func2 = func2_sse2;
  }
  else if (detect_3dnow())
  {
    func = func_3dnow;
    func2 = func2_3dnow;
  }
  else if (detect_mmx())
  {
    func = func_mmx;
    func2 = func_mmx;
  }
}

With this, instruction_detect() can be called when the program is started, or the library is initialized, and since the instruction set is not going to change in the middle, you just call this once and forget about it. With this, you can achieve optimal speed for any given processor in a program, without wasting any speed for overhead, aside from an initial call.