Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #15417 > unrolled thread

Function pointer vs conditional branch

Back to article view | Back to comp.lang.c

Contents

  Function pointer vs conditional branch Edward Rutherford <edward.p.rutherford79@REMOVETHIS.gmail.com> - 2012-01-04 22:20 +0000
    Re: Function pointer vs conditional branch Kaz Kylheku <kaz@kylheku.com> - 2012-01-04 22:46 +0000
    Re: Function pointer vs conditional branch Ian Collins <ian-news@hotmail.com> - 2012-01-05 11:47 +1300
    Re: Function pointer vs conditional branch Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-04 20:15 -0500
      Re: Function pointer vs conditional branch Kaz Kylheku <kaz@kylheku.com> - 2012-01-05 01:25 +0000
        Re: Function pointer vs conditional branch Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-04 20:36 -0500
          Re: Function pointer vs conditional branch Kaz Kylheku <kaz@kylheku.com> - 2012-01-05 06:02 +0000
    Re: Function pointer vs conditional branch "BartC" <bc@freeuk.com> - 2012-01-05 01:25 +0000
    Re: Function pointer vs conditional branch Gene <gene.ressler@gmail.com> - 2012-01-04 17:57 -0800
    Re: Function pointer vs conditional branch gordonb.vj0cm@burditt.org (Gordon Burditt) - 2012-01-04 23:54 -0600
    Re: Function pointer vs conditional branch 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-04 23:25 -0800
    Re: Function pointer vs conditional branch 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-04 23:38 -0800
    Re: Function pointer vs conditional branch Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2012-01-05 13:47 -0700
    Re: Function pointer vs conditional branch Nobody <nobody@nowhere.com> - 2012-01-05 21:29 +0000
      Re: Function pointer vs conditional branch Dr Nick <3-nospam@temporary-address.org.uk> - 2012-01-06 06:44 +0000
    Re: Function pointer vs conditional branch BGB <cr88192@hotmail.com> - 2012-01-06 11:41 -0600
      Re: Function pointer vs conditional branch Kaz Kylheku <kaz@kylheku.com> - 2012-01-06 18:33 +0000
        Re: Function pointer vs conditional branch Willem <willem@toad.stack.nl> - 2012-01-06 21:41 +0000
          Re: Function pointer vs conditional branch Stephen Sprunk <stephen@sprunk.org> - 2012-01-06 16:08 -0600
          Re: Function pointer vs conditional branch Kaz Kylheku <kaz@kylheku.com> - 2012-01-06 22:35 +0000
            Re: Function pointer vs conditional branch BGB <cr88192@hotmail.com> - 2012-01-06 17:00 -0600
              Re: Function pointer vs conditional branch Kaz Kylheku <kaz@kylheku.com> - 2012-01-06 23:44 +0000
            Re: Function pointer vs conditional branch Stephen Sprunk <stephen@sprunk.org> - 2012-01-06 17:08 -0600
              Re: Function pointer vs conditional branch Kaz Kylheku <kaz@kylheku.com> - 2012-01-06 23:49 +0000
                Re: Function pointer vs conditional branch jacob navia <jacob@spamsink.net> - 2012-01-07 00:55 +0100
                  Re: Function pointer vs conditional branch Kaz Kylheku <kaz@kylheku.com> - 2012-01-07 00:07 +0000
          Re: Function pointer vs conditional branch "christian.bau" <christian.bau@cbau.wanadoo.co.uk> - 2012-01-07 06:14 -0800
            Re: Function pointer vs conditional branch "BartC" <bc@freeuk.com> - 2012-01-07 14:44 +0000
              Re: Function pointer vs conditional branch Robert Wessel <robertwessel2@yahoo.com> - 2012-01-07 14:37 -0600
                Re: Function pointer vs conditional branch Kaz Kylheku <kaz@kylheku.com> - 2012-01-07 20:42 +0000
                  Re: Function pointer vs conditional branch Stephen Sprunk <stephen@sprunk.org> - 2012-01-07 16:47 -0600
                    Re: Function pointer vs conditional branch Robert Wessel <robertwessel2@yahoo.com> - 2012-01-08 01:49 -0600
                      Re: Function pointer vs conditional branch Kaz Kylheku <kaz@kylheku.com> - 2012-01-08 08:35 +0000
              Re: Function pointer vs conditional branch Stephen Sprunk <stephen@sprunk.org> - 2012-01-07 17:02 -0600
      Re: Function pointer vs conditional branch "BartC" <bc@freeuk.com> - 2012-01-06 21:29 +0000
        Re: Function pointer vs conditional branch BGB <cr88192@hotmail.com> - 2012-01-06 17:15 -0600
    Re: Function pointer vs conditional branch Michael Angelo Ravera <maravera@prodigy.net> - 2012-01-06 23:00 -0800
    Re: Function pointer vs conditional branch jgk@panix.com (Joe keane) - 2012-01-07 21:04 +0000

Page 1 of 2  [1] 2  Next page →

#15417 — Function pointer vs conditional branch

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.

[toc] | [next] | [standalone]

#15419

On 2012-01-04, Edward Rutherford <edward.p.rutherford79@REMOVETHIS.gmail.com> wrote:
> 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?

[toc] | [prev] | [next] | [standalone]

#15421

On 01/ 5/12 11:20 AM, Edward Rutherford wrote:
> 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.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#15435

On 1/4/2012 5:20 PM, Edward Rutherford wrote:
> 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.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#15437

On 2012-01-05, Eric Sosman <esosman@ieee-dot-org.invalid> wrote:
>      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.)

[toc] | [prev] | [next] | [standalone]

#15440

On 1/4/2012 8:25 PM, Kaz Kylheku wrote:
> On 2012-01-05, Eric Sosman<esosman@ieee-dot-org.invalid>  wrote:
>> [...]
>>       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/

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#15449

On 2012-01-05, Eric Sosman <esosman@ieee-dot-org.invalid> wrote:
> On 1/4/2012 8:25 PM, Kaz Kylheku wrote:
>> On 2012-01-05, Eric Sosman<esosman@ieee-dot-org.invalid>  wrote:
>>> [...]
>>>       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.

[toc] | [prev] | [next] | [standalone]

#15438

"Edward Rutherford" <edward.p.rutherford79@REMOVETHIS.gmail.com> wrote in 
message news:je2jb2$886$1@speranza.aioe.org...
> 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?

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#15444

On Jan 4, 5:20 pm, Edward Rutherford
<edward.p.rutherfor...@REMOVETHIS.gmail.com> wrote:
> 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.

[toc] | [prev] | [next] | [standalone]

#15448

> 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?

Calling via a function pointer involves argument passing, setting
up a new stack frame (yes, we know C doesn't require a hardware
stack), and a call instruction (which on some platforms gets
complicated).

An if statement involves a conditional branch.

I'd say the if statement usually wins, *ESPECIALLY* if you have to
pass a dozen or two local variables (or pointers to them) to get
them in scope of the function you called.

> 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?

If you are going to render an image, who *CARES* how efficient the
calling sequence is?  Worry about the image renderer, which probably
takes a billion clock cycles rather than a few dozen.

If you are trying to travel overseas as fast as possible, do you
worry about polishing your car key to reduce wind resistance as you
insert the key into the lock?  Or do you worry about selecting the
best airline schedule, and going through security in a skimpy bikini
to reduce search time?

[toc] | [prev] | [next] | [standalone]

#15454

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? 
 



 

[toc] | [prev] | [next] | [standalone]

#15455

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[i]=0;
for(; i<256;i++)  map[i]=255; 
for each pixel in the image: 
    store map[gay]; 

Both methods will work. 
 


     

[toc] | [prev] | [next] | [standalone]

#15471

Edward Rutherford <edward.p.rutherford79@REMOVETHIS.gmail.com> writes:

> 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.

[toc] | [prev] | [next] | [standalone]

#15473

On Wed, 04 Jan 2012 22:20:18 +0000, Edward Rutherford wrote:

> 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.

[toc] | [prev] | [next] | [standalone]

#15482

Nobody <nobody@nowhere.com> writes:

> On Wed, 04 Jan 2012 22:20:18 +0000, Edward Rutherford wrote:
>
>> 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.

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.
-- 
Online waterways route planner            | http://canalplan.eu
Plan trips, see photos, check facilities  | http://canalplan.org.uk

[toc] | [prev] | [next] | [standalone]

#15489

On 1/4/2012 4:20 PM, Edward Rutherford wrote:
> 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).

[toc] | [prev] | [next] | [standalone]

#15490

On 2012-01-06, BGB <cr88192@hotmail.com> 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.

[toc] | [prev] | [next] | [standalone]

#15499

Kaz Kylheku wrote:
) On 2012-01-06, BGB <cr88192@hotmail.com> 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

[toc] | [prev] | [next] | [standalone]

#15500

On 06-Jan-12 15:41, Willem wrote:
> Kaz Kylheku wrote:
> ) On 2012-01-06, BGB <cr88192@hotmail.com> 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

-- 
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

[toc] | [prev] | [next] | [standalone]

#15501

On 2012-01-06, Willem <willem@toad.stack.nl> wrote:
> Kaz Kylheku wrote:
> ) On 2012-01-06, BGB <cr88192@hotmail.com> 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.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c

csiph-web