Computations - which is faster?

This is a discussion on Computations - which is faster? within the C Programming forums, part of the General Programming Boards category; When adding equations and formulas to programs, there are many ways to express the same thing. Which of the methods ...

  1. #1
    Math wizard
    Join Date
    Dec 2006
    Location
    USA
    Posts
    582

    Computations - which is faster?

    When adding equations and formulas to programs, there are many ways to express the same thing. Which of the methods in each group, of which have the exact same effect mathematically, is the fastest, the second-fastest, and so on (in other words, the fastest to the slowest)?

    my_var = another_var*2/3;
    my_var = another_var*12/18; // see notes on why this would be used
    my_var = another_var*0.6666666666666667; // not decent when integerical variables are used

    my_var = another_var*2/3;
    my_var = another_var*(2/3);

    my_var += another_var*(third_var-4/fourth_var)+2; // minimal use of parentheses
    my_var += (another_var*(third_var-(4/fourth_var))+2); // excessive use of parentheses

    my_var = pow(another_var, 2.0);
    my_var = another_var*another_var;

    my_var = pow(another_var, 0.5);
    my_var = sqrt(another_var);

    my_var = another_var+another_var;
    my_var = another_var*2;



    The first group represents fractions. When doing a series like this:

    my_var = another_var/8; // obviously faster - fewer operators
    my_var = another_var/4; // same as above
    my_var = another_var*3/8; // three-eighths
    my_var = another_var/2;
    my_var = another_var*5/8;
    my_var = another_var*3/4; // reduced from six-eighths
    my_var = another_var*7/8;

    It's a bit tricky to tell what the fractions are, but if I did this instead:

    my_var = another_var*1/8;
    my_var = another_var*2/8;
    my_var = another_var*3/8;
    my_var = another_var*4/8;
    my_var = another_var*5/8;
    my_var = another_var*6/8;
    my_var = another_var*7/8;
    my_var = another_var*8/8;

    It's much easier to see the fractions. I use this in my 2D game to get realistic scaling effects and thus a realistic 3D appearance.

    The other is only useful when floating point values are used (the float and double).

    The next two groups involve the usage of parentheses, particularly whether or not excessive parentheses have any effect on the speed. Given that multiplication and division come first before addition and subtraction, there is no need to group the multiplication, unless a higher order operation is used and the multiplication needs to be done first.

    The next involve different ways of doing the same thing. Raising something to the second power is the same as multiplying it by itself. Raising something to the 0.5 power is the same as taking the square root of something and either of these methods could work. Which are the faster and slower methods?

  2. #2
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    my_var = another_var*2/3;
    my_var = another_var*12/18; // see notes on why this would be used
    my_var = another_var*0.6666666666666667; // not decent when integerical variables are used

    Why the second, what's integerical and why is it 'indecent'

    my_var = another_var*2/3; // Value
    my_var = another_var*(2/3); // 0

    And well, hardcoding the decimal would be better, unless it's 'indecent'

    my_var += another_var*(third_var-4/fourth_var)+2; // minimal use of parentheses
    my_var += (another_var*(third_var-(4/fourth_var))+2); // excessive use of parentheses

    Exactly the same

    my_var = another_var+another_var;
    my_var = another_var*2;

    Definitely the first

    my_var = pow(another_var, 0.5);
    my_var = sqrt(another_var);

    I would assume sqrt is optimized for a sqrt operation, but of course you can attain arbitrary uh -- rootage -- level of roots -- using pow.

    I would use things like the scaling operations your graphics library should provide.

    ╔╗╔╦══╦╗╔╦══╦╗
    ║╚╝║╔╗║╚╝║╔╗║║
    ║╔╗║╠╣║╔╗║╠╣╠╣
    ╚╝╚╩╝╚╩╝╚╩╝╚╩╝

    codez http://code.google.com/p/zxcvbn/

  3. #3
    Mad OnionKnight's Avatar
    Join Date
    Jan 2005
    Location
    Umeň, Sweden
    Posts
    555
    Which of the methods in each group, of which have the exact same effect mathematically, is the fastest, the second-fastest, and so on (in other words, the fastest to the slowest)?
    That isn't always easy to answer as it differs depending on your processor, the implementation, compiler optimizations and so on.

    First: What is my_var? An integer? I'll assume that.
    my_var = another_var*2/3;
    my_var = another_var*12/18; // see notes on why this would be used
    my_var = another_var*0.6666666666666667; // not decent when integerical variables are used
    I don't know if the floating point operation is faster but I guess it isn't because it would require that my_var to be casted to a float, perform the operation and the cast it back to an integer.
    As for the two fractions I don't think there will be any difference but the compiler could also choose not to optimize 12/18 to 2/3 since 12/18 is different in that a multiplication by 12 causes an overflow for a larger interval than multiplication with 2.
    my_var = another_var*2/3;
    my_var = another_var*(2/3);
    The second one evaluates to 0 because 2/3 is an integer division.
    my_var += another_var*(third_var-4/fourth_var)+2; // minimal use of parentheses
    my_var += (another_var*(third_var-(4/fourth_var))+2); // excessive use of parentheses
    There's no difference between the two.
    my_var = pow(another_var, 2.0);
    my_var = another_var*another_var;
    Second one is faster, and I don't think there's any system where that would differ.
    my_var = pow(another_var, 0.5);
    my_var = sqrt(another_var);
    This is depends on the implementation, but in glibc sqrt() has it's own optimized version so sqrt() is faster. You should choose the least general functions if you want speed.
    my_var = another_var+another_var;
    my_var = another_var*2;
    The second one should be faster as the compiler will most likely optimize that to a bit-shift operation, another_var << 1.
    EDIT: Or maybe not. The first one would probably also be optimized in the same way.
    Last edited by OnionKnight; 12-09-2006 at 07:08 PM.

  4. #4
    Registered User
    Join Date
    Nov 2006
    Posts
    176
    I would personnaly just write a small timing program.

    start = gethrtime() (solaris timing)
    equation
    stop = gethrtime()
    output difference / 1000
    do the next
    do the next
    ...
    ...

  5. #5
    Math wizard
    Join Date
    Dec 2006
    Location
    USA
    Posts
    582
    I can understand the issue with overflow in the case of the 2/3 versus 12/18. In the second case, I'm normally thinking of floating-point numbers, the kind we humans deal with (since there are fractions). It ties in with the case of parentheses usage. As for the fourth set, why is "another_var*another_var" definitely faster than with using the pow() function? What do you mean by "least general functions"? As to the sixth group, I tend to forget about the bitwise operators. Having forgotten the bitwise operators, I want to modify that last group a little:

    my_var = another_var+another_var;
    my_var = another_var*2;
    my_var = another_var << 1; // the only change is this

    Of these three, which is the fastest and what is the second-fastest?

    Also, since you assumed "my_var" was in integer, what are the effects if it was a floating point value instead? I was thinking you'd evaluate it in both cases.

  6. #6
    Math wizard
    Join Date
    Dec 2006
    Location
    USA
    Posts
    582
    Quote Originally Posted by Tonto
    I would use things like the scaling operations your graphics library should provide.
    What I mean by scaling is distance, not stretching. If the character is at a scaling of 1, he/she is approximately 30 feet away and each pixel is 11/75 of a foot, after the distance travelled in a tenth of a second at 20 mph per second acceleration (after my animated GIFs I've made for years). If the scaling was 30, decent for a skyscraper relatively nearby, each pixel would be 330/75 of a foot, which is 4.4 feet, is about 900 feet distant, and when moving, appears to move 1/30 as fast. A scaling of 1500 would be typical for mountains or very distant hills. this screenshot shows this scaling concept in my 2D game. It looks strongly 3D due to the use of scaling. This was made with the other tool I had and due to it's limitations, I couldn't do much and I'm learning C to expand and include other things. this animation shows the effects of scaling as I refer to it very well. This is used in my 2D game to provide realistic effects and the case of the fractions is used often in my 2D game when it comes to the city (not shown in the linked screenshot), the clouds, and mountains. I just thought I'd clear this possible misunderstanding up.

  7. #7
    Mad OnionKnight's Avatar
    Join Date
    Jan 2005
    Location
    Umeň, Sweden
    Posts
    555
    As for the fourth set, why is "another_var*another_var" definitely faster than with using the pow() function? What do you mean by "least general functions"?
    pow(x, y) computes x^y for all y, whereas sqrt(x) computes x^y with y being only 0.5. The sqrt() function has "less functionality" in that pow() can do what sqrt() does and more. Since it has less variables to take account for it can do some optimizations. Which ones it can do I don't know since I don't even know how to do take the square root of something other than using a calculator to do it or some approximation technique :|
    If you were to look at the source code of glibc you'd see that the sqrt() uses less instructions though.
    my_var = another_var+another_var;
    my_var = another_var*2;
    my_var = another_var << 1; // the only change is this

    Of these three, which is the fastest and what is the second-fastest?
    I know little about processors so correct me if I'm wrong.
    I think that bit-shifting would be faster, summation second and multiplication least fast. You should however leave these things to the compiler as it would most likely optimize things to suit the machine best you're compiling on. If I were to choose which one it would be multiplication by 2 as it's easier to follow.
    Also, since you assumed "my_var" was in integer, what are the effects if it was a floating point value instead? I was thinking you'd evaluate it in both cases.
    I don't really know. Floating-point operations are said to be faster than integer operation on modern machines though.

  8. #8
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote Originally Posted by ulillillia
    my_var = another_var+another_var;
    my_var = another_var*2;
    my_var = another_var << 1; // the only change is this

    Of these three, which is the fastest and what is the second-fastest?
    They might all be the same.

    Write code you would want to maintain. If, after profiling, you find a bottleneck, then optimize (and comment!).

    Be careful about premature optimization.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  9. #9
    Registered User
    Join Date
    Nov 2006
    Posts
    65
    You are looking for optimization in the wrong place. Compilers will do as many computations as possible at compile time, if you enable optimizing. Any mathematical expression consisting entirely of constants probably will fall into this category. Here's an example of 2 programs and what they look like after compiling on gcc with the following flags:
    -03 (optimization)
    -S (to prevent assembling; thus stopping at assembler code. So we can compare output.)

    test21_1.c
    Code:
    #include <stdio.h>
    
    int main(void) {
      float a_float;
      float another_float = 2.3f;
      a_float = another_float*2/3;
      return 0;
    }
    test21_2.c
    Code:
    #include <stdio.h>
    
    int main(void) {
      float a_float;
      float another_float = 2.3f;
      a_float = another_float*222/111/(18/6);
      return 0;
    }

    OUTPUT:
    test21_1
    Code:
        .file    "test21_1.c"
        .text
        .p2align 4,,15
    .globl main
        .type    main, @function
    main:
        leal    4(%esp), %ecx
        andl    $-16, %esp
        pushl    -4(%ecx)
        xorl    %eax, %eax
        pushl    %ebp
        movl    %esp, %ebp
        pushl    %ecx
        popl    %ecx
        popl    %ebp
        leal    -4(%ecx), %esp
        ret
        .size    main, .-main
        .ident    "GCC: (GNU) 4.1.1 20060525 (Red Hat 4.1.1-1)"
        .section    .note.GNU-stack,"",@progbits
    test21_2
    Code:
        .file    "test21_2.c"
        .text
        .p2align 4,,15
    .globl main
        .type    main, @function
    main:
        leal    4(%esp), %ecx
        andl    $-16, %esp
        pushl    -4(%ecx)
        xorl    %eax, %eax
        pushl    %ebp
        movl    %esp, %ebp
        pushl    %ecx
        popl    %ecx
        popl    %ebp
        leal    -4(%ecx), %esp
        ret
        .size    main, .-main
        .ident    "GCC: (GNU) 4.1.1 20060525 (Red Hat 4.1.1-1)"
        .section    .note.GNU-stack,"",@progbits

    The output is the same in each case (obviously). Basically, make sure you read the manual for your compiler and at least enable basic optimizing. There is also a few options which control floating point mathematics. You can speed it up, if you enable those options, which might rely on certain requirements (see manual). Lastly, you can tune the output for a specific processor group. All of these things are probably going to make hundred times more difference in speed than writing 2/3 or 4/6 or 0.6667 or (((0.6667))).

  10. #10
    Math wizard
    Join Date
    Dec 2006
    Location
    USA
    Posts
    582
    Thanks for the details. I'll consider this for my game design stuff to help keep the frame rate as high as possible. This thread might be useful for the FAQ forum.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Faster bitwise operator
    By Yarin in forum C++ Programming
    Replies: 18
    Last Post: 04-29-2009, 01:56 PM
  2. Faster way of printing to the screen
    By cacophonix in forum C Programming
    Replies: 16
    Last Post: 02-04-2009, 12:18 PM
  3. does const make functions faster?
    By MathFan in forum C++ Programming
    Replies: 7
    Last Post: 04-25-2005, 09:03 AM
  4. if is faster than switch?
    By skorman00 in forum C++ Programming
    Replies: 32
    Last Post: 03-06-2004, 12:15 PM
  5. Floating point faster than fixed-point
    By VirtualAce in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 11-08-2001, 10:34 PM

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