Function pointer vs conditional branch

[Edward Rutherford]

Hello

As a general rule-of-thumb: Are function pointers more efficient than if
statements, if the same path will be taken throughout the course of the
program?

E.g. If I was going to repeatedly render an image in one of three ways,
and the method of rendering it gets selected at the beginning of
execution: Would it be more efficient to use a function pointer instead
of an if statement?

Thanks.

 

[Kaz Kylheku]

Hello

As a general rule-of-thumb: Are function pointers more efficient than if
statements, if the same path will be taken throughout the course of the
program?

E.g. If I was going to repeatedly render an image in one of three ways,
and the method of rendering it gets selected at the beginning of
execution: Would it be more efficient to use a function pointer instead
of an if statement?

An if statement selects a body of code which is still within the same lexical
scope, whereas a function call branches into a different scope. So the program
organization perspective is the most important. Obviously, if you have to
select from among multiple execution branches, which all require access to the
same set of local variables, you cannot use a function call (unless you go out
of your way to emulate lexical closures).

Are you asking which of these is better:

if (condition1) {
func1(...);
} else if (condition2) {
func2(...);
} else {
func3(...);
}

versus:

if (condition1) {
fptr = func1;
} else if (condition2) {
fptr = func2;
} else {
fptr = func3;
}

(*fptr)(...);

Stated in this way, the rewrite is unlikely to be fruitful in obtaining a
performance improvement, and may even be worse.

To obtain the benefit of using the function pointer, you have to turn your
attention into how that pointer is obtained.

Perhaps the conditions are numeric and can be put into a static dispatch
table, function pointers.

However, note that compilers do these kinds of optimizations. Code like:

switch (x) {
case 0:
func0(...);
break;
case 1:
func1(...);
break;
...
case N:
func1(...);
break;
default:
foo();
}

may well be compiled into an indirect jump through a hidden table indexed by N:

if (x >= 0 && x <= N)
hidden_table[x](...)
else
foo();

so unless you verify that the compiler isn't doing it, it wouldn't be worth it
to do it manually (other than for improving the code).

Such a table dispatch is almost certainly going to be faster than a naive
compile of the switch, because on modern CPU's it's faster to fetch some data
from a table and branch once than to go through two branches (as a rule of
thumb). Branches disrupt pipelines, requiring techniques like scheduling
instructions in branch delay slots, and branch prediction.

Another question is, how often does the three-way decision have to be
re-evaluated? Is it always different for each rendering job?

If the same choice is applied to multiple rendering jobs, it may help to
represent that by a context structure which has the function pointer in it,
already initialized to point to the correct function whenever the variables
are updated which influence the decision. There is no decision to make at
render time: just retrieve the pointer and call it:

render_context->render(render_context, ...);

How complicated are the conditions being evaluated to make the three-way
switch? Does it boil down to dispatch based on a numeric code, or something
else?

What is more frequently occuring: rendering jobs, or changes to the conditions
that influence the three-way choice?

 

[Ian Collins]

Hello

As a general rule-of-thumb: Are function pointers more efficient than if
statements, if the same path will be taken throughout the course of the
program?

E.g. If I was going to repeatedly render an image in one of three ways,
and the method of rendering it gets selected at the beginning of
execution: Would it be more efficient to use a function pointer instead
of an if statement?

There isn't a general rule-of-thumb answer, there ate too many variables
to consider.

 

[Eric Sosman]

Hello

As a general rule-of-thumb: Are function pointers more efficient than if
statements, if the same path will be taken throughout the course of the
program?

"I have it on the best authority." -- Arthur

E.g. If I was going to repeatedly render an image in one of three ways,
and the method of rendering it gets selected at the beginning of
execution: Would it be more efficient to use a function pointer instead
of an if statement?

Mu.

Here's a counter-question: Does it matter? Estimate, pray,
the amount of time spent dispatching to one rendering function or
another versus the amount of time spent in that function actually
doing the rendering. Let's see: A smallish 640x480 image has 50K
pixels, depending on image characteristics that's anywhere from
50K to 200K values to compute, 50K pixel-to-pixel navigations to
figure out ("Have I hit the end of a row?"), ... And you're
worried about the once-per-rendering cost of deciding which
function to call?

I've mentioned an old friend's metaphor more than once, but
I think it applies rather strongly here: You're cleaning the bottle
caps and cigarette butts off the beach, to make the sand nice and
neat around the whale carcases.

 

[Kaz Kylheku]

Here's a counter-question: Does it matter? Estimate, pray,
the amount of time spent dispatching to one rendering function or
another versus the amount of time spent in that function actually
doing the rendering. Let's see: A smallish 640x480 image has 50K
pixels, depending on image characteristics that's anywhere from
50K to 200K values to compute, 50K pixel-to-pixel navigations to
figure out ("Have I hit the end of a row?"), ... And you're
worried about the once-per-rendering cost of deciding which
function to call?

My reaction (hitherto unwritten) was that he must be just handing the images
off to some very fast hardware to care about the dispatch speed.

I've mentioned an old friend's metaphor more than once, but
I think it applies rather strongly here: You're cleaning the bottle
caps and cigarette butts off the beach, to make the sand nice and
neat around the whale carcases.

That little beauty doesn't apply that well; if you keep using it, you will soon
wear a hole right through!

Here, we may have a case of borrowing a motorcycle for the last 50 meters
of a marathon.

(Well, that might be attractive, depending on what shape you're in, but
it won't make a big difference to your time.)

 

[BartC]

Hello

As a general rule-of-thumb: Are function pointers more efficient than if
statements, if the same path will be taken throughout the course of the
program?

E.g. If I was going to repeatedly render an image in one of three ways,
and the method of rendering it gets selected at the beginning of
execution: Would it be more efficient to use a function pointer instead
of an if statement?

How many times will that if statement or function dispatch get executed? For
example, once per image, once per row, or once per pixel?

 

[Eric Sosman]

[...]
I've mentioned an old friend's metaphor more than once, but
I think it applies rather strongly here: You're cleaning the bottle
caps and cigarette butts off the beach, to make the sand nice and
neat around the whale carcases.

That little beauty doesn't apply that well; if you keep using it, you will soon
wear a hole right through!

I've also used one about waxing your car to improve fuel economy:
Does it help by making the car slipperier, or hurt by increasing the
weight, and how do these effects compare to those of the underinflated
tires, the empty boat trailer dragging along behind, and the driver's
lamentable fondness for jackrabbit starts?

Here, we may have a case of borrowing a motorcycle for the last 50 meters
of a marathon.

Nice! I'll add it to the repertoire, if you don't mind/

 

[Gene]

Hello

As a general rule-of-thumb: Are function pointers more efficient than if
statements, if the same path will be taken throughout the course of the
program?

E.g. If I was going to repeatedly render an image in one of three ways,
and the method of rendering it gets selected at the beginning of
execution: Would it be more efficient to use a function pointer instead
of an if statement?

Rendering an image will involve billions of instructions. Branching
to the start of the rendering algorithm is one or two instructions.
The choice doesn't matter.

Now if the branch is in the inner loop being executed once per pixel,
it _might_ make a small, very processor-dependent difference. Modern
processors often have some kind of branch prediction or split
execution path to optimize pipeline behavior for conditional branch
instructions. These mechanisms don't normally work for function
pointers. So for a 2- or 3-way branch, you'd probably want to first
try the natural if...then...else. As always, profile and tweak only
if you're sure the simplest coding isn't fast enough.

 

[Kaz Kylheku]

[...]
I've mentioned an old friend's metaphor more than once, but
I think it applies rather strongly here: You're cleaning the bottle
caps and cigarette butts off the beach, to make the sand nice and
neat around the whale carcases.

That little beauty doesn't apply that well; if you keep using it, you will soon
wear a hole right through!

I've also used one about waxing your car to improve fuel economy:
Does it help by making the car slipperier, or hurt by increasing the
weight, and how do these effects compare to those of the underinflated
tires, the empty boat trailer dragging along behind, and the driver's
lamentable fondness for jackrabbit starts?

Washing and waxing the car smoothes out the engine idle, lowers the exhaust
rattle by 15 dB and causes the clutch to engage like it's leather-padded.

 

[88888 Dihedral]

Edward Rutherfordæ–¼ 2012å¹´1月5日星期四UTC+8上åˆ6時20分18秒寫é“：

Hello

As a general rule-of-thumb: Are function pointers more efficient than if
statements, if the same path will be taken throughout the course of the
program?

E.g. If I was going to repeatedly render an image in one of three ways,
and the method of rendering it gets selected at the beginning of
execution: Would it be more efficient to use a function pointer instead
of an if statement?

Thanks.

I'll give an example to illustrate my understanding of the questions in your
post in pseudo code.

//Filter all gray levels equual or above 170 to be 255 and those bellows to 0.

For each pixel in the image:
if gray>=170 store 255 ;
else store 0;

For each pixel in the image:
store map[gray];

Which will work better?

 

[88888 Dihedral]

Edward Rutherfordæ–¼ 2012å¹´1月5日星期四UTC+8上åˆ6時20分18秒寫é“：

Hello

As a general rule-of-thumb: Are function pointers more efficient than if
statements, if the same path will be taken throughout the course of the
program?

E.g. If I was going to repeatedly render an image in one of three ways,
and the method of rendering it gets selected at the beginning of
execution: Would it be more efficient to use a function pointer instead
of an if statement?

Thanks.

I'll give an example in pseudo code here for problems in your post.

How to turn a gray level image into a binary one?

The rule: given a Th=170, if the gray level>=Th just make it 255 else 0

//Method1:
for each pixel:
if gray>=Th store 255; else store 0;

//Method2:
for(i=0;i<Th;i++) map=0;
for(; i<256;i++) map=255;
for each pixel in the image:
store map[gay];

Both methods will work.

 

[Joe Pfeiffer]

Hello

As a general rule-of-thumb: Are function pointers more efficient than if
statements, if the same path will be taken throughout the course of the
program?

E.g. If I was going to repeatedly render an image in one of three ways,
and the method of rendering it gets selected at the beginning of
execution: Would it be more efficient to use a function pointer instead
of an if statement?

I can't imagine it would make any noticeable difference. The work in
rendering the image will overwhelm any difference in choosing which
function to call so massively that the choice won't even show up in the
noise.

Choose the one that better fits the overall structure of the program and
your own coding style.

 

[Nobody]

As a general rule-of-thumb: Are function pointers more efficient than if
statements, if the same path will be taken throughout the course of the
program?

I suspect that the conditionals will be more efficient in most cases.

A function pointer tends to act as a barrier to optimisation, as the
compiler will normally have to assume that:

a) the pointer can point to any function of the correct type, and
b) the function itself can be called from anywhere.

Even if everything (the functions and the pointer) is limited to a single
translation unit (i.e. none of them have external linkage), the compiler
is unlikely to take advantage of this (at least, I've never seen a
compiler do this).

OTOH, when you have code in a particular context, the compiler can
optimise the code for that context.

 

[Dr Nick]

I suspect that the conditionals will be more efficient in most cases.

I suspect we don't know enough. I'm sure this is the case if it's a
choice between doing a simple "if x" do this within a 20 iterations
loop, or do that on one hand and doing the same thing once before the
loop to set a function pointer, the if will win.

If it's a nest of 50 if statements to pick one of 17 different
operations, and some of the ifs involve calculating the same thing each
time, and there are billions of iterations of the loop, the function
pointer might win.

Then, of course, you pull the nest of ifs out of the loop, case it
inside the loop and let the compiler build a table if it thinks it's the
best thing.

The if is almost certainly easier to read, and that's a form of
efficiency.

 

[BGB]

Hello

As a general rule-of-thumb: Are function pointers more efficient than if
statements, if the same path will be taken throughout the course of the
program?

if placed head-to-head, the 'if' will likely be significantly faster.
this is because the 'if' is a simple conditional jump, and the CPU can
typically branch-predict it.

an indirect function call involves call/return magic
(creating/destroying stack frames, passing any arguments, ...), and also
can't generally be branch-predicted (so, one gets a pipeline spill every
time the call is made).


the function pointer can win though if it can save going through a bunch
of winding logic (say, the "choosing what to do" part is fairly
expensive, and the function pointer can get more directly to the goal).

an example of the above:
an x86 interpreter, where decoding instructions is fairly expensive;
if one caches decoded instructions with a function pointer pointing to
the logic for the operation, it can be faster than a small mountain of
'if' and 'switch' statements.

another case I had found was when dealing with dynamically-typed method
dispatch, where:
the arguments could be passed to the called function in one of several
ways (as ordinary function arguments, as a packed array, as an array of
dynamically-typed references, as a list, ...);
multiple layers of abstraction were involved (the logic wound through
about 4 different libraries);
there were multiple types of ways the method could be dispatched (native
vs passed off to an interpreter vs ...);
also, types were based on strings, so this would involve looking up the
type for an object a number of times, and a bunch of calls to "strcmp()";
....

caching a function pointer to the specific dispatch logic in the vtable
(only for certain common cases) was able to cut a 500ns operation down
to more about 15ns (with a 2.8GHz AMD CPU).


typically it only really matters if this sort of thing is off in an
inner-loop somewhere.

a big expensive operation, if done rarely, will often cost hardly anything.

E.g. If I was going to repeatedly render an image in one of three ways,
and the method of rendering it gets selected at the beginning of
execution: Would it be more efficient to use a function pointer instead
of an if statement?

as others have noted, in such a scenario is shouldn't likely matter.


if it is a long inner loop, and something like:
for(...)
{
if(X) { A... }
else if(Y) { B... }
else { C... }
}

a slight speedup may be gained from something like:

if(X)
{
for(...) { A... }
}
else if(Y)
{
for(...) { B... }
}
else
{
for(...) { C... }
}

dropping a function pointer call in the middle of a loop could very well
cost more, and it is very well possible that the later form could be
slower (say, if the checks are very simple and the CPU's
branch-predictor does its thing).

 

[Kaz Kylheku]

an indirect function call involves call/return magic
(creating/destroying stack frames, passing any arguments, ...), and also
can't generally be branch-predicted

You can safely predict that an indirect function call is always taken,
since it is unconditional.

 

[BartC]

On 1/4/2012 4:20 PM, Edward Rutherford wrote:

as others have noted, in such a scenario is shouldn't likely matter.

The OP hasn't clarified exactly what he means. Perhaps selecting the render
mode simply means it is known at the start of the process.

That mode might still need checking on a per-line, per-pixel, or per-byte
basis, or maybe it's per primitive.

In fact I think it is likely the OP knows perfectly well that a single
if-statement or indirect call per render (even if it's per frame, and there
are many frames per second), has no significance, but it is not practical to
have several independent lots of render subsystems, which only differ in one
small rendering detail. But I might be wrong...

 

[Willem]

Kaz Kylheku wrote:
)> an indirect function call involves call/return magic
)> (creating/destroying stack frames, passing any arguments, ...), and also
)> can't generally be branch-predicted
)
) You can safely predict that an indirect function call is always taken,
) since it is unconditional.

But you can't predict *where* it will jump, which is the point.

The purpose of branch prediction is to be able to pipeline the instructions
after the branch.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Stephen Sprunk]

Kaz Kylheku wrote:
)> an indirect function call involves call/return magic
)> (creating/destroying stack frames, passing any arguments, ...), and also
)> can't generally be branch-predicted
)
) You can safely predict that an indirect function call is always taken,
) since it is unconditional.

But you can't predict *where* it will jump, which is the point.

The purpose of branch prediction is to be able to pipeline the instructions
after the branch.

That's the point of the BTB in modern CPUs: to predict the target of
indirect branches. How successful they are, of course, depends on the
program; for many common scenarios (eg. virtual method calls), they work
very well, though there are some where they're known to be completely
ineffective.

S

 

[Kaz Kylheku]

Kaz Kylheku wrote:
)> an indirect function call involves call/return magic
)> (creating/destroying stack frames, passing any arguments, ...), and also
)> can't generally be branch-predicted
)
) You can safely predict that an indirect function call is always taken,
) since it is unconditional.

But you can't predict *where* it will jump, which is the point.

really?

load r1, <whatever>
add r2, r3
jmp [r1]

We already know where the jmp [r1] will go as soon as r1 is loaded, and can start
prefetching instructions as soon as the value of r1 is stable.

The purpose of branch prediction is to be able to pipeline the instructions
after the branch.

That is called pipeline prefetch. Branch prediction is an educated guess
whether or not a conditional jump will be taken, or fall through.