Function pointers: performance penalty?

[Rui Maciel]

Perhaps. What do your measurements tell you?

Isn't this issue deterministic? Why should anyone employ empirical methods to try to understand the behavior
of deterministic systems? And why do you believe that measurements would enable you to arrive at a meaningful
conclusion?


Rui Maciel

 

[Rui Maciel]

And for much the same reason, asking people what the performance penalty
is won't do you much better.

Programming languages, particularly those defined by international standards such as C, are implemented
according to specific rules. Even the aspects which are left undefined are still implemented from a concrete
set of instructions. Therefore, if you are dealing with a deterministic system then things happen for a very
good, tangible and meticulously defined reason. They don't just happen due to unexplainable whims.


Rui Maciel

 

[bartc]

Nope, function pointers are faster.

If that was the case then all function calls would be via pointers, with the
compiler pointerfying direct function calls.

But oddly I haven't noticed that when I look at asm output.

 

[Nick Keighley]

your posts should make sense standalone

[Subject: Funtion pointers: performance penalty?]

Seebs wrote:

Programming languages, particularly those defined by international standards
such as C, are implemented according to specific rules. Even the aspects which
are left undefined are still implemented from a concrete set of instructions.
Therefore, if you are dealing with a deterministic system then things happen
for a very good, tangible and meticulously defined reason. They don't just happen
due to unexplainable whims.

so what? The fact is the penalty will vary from harware architecture
to hardware
architecture and even compiler to compiler so in general the question
cannot be
answered.

Other posters seem to be suggesting that once caching and pipeling are
added to the mix then the behaviour of "deterministic" processors can
be quite
difficult to "determine"

 

[Tim Rentsch]

[snip] The
indirect call and direct call are not intrinsically different; ultimately,
a "direct" call is still a call through a pointer anyway.

That's true in the abstract machine, but for actual hardware
the difference can be substantial (eg, speed ratio of more
than a factor of 10). So conceptual similarity and practical
similarly may not be the same here, depending on what
processor architecture and implementation is being used.

 

[James Kuyper]

Programming languages, particularly those defined by international standards such as C, are implemented
according to specific rules. Even the aspects which are left undefined are still implemented from a concrete
set of instructions. ...

Yes, but it can be a very different set of of instructions on different
platforms, and the C standard itself tells you nothing about those
instruction sets.

... Therefore, if you are dealing with a deterministic system then things happen for a very
good, tangible and meticulously defined reason. They don't just happen due to unexplainable whims.

"very good ... reason"? Implementors often make decisions for bad
reasons, just like anyone else. "Meticulously defined"? That depends
upon how good the software development process is that the implementor
uses; as with any other kind of software, there are some C implementors
who use a very poor software development process. No "unexplainable
whims"? These systems are designed by human beings - unexplainable whims
are routine occurrences.

None of that is relevant, however. The point is not whether the relevant
reasons for a decision are "very good", or "meticulously defined",
rather than "unexplained whims". What matters is that different
decisions are made even when the same implementor produces a new version
of a compiler for the same platform targeted to the same market; when
you add in the variety of choices made by different implementors on
different platforms for compilers targeted at different markets, the
variety is nearly endless. Paying too close attention to the details of
performance is pointless for software that is intended to be portable.

You have not yet identified which alternative approach you'd like
function pointers to be compared with. However, once that's decided,
issues like "is it better to use function pointers or ... (alternative)
", are more appropriately resolved by considering which approach makes
the code easier to understand, than by worrying about inherently
platform-specific details such as efficiency.

 

[James Kuyper]

Compared to what alternative? In any situation where use of function
pointers is appropriate, the alternative is more complicated than simply
calling the function directly. Example:

fptr = (condition ? func1 : func2);

x = fptr(y);

Could be changed to

x = (condition ? func1(y) : func2(y));

or
x = bigfunc(condition, y);

where bigfunc(true, y) behaves just like func1(y), while bigfunc(false,
y) behaves just like func2(y). Note that either of these approaches
requires storage of the condition that controls the choice, rather than
storage of a function pointer.

There's many other alternatives, as well. Which one are you thinking of?

Isn't this issue deterministic?

No, not in general. It can become deterministic if you're restricting
your attention to one particular machine, and one particular compiler,
running in single-user mode so that the performance does not depend upon
any other programs that might be running at the same time. Also, your
program must not be engaged in any real-time activities such as waiting
on a device, which can have side-effects that influence the performance
even of code that is completely unrelated to the the wait.

... Why should anyone employ empirical methods to try to understand the behavior
of deterministic systems?

Even if you do have a deterministic system, figuring out the performance
penalty by deriving it from the rules governing that system can be
prohibitively difficult and error-prone. Empirical testing is often
simpler and more robust.

In any event, determinism is not the relevant problem; it's the fact
that the answer will, in general, be different on different
deterministic systems.

 

[bartc]

Then look at the machine code. (Seriously.)

What's the difference between that and assembler code? Are you suggesting
that assembler code that looks like this:

call userfn

is silently converted to the following machine code equivalent:

call [userfnaddr]
...
userfnaddr: dd userfn

or perhaps to:

load Rn,userfn
...
call [Rn] ?

 

[James Kuyper]

If that was the case then all function calls would be via pointers, with
the compiler pointerfying direct function calls.

As far as the C standard is concerned, all function calls are via
pointer values: "The expression that denotes the called function shall
have type pointer to function". (6.5.2.2p1)

"Except when it is the operand of the sizeof operator or the unary &
operator, a function designator with type ‘‘function returning type’’ is
converted to an expression that has type ‘‘pointer to function returning
type’’." (6.3.2.1p4)

A compiler that uses any other method of calling the function would be,
"directifying" pointer function calls.

But oddly I haven't noticed that when I look at asm output.

The three assembly languages I'm familiar with all perform function
calls by loading a special register with the memory address (a pointer
value) of the entry point to the function to be called. I'm curious -
how does the non-pointer way of implementing function calls work?

 

[Seebs]

Isn't this issue deterministic?

No.

(Not only is there not a single general answer which is determined by
something, I think there's plenty of real-world cases where the performance
penalty or advantage on a given target is not deterministic for a specific
program, because there can be other programs running which impose
non-deterministic variance on the environment.)

-s

 

[Seebs]

Programming languages, particularly those defined by international
standards such as C, are implemented according to specific rules.

Performance is, as the nice people say, "a quality of implementation
issue".

Even the aspects which are left undefined are still implemented
from a concrete set of instructions. Therefore, if you are dealing
with a deterministic system then things happen for a very good,
tangible and meticulously defined reason. They don't just happen
due to unexplainable whims.

If the original poster had asked "using gcc 3.4.4, with the following
compiled-in options and the following command line options, running bare
metal code on a TI OMAP 2430 CPU, what is the performance penalty of
function pointers", it is quite possible that it would be meaningful
to speak of a deterministic answer.

In the general case, there's no answer. It's not even entirely obvious
that there will be a penalty at all.

-s

 

[Seebs]

What's the difference between that and assembler code?

Assembly is, itself, a rather higher-level language than people
often expect.

Are you suggesting
that assembler code that looks like this:

call userfn
[...]

load Rn,userfn
...
call [Rn] ?

Quite possibly.

Modern assemblers often hide a surprising amount of Stuff.

-s

 

[Seebs]

That's true in the abstract machine, but for actual hardware
the difference can be substantial (eg, speed ratio of more
than a factor of 10). So conceptual similarity and practical
similarly may not be the same here, depending on what
processor architecture and implementation is being used.

True.

I guess I'm more looking at the question "is there a definite answer",
and the answer to that is "no, not in general".

-s

 

[bartc]

As far as the C standard is concerned, all function calls are via
pointer values: "The expression that denotes the called function shall
have type pointer to function". (6.5.2.2p1)

"Except when it is the operand of the sizeof operator or the unary &
operator, a function designator with type ‘‘function returning type’’
is converted to an expression that has type ‘‘pointer to function
returning type’’." (6.3.2.1p4)

A compiler that uses any other method of calling the function would
be, "directifying" pointer function calls.


The three assembly languages I'm familiar with all perform function
calls by loading a special register with the memory address (a pointer
value) of the entry point to the function to be called. I'm curious -
how does the non-pointer way of implementing function calls work?

You mean this register is loaded using explicit instructions that a compiler
will generate, or are you just explaining how a conventional call
instruction works, by loading the address of the function into the program
counter?

The direct call method looks like this:

(A) call immediate-function-address (or, sometimes, immediate-offset)

An indirect call looks something like this:

(B) call [address-of-location-containing-address-of-function]

What I'm saying is that if method (B) was always faster than (A), then only
(B) would ever be generated, which sounds unlikely.

A variation of (B) is to have the function address permanently in a
register. This could conceivably be faster than (A), but there aren't enough
registers to treat every function like this.

 

[bartc]

Nope, function pointers are faster.

If that was the case then all function calls would be via
pointers, with the compiler pointerfying direct function calls.

But oddly I haven't noticed that when I look at asm output.

Then look at the machine code. (Seriously.)

What's the difference between that and assembler code? Are you
suggesting that assembler code that looks like this:

call userfn

is silently converted to the following machine code equivalent:

call [userfnaddr]

Are you suggesting that the name of the function is (necessarily)
present in the binary?

No. I said machine code 'equivalent', ie. the mnemonic that might be
associated with an indirect call instruction.

My implication is that assembler code maps pretty much one-to-one with
machine code, so that you normally wouldn't mistake a direct call with an
indirect call (unless you're using Masm then it's anyone's guess what a
particular line might mean).

I've since looked at some disassembled code from my x86 machine and most
calls do seem to be direct (and to avoid misunderstanding, since apparently
assembler source is not to be trusted, they all start with the E8 opcode for
direct call instructions).

 

[bartc]

It's not clear to me what distinction you are making. The obvious way
to call a function is by loading its address into the instruction
pointer register. You seem to be suggesting that there is some other
way. Could you possibly enlighten us?

And it's not clear to me why you are blurring such an obvious distinction,
since that would render the subject of this thread meaningless.

I've already replied on this to James, but to summarise, a direct call might
use an immediate instruction operand, while an indirect call might use an
indirect operand, ie. to be fetched from another location first. Both end up
with the function address in the program counter.

But I've sure you guys are just pretending not to know what I'm on about.

 

[James Kuyper]

You mean this register is loaded using explicit instructions that a
compiler will generate, ...

I said nothing to imply that.

... or are you just explaining how a conventional
call instruction works, by loading the address of the function into the
program counter?

Of course. If it's the only method I'm familiar with after learning
three different assembly languages, you can be reasonably sure that I'm
referring to something fairly conventional.

The direct call method looks like this:

(A) call immediate-function-address (or, sometimes, immediate-offset)

That would, in C terms, be comparable to calling a function through a
function pointer value.

An indirect call looks something like this:

(B) call [address-of-location-containing-address-of-function]

Again, in C terms, that would be comparable to calling a function
through the value stored in a pointer object.

Either way, it's a call by pointer; which is good, since it matches the
way that the C standard describes function calls.

 

[Keith Thompson]

bartc wrote: [...]

The direct call method looks like this:

(A) call immediate-function-address (or, sometimes, immediate-offset)

That would, in C terms, be comparable to calling a function through a
function pointer value.

An indirect call looks something like this:

(B) call [address-of-location-containing-address-of-function]

Again, in C terms, that would be comparable to calling a function
through the value stored in a pointer object.

Either way, it's a call by pointer; which is good, since it matches
the way that the C standard describes function calls.

In general, the generated code for a C function call might use
mechanism X when the identity of the called function is known at
compile time, and mechanism Y when it isn't.

Assumptions: Mechanisms X and Y are distinct, and mechanism X
*cannot* be used unless the identity of the called function is
known at compile time. These assumptions might not be true for
some platforms.

Whatever they look like, whether or not the function's address
is stored in a register at some point, let's call Mechanism X a
"direct call" and Mechanism Y an "indirect call".

Now that we've defined our terms in (I think) a sufficiently
abstract way, the question is: are direct calls more efficient than
indirect calls? And as we've discussed, there's no definitive
answer, though I'd expect direct calls to be faster, or at least
no slower, on most systems. (If indirect calls are faster, the
compiler probably would never generate direct calls.)

And, as others have pointed out, you can't typically replace an
indirect call with a direct call to get better speed; they serve
different purposes.

 

[Nick Keighley]

If you don't use a funtion pointer what will you do instead
and is *that* cheaper?

you never addressed this point.
If you don't use a function pointer what will you use?

 

[Nick Keighley]

if there isn't a 1 -to-1 mapping between assembler and machine code
doesn't that kind of defeat the purpose of assembler? By the time
we're
down this low we want to know what the processor is *really* doing.
(ignoring the fact it is actually JITing the x86 code into some pseudo
RISC stream which it then executes out of order).

Why would you want assembly code that lied to you?

What's the difference between that and assembler code? Are you
suggesting that assembler code that looks like this:
 call userfn
is silently converted to the following machine code equivalent:
 call [userfnaddr]
Are you suggesting that the name of the function is (necessarily)
present in the binary?

I never saw him say that. Going back to the Z80 (the last assembler I
actually
memorised)

call fun -> CD 00 50

CD "is equivalent to" "call"

It's not clear to me what distinction you are making. The obvious way
to call a function is by loading its address into the instruction
pointer register. You seem to be suggesting that there is some other
way. Could you possibly enlighten us?

some machines can't load directly from memory to the rI- well not as
an instruction. So

*f (i); /* I know I don't need the * */

might assemble to something like (RISC-like assembler)

ld r1 i
push r1
ld r1 f
call r1

That isn't anything like as true as it used to be.

doesn't seem like a great step forward