Showing results 1 to 4 of 4

Thread: Optimization Confusion

  1. #1

    Advocate
    zack's Avatar
    Join Date
    Jan 2010
    Location
    Middle Tennessee
    Posts
    225

    Default Optimization Confusion

    I wrote fizz-buzz (wiki it ) in forth as a excersize to help me learn the language and then I tested it up to ten million elements outputing to /dev/null ( black hole for you windows folks ) . I noticed the results were taking a while, twelve seconds, so I rewrote it in c using counters. At this point I decided to see how expensive % was compared to counters, so with some preprocessor magic I made it happen and the results were shocking. Using modulo division leads to times around .73 seconds. Using two counters to compute %3 and %5 leads to times around 1.2 seconds.

    This baffles me, how can division be faster than adding 1 to some counters and checking the result? I'd like to have the people of GameThreat test it to get a broad range of computers involved to see if this is a fluke on both my friends computer and my own.


    timing can be compleated in *nix systems by typing time ./a.out or on windows by typing Measure-Command {start-process c.exe | Null} into power shell ( can't confirm this my self, but he said it worked on the windows 8 consumer preview )
    Please state your OS ( most importantly 64 vs 32 bit ), compiler, and processor along with your results if you want to contribute to the testing pool.

    To change weather you use mod or counter comment in or out the line #define modWay
    comment out : use counters
    comment in : use mod

    the code
    Code:
    #include <stdio.h>
    //#define modWay
    int main(){
    #ifndef modWay
            int three =0;
            int five =0;
    #endif
            int bizz;
            int buzz;
            int temp;
    
            int i=1;
    
            while( i <= 10000000 ){
    #ifndef modWay
                    three++;
                    five++;
    #endif
    
    #ifndef modWay
                    if ( three == 3 ){
                            three=0;
    #else
                    if( i % 3 == 0 ){
    #endif
                            bizz=1;
                    }
                    else {
                            bizz=0;
                    }
    
    #ifndef modWay
                    if ( five == 5 ){
                            five =0;
    #else
                    if ( i % 5 ){
    #endif
    
                            buzz=1;
                    }
                    else {
                            buzz=0;
                    }
    
                    temp = bizz+buzz;
    
                    switch (temp) {
    
                            case 0:
                                    printf("%i\n",i);
                                    break;
                            case 1:
                                    printf("%s\n",bizz==1 ?"bizz":"buzz");
                                    break;
                            case 2:
                                    printf("bizzBuzz\n");
                    }
                    i++;
            }
    
            return 0;
    }

    if you can think of a reason for the unexpected slowness of counters or the speed of % please let us know.

  2. #2
    A zero-your personal hero Senior Member
    Gold Member

    Blessed

    Join Date
    Jul 2004
    Posts
    2,041

    Default

    Since every higher-level language boils down to assembly instructions eventually, here's a few "optimization" snippets you might want to be aware of in x86:
    - division and modulo is one same instruction, which is why it's so fast; dividing by powers of 2 is even faster, since these operations can be implemented as bit shifts
    - pre-incrementation is usually faster than post-incrementation - this solely depends on how the compiler and assembler build instructions, but generally this is true

    If you really intend on making your code cutting-edge optimal, you'll eventually end up implementing even the simplest instructions on your own in assembly of a particular architecture.
    Last edited by Indefinite : 05-30-2012 at 10:53 PM

  3. #3
    Senior Member
    Retired Staff Member

    Celestial Entity
    gamepin126's Avatar
    Join Date
    Oct 2004
    Posts
    20,794

    Default

    The compiler is smart enough to use pre-increments 100% of the time on atomic datatypes.

    I guess our results are at odds.

    It being 5:30am, your interleaved ifdefs made my head spin so I wrote my own. Apparently, cmd prompt is horribly slow, who knew? Gonna have to go to the assembly to get the answer

    verbose
    nomod = 127.670s
    nomod commented = 144.327s
    verbose commented
    nomod = 0.012s
    nomod commented = 0.034s
    Code:
    using namespace std;
    
    //#define nomod
    //#define verbose
    
    int main(void)
    {
        int i = 0;
        bool m = 0;
    
        int three = 0;
        int five = 0;
        bool t;
        bool f;
    
        for (i = 0; i < 10000000; ++i)
        {
    #ifdef verbose
                t = false;
                f = false;
        #ifdef nomod
    
                if (three == 3)
                {
                    t = true;
                    three = 0;
                } else {
                    three++;
                }
    
                if (five == 5)
                {
                    f = true;
                    five = 0;
                } else {
                    five++;
                }
    
                cout << endl;
    
                if (t && f ) cout << "fizzbuzz";
                else if (t) cout << "fizz";
                else if (f) cout << "buzz";
                else cout << i;
    
    
        #else
                m = false;
    
                cout<<endl;
    
                if ( i % 3 == 0) cout << "fizz";
                else m = true;
    
                if ( i % 5 == 0) cout << "buzz";
                else if (m) cout << i;
        #endif
    #else
                t = false;
                f = false;
        #ifdef nomod
    
                if (three == 3)
                {
                    t = true;
                    three = 0;
                } else {
                    three++;
                }
    
                if (five == 5)
                {
                    f = true;
                    five = 0;
                } else {
                    five++;
                }
    
                ;//cout << endl;
    
                if (t && f ) ;//cout << "fizzbuzz";
                else if (t) ;//cout << "fizz";
                else if (f) ;//cout << "buzz";
                else ;//cout << i;
    
    
        #else
                m = false;
    
                ;//cout<<endl;
    
                if ( i % 3 == 0) ;//cout << "fizz";
                else m = true;
    
                if ( i % 5 == 0) ;//cout << "buzz";
                else if (m) ;//cout << i;
        #endif
    #endif
        }
    
        return 0;
    }
    edit: line 36 "if ( i % 5 ){" needs to be "if ( i % 5 == 0 ){" in ur code

    edit2: I let my derp show, sorry everyone had to see that. I changed a couple things in your code to make the methodology more consistent.

    Code:
    #include <stdio.h>
    //#define modWay
    int main(){
            int three =0;
            int five =0;
            int bizz;
            int buzz;
            int temp;
    
            int i;
    
            for ( i=1; i <= 10000000; ++i ){
                    three++;
                    five++;
    
    #ifndef modWay
                    if ( three == 3 ){
    #else
                    if( i % 3 == 0 ){
    #endif
                            three=0;
                            bizz=1;
                    }
                    else {
                            bizz=0;
                    }
    
    #ifndef modWay
                    if ( five == 5 ){
    #else
                    if ( i % 5 == 0 ){
    #endif
    
                            five =0;
    
                            buzz=1;
                    }
                    else {
                            buzz=0;
                    }
    
                    temp = bizz+buzz;
    
                    switch (temp) {
    
                            case 0:
                                    printf("%i\n",i);
                                    break;
                            case 1:
                                    printf("%s\n",bizz==1 ?"bizz":"buzz");
                                    break;
                            case 2:
                                    printf("bizzBuzz\n");
                    }
            }
    
            return 0;
    }
    Last edited by gamepin126 : 05-31-2012 at 05:12 AM
    "A Responsible Citizen Not Only Shares Culture, But Destroys The Copyright Industries"

    "Elegance is not a dispensable luxury but a quality that decides between success and failure. "
    "It Don't Mean a Thing (If It Ain't Got That Swing)"
    “Absence of evidence is not evidence of absence.”

  4. #4
    The Pandanator Senior Member

    Zealot
    pandas's Avatar
    Join Date
    Jul 2005
    Location
    Massachusetts
    Posts
    698

    Default

    possible reasons
    a) optimizing compilers do weird ****, perhaps the way that looks slow is not optimized by the compiler as well as the way that looks fast? it would be more useful to look at `gcc -S`.
    b) hardware is complex and machine code performs well for strange reasons. intel changes the depth of the instruction pipeline and afterward some software runs faster and some runs lower, basically at random. in particular, caching and branch prediction completely **** everything up. but that's just the beginning, see for example all of this ****: http://www.lxhp.in-berlin.de/lhpk6opt.html . considering whether one instruction generally takes more clocks than another in isolation is not always useful.
    c) since one of your implementations is wrong, printfing different numbers of characters will be the #1 performance difference.

    ... profanity filter, we meet again

    edit: fixing code before i post results
    Code:
    #include <stdio.h>
    #define modWay
    int main(){
            int x = 0;
            int three =0;
            int five =0;
            int bizz;
            int buzz;
            int temp;
    
            int i;
    
            for ( i=1; i <= 10000000; ++i ){
                    three++;
                    five++;
    
    #ifndef modWay
                    if ( three == 3 ){
    #else
                    if( !(i % 3) ){
    #endif
                            three=0;
                            bizz=1;
                    }
                    else {
                            bizz=0;
                    }
    
    #ifndef modWay
                    if ( five == 5 ){
    #else
                    if ( !(i % 5) ){
    #endif
    
                            five =0;
    
                            buzz=1;
                    }
                    else {
                            buzz=0;
                    }
    
                    temp = bizz+buzz;
    
                    switch (temp) {
                            case 0:
                                    x += 1;
                                    break;
                            case 1:
                                    x += 5;
                                    break;
                            case 2:
                                    x += 8;
                    }
            }
            printf("%d\n", x);
            return 0;
    }
    Code:
    $ gcc fizzbuzz.c; time ./a.out
    30666666
    
    real    0m0.057s
    user    0m0.060s
    sys     0m0.000s
    $ gcc fizzbuzzmod.c; time ./a.out
    30666666
    
    real    0m0.085s
    user    0m0.090s
    sys     0m0.000s
    $ gcc -O3 fizzbuzz.c; time ./a.out
    30666666
    
    real    0m0.034s
    user    0m0.030s
    sys     0m0.000s
    $ gcc -O3 fizzbuzzmod.c; time ./a.out
    30666666
    
    real    0m0.057s
    user    0m0.060s
    sys     0m0.000s
    Last edited by pandas : 05-31-2012 at 02:03 PM
    Quote Originally Posted by shoutbox
    [Today 05:57 AM] dt: stfu
    [Today 05:56 AM] *Zerus45 hi*

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. Voter intimidation, fraud, misdirection, confusion, etc.
    By Mobilus in forum Serious Discussion
    Replies: 19
    Last Post: 11-03-2008, 08:33 PM
  2. The ultimate confusion to end all confusions
    By Dr. Silence in forum General Chat
    Replies: 25
    Last Post: 03-22-2005, 08:45 PM
  3. stupid WPM confusion
    By TheTempest in forum Software Development
    Replies: 2
    Last Post: 07-03-2004, 10:19 AM

Posting Rules

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •