Basics Of Function Pointers In C

Sure, you can get away with, say, implementing a parser with a big switch statement that calls various parse_this() or parse_that() functions, depending on what kind of token you hit. On the other hand, you could instead keep a hash table with token-type keys and function-pointer values. Then instead of O(n) cmp/jnz operations (as a switch statement boils down to), you get O(1) for the hash function, and no processor branch-prediction penalty.

Where it really gains advantage is callbacks: where you write a function for a library (low-level code; mechanism) which can call a user-provided function (high-level code; policy) to do something. The low-level isn't supposed to be aware of the high-level; you shouldn't have to recompile the library every time you have a new callback to pass to it. So function pointers are ideal for this. You call the function, pass it the address of your function, and then it jumps to it to get some answer whenever it needs it.

Think on this for a little bit, and you might be able to invent the traditional higher-order functions: things like map, filter, and fold, which let you do things (adding one to each element; making a new list with just the elements that are even; summing the elements together) by just specifying the policy of what you want to do with each item, without worrying about the mechanism of how it's iterating through the list, keeping temporary values, etc.

Thinking further, you might realize that if you can read a file into executable memory at runtime using some OS function, then you could put native machine code in that file, along with a table specifying function names and the offsets where those functions start in the file. You could read this table in, add the pointer representing where the file starts in memory, to the offset from the table representing where the machine-code is in the file... and bam, you've got a function pointer! Now you can call it. That's a plugin system! (These files containing symbol tables and machine code are called "Shared Object-code" or ".so" files--or Dynamically-Linked Libraries (".dll"s) in Windows--and the function to load them is dlopen(). You don't have to do the math yourself; it's abstracted away by the mechanism--but that's what's really going on there. It's just a plain-old file, mapped into memory, and then you get an address into that memory and call it.)

I would say that the ultimate use of function pointers, though, is a tracing JIT (the JIT being short for "Just In Time".)

In some languages (themselves implemented on top of C), the language's compiler is built into the language's runtime; you can take code specified in source form, or as bytecode, and pass it as a regular old string to a function, which will turn it into native machine code, load it into (an executable range of) memory, and then return you a function pointer to it.

Given this, the language can be based around an interpreter that normally just reads source- or byte-code directly. Interpreters are great, for the most part--they're easy to program; shorter and cleaner than compilers in source form; they frequently fit entirely in processor-cache in compiled form, whereas globs of native code don't; and they don't tend to branch much. If you've never implemented one, they tend to just be a short little "read instruction, parse it into an op and arguments, look up what function that op translates to (via the hash-table-of-function-pointers method above), pass that function the arguments, repeat" loop.

The only thing is, if you have to do that over and over for the same 1000 instructions, the "read, interpret, jump, return" loop does add overhead--especially since each of these operations has to execute separately and serially, where native instructions might get optimized together into a single clever instruction like x86's "lea" (fused multiply-add followed by load-from-memory, all in a single CPU cycle!)

So, if you want that performance boost for your tight inner-loop code, you could write a separately-compiled module in a lower-level language, and hook it into your code through the C ABI (as above--plugin system = dlopen = more function pointers!) But that's a big jump in complexity. Instead, if you just hook a JIT to your interpreter, the result is only slightly more complex than a plain interpreter.

A JITing interpreter does the same loop, but it also keeps statistics on how often it executes each piece of your code. When it notices that some piece of code is getting interpreted over and over a lot, it'll pass it into the JIT; get back a function pointer to real, native, optimized code; and then patch its in-memory representation of the code you fed it, so instead of saying "A, B, [C, D, E], F", where [C, D, E] is the block that's getting executed all the time, it'll say "A, B, jump to [this native address] and run what's there, F".

That single instruction will transfer control from the interpreter to the code compiled by the JIT, through the function pointer. When the compiled function is done, control comes back, and the interpreter steps to the next instruction like normal. Still easy, still simple, but way faster where and when you need it. Neat, huh?

    func(foot);
    /* Should check func != gun.shoot */

I wrote a fluent reflection/serialization engine a while back which made heavy use of them.

https://github.com/sparecycles/reflect/blob/master/include/r...

People often say this in regards to pointers, or something similar like in the article too, "When understood, function pointers become a powerful tool in the C toolbox.", but often don't explain how/why. In the article the author says that at some indefinite point of time in future they may write about that.

Do you, or anyone, have a link to somewhere not simply explaining the technical side of pointers, but their usage in idealistic and primarily real world examples? Bonus points if it includes indirection, function pointers and other things.

Update: User derefr gave a seemingly great answer below to a similar question like mine.