What Are the Operations Supported by Raw Pointer and Function Pointer in C/C++

What are the operations supported by raw pointer and function pointer in C/C++?

For both function and object pointers, they compile but their result is only guaranteed to be consistent for addresses to sub-objects of the same complete object (you may compare the addresses of two members of a class or array) and if you compare a function or object against itself.

Using std::less<>, std::greater<> and so on will work with any pointer type, and will give consistent results, even if the result of the respective built-in operator is unspecified:

void f() { }
void g() { }

int main() {
  int a, b;

  ///// not guaranteed to pass
  assert((&a < &b) == (&a < &b));

  ///// guaranteed to pass
  std::less<int*> lss1;
  assert(lss1(&a, &b) == lss1(&a, &b));
  // note: we don't know whether lss1(&a, &b) is true or false. 
  //       But it's either always true or always false. 

  ////// guaranteed to pass
  int c[2];
  assert((&c[0] < &c[1]) == (&c[0] < &c[1]));
  // in addition, the smaller index compares less:
  assert(&c[0] < &c[1]);

  ///// not guaranteed to pass
  assert((&f < &g) == (&f < &g));

  ///// guaranteed to pass
  assert((&g < &g) == (&g < &g));
  // in addition, a function compares not less against itself. 
  assert(!(&g < &g));

  ///// guaranteed to pass
  std::less<void(*)()> lss2;
  assert(lss2(&f, &g) == lss2(&f, &g));
  // note: same, we don't know whether lss2(&f, &g) is true or false.

  ///// guaranteed to pass
  struct test {
    int a;
  // no "access:" thing may be between these!
    int b;

    int c[1];
  // likewise here
    int d[1];

    test() {
      assert((&a < &b) == (&a < &b));
      assert((&c[0] < &d[0]) == (&c[0] < &d[0]));

      // in addition, the previous member compares less:
      assert((&a < &b) && (&c[0] < &d[0]));
    }
  } t;
}

Everything of that should compile though (although the compiler is free to warn about any code snippet it wants).

---

Since function types have no sizeof value, operations that are defined in terms of sizeof of the pointee type will not work, these include:

void(*p)() = ...;
// all won't work, since `sizeof (void())` won't work.
// GCC has an extension that treats it as 1 byte, though.
p++; p--; p + n; p - n; 

The unary + works on any pointer type, and will just return the value of it, there is nothing special about it for function pointers.

+ p; // works. the result is the address stored in p.

Finally note that a pointer to a function pointer is not a function pointer anymore:

void (**pp)() = &p;
// all do work, because `sizeof (void(*)())` is defined.
pp++; pp--; pp + n; pp - n;

How do function pointers in C work?

Function pointers in C

Let's start with a basic function which we will be pointing to:

int addInt(int n, int m) {
    return n+m;
}

First thing, let's define a pointer to a function which receives 2 ints and returns an int:

int (*functionPtr)(int,int);

Now we can safely point to our function:

functionPtr = &addInt;

Now that we have a pointer to the function, let's use it:

int sum = (*functionPtr)(2, 3); // sum == 5

Passing the pointer to another function is basically the same:

int add2to3(int (*functionPtr)(int, int)) {
    return (*functionPtr)(2, 3);
}

We can use function pointers in return values as well (try to keep up, it gets messy):

// this is a function called functionFactory which receives parameter n
// and returns a pointer to another function which receives two ints
// and it returns another int
int (*functionFactory(int n))(int, int) {
    printf("Got parameter %d", n);
    int (*functionPtr)(int,int) = &addInt;
    return functionPtr;
}

But it's much nicer to use a typedef:

typedef int (*myFuncDef)(int, int);
// note that the typedef name is indeed myFuncDef

myFuncDef functionFactory(int n) {
    printf("Got parameter %d", n);
    myFuncDef functionPtr = &addInt;
    return functionPtr;
}

The Benefits of Using Function Pointers

There is nothing especially "fast" about function pointers. They allow you to call a function which is specified at runtime. But you have exactly the same overhead as you'd get from any other function call (plus the additional pointer indirection). Further, since the function to call is determined at runtime, the compiler can typically not inline the function call as it could anywhere else. As such, function pointers may in some cases add up to be significantly slower than a regular function call.

Function pointers have nothing to do with performance, and should never be used to gain performance.

Instead, they are a very slight nod to the functional programming paradigm, in that they allow you to pass a function around as parameter or return value in another function.

A simple example is a generic sorting function. It has to have some way to compare two elements in order to determine how they should be sorted. This could be a function pointer passed to the sort function, and in fact c++'s std::sort() can be used exactly like that. If you ask it to sort sequences of a type that does not define the less than operator, you have to pass in a function pointer it can call to perform the comparison.

And this leads us nicely to a superior alternative. In C++, you're not limited to function pointers. You often use functors instead - that is, classes that overload the operator (), so that they can be "called" as if they were functions. Functors have a couple of big advantages over function pointers:

• They offer more flexibility: they're full-fledged classes, with constructor, destructor and member variables. They can maintain state, and they may expose other member functions that the surrounding code can call.
• They are faster: unlike function pointers, whose type only encode the signature of the function (a variable of type void (*)(int) may be any function which takes an int and returns void. We can't know which one), a functor's type encodes the precise function that should be called (Since a functor is a class, call it C, we know that the function to call is, and will always be, C::operator()). And this means the compiler can inline the function call. That's the magic that makes the generic std::sort just as fast as your hand-coded sorting function designed specifically for your datatype. The compiler can eliminate all the overhead of calling a user-defined function.
• They are safer: There's very little type safety in a function pointer. You have no guarantee that it points to a valid function. It could be NULL. And most of the problems with pointers apply to function pointers as well. They're dangerous and error-prone.

Function pointers (in C) or functors (in C++) or delegates (in C#) all solve the same problem, with different levels of elegance and flexibility: They allow you to treat functions as first-class values, passing them around as you would any other variable. You can pass a function to another function, and it will call your function at specified times (when a timer expires, when the window needs redrawing, or when it needs to compare two elements in your array)

As far as I know (and I could be wrong, because I haven't worked with Java for ages), Java doesn't have a direct equivalent. Instead, you have to create a class, which implements an interface, and defines a function (call it Execute(), for example). And then instead of calling the user-supplied function (in the shape of a function pointer, functor or delegate), you call foo.Execute(). Similar to the C++ implementation in principle, but without the generality of C++ templates, and without the function syntax that allows you to treat function pointers and functors the same way.

So that is where you use function pointers: When more sophisticated alternatives are not available (i.e. you are stuck in C), and you need to pass one function to another. The most common scenario is a callback. You define a function F that you want the system to call when X happens. So you create a function pointer pointing to F, and pass that to the system in question.

So really, forget about John Carmack and don't assume that anything you see in his code will magically make your code better if you copy it. He used function pointers because the games you mention were written in C, where superior alternatives are not available, and not because they are some magical ingredient whose mere existence makes code run faster.

Why does the implementation of std::any use a function pointer + function op codes, instead of a pointer to a virtual table + virtual calls?

Consider a typical use case of a std::any: You pass it around in your code, move it dozens of times, store it in a data structure and fetch it again later. In particular, you'll likely return it from functions a lot.

As it is now, the pointer to the single "do everything" function is stored right next to the data in the any. Given that it's a fairly small type (16 bytes on GCC x86-64), any fits into a pair of registers. Now, if you return an any from a function, the pointer to the "do everything" function of the any is already in a register or on the stack! You can just jump directly to it without having to fetch anything from memory. Most likely, you didn't even have to touch memory at all: You know what type is in the any at the point you construct it, so the function pointer value is just a constant that's loaded into the appropriate register. Later, you use the value of that register as your jump target. This means there's no chance for misprediction of the jump because there is nothing to predict, the value is right there for the CPU to consume.

In other words: The reason that you get the jump target for free with this implementation is that the CPU must have already touched the any in some way to obtain it in the first place, meaning that it already knows the jump target and can jump to it with no additional delay.

That means there really is no indirection to speak of with the current implementation if the any is already "hot", which it will be most of the time, especially if it's used as a return value.

On the other hand, if you use a table of function pointers somewhere in a read-only section (and let the any instance point to that instead), you'll have to go to memory (or cache) every single time you want to move or access it. The size of an any is still 16 bytes in this case but fetching values from memory is much, much slower than accessing a value in a register, especially if it's not in a cache. In a lot of cases, moving an any is as simple as copying its 16 bytes from one location to another, followed by zeroing out the original instance. This is pretty much free on any modern CPU. However, if you go the pointer table route, you'll have to fetch from memory every time, wait for the reads to complete, and then do the indirect call. Now consider that you'll often have to do a sequence of calls on the any (i.e. move, then destruct) and this will quickly add up. The problem is that you don't just get the address of the function you want to jump to for free every time you touch the any, the CPU has to fetch it explicitly. Indirect jumps to a value read from memory are quite expensive since the CPU can only retire the jump operation once the entire memory operation has finished. That doesn't just include fetching a value (which is potentially quite fast because of caches) but also address generation, store forwarding buffer lookup, TLB lookup, access validation, and potentially even page table walks. So even if the jump address is computed quickly, the jump won't retire for quite a long while. In general, "indirect-jump-to-address-from-memory" operations are among the worst things that can happen to a CPU's pipeline.

TL;DR: As it is now, returning an any doesn't stall the CPU's pipeline (the jump target is already available in a register so the jump can retire pretty much immediately). With a table-based solution, returning an any will stall the pipeline twice: Once to fetch the address of the move function, then another time to fetch the destructor. This delays retirement of the jump quite a bit since it'll have to wait not only for the memory value but also for the TLB and access permission checks.

Code memory accesses, on the other hand, aren't affected by this since the code is kept in microcode form anyway (in the µOp cache). Fetching and executing a few conditional branches in that switch statement is therefore quite fast (and even more so when the branch predictor gets things right, which it almost always does).

Function/Method pointers Pushed to a Deque

The problem is that the signature of the class methods don't match with the function signature bool (*)(). The signatures of the two methods are bool (Button::*)(); or bool (A2_Game::*)(); respectively. (The actual class to which the method belongs is part of its signature!)

The solution here is to use functors/function objects. Functors are wrapper objects around "callable elements" that are useful if you want to treat functions like objects (in a OOP sense). If you have boost at hand your code could look similar to this (code compiles):

#include <boost/function.hpp>
#include <deque>

class Button
{
public:
    bool DoInput() { return true; }
};

class A2_Game
{
public:
    typedef boost::function<bool()> Functor;
    std::deque<Functor> Input_Functions;
    bool EnterName() { return true; }
    void OtherMethod();
};

void A2_Game::OtherMethod()
{
    Button* btn1 = new Button();
    Input_Functions.push_back(boost::bind(&A2_Game::EnterName, this));
    Input_Functions.push_back(boost::bind(&Button::DoInput, btn1));
}

boost::bind combines a function pointer with the reference to an actual class instance and returns an function object of the same type as A2_Game::Functor.

Note that boost::function has been integrated into the C++11 standard (see here), so if your project supports C++11 simply use #include <functional> and std instead of boost namespaces.

Is is valid to construct std::set of pointer type?

While it is true that built-in operator < only works for pointers into the same array, std::set and std::map don't use that operator - they use std::less. This, in turn, is guaranteed to impose a total order on all pointers:

[comparisons]/2 For templates less, greater, less_equal, and greater_equal, the specializations for any pointer type yield a strict total order that is consistent among those specializations and is also consistent with the partial order imposed by the built-in operators <, >, <=, >=.

---

Related Topics