Function pointer vs conditional branch

Discussion in 'C Programming' started by Edward Rutherford, Jan 4, 2012.

  1. 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.
    Edward Rutherford, Jan 4, 2012
    #1
    1. Advertising

  2. Edward Rutherford

    Kaz Kylheku Guest

    On 2012-01-04, 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?


    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?
    Kaz Kylheku, Jan 4, 2012
    #2
    1. Advertising

  3. Edward Rutherford

    Ian Collins Guest

    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
    Ian Collins, Jan 4, 2012
    #3
  4. Edward Rutherford

    Eric Sosman Guest

    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
    d
    Eric Sosman, Jan 5, 2012
    #4
  5. Edward Rutherford

    Kaz Kylheku Guest

    On 2012-01-05, Eric Sosman <> 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.)
    Kaz Kylheku, Jan 5, 2012
    #5
  6. Edward Rutherford

    BartC Guest

    "Edward Rutherford" <> wrote in
    message news:je2jb2$886$...
    > 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
    BartC, Jan 5, 2012
    #6
  7. Edward Rutherford

    Eric Sosman Guest

    On 1/4/2012 8:25 PM, Kaz Kylheku wrote:
    > On 2012-01-05, Eric Sosman<> 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
    d
    Eric Sosman, Jan 5, 2012
    #7
  8. Edward Rutherford

    Gene Guest

    On Jan 4, 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?
    >
    > 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.
    Gene, Jan 5, 2012
    #8
  9. Edward Rutherford

    Kaz Kylheku Guest

    On 2012-01-05, Eric Sosman <> wrote:
    > On 1/4/2012 8:25 PM, Kaz Kylheku wrote:
    >> On 2012-01-05, Eric Sosman<> 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.
    Kaz Kylheku, Jan 5, 2012
    #9
  10. 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, Jan 5, 2012
    #10
  11. 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.
    88888 Dihedral, Jan 5, 2012
    #11
  12. Edward Rutherford

    Joe Pfeiffer Guest

    Edward Rutherford <> 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.
    Joe Pfeiffer, Jan 5, 2012
    #12
  13. Edward Rutherford

    Nobody Guest

    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.
    Nobody, Jan 5, 2012
    #13
  14. Edward Rutherford

    Dr Nick Guest

    Nobody <> 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
    Dr Nick, Jan 6, 2012
    #14
  15. Edward Rutherford

    BGB Guest

    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).
    BGB, Jan 6, 2012
    #15
  16. Edward Rutherford

    Kaz Kylheku Guest

    On 2012-01-06, BGB <> 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.
    Kaz Kylheku, Jan 6, 2012
    #16
  17. Edward Rutherford

    BartC Guest

    "BGB" <> wrote in message
    news:je7bph$g44$...
    > On 1/4/2012 4:20 PM, Edward Rutherford wrote:


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


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

    --
    Bartc
    BartC, Jan 6, 2012
    #17
  18. Edward Rutherford

    Willem Guest

    Kaz Kylheku wrote:
    ) On 2012-01-06, BGB <> 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
    Willem, Jan 6, 2012
    #18
  19. On 06-Jan-12 15:41, Willem wrote:
    > Kaz Kylheku wrote:
    > ) On 2012-01-06, BGB <> 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
    Stephen Sprunk, Jan 6, 2012
    #19
  20. Edward Rutherford

    Kaz Kylheku Guest

    On 2012-01-06, Willem <> wrote:
    > Kaz Kylheku wrote:
    > ) On 2012-01-06, BGB <> 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.
    Kaz Kylheku, Jan 6, 2012
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Guy Montag

    Branch prediction

    Guy Montag, Jul 3, 2004, in forum: VHDL
    Replies:
    3
    Views:
    728
    Mike Treseler
    Jul 6, 2004
  2. Scott Shuster
    Replies:
    4
    Views:
    625
  3. Bede
    Replies:
    0
    Views:
    1,416
  4. wing
    Replies:
    1
    Views:
    18,308
    Robert Klemme
    Oct 13, 2003
  5. Alan Gutierrez

    How To Branch Java

    Alan Gutierrez, Feb 4, 2005, in forum: Java
    Replies:
    8
    Views:
    508
Loading...

Share This Page