## Saturday, May 26, 2007

### 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.

DeFender1031 said...

I hate how underused function pointers are. I mean, as you know, I never would have learned them if Nach hadn't taught me, as most teachers tend to skip them. I think it's great that someone is finally trying to get them out there.

Give the wife and adorable little cuties my regards.

sinamas said...

Wait a minute. You mean there're actually c programmers that don't use function pointers?

Unknown said...

Yes there are plenty that don't. If you look at source code to many open source projects, you think to yourself on many occasions that they could have wrote the code much better using function pointers. I hope Insane Coder blogs again about function pointer uses, it's an important subject.

younus saleem saifullah said...

whenever I hit any "function pointer" tutorial I used to come across an example of "HOW TO REPLACE A SWITCH"....it was insane the way most examples were programmed.
I had almost come toa conclusion that function pointers are not all that useful.

Thanks to this blog now I do know the real power of function pointers. I made use of the same in "HOW TO REPLACE A SWITCH" and it gave wonderful results.

Thanks for the explaination...:)

Unknown said...

thanks a lot for sharring a very successful

ravi kumar said...

Thanks for provide great informatic and looking beautiful blog, really nice required information & the things i never imagined and i would request, wright more blog and blog post like that for us. Thanks you once agian

Birth certificate in delhi
Birth certificate in gurgaon
Birth certificate in noida
How to get birth certificate in ghaziabad
how to get birth certificate in delhi
birth certificate agent in delhi
birth certificate in greater noida
birth certificate agent in delhi
Birth certificate delhi

keanna said...

Endless supply of AWS Training Sessions in Gurgaon, wannabes can without much of a stretch form subject abilities in each module to convey a most streamlined arrangement. This for the most part empowers the group of spectators to use aptitudes in each idea and become specialists in each propelled cloud based arrangement and moving existing remaining burdens to the cloud.

sohbet.cm said...

sohbet www.yuvam.net
sohbet www.sohbet.cm

sohbet said...

Laklak Sohbetler de sakin olan yada içine kapanık olan insanlar sohbet etmezler diye düşünmeyin asla. Onların da kafa dengi insanlar elbette ki var. İçerisinde saklamış oldukları duyguları ortaya çıkaran insanlar…

https://forum.hayalsohbet.net

Free Chat said...

Thank you for sharing great information also Omegle may useful for talk to stranger people

alex said...

A common way of implementing OO-like code encapsulation and polymorphism in C is to return opaque pointers to a structure containing some function pointers. This is a very frequent pattern for example in the Linux kernel. Using function pointers instead of function calls introduces an overhead which is mostly negligible due to caching, as has already been discussed in other questions. omegle

Unknown said...
Carnegi said...

I will do it later!! ometv nirvam

Easy Loan Mart said...

Hi...
pointers from tampering. Before a function pointer is stored into memory, it is encrypted (i.e. XOR) with the secret key.
You are also read more How to Apply for a Business Loan Online

kajal said...

Streaming is great but sometimes you want to watch that movie during the camping trip in the middle of nowhere or on the plane when the internet is much slower than at home. The solution is to download the movie onto your device so you can watch it (aka "stream it locally") later on, when the internet isn't so great.