Like Tree6Likes

Branching vs array indexing

This is a discussion on Branching vs array indexing within the General Discussions forums, part of the Community Boards category; I was wondering... if I had many different functions that I wanted to call based on what the value of ...

  1. #1
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,602

    Branching vs array indexing

    I was wondering... if I had many different functions that I wanted to call based on what the value of a variable would be, and the limits of that value where integral [0, N) , would the second method be much faster than the first?:
    Code:
    void proc1();
    void proc2();
    ...
    void procN();
    1st:
    Code:
    switch (value)
    {
        case 0:
            proc1();
        break;
        case 1:
            proc2();
        break;
        ...
        case N-1:
            procN();
        break;
    }
    2nd:
    Code:
    typedef void (*procedure)();
    
    procedure procArray[N] = { proc1, proc2, ... , procN };
    ...
    procArray[value]();
    In the case of indexing though, what "guessing" rules would apply, if any?
    Last edited by GReaper; 06-20-2012 at 12:21 AM.
    Devoted my life to programming...

  2. #2
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,184
    Premature optimization.
    The compiler may very well optimize a switch into a function table. Regardless, don't concern yourself about it. Let the compiler do its work, while you keep the code readable.
    antred and smokeyangel like this.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  3. #3
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,532
    In my opinion indexing is more useful and I try to use it when I can. Indexing is an important operation to consider, especially if you want to speed up something nontrivial like random file access. Sometimes I just do it this way for the practice.

    The compiler may very well optimize a switch into a function table. Regardless, don't concern yourself about it. Let the compiler do its work, while you keep the code readable.
    That really sounds like you made it up. Surprise me.
    Last edited by whiteflags; 06-20-2012 at 01:14 AM.

  4. #4
    the hat of redundancy hat nvoigt's Avatar
    Join Date
    Aug 2001
    Location
    Hannover, Germany
    Posts
    3,138
    Quote Originally Posted by Elysia View Post
    Premature optimization.
    The compiler may very well optimize a switch into a function table. Regardless, don't concern yourself about it. Let the compiler do its work, while you keep the code readable.
    Second that. Even if you optimize it to save 1ms (a LOT of time in computing) per run, you would need a lot of runs to compensate for the one additional working day (28.800.000ms) your colleague needs to understand your program because you optimized it for speed. Optimize for readability while keeping it "fast enough" is probably more rewarding.

    That said I think your second approach using a table would indeed be more readable as the number of functions increases. I would not want to read a 2000 line switch statement where I can never be sure if there isn't one case that is not just the single function call. So it's win-win. Probably faster, most likely more readable.
    GReaper likes this.
    hth
    -nv

    She was so Blonde, she spent 20 minutes looking at the orange juice can because it said "Concentrate."

    When in doubt, read the FAQ.
    Then ask a smart question.

  5. #5
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,602
    Thanks guys. I asked this because I've been building some old PC emulators( like Kenbak-1 ), and I thought I could use the opcodes as indices! It'd be nice if I managed to get it to run at approx 300 IPS( speaking about the Kenbak-1 ) with less than 5% of my CPU( Core2 Duo 2.4GHz ) .
    Devoted my life to programming...

  6. #6
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    3,831
    I offer my vote for the table method.

    "Table Driven Development" for the win!

    Soma
    GReaper likes this.

  7. #7
    Registered User
    Join Date
    Oct 2006
    Posts
    2,151
    I use a function pointer table in one of my big programs, because there are literally hundreds of entries. a switch statement in my case would be insanely huge and unreadable. if C++ had reflection, I might be able to use that instead, but the function pointer table works great for my purposes. it's fast, it's obvious what it does, and it's easy to add elements when necessary.

  8. #8
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,184
    Quote Originally Posted by whiteflags View Post
    That really sounds like you made it up. Surprise me.
    If this suffices for you...
    Code:
    #include <iostream>
    
    void foo0() { std::cout << "I am foo0!\n"; }
    void foo1() { std::cout << "I am foo1!\n"; }
    void foo2() { std::cout << "I am foo2!\n"; }
    void foo3() { std::cout << "I am foo3!\n"; }
    void foo4() { std::cout << "I am foo4!\n"; }
    void foo5() { std::cout << "I am foo5!\n"; }
    void foo6() { std::cout << "I am foo6!\n"; }
    void foo7() { std::cout << "I am foo7!\n"; }
    void foo8() { std::cout << "I am foo8!\n"; }
    void foo9() { std::cout << "I am foo9!\n"; }
    
    int main(void)
    {
    	int n;
    	std::cout << "Enter function to call: ";
    	std::cin >> n;
    
    	switch (n)
    	{
    		case 0: foo0(); break;
    		case 1: foo1(); break;
    		case 2: foo2(); break;
    		case 3: foo3(); break;
    		case 4: foo4(); break;
    		case 5: foo5(); break;
    		case 6: foo6(); break;
    		case 7: foo7(); break;
    		case 8: foo8(); break;
    		case 9: foo9(); break;
    	}
    	
    	return 0;
    }
    Looking at optimized assembly from VC++, we see:

    Code:
    switch (n)
    003610FF  mov         eax,dword ptr [n]  
    00361102  cmp         eax,9  
    00361105  ja          $LN1+5 (361152h)  
    00361107  jmp         dword ptr  (361159h)[eax*4]  
    	{
    		case 0: foo0(); break;
    0036110E  call        foo0 (36101Bh)  
    00361113  jmp         $LN1+5 (361152h)
    Essentially, it jumps directly to the right position in the switch, then performs the call. If I enable inlining, it inlines the functions directly into the switch.
    Not a direct function table call, but almost. But that's what I meant, if it isn't clear. The compiler can optimize the switch to essentially jump to the right position.
    Dunno if a compiler is smart enough to understand that all cases essentially just call a function, though.
    whiteflags likes this.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  9. #9
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,160
    Quote Originally Posted by whiteflags View Post
    That really sounds like you made it up. Surprise me.
    Seriously? That's literally the textbook way of implementing switch statements.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  10. #10
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,532
    Quote Originally Posted by brewbuck View Post
    Seriously? That's literally the textbook way of implementing switch statements.
    I only pretend to know everything about how it works.

  11. #11
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    3,831
    That's literally the textbook way of implementing switch statements.
    O_o

    "That's literally the textbook way of implementing switch statements with cases that follow discernible mathematics logic."

    I thought I should fix that before someone runs off and misuses a switch statement.

    Soma
    Elkvis likes this.

  12. #12
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,146
    I believe compilers will turn switch into jump table for you only if the indices are more or less continuous. Otherwise memory space wasted would be significant, especially if it decreases code density to the point that you get more instruction cache misses, then it would definitely not be worth it.

  13. #13
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    3,831
    I believe compilers will turn switch into jump table for you only if the indices are more or less continuous.
    I think "GCC" will happily mix and match as is appropriate.

    In other words, if several cases follow easily discernible linear mathematics the compiler may build a table for parts of the `switch' and branch otherwise as appropriate.

    Soma

  14. #14
    Registered User
    Join Date
    Jul 2010
    Posts
    86
    map<"some kind of key", object> .... have the objects inherit from an abstract class which has a public void function like "execute()", then you can insert various objects in there that do different jobs, and fire them all off using the same command after you've looked up what you want (command pattern)

    Maybe I just spoke craziness there. Don't know. I'm trying to translate java style OO with interfaces into "c++ style". Either way, I'm quite sure I can count on a good chastising if I am wrong on any count.
    I made a pair of "Braille Gloves" which have 6 vibration motors in six finger tips and vibrate in the relevant patterns. I have used this to read stuff while out walking. Given there is a fairly well defined programmer-oriented Braille encoding I should imagine it would work in this situation. Diagrams could be a pain still.

    Note: I am not blind but have learnt Braille fairly easily so for me it works quite well

    Disclaimer: I haven't tried this while driving yet...

  15. #15
    Registered User
    Join Date
    Mar 2010
    Posts
    531
    I had a look at some old (2005ish) articles on GCC's behaviour (http://ivoras.sharanet.org/papers/switch-complexity.pdf, Branch Patterns, Using GCC - CellPerformance) -- the heuristic is (was?) pretty basic -- switch tables with a large range of case values relative to the number of cases will revert to normal compare and branch. I prodded GCC a bit and I'm pretty sure the exact heuristic given on those pages is no longer correct (look it up if you're interested).

    Quote Originally Posted by phantomotap
    I think "GCC" will happily mix and match as is appropriate.

    In other words, if several cases follow easily discernible linear mathematics the compiler may build a table for parts of the `switch' and branch otherwise as appropriate.
    From some testing, I don't think GCC does mix and match, but I think MSVC does. I may be wrong though, not great at reading x86 disassembly.


    On the original question... I completely agree with what's already been said. Use whatever is appropriate and most readable/maintainable for the task at hand. For what you said (building an emulator) I'd probably opt for the table approach.

    I don't know if it'll be any faster than the optimised-switch code. You've saved a branch, but gained array index and load of the function address. I'd guess it'll work out about the same.


    I think "optimised" C/C++ can be useful and has its place. The programmer will know things about the application that the compiler can't know or coudln't be expected to figure out, so the programmer can write their code in a way that expresses their intent explicitly or implicitly to the compiler. I think treading on the compiler's standard optimisation turf is less likely to be useful, as you don't have total control of what is output.

    Quote Originally Posted by wildcard_seven
    map<"some kind of key", object> .... have the objects inherit from an abstract class which has a public void function like "execute()", then you can insert various objects in there that do different jobs, and fire them all off using the same command after you've looked up what you want (command pattern)

    Maybe I just spoke craziness there. Don't know. I'm trying to translate java style OO with interfaces into "c++ style". Either way, I'm quite sure I can count on a good chastising if I am wrong on any count.
    lol, no chastising from me.... much too OO for me to comment. Didn't sound crazy until I looked up the command pattern -- looks, err, rather heavyweight!

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. probability branching
    By Dale in forum C# Programming
    Replies: 5
    Last Post: 11-18-2011, 09:32 AM
  2. Minimizing array lookup times using effective indexing...?
    By The Dog in forum Game Programming
    Replies: 5
    Last Post: 02-08-2011, 06:11 AM
  3. Array Indexing w/ strlen()
    By c++_n00b in forum C++ Programming
    Replies: 8
    Last Post: 06-04-2002, 11:18 AM
  4. Branching?
    By Brian in forum C Programming
    Replies: 1
    Last Post: 01-20-2002, 10:06 AM
  5. array indexing
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 10-01-2001, 11:42 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21