Sign in to follow this  
Ro_Akira

C++ function pointer optimization

Recommended Posts

Is there any chance of function calls via a pointer will be inlined and optimised away? Hypothetically speaking? I tried this simple contrived example in MSVC++ 2005 EE, Release, inlining Any Suitable, Link Time Code Generation (compiler+linker). The inline depth should be the default 254, but I manually set in anyway:
#pragma inline_depth(254)

inline int SimpleFunction ()
{
    return 1200;
}

typedef int (*SimpleFunctionPointerType) ();

// const there should make the function pointer const, I believe
SimpleFunctionPointerType const SimpleFunctionGlobalPointer (&SimpleFunction);

int main ()
{
    int k = 0;

    // const here should make the function pointer const, I believe
        SimpleFunctionPointerType const SimpleFunctionLocalPointer (&SimpleFunction);
        k += SimpleFunctionLocalPointer ();
004012AE  call        SimpleFunction (401250h)
004012B3  add         eax,edi
004012B5  add         esi,eax
        k += SimpleFunctionGlobalPointer ();
004012B7  call        dword ptr ds:[4021C8h]

    cout << k;
}

I'm trying to make things real simple here for the compiler. const function pointers to a locally declared function. It's interesting that the LocalPointer gets resolved to a regular function call, but then the compiler doesn't make the next step of inlining that (simple) function call. The call itself resolves to a mov eax,1200 ret :S Presumably there's greater difficulty involved in inlining the GlobalPointer, because the compiler has more trouble in general, determining if the pointer is safe/const?

Share this post


Link to post
Share on other sites
Quote:
Original post by Ro_Akira
Is there any chance of function calls via a pointer will be inlined and optimised away? Hypothetically speaking?


Hélas, no. I guess it's compiler dependent (I'm not brave enough to search the exact behavior in the Holy One). It's even the contrary: most of the time, you can force the compiler to not inline a function call by using a function pointer. For example, consider this code:


int function(int param)
{
return param+1;
}

int main(int argc, char* argv[])
{
int i;

i = function(100);

i = (true ? function : NULL) (i);

std::cout << "i = " << i << std::endl;

return 0;
}



The code resolves to:


int function(int param)
{
return param+1;
// 00401000 mov eax,dword ptr [esp+4]
// 00401004 inc eax
}
// 00401005 ret

// ----------------------

int main(int argc, char* argv[])
{
// 004018D0 push esi
int i;

i = function(100);

i = (true ? function : NULL) (i);
// 004018D1 push 65h // this is i = function(100);
// 004018D3 call function (401000h) // function is called, due to the function pointer
// 004018D8 add esp,4
// ...



As you see, even if the compiler knows that "function" will be called (true is always true, so there's only one code path), it still consider it as a pointer to function - while he correctly inlined function(100).

HTH,

Share this post


Link to post
Share on other sites
Quote:
Original post by Ro_Akira
Is there any chance of function calls via a pointer will be inlined and optimised away? Hypothetically speaking?

Yes. GCC 3.3.1 fully inlines every example given in this thread.

Σnigma

Share this post


Link to post
Share on other sites
Quote:
Original post by Ro_Akira
Is there any chance of function calls via a pointer will be inlined and optimised away? Hypothetically speaking?


Taking the address of a function makes it unsuitable for inlining. The compiler should not be inlining the call.

Quote:
// const here should make the function pointer const, I believe
SimpleFunctionPointerType const SimpleFunctionLocalPointer (&SimpleFunction);


There is no difference between const Foo and Foo const. There is a difference, however, between const Foo*, Foo const* on one hand, and Foo* const on the other.

Quote:
Presumably there's greater difficulty involved in inlining the GlobalPointer, because the compiler has more trouble in general, determining if the pointer is safe/const?


Not just more difficulty, it's impossible. For all the compiler knows, you could link against a DLL that modifies that global variable.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
Taking the address of a function makes it unsuitable for inlining. The compiler should not be inlining the call.

Since the observable behaviour is identical whether the function call is inlined or called through a function pointer a C++ compiler is perfectly within its rights to inline a call written using a function pointer under the "as-if" rule:
Quote:
C++ Standard, Final Draft, Section 1.8, Paragraph 1
The semantic descriptions in this International Standard define a parameterized nondeterministic abstract machine. This International Standard places no requirement on the structure of conforming implementations. In particular, they need not copy or emulate the structure of the abstract machine. Rather, conforming implementations are required to emulate (only) the observable behavior of the abstract machine as explained below.3)

3) This provision is sometimes called the "as-if" rule, because an implementation is free to disregard any requirement of the Standard as long as the result is as if the requirement had been obeyed, as far as can be determined from the observable behavior of the program.


Quote:
Original post by Fruny
Not just more difficulty, it's impossible. For all the compiler knows, you could link against a DLL that modifies that global variable.

The function pointer was declared const. Therefore any attempt to modify it is undefined behaviour, thus allowing the compiler to inline the function call.

Σnigma

Share this post


Link to post
Share on other sites
Quote:
Is there any chance of function calls via a pointer will be inlined and optimised away? Hypothetically speaking?

Quote:
Hélas, no....

Quote:
Yes...

Unless Hélas has a meaning of 'Opposite of ' or similar, these two arguments appear to be in conflict.

Quote:
There is no difference between const Foo and Foo const. There is a difference, however, between const Foo*, Foo const* on one hand, and Foo* const on the other.

Understood, and I thought what I gave would be an example of the later (Foo* const). Anyway, I changed the typedef to
typedef int (*const SimpleFunctionPointerType) ();

and it made no difference - to the compiler's output at least.

Quote:
The function pointer was declared const. Therefore any attempt to modify it is undefined behaviour, thus allowing the compiler to inline the function call.

You see, this is what I'm getting at. If the compiler has a const pointer, to a function that it knows won't be coming from a DLL or some such, then it should be able to resolve it to a non function call, and thus inline. This is my thinking anyway. How common const pointers are, is another thing. Although references should provide the same opportunities as a const pointers should they not?

Check out the resolving it does to the LocalPointer above. Do my eyes deceive me, or is that a simple function call, which should in turn be inlined? Can anyone explain the behaviour?

I'll see if I can check out gcc...

Share this post


Link to post
Share on other sites
Quote:
Anyhow, OP, you probably shouldn't even worry about it. The odds that will be the bottleneck of your program are VERY small.

Most likely. But it's just interesting to know sometimes :)

Share this post


Link to post
Share on other sites
Quote:

I'll see if I can check out gcc...


GCC converts both calls via function pointer to direct calls, even with optimisation disabled. With -O3, both calls to the function compile down to a single instruction:
mov eax, 2400


EDIT: Now I see this was posted earlier, by Enigma:

Quote:
GCC 3.3.1 fully inlines every example given in this thread.

Share this post


Link to post
Share on other sites
Even in debug you say? GCC kicks far more ass than I suspected :o

The example that Emmanuel Deloget provided:

i = (true ? function : NULL) (i);
// 004018D1 push 65h // this is i = function(100);
// 004018D3 call function (401000h) // function is called, due to the function pointer
// 004018D8 add esp,4





I get the same result as Emmanuel with VC++ 2005 EE Release. If I change it to a comparable if-else statement though, the compiler sees it for what it is. Is the conditional operator handled differently by the compiler? A question for another thread I guess.
Edit: Enigma said all mentioned in the thread to his post were inlined - I presume he's including this too! I thought VC++ 2005 was pretty good until today, what with it's Link Time Program Generation and all.

=== C++ - Virtual Functions ===
You'll notice that I mentioned C++ in this thread's title, but mostly I've been talking just about function pointers. The whole reason I got into this line of thought is with C++ encounters like this:

Derived d;

int Derived::VirtualFunction () const
{
return simple_expression;
}

void Function (const Base& b)
{
cout << b->VirtualFunction () << endl;
}

int main ()
{
Derived d;

Function (d);

return 0;
}


When I was finding that even simple
base_pointer_to_base_object->VirtualFunction ()

calls were not being inlined, I simplified the question to functions being called by pointers in general.

Is there any chance for the compiler to inline the above call to VirtualFunction within Function, as called?

[Edited by - Ro_Akira on June 6, 2006 10:40:13 AM]

Share this post


Link to post
Share on other sites
A compiler never ever has to inline. A compiler is allowed to inline in those cases.

Because many compilers suck at inlining function pointers, functors are often a useful tool.


struct myfunctor {
int operator()() const { printf("I ran my functor!\n"); return 1200; };
};

int main() {
myfunctor const func;
k += func();
k += myfunctor()();
};


The above code tends to beat the compiler over the head with the "inline this thing!". Sadly, it can require some coding gymnastics.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ro_Akira
Unless Hélas has a meaning of 'Opposite of ' or similar, these two arguments appear to be in conflict.


"Hélas" is accurate (French, I believe), but uncommon in English, and therefore comes off as incorrect spelling. I suggest converting to the more modern day English form "alas", which is the equivalent of "unfortunately" (an expression of regret).

How's that for an off-topic post? :)

Share this post


Link to post
Share on other sites
Quote:
A compiler never ever has to inline. A compiler is allowed to inline in those cases.

Agreed. It's dead handy though when a function can be resolved down to an inlined constant for example, and can prune away whole branches of code.
In addition I'd like anyone to suggest a possible reason, apart from not having to, that MSVC++ appeared to fail to fully inline the LocalPointer mentioned earlier.

Forgive me NotAYakk, but would this be a use of functors closer to that of function pointers and virtual functions given earlier:

struct Functor
{
virtual int operator() () const = 0;
};

struct MyFunctor : public Functor
{
int operator() () const { cout << "I ran my functor!" << endl; return 1800; }
};

struct YourFunctor : public Functor
{
int operator() () const { cout << "I ran your functor!" << endl; return 1700; }
};

int UseFunctor (const Functor& f)
{
return f ();
}



The result doesn't seem to be inlining:

MyFunctor my;
YourFunctor your;
k += UseFunctor (my);
0040134C lea ecx,[esp+0Ch]
00401350 lea esi,[eax+eax+1]
00401354 mov dword ptr [esp+0Ch],offset MyFunctor::`vftable' (403210h)
0040135C mov dword ptr [esp+8],offset YourFunctor::`vftable' (403218h)
00401364 call dword ptr [MyFunctor::`vftable' (403210h)]
0040136A add esi,eax
k += UseFunctor (your);
0040136C mov eax,dword ptr [esp+8]
00401370 mov edx,dword ptr [eax]
00401372 lea ecx,[esp+8]
00401376 call edx

Share this post


Link to post
Share on other sites
Virtual functors are analagous to function pointers, yes.

The typical use of functors as a replacement for function pointers, but allowing inlining, is you template the code that uses the functor.


template<typename functor>
void do_something_to_data( data d, functor const& func ) {
func(d);
}


Now, the above code works on anything with an operator(), be it a function pointer, a functor, or a virtual functor.

If you use a non-virtual functor, you end up with the code being inlined in effectively every compiler.

This is the method that the STL algorithm functions use, and using a non-virtual functor makes your code easy for the compiler to inline.

Quote:
In addition I'd like anyone to suggest a possible reason, apart from not having to, that MSVC++ appeared to fail to fully inline the LocalPointer mentioned earlier.


Probably because MSVC doesn't trust const as much as it is allowed to. :)

Out of curiosity, does:
static SimpleFunctionPointerType const SimpleFunctionGlobalPointer (&SimpleFunction);

make any difference? (doubt it, but I am curious).

I wonder why C++ doesn't have a "compile_time" keyword (incidating that this value can be determined at compile_time, or the function can be evaluated at compile_time if all the arguments are compile_time.)

Share this post


Link to post
Share on other sites
Quote:
The typical use of functors as a replacement for function pointers, but allowing inlining, is you template the code that uses the functor.

Ah, that's cheating ;) Seriously though, templates are great for compile time evaluation for sure. I'd argue though that they're not always a drop in replacement. Especially if some of the calls really can't be determined until run-time.

Quote:
Out of curiosity, does:
static SimpleFunctionPointerType const SimpleFunctionGlobalPointer (&SimpleFunction);

make any difference? (doubt it, but I am curious).

I'm afraid not.

Quote:
I wonder why C++ doesn't have a "compile_time" keyword (incidating that this value can be determined at compile_time, or the function can be evaluated at compile_time if all the arguments are compile_time.)

I'd argue agaist the introduction of such a thing. It's more work for me :P. The compiler is in a much better position to resolve things to constants I think. I much prefer the compiler finding out all the things that can be resolved, rather than me thinking if there's about 2000 instances that I've missed.
Edit: Unless you mean that you have functions that can be used in templates and what not (Compile time functions in LISP?). One can use a static member in a template (not compiled):

template<int a>
struct MyClass
{
static const int static_a = a;
};

template<int b>
struct OtherClass
{
OtherClass (const MyClass<b>& other) {}
};

template<typename T>
void Use (T& var)
{
OtherClass<T::static_a> temp (var);
temp.DoStuff ();
}

int main ()
{
MyClass var;
Use (var);
}



Even inlining is best left to the compiler I think. With the Link Time Code Generation option in MSVC++ 2005 for example, it can do things like inline Getters and Setters, or any other suitable function, that you never bothered to move out of your .cpp file! I think that's pretty cool. That's part of why I'm surprised to find it falls flat on it's face when presented with some of the examples given in this thread :/

Even if all the inlining and resolving took 30 minutes, for a final release build I'd take it.

Thanks for all the valuable insight everyone! Feel free to add/clarify more, for example the Derived example I gave :)

Share this post


Link to post
Share on other sites
Apologies on the confusion on my part NotAYakk.

I've read that document, and for the most part, I like what I see. I ran into the
static const int my_int = numeric_limits<int>::max ();

problem myself just the other day.

I hope it doens't make compiler vendors lazy, and make them think that any possible constant expressions will be declared as such :/

Share this post


Link to post
Share on other sites
I want to be able to say "I intend this function to be compile_time calculatable. Please scream and yell at me if it isn't."

Sadly, the paper seems to want to restrict what class of functions can be compile_time to a huge extent. Possibly because they want to be nice to compiler writers. :)

You can't even implement a compile_time factorial calculator using their system. No loops or recursion is allowed. :(

Share this post


Link to post
Share on other sites
Quote:
Original post by NotAYakk
You can't even implement a compile_time factorial calculator using their system. No loops or recursion is allowed. :(


Well, you can, only it would be a class, not a function, but I understand what you are saying.


template<int N>
class Factorial {
public:
enum { value = N * Factorial<N-1>::value };
};

class Factorial<1> {
public:
enum { value = 1 };
};


Share this post


Link to post
Share on other sites
Quote:
Original post by mfawcett
Quote:
Original post by NotAYakk
You can't even implement a compile_time factorial calculator using their system. No loops or recursion is allowed. :(


Well, you can, only it would be a class, not a function, but I understand what you are saying.

*** Source Snippet Removed ***


That's using the template system.

The template system is sufficiently powerful(tm), it just has annoying syntax to get at the sufficiently powerful capabilities, which sucks.

I want to write clean C style code that has no side effects, feed it compile-time determined inputs, and have it generate compile-time determined outputs.

For example:
static const int my_int = numeric_limits<int>::max ();

you can "fix" this by using enums for max:
enum{ my_int = numeric_limits<int>::max };

assuming that numeric_limits was written "correctly".

But that isn't what I want.

I want:


compile_time int max( int, int ) { return a>b?a:b; }
compile_time int min( int a, int b) { return a<b?a:b; }
compile_time int bound( int bottom, int value, int top ) { return max(bottom, min(value, top) ); }
compile_time int factorial( int n ) { if (n==0) return 1; return n*factorial(n-1); }
compile_time double sin( double radians ); // in a .cpp file somewhere
compile_time double cos( double radians ); // in a .cpp file somewhere
compile_time double tan( double radians ); // in a .cpp file somewhere
compile_time double sqrt( double src ); // in a .cpp file somewhere


at the very least. On top of this, it would be nice to have:


void do_stuff( compile_time int n );


which forces the caller to pass a compile_time value to the function. Such a parameter can be used internally like any other compile-time-determined value.

Of course, I ain't respecting how hard it is to write a compiler when I ask for these sorts of things. :)

Share this post


Link to post
Share on other sites
They're some nice ideas I think.

Even though this thread started with the question of optimizing potentially run-time variant functions, which are not really (const pointers to functions), and specifically the ability to inline them as a result, I guess the basic idea is the ability to resolve everything that can be resolved at compile time.

I find it interesting that there's still room for optimization improvements from compilers (well VC++ 2005) even within the bounds of the current standard. I guess concentrating on SSE2 support and similar, results in more noticeable gains for some programs, but still...

Quote:

That's using the template system.

The template system is sufficiently powerful(tm), it just has annoying syntax to get at the sufficiently powerful capabilities, which sucks.

I want to write clean C style code that has no side effects, feed it compile-time determined inputs, and have it generate compile-time determined outputs.
.
.
compile_time int max( int, int ) { return a>b?a:b; }
.
.

You've got my vote that the compile_time idea is orders of magnitude better than using templates for that sort of thing!


template<typename T>;
T max (const T& a, const T& b) compile_time { return a>b?a:b; }

I guess you were just giving quick examples. How about the above though? I put compile_time is where it is for two reasons:

1. This is where the const modifier appears for functions
2. Much like member functions may be overloaded by their constness, so can max be overloaded by it's compile_time-ness

I suppose you placed compile_time at the beginning to indicate that the return time is compile_time, and thus the function and it's parameters are implicitly compile_time also. I was just thinking that one can't overload on return types, thus every use of max would need compile_time parameters. Necessitating a max_not_compile_time function perhaps. Details, details though :P

[Edited by - Ro_Akira on June 8, 2006 3:44:50 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by NotAYakk
I want:


compile_time int max( int, int ) { return a>b?a:b; }
compile_time int min( int a, int b) { return a<b?a:b; }
compile_time int bound( int bottom, int value, int top ) { return max(bottom, min(value, top) ); }


If the constexpr proposal is accepted, these will be possible in C++0x.

Quote:
compile_time int factorial( int n ) { if (n==0) return 1; return n*factorial(n-1); }

Should recursion be eventually allowed in a constexpr function, this could be written as:

constexpr int factorial(unsigned int n) { return n ? n * factorial(n-1) : 1; }

The requirement that a constexpr function contain a single expression is valid; we don't want to force compiler vendors to implement a whole working C++ interpreter inside the compiler! Anyway, loops would be problematic since they are stateful constructs, and besides, detecting infinite loops would be tricky if not impossible (cf. the Halting Problem).

Quote:


compile_time double sin( double radians ); // in a .cpp file somewhere
compile_time double cos( double radians ); // in a .cpp file somewhere
compile_time double tan( double radians ); // in a .cpp file somewhere
compile_time double sqrt( double src ); // in a .cpp file somewhere


These would be impossible given the C++ compilation model. The compiler can't possibly compile-time evaluate a function whose implementation is "in a .cpp file somewhere".

Quote:

On top of this, it would be nice to have:

void do_stuff( compile_time int n );

Indeed. I wonder why Stroustrup&Reis don't mention that possibility in their proposal. It would allow building nicer interfaces on top of template metafunctions, for example:

template <unsigned int i>
struct factorial_t { ... }

constexpr unsigned int factorial(constexpr unsigned int n) { return factorial_t<n>::value; }

Share this post


Link to post
Share on other sites
Quote:
Original post by Sharlin
Quote:
Original post by NotAYakk
I want:


compile_time int max( int, int ) { return a>b?a:b; }
compile_time int min( int a, int b) { return a<b?a:b; }
compile_time int bound( int bottom, int value, int top ) { return max(bottom, min(value, top) ); }


If the constexpr proposal is accepted, these will be possible in C++0x.


*nod*.

Quote:
Quote:
compile_time int factorial( int n ) { if (n==0) return 1; return n*factorial(n-1); }

Should recursion be eventually allowed in a constexpr function, this could be written as:

constexpr int factorial(unsigned int n) { return n ? n * factorial(n-1) : 1; }

The requirement that a constexpr function contain a single expression is valid; we don't want to force compiler vendors to implement a whole working C++ interpreter inside the compiler!


Bah. They have a C compiler.

Simply disallow from the C language:
1> new/delete
2> reinterpret_cast, static_cast and (C) casts that cause the same effect
3> Pointer arithmetic.
4> other stuff(tm) (which, I'll admit, may be far harder than I could imagine).

No function or variable that isn't compile_time can be called from within a compile_time function.

Compile the compile_time code. Run it in a seperate memory space. Get the output of the result. Substitute the result for the function call.

Quote:
Anyway, loops would be problematic since they are stateful constructs,


I don't care about the intermediate state -- I care about the result of the function.

In effect, I want compile_time to mean, in essence:
"Compile and run a program, get the result of the program, and put it here."
with the caviat:
"Weaken the language just enough so that compiling and running a program doesn't let someone format my C: drive. They should be restricted by the language to side-effect-free actions."

Now, I can do this currently. But I want to do it inside the language.

In effect, I want a full strength functional sub-set of the C++ language in C++ syntax that can be executed at compile_time, but can also be executed at run_time.

Quote:
and besides, detecting infinite loops would be tricky if not impossible (cf. the Halting Problem).


Yes, you will be able to write a program whose compilation never halts.

You can do this already using templates. I don't see the fundamental problem here. Programmers will be able to write code that the compiler will spend a bit of time evaluating, then says "Suspected compile_time infinite loop -- execution time too long, or memory use too great. Increase compile_time execution time and memory limits to avoid this."

Quote:
Quote:


compile_time double sin( double radians ); // in a .cpp file somewhere
compile_time double cos( double radians ); // in a .cpp file somewhere
compile_time double tan( double radians ); // in a .cpp file somewhere
compile_time double sqrt( double src ); // in a .cpp file somewhere


These would be impossible given the C++ compilation model. The compiler can't possibly compile-time evaluate a function whose implementation is "in a .cpp file somewhere".


It could in theory let the linker evaluate the compile_time functions. I will admit what I'm asking for is a cruel thing to ask of a compiler writer.

Stroustrup&Reis's solution is probably better for a first generation.

Quote:
Quote:

On top of this, it would be nice to have:

void do_stuff( compile_time int n );

Indeed. I wonder why Stroustrup&Reis don't mention that possibility in their proposal. It would allow building nicer interfaces on top of template metafunctions, for example:

template <unsigned int i>
struct factorial_t { ... }

constexpr unsigned int factorial(constexpr unsigned int n) { return factorial_t<n>::value; }


It does make their proposal more complex. I suspect Stroustrup&Reis wanted a proposal that was easy to implement and required the least amount of changes.

In my case, I want an implementation that gives me new, useful, tools.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this