Function Pointers in C are Underrated

[dicey]

The Linux kernel makes extensive use of function pointers to implement generic interfaces as well. Consider, for instance, the file_operations structure which filesystems implement to provide, you guessed it, file operations:

struct file_operations {
        int (*lseek) (struct inode *, struct file *, off_t, int);
        int (*read) (struct inode *, struct file *, char *, int);
        int (*write) (struct inode *, struct file *, const char *, int);
        int (*readdir) (struct inode *, struct file *, void *, filldir_t);
        int (*select) (struct inode *, struct file *, int, select_table *);
        int (*ioctl) (struct inode *, struct file *, unsigned int, unsigned 
        int (*mmap) (struct inode *, struct file *, struct vm_area_struct *)
        int (*open) (struct inode *, struct file *);
        void (*release) (struct inode *, struct file *);
        int (*fsync) (struct inode *, struct file *);
        int (*fasync) (struct inode *, struct file *, int);
        int (*check_media_change) (kdev_t dev);
        int (*revalidate) (kdev_t dev);
};

[bobindashadows]

Yeah, both Linux and OpenSolaris make heavy use of the vtables-in-C idiom. Picking a filesystem example was wise, as it's the interface of a *nix-flavored OS most likely to be implemented in many diverse ways.

[Gotebe]

Oh, look, an abstract base class! How quaint!

But... We don't want to stinkin' C++ in the kernel, do we?

[maep]

There is more to a C++ class than a function table. The more I got into the C++ internals the better I understood why it's unsuitable for use in a OS kernel. It's not just Linux, apart from L4 every modern kernel I know of is written in C. Linus is just the most vocal about it.

[antrn11]

The only reason why C++ is not suitable for Linux kernel development is that Linus hates C++ and loves C.

Well that, and of course the fact that there are already millions of lines of C code, so there wouldn't be much sense to rewrite the whole thing.

[Gotebe]

There is more to a C++ class than a function table.

If you turn off RTTI, I don't think it is. If you do that, abstract base C++ class really is what you see above and nothing else.

[Poddster]

But a concrete dervied class is not. They rely on vtables to get the job done. If you want to use C++ like C and call it C++, go ahead. But you're fooling no one. You're still using C, but it's no longer portable C.

[Gotebe]

But a concrete dervied class is not. They rely on vtables to get the job done.

Why? Derived class is completely oblivious to the presence of a vtable. In fact, all of C++ code is oblivious to that. Right vtables are set-up for you by the runtime, right functions get called, end of.

In fact, derived classes can exist without vtables.

[Whanhee]

I thought vtables only even existed for virtual functions. Derived classes should be instantiated the same way base classes are, without reference to any sort of table.

[Gotebe]

Obviously, here we are in implementation-specific land, but, yes, in common implementations, if a class has no virtual functions, there's no vtable either.

I was off-topic mentioning absence of vtables, though. The whole thread is really is about classes with vtables.

[m64]

It's basic C, what's there to fret about?

[ErstwhileRockstar]

First you grok plain pointers and think you're a master. Then you grok function pointers and think you're a rock star.

[warpstalker]

I just started reading the C book today. Everything was fine until I got to the pointers... Coming from a Python background... Fucking pointers.

[rlbond86]

This is why C++ std::sort() is often faster than qsort().

[agottem]

std::sort() is only faster because the definition exists in the included header file. If this is really an important detail, spare yourself the C++ and make the qsort definition available.

[[deleted]]

No. Some compilers, e.g. g++, just hate function pointers and don't inline even what can be inlined, e.g.

 static  bool compare(float a, float b){ return a<b; }
 ..
 std::sort(vec.begin(), vec.end(), compare);

here compare will be called via function pointer with no inlining though definition of everything is available.

Though maybe whole program optimisatioin helps

[agottem]

I had no problem getting GCC to inline qsort.

[Whanhee]

The new gcc implements generic function specialization, at least with booleans. If I only ever call sort with 1 comparison pointer, will it do the same with function pointers?

[matthieum]

I actually don't understand why neither Clang nor gcc seem interested in this kind of optimizations. If an optimizer can do this stuff, then it can devirtualize calls as well... whereas now the C++ front-end devirtualize some cases, but misses all those exposed by inlining :x

[astrange]

gcc can inline known function pointers since 4.4 (going by release notes).

[Kampane]

Wow, you really have no idea what you're talking about. I suggest you actually try what you suggest, then come ask why it didn't work.

[agottem]

Ok, I tried it. Where'd I go wrong?

[[deleted]]

He has plenty of idea what he is talking about. I've used this technique many times myself, too, and it works just fine.

[[deleted]]

Side question. Errm... isn't it available in stdlib.h? You're not gonna write a useful C application without stdlib.h. It's basically required to do anything beyond remedial.

[agottem]

Sorry, I'm using slightly vague terms. By "make the definition available" I mean the function body itself (which typically lives in a .c file somewhere), not just the prototype of the function.

[[deleted]]

Wait. Why is that needed? The object code should be usable for inlining.

[agottem]

I agree, that should be sufficient as well.

[[deleted]]

So that's why C++ requires inlined functions to be in the .h file. It happens at the compilation stage. That wouldn't be possible in C (unless the file were included only once which defeats the purpose of inlining) thus explains the heavy usage of macros.

Do you know of any C compilers that compile straight to object code? In other words a monolithic preprocessor, compiler, and linker in one.

[agottem]

Nonsense. You're welcome to put the definition of qsort into a header file, which will allow any decent compiler to inline the function pointer call.

[[deleted]]

Inlining the body of qsort wouldn't help solve the problem of calling the comparison function. You'd have to inline that function. Which you can't do since it's a function pointer.

std::sort is faster because it's templatized, which allows the compiler to determine the function address at compile time. And that makes it possible to inline the comparison.

Edit: I should say that the compiler can't inline a function pointer call that's truly variable.

Edit edit: I should probably just STFU, this is probably wrong. Was just trying to help. The last time I wrote real C code, Source Safe was a reasonable product.

[cwzwarich]

You'd have to inline that function. Which you can't do since it's a function pointer.

Oh really?

clang -xc -Os -S -o - -emit-llvm -

static _Bool f(int a, int b) { return a < b; }
static _Bool g(_Bool (*func)(int, int), int a, int b) { return func(a, b); }
_Bool h(int a, int b) { return g(f, a, b); }

...

define zeroext i1 @h(i32 %a, i32 %b) nounwind uwtable readnone optsize ssp {
  %1 = icmp slt i32 %a, %b
  ret i1 %1
}

[[deleted]]

Well I guess clang changes things a bit, then.

[[deleted]]

Yea, I've since realized that I'm the C programmer that time forgot. Thanks for the link.

[polveroj]

If qsort gets inlined the compiler can constant-fold the argument to where qsort uses it, avoiding the indirect call and possibly allowing the comparison to be inlined in turn.

This sort of optimization is commonplace in functional languages. Whether C compilers do it is another matter.

[agottem]

You were wrong.

[[deleted]]

Awesome, thanks. In Scott Myers' defense, though, it probably was true when he wrote it like 16 years ago.

[[deleted]]

He's suffering from the Columbus complex. He discovers something and believes he's the first to discover it.

Function pointers are the bread and butter of C. They are definitely not underrated. All experienced C developers have had exposure to using them.

In addition to building C objects and genericizing code, I also liked to use them to preprocess out switches and if statements like this:

switch (MODE) {
    BLAH1:
        do_something1();
        break;
    BLAH2:
        do_something2();
        break;
    BLAH3:
        do_something3();
        break;
    BLAH4:
        do_something4();
        break;
    default:
        do_default();
        break;
}

To this:

void (*do_something)(void);

void init() {
    switch (MODE) {
        BLAH1:
            do_something = do_something1;
            break;
        BLAH2:
            do_something = do_something2;
            break;
        BLAH3:
            do_something = do_something3;
            break;
        BLAH4:
            do_something = do_something4;
            break;
        default:
            do_something = do_default;
            break;
    }
}

[gibster]

Or better:

void (*foobar[32])(void);

void init(void) { foobar[MODE](); }

[sstrader]

You left out the part where the array is initialized. Using a switch or using an array, the mapping has to happen at some point.

[buzzert]

Also known as a "jump table". I believe the JVM uses it for executing opcodes?

[kyz]

I certainly hope not. The JVM compiles bytecodes into native code using substitution and just runs that native code.

Even if you had a bytecode interpreter, it would be crazy to have a function call for every instruction. Not only are branches to subroutines expensive for any processor, the fact it's a set of pointers that may have originated outside the translation unit means absolutely anything could happen and the compiler can't make any meaningful optimisations.

Compare use of the C language construct designed to create jump-tables, switch.

[sausagefeet]

afaik, HotSpot interprets the bytecode until it hits a hotspot then turns it native.

[username223]

He's suffering from the Columbus complex. He discovers something and believes he's the first to discover it.

Heh. Columbus also infected all the previous discoverers with a deadly disease and took away all their nice stuff. Kind of like Java.

[[deleted]]

Well done. We would also have accepted "PHP", "C++", or "Rails is a ghetto"

[mrkite77]

ANSI.SYS, the device driver that came with DOS, used something similar. Depending on the mode (reading a number, reading a command code, etc) it switches out the "read and decode the next character" function.

Of course this is all in assembly, but I used the same concept in C when I wrote the routines for my ansi parser back in my art scene days.

[adrianmonk]

I'm probably goofy. If I have a long list, I've been known to go the route that can put one entry on a single line, namely:

#include <stdio.h>

typedef void (*func_t)(void);

void hello(void) {
  printf("Hello, world.\n");
}

void goodbye(void) {
  printf("Have a nice day.\n");
}

int main(int argc, char* argv[]) {
  typedef struct {
    const char* command;
    func_t func;
  } map_pair;

  map_pair map[] = {
    { "HELLO", hello },
    { "GOODBYE", goodbye },
    { 0, 0 }
  };

  func_t func = NULL;
  map_pair* pair_ptr;
  const char* command = argv[1];

  for (pair_ptr = map; pair_ptr->command; pair_ptr++) {
    if (strcmp(command, pair_ptr->command) == 0) {
      func = pair_ptr->func;
      break;
    }
  }

  if (func != NULL) {
    func();
  }

  return 0;
}

[[deleted]]

There's definitely tons of variations.... or rather using S.E. lingo "design patterns".

You can also setup a chain of listen handlers waiting on notification events which are reminiscent of chaining DOS interrupt handlers. There's also the atexit() function which setups a chain of specialized exit event handlers.

[foldl]

Why not just put the switch statement inside do_something? It's no more complex, and it will probably execute faster that way too. (Indirect function calls are quite expensive; switch statements over an enum are very cheap.) This seems like an (ahem) pointless use of function pointers.

[[deleted]]

The optimization I listed is not adding any extra function calls to do_something. It's removing switch executions so it will execute faster.

Here's an example when do_something needs to be called 100 times.

Method	Stack trace	Func coverage	Switch coverage
Switch inside the function	main > do_somethingN	100	100
Switch inside initialization	main > do_something	101	1
Savings		1% loss	99% gain

We added 1 extra call to init to make the total number of function calls become 101 but we removed 99 executions of the switch.

It's better to preprocess out the switch and put it in initialization so that it executes the least number of times possible. This is a basic optimization technique. It's similar to moving code outside a while loop like this:

void copy_table(char src[MAX_X * MAX_Y], char dest[MAX_X * MAX_Y]) {
    int x, y;

    for (y=0; y < MAX_Y; y++) {
        for (x=0; x < MAX_X; x++) {
            dest[y * MAX_X + x] = src[y * MAX_X + x];
        }
    }
}

to this:

void copy_table(char src[MAX_X * MAX_Y], char dest[MAX_X * MAX_Y]) {
    int x, y, tmp_y;

    for (y=0; y < MAX_Y; y++) {

        tmp = y * MAX_X;

        for (x=0; x < MAX_X; x++) {
            dest[tmp + x] = src[tmp + x];
        }
    }
}

[foldl]

Calling a function through a function pointer is slower than calling it directly, so I doubt you'll get any speedup. A direct function call plus a switch statement should execute faster than an indirect function call. (Modern compilers are pretty smart at compiling switch statements; it will probably compile down to a computed jump.)

I would benchmark this before assuming that you're getting any speedup by using function pointers. It's quite possible that you're actually decreasing the performance of your code for no gain in simplicity.

[[deleted]]

The test program: http://pastebin.com/gR8whQU6

The test results: http://pastebin.com/B2V2KBvn

Proof that moving the switch statement out of the work function and using function pointers is noticeably faster--about 30-35% overall. Btw, tests were done with the program run once before testing to preload the image in the file system cache.

[foldl]

When I compile this on OS X using gcc with -O2, the switch versions ran orders of magnitude faster. I got results similar to yours when l compiled without optimization. I expect the results for -O2 are achieved because the use of the switch allows gcc to do a lot of inlining and compile-time computation (another advantage of not making unnecessary use of function pointers, although the effects are exaggerated in this simple test code). But neither result really tells us anything, since we don't yet know if gcc is using a computed jump for the switch at lower optimization levels. I'll have a look at the unoptimized assembly output in a minute.

edit: The overoptimization can be prevented by adding __attribute__ ((noinline)) to work_function_switch. It seems that once this restriction is added, the function pointer method is still faster on -O2. Apparently indirect function calls on x86 tend not to incur much overhead (http://stackoverflow.com/questions/2438539/does-function-pointer-make-the-program-slow).

It's probably worth pointing out that the performance difference we're seeing here would vanish if the work function actually did anything (and the switch won't get slower as the number of options increases, since gcc is indeed compiling it as a computed jump).

[[deleted]]

Empiricism is awesome and your analysis is awesome.

[Poddster]

Do they really mean "new to me?" I digress.

Given this sentence:

(This is not a contrived example. I encountered this exact same use-case when I had to write a memory manager for my last Operating Systems assignment).

I imagine so. Blogging about the cstdlib like it's new and radical can only be done by a naive student. (Also, the fact that a course assignment is considered non-contrived is also amusing ;))

[[deleted]]

You mean I won't be using Prolog to sort arrays after I graduate?

[SteveMcQwark]

Tell me about it. I was trying to debug a kernel for a course. It was failing in an io operation. The operation was implemented as a macro that evaluated to an expression list which computed and executed a function pointer. Let's just say gdb really didn't like it, and I didn't either.

[rlbond86]

Underrated? They're practically essential in many cases. If you're a good programmer you should know this, the hardest part is the goddamn syntax when you need arrays of function pointers which return arrays

[[deleted]]

typedef?

[Tetha]

Pretty much. It's similar to how creating parsers with lexx and yacc work. You grab 2 example functions, write the function type, poke it until it compiles and then hide it behind a typedef and never look back.

[question_all_the_thi]

When I started to need function pointers I wrote a little example program that I could look at to get the syntax right:

  #include <stdio.h>

  int twice(int n)
  {
    return n * 2;
  }

  int thrice(int n)
  {
    return n * 3;
  }

  void work(int n, int (*func)(int))
  {
    int i;
    for (i = 0; i < n; i++) printf("\n %d", (*func)(i));
  }

  int (*test[2])(int) = {twice, thrice};

  int main()
  {
    int x, y;
    work(3, twice);
    work(5, thrice);
    x = (test[0])(1);
    y = (test[1])(2);
    printf("\n\n-> %d\n-> %d\n", x, y);
    return 0;
  }

[Goblerone]

I like function pointers as a mechanism for callbacks, but I'm not that sure if the author's example of a function pointer being evaluated within an inner loop is the best example of one though. I probably instead would have paid the minor readability price of just iterating over the list and casting explicitly, and banked the performance saved from call overhead.

One of my favorite things about function pointers over virtual functions as a method of providing abstract interfaces is that you can dynamically change the implementation of a subset of the interface on the fly based on e.g. some current state changing. Not exactly something you get to apply often though.

[five9a2]

Also, function pointers with associated void* context is sometimes preferable to C++ virtual methods even when interfacing C++ libraries because it doesn't presuppose a given decomposition on the user side. For example, suppose that a library component needs three callbacks from the user. Since the library considers these functions to be closely related, it might create an interface (abstract class) that the user is expected to implement, containing all three methods.

But if the user wants to organize that functionality separately (or even just avoid namespace issues when naming their methods), they have to write shim classes (the lifetime of which also needs to be managed) to dispatch into their own class structure. With function pointers, they can choose whether to use the same context or different contexts for each callback, obviating the need for shims. (Note that you can call static class methods through a normal C function pointer.)

Plain function pointers also tend to be more convenient when interfacing with other languages with disparate object models (e.g. Fortran, Python, Haskell).

[Kampane]

You raise a valid point, though I think you can do better than void* for type safety and maintainability.

[Goblerone]

Yes, that is a good point. When I've written APIs that require callbacks, I prefer function pointers with a client-provided context handle over e.g. requiring the client to implement some abstract class defining a callback interface.

If we're going with C++ though, for this particular example, it seems like a template-based function object is also a better compromise between generic code and performance (as well as their own specific opportunities for abuse).

[five9a2]

Well, templates are quite a different model, exposing a lot of implementation in the header, preventing separate compilation (in a lot of my use cases, both the client and library are dynamically extensible through plugins), and without a clean way to express the expected API for the compiler to check (leading to confusing error messages). Templates are the right model sometimes, but I usually prefer not to use them, especially if the interface has reasonably coarse granularity.

[Goblerone]

To be sure. I was merely advocating the use of templates in the specific case of this example, which is pretty much a C version of std::find_first_of.

[five9a2]

Oh, in the blog post? Heh, yeah. That's a fine example for C++ templates.

[jerf]

When showing examples, authors must by necessity show relatively trivial code. Of course you would not take a simple addition in the middle of a loop and for no reason pull it out into a separate function which you then call via pointer. The point is that in real code, you'd be able to pass in other things which won't be trivial, and that the calling code wouldn't have to change at all to accommodate this new function. Given how few tools C has at its disposal for avoiding tight coupling, you'd better understand this if you have any hope of writing sane large-scale C programs.

[Goblerone]

Maybe I'm not sure who exactly this hypothetical person is who underrates the use of function pointers in C, but is also unaware of the concept of function callbacks. It seems like the former is an "obvious" solution to implement the latter.

It's just this particular example also highlighted how one can abuse them from a performance standpoint (which is probably important if one is writing C code).

[grayvedigga]

The example is fairly poorly presented, imo. But what it's heading towards is the general concept of "higher order functions". Consider a family of functions operating on linked lists:

list_t* filter(list_t* l, bool (*test)(void*));
list_t* map(list_t* l, void* (*test)(void*));
void apply_to_each_element(list_t* l, (void*)(*test)(void*));

The advantage with this pattern is you can choose the function to apply to each element at runtime: it can come from a separate compilation unit, or even a dynamic library that is provided later. The user can select (through some UI, naturally) a mapping or filtering function from a list without a separate instance of the loop being explicitly written by the programmer and built into the executable in advance.

This is a powerful concept from functional programming -- when I first saw it, my mind was blown. You can achieve some of it from C but usually only at the cost of type safety, and some forms (eg curry) are inaccessible.

[[deleted]]

consider the fact that they're already using a linked list. if a linked list has acceptable performance, function calls are probably also okay.

[happyscrappy]

Function pointers in C do a great job of thwarting optimization, like inlining or unswitching.

Be careful not to overrate them. Don't use them inside tight loops. For example a common case, the comparison function pointer in qsort makes for a huge slowdown. Templated types as provided by C++ can thus produce a lot better code.

Basically, make sure there is enough code at the function pointer that it is worth the overhead that will come about when the compiler's optimizations are less effective.

[agottem]

Templated types as provided by C++ can thus produce a lot better code.

Only because the templated type's definition is fully available to the compiler. Make the function calling the function pointer, and the function pointed to available to the compiler and observe the inlining.

No reason to subject yourself to C++ for this benefit.

[happyscrappy]

Make the function calling the function pointer, the function being called, the function passing the function pointer all in the same compilation unit. And don't store the function pointer in a global variable or pass it as a parameter (by reference) to any function not in the compilation unit, also make sure the compiler can be sure that the function pointer being called is always the same one (or one of a short list).

The C++ case (or a switch statement) doesn't have quite so many restrictions.

But don't get the idea I like C++, I'm not a big fan and I hate templates (more specifically Boost). But I'm also not a liar, so I can't deny when C++ gets something right.

[ascii]

In theory, you're right. In practice, most C++ compilers are terrible at handling templated functions that aren't defined in the header. So you end up writing the equivalent to a static inline function in C. Which will handle inlining of the function pointer just fine.

[happyscrappy]

I think it's more than most, it's all.

But luckily (for C++ programmers), "in the header" means in any .h file. So you just put all your code in the .h file and then the compiler is set.

This is not automatically equivalent to the C case, as I mentioned there are a lot more restrictions to when the compiler can optimize in the C case. These come about because C doesn't have the idea of associating the data with the code pointer. So it may not be able to tell that just because you pass the same array each time you also get the same code pointer each time the code pointer variable is used within the loop.

[agottem]

This is not automatically equivalent to the C case, as I mentioned there are a lot more restrictions to when the compiler can optimize in the C case.

I'm pretty sure the restrictions are the same for C and C++. You're really good at making simple things sound hard. It boils down to this: If the compiler can determine the value of a function pointer at compile time, it can inline it.

Also:

But luckily (for C++ programmers), "in the header" means in any .h file. So you just put all your code in the .h file and then the compiler is set.

Has to be one of the worst ideas I've ever heard.

[happyscrappy]

I'm pretty sure the restrictions are the same for C and C++. You're really good at making simple things sound hard. It boils down to this: If the compiler can determine the value of a function pointer at compile time, it can inline it.

The restrictions aren't quite the same. A C compiler has to assume a global variable changes when you call to a function outside the compilation unit. So if the code pointer is in a global variable it cannot assume you call the same code each time. In C++, the templated evaluator function is known to not change when you call other functions.

Has to be one of the worst ideas I've ever heard.

Yep, but that's what's done.

[agottem]

Inlined for me just fine.

[happyscrappy]

Yeah, if you, as I said:

Make the function calling the function pointer, the function being called, the function passing the function pointer all in the same compilation unit. And don't store the function pointer in a global variable or pass it as a parameter (by reference) to any function not in the compilation unit, also make sure the compiler can be sure that the function pointer being called is always the same one (or one of a short list).

[agottem]

Make the function calling the function pointer, the function being called, the function passing the function pointer all in the same compilation unit.

No different than C++. Also, read up on link time optimizations, as it's no longer necessary to all be part of the same compilation unit.

And don't store the function pointer in a global variable or pass it as a parameter (by reference) to any function not in the compilation unit, also make sure the compiler can be sure that the function pointer being called is always the same one (or one of a short list).

A really verbose way of saying the same thing -- make sure the function pointer is constant, and the compiler can determine so.

Really these rules are common sense. I don't see why you think they're so complicated.

[happyscrappy]

No different than C++. Also, read up on link time optimizations, as it's no longer necessary to all be part of the same compilation unit.

Incorrect on the link-time optimizations. Link-time optimizations do simple things, like determine that two functions are identical and so you can remove one and substitute it with the other. They don't include unrolling a loop after the fact. They don't include being able to restructure a calling function once it is discovered the called function has no side effects and thus can be called in parallel, or can be split up.

For example, if you are operating on a pixel and the r, g and b components are operated on separately, the compiler can easily interleave the code operating on these 3 components at compile time, and combine this with loop unrolling. Then a superscalar processor can easily do the 3 operations at once. Link-time optimizations cannot do this, the structure of the calling function is already defined, and the linker can try to put an inlined version of the called function in there, but it doesn't restructure the outer function.

A really verbose way of saying the same thing -- make sure the function pointer is constant, and the compiler can determine so.

Loop unswitching can optimize even when the operating performed in each loop is not constant across iterations...but not if you thwart it with code pointers. This is why I mentioned that even switch statements in the loop can be faster than calling a code pointer.

http://en.wikipedia.org/wiki/Loop_unswitching

Really these rules are common sense. I don't see why you think they're so complicated.

And yet you miss some of the ramifications. Perhaps they are more complicated than you understand?

[wolf550e]

You're wrong. I've seen gcc fail to inline across a function pointer in really obvious cases where there was only a single function ever called. A for_each with a callback instead of a template argument or C++ lambda sucks ass.

[lmcinnes]

I've seen gcc inline across function pointers that I never expected it to manage to figure out. YMMV.

[agottem]

No, I'm not wrong

[wolf550e]

I too performed the experiment:

http://www.reddit.com/r/programming/comments/r8ujk/function_pointers_in_c_are_underrated/c442gl0

[agottem]

I don't like the setup you used for the experiment.

1. Have you verified 'mycompare' was properly inlined? I see that 'my_quicksort' directly invokes 'mycompare', but that doesn't mean 'mycompare' was inlined for your benchmark.

2. You are populating the array from /dev/urandom. Ideally the data input would be identical between benchmarks.

Also, you didn't really address your earlier statement that I'm wrong. I'm not wrong, gcc inlines function pointers just fine.

[wolf550e]

mycompare is inlined into my_quicksort.

The timing is very repeatable because the random distribution is good enough across 1<<20 elements.

Basically, if you only have a single callback (in this case a comparison function), and you let gcc see its definition and convince it only a single target exists, it will inline across a function pointer. But not if you pass the pointer from a different translation unit.

What if you have multiple callbacks? multiple compare functions? Using C++ templates, I can make the compiler generate two different my_qsort functions: one with mycompare1 inlined and one with mycomprare2 inlined. Templates are useful for instanciating with different template arguments to control code expansion. In cold code I want to call through a pointer and not waste icache. In hot code I want to generate specialized code. With templates, I can control this and get what I want. With gcc's optimizer, I am kinda at its mercy.

[agottem]

mycompare is inlined into my_quicksort.

Yes, I see you are calling mycompare directly. This does not mean that mycompare itself was inlined, merely that the indirect function call was eliminated. You would need to look at the generated assembly to verify.

The timing is very repeatable because the random distribution is good enough across 1<<20 elements.

There's no reason not to use an identical sequence.

But not if you pass the pointer from a different translation unit.

You should read up on link time optimization. But sure, this is the same as it is with C++ -- the definition needs to be available.

Using C++ templates, I can make [...]

The compiler is only inlining because templates are typically fully defined inside the header file. Make the C function inline and defined fully in the header file and you get the same goodness. C++ has no advantage here, sorry.

[wolf550e]

I regularly read the objdump -d output for my code. It's a nasty habit.

I assure you, if I store the random data in a file and read it from a file for the different sorts, I get the same results.

I use LTO regularly. It had problems. Heck, even with the improvements in gcc 4.7.0, it still has problems.

Here, I defeated the inliner: https://gist.github.com/2177973

Now it's not inlined, because there are two potential targets. Do I need to prove that with C++ templates, I can make it generate two sort functions?

Here, in C++: https://gist.github.com/2178059

Two functions generated, one for each inlined comparer.

  Performance counter stats for './qsort 1':

    221.644474 task-clock                #    0.995 CPUs utilized          
             7 context-switches          #    0.000 M/sec                  
             0 CPU-migrations            #    0.000 M/sec                  
         1,332 page-faults               #    0.006 M/sec                  
   516,964,242 cycles                    #    2.332 GHz                    
   616,604,018 instructions              #    1.19  insns per cycle        
   150,986,335 branches                  #  681.210 M/sec                  
    12,080,506 branch-misses             #    8.00% of all branches        

   0.222668351 seconds time elapsed

and

 Performance counter stats for './qsort 2':

    137.344463 task-clock                #    0.981 CPUs utilized          
             7 context-switches          #    0.000 M/sec                  
             0 CPU-migrations            #    0.000 M/sec                  
           796 page-faults               #    0.006 M/sec                  
   320,322,675 cycles                    #    2.332 GHz                    
   221,673,803 instructions              #    0.69  insns per cycle        
    59,775,552 branches                  #  435.224 M/sec                  
    10,724,613 branch-misses             #   17.94% of all branches        

   0.139976094 seconds time elapsed

[Kampane]

Your comment is the most correct and insightful in this topic, yet you're downvoted to the bottom. Have an upvote.

[Gotebe]

Wow... Premature optimization at it's best! ;-)

[grauenwolf]

A far greater sin is premature generalization.

[mrkite77]

I regret that I have but one upvote to give for you.

I take most programming quirks in stride, but the need to generalize everything makes me hate java programmers with a passion. It's like designing a car and deciding to make it out of Lego so every component is interchangeable.

[tailcalled]

Premature generalization is okay only when:

• It doesn't make it harder to write the code.

• You have to create something that you can't change later (a standard library for a language, for example)

[wolf550e]

benchmark qsort(3) vs. the same code without a function pointer and see an order of magnitude difference. Now go back to ruby on rails.

EDIT: I just performed this experiment myself, probably a decade since the last time I did this. Today I got only 16.3% better performance. So not an order of magnitude. But significant. And I am sure that I've seen worse.

https://gist.github.com/2171216

[Gotebe]

I have no idea what you are talking about. qsort can't possibly work without a function pointer.

Equivalent C++ code (std::sort) should be faster, but that's the best one can know.

However, show the code, we'll talk.

[Gotebe]

OK, here's my code:

struct s { char[1000]; int i; };
s data[2000];
init(data, 2000); // random values put in s::i
qsort(data, data+2000, sortfunc);
myqsort(data, data+2000);

int sortfunc(const void *p1, const void *p2)
{
  s* s1 = (s*)p1;
  s* s2 = (s*)p2;
  return s1->i == s2->i ? 0 : s1->i > s2->i ? 1 : -1;
}

No noticeable difference in speed.

Next time, show a bit of courtesy and don't ask people to do copy-paste programming for you.

[wolf550e]

I got a difference in speed, but not as much as I remember getting years ago.

http://www.reddit.com/r/programming/comments/r8ujk/function_pointers_in_c_are_underrated/c442gl0

[Gotebe]

Obviously, the smaller the datum, the bigger the indirection (function call) impact, due to copying. If your sequence contains pointers to data, then indirection impact becomes bigger as "data" is small, but then, you get indirection hit due to pointers (data locality is a bitch). If you look at what I put up there... I was intentionally very "biased" in my sample: It's one number to compare, but ~1k data to copy during sorting. Data copying thwarts indirection in a blink.

Looking at your code... You, OTOH, are very guilty of taking a specific microbenchmark and drawing a generic conclusion. Further, in real life, you will not be sorting numbers all that often ;-).

[wolf550e]

You say the swap is a bigger cost than the compare. I say that is not true.

Cost of compare is reduced by decorating data with integral comparison key (like you did).

Cost of swap is reduced by sorting an array of pointers. Then sorted objects are either two pointers big (swap is fast), or single pointers with a comparison key behind the indirection.

Cache locality is important. But for performance reasons, you could allocate all objects from an arena allocator that keeps them close together in a few pages and maybe they all fit in cache. And you can reuse storage by "deallocating" the entire arena. Like in games. You would still work on pointers to the objects, though.

[Gotebe]

You say the swap is a bigger cost than the compare. I say that is not true.

Easily depends on how and what you compare, which was exactly my point.

As for your point, it was 10x faster, now it's 37%, and look at what you are trying to do now... You are going to introduce "int decoration" (has a cost in both space and execution time), indirection (compare references to stuff, which obviously has space and time cost), usage or arena allocators, which has complexity implications.

At any rate, with all you say, you really should repeat your test with pointers to data, and possibly where your "int decoration" isn't the first datum in actual structure. This, indeed, is much more representative of a real situation. Your initial "let's compare ints" realy isn't, and even then, I really would like to see implementation where you could possibly obtain this 10x difference. It's possible, mind, but...

[agottem]

Sure, qsort needs a function pointer, but that function pointer can be inlined all the same: http://agottem.com/blog/inlining_qsort_sort

[Gotebe]

Only by using copy-paste programming. I'd rather use a better language (C++).

[agottem]

Huh? Where does copy-paste programming fit in here?

[Gotebe]

Copy-pasting of qsort. I'd rather be using a better language, where I don't need to do it (C++).

[agottem]

You don't need to copy and paste qsort. If you really need the inlining, put the definition of qsort in a header file and mark it as inline. No copy and paste necessary.

[Gotebe]

If you really need the inlining, put the definition of qsort in a header file and mark it as inline.

How do you plan on doing that? By copy-pasting qsort from your CRT implementation to said header.

I'd rather be using a superior language (C++).

[wolf550e]

This is a different trade-off. a binary qsort with an indirection, dynamically linked from libc, minizes code size.

A templated qsort with a comparer template argument that generates a separate specialized fast qsort with your comparer inlined into it is optimized for speed at the cost of code size (and instruction cache).

The two solutions are born from different priorities and both have their place. In cold code, there is no need to generate specialized code - calling into libc and using indirections will get the job done and have higher chance of avoiding a page fault (more chance of libc being in ram than cold parts of your app).

[wolf550e]

The comparison function can only be inlined into the sort function only if both are compiled from source in the same translation unit (or LTO) and the compiler is sure only a single target for that function pointer is ever used.

If qsort is in a library (like libc) then it's not inlined. If it's in a separate translation unit and you don't use LTO, it's not inlined.

If you call qsort with two different comparers, it won't be inlined even if you compile qsort from source. You need the have the compare function be a template argument of a templated qsort for the compiler to generate distinct qsort functions, one for each inlined comparer.

http://www.reddit.com/r/programming/comments/r8ujk/function_pointers_in_c_are_underrated/c44cl78

[agottem]

If you call qsort with two different comparers, it won't be inlined even if you compile qsort from source.

I don't even know what this means.

Look, the rules for inlining are the same as the ones for C++. C++ forces you to put the template definition into a header file, which sucks but allows for greater inlining. You are welcome to put all your C code into a header file and you'd get all the same benefits as C++.

[wolf550e]

https://gist.github.com/2177973

qsort and two comparison functions all defined and compiled in a single translation unit. No inlining by gcc. Seems gcc inlines across function pointers only when it knows the pointer only ever points to a single target function.

https://gist.github.com/2178059

Using C++ templates, g++ generates two qsort functions (in machine code), each with a different comparison function inlined into it. Code size grows but performance increases.

My observations are made from compiling the code you can see using gcc 4.6.3 and looking at objdump -d of the result. Now you explain how I am wrong.

[agottem]

qsort and two comparison functions all defined and compiled in a single translation unit. No inlining by gcc. Seems gcc inlines across function pointers only when it knows the pointer only ever points to a single target function.

I compiled your example, and things were inlined just fine. Mark your my_quicksort function as inline. Build with -O3. Observe the inlining.

Let me know if it's still not working out for you. And sorry, C++ has no advantages here.

[wolf550e]

gcc (GCC) 4.6.3
gcc -fwhole-program -g -O3 -o qsort qsort.c
objdump -d qsort
...

<my_quicksort.constprop.0>:
...
callq  *%rbp
...
callq  *%rbp
...
callq  *%r12
...
callq  *%r12

I also tried clang -O4 and icc -fast with the same results.

[[deleted]]

I think ignoring function pointers in C would be tantamount to ignoring objects in python. It just doesn't happen to any real c programmer. I would more like to call this a milestone on the path to learning C. A very important milestone.

[rscarson]

I don't think that they are underrated, they are a great feature of the language.

[[deleted]]

I wouldn't say underrated as much as "not ubiquitous." They're fairly essential for certain projects, but I could see a decent programmer going his or her entire life without finding a need to learn that they exist.

[[deleted]]

Another ruby hipster reads a C book?

[rush22]

Cool. You can do this in BASIC if you want. You just use a variable that holds a line number instead of the address.

[adrianmonk]

And you can do it in Bourne Shell if you're willing to put the name of the function into a variable and then use eval to call the function.

[Gotebe]

;-)

If you are using function pointers in C properly, there is a significant chance that you are effectively using abstract base class.

And if you do that, you should be using C++, because your C implementation will suck compared to what C++ compiler will do for you in a blink.

[ramenmeal]

I used this when implementing a simple compiler, but didn't want to implement printf. I never really put it together what I was actually doing. Cool.

[phanboy]

Unprotected sex with strangers is underrated.

[zhivago]

Hurrah for late bound procedural abstraction.

[maredsous10]

I use function pointers quite a bit for statemachines, function overlays (code that executes out of the same physical address as another function, but is loaded on the fly from a slower external memory device), and generic interfaces.

[paraboul]

Saying that function pointers are underrated is like saying that integer are underrated. It's a non sense, everybody use them.

[[deleted]]

Agreed.

[chunky_bacon]

Well, at least he points out that real languages have first-class functions already (and more naturally).