Thread: Zero multiplication

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    147

    Zero multiplication

    I have this code which runs a lot of times:

    Code:
    int z = 10;
    int x = b * z;
    I know my program assing b = 0 about 35% of times. Does the CPU or compiled code runs into a complete multiplication routines, or does it returns 0 fast?

    I ask this because I dont know if for speed optimization is better to put this code:

    Code:
    int z = 10;
    if (b) x = b*z;
    what is faster?

    thanks
    FS

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Optimization is a good thing to think about, but I doubt the cost of an "if" is much different than the cost of multiplying by zero. In fact, the multiplication might be cheaper, speed wise.

    I don't know assembly language and cannot claim this as fact, but the next couple of posters seem to agree.
    Last edited by MK27; 05-08-2009 at 07:54 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    Quote Originally Posted by Kempelen View Post
    I have this code which runs a lot of times:

    Code:
    int z = 10;
    int x = b * z;
    I know my program assing b = 0 about 35% of times. Does the CPU or compiled code runs into a complete multiplication routines, or does it returns 0 fast?

    I ask this because I dont know if for speed optimization is better to put this code:

    Code:
    int z = 10;
    if (b) x = b*z;
    what is faster?

    thanks
    FS
    In my opinion speedwise extra time will be spent on checking the condtion of the if statement and thus 'if' will lead to a slower code.
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  4. #4
    and the hat of copycat stevesmithx's Avatar
    Join Date
    Sep 2007
    Posts
    587
    Quote Originally Posted by web
    Premature optimization is the root cause of all evil.
    So make sure you do all your optimizations stuff at the end.
    Not everything that can be counted counts, and not everything that counts can be counted
    - Albert Einstein.


    No programming language is perfect. There is not even a single best language; there are only languages well suited or perhaps poorly suited for particular purposes.
    - Herbert Mayer

  5. #5
    Registered User
    Join Date
    May 2007
    Posts
    147
    stevesmithx, right on!

    Oy - with the "which is faster" on a construct that resolves to a few assembler instructions....


    Yes, the "if" test would make all multiplications slower, but consider this:

    On modern hardware you'll see tens or hundreds of millions of multiplications go by in a second. The "if" will be nearly as fast.

    What could you be doing that needs to consider the difference between a hundred millionth of a second or two? (I know the answer BTW).

    You will want to understand the performance implications of what you write, no doubt about that (or you wouldn't be using C).

    On the other hand, you need to learn the critical mass before any of that level of thinking is going to make much sense.

    In your future it will probably be more important to know how to make matrix multiplications fast, or how to rip through a large buffer quickly - and you will.

  6. #6
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    Believe me - your CPU is probably faster than you'll ever be. Or it wouldn't be sold anymore. And we're talking about micro-to-nanoseconds. That won' really matter (unless you're writing a hi-speed program). First finish your program - then try this. You know about premature optimization, huh? ;-) And a single optimization switch is more worthy than most efforts put into this.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by stevesmithx
    So make sure you do all your optimizations stuff at the end.
    I suggest reading this article, and those it cites, for a more balanced view: Mature Optimization.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    Well, I think I'm missunderstood. Any CPU industry wanting to make money optimizes, optimizes and lowers the prices. I think they would be smart enough to make multiplication by one or zero possible in constant time (if it turns out not really to affect other numbers). And it's true that you first should optimize your code in another way maybe. And your question is machine-specific: On machines with expensive branching, I'd leave everything as is. Else, it might save you some nanoseconds per multiplication.

    @laserlight: Thanks for the enlightenment ;-D

  9. #9
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    That "if" does not matter because of branch prediction and speculative execution. On some modern processors the code will actually take both paths at once while the comparison is still pipelined. On the other hand, a modern processor might also optimize explicitly for multiplying by 0, 1, and maybe even 2.

    I wouldn't be surprised if some architectures might benefit from an explicit check for zero before multiplying. Try it and find out.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  10. #10
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    I think some other architectures first check for zero.

  11. #11
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    If it's a modern processor, it will not be beneficial to skip multiplies by zero - I just wrote a small program to benchmark it. The checking version is about twice as slow.

    Obviously, different processors do this more or less well. But on any recent processor, a mul instruction will be about the same number of clock-cycles as a branch.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  12. #12
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Even if using the if-statement did improve performance for the multiply by 0 case, that is only 35% of your data, do you'd be adding an extra if-statement for the other 65% of the cases and slowing them down.
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by cpjust View Post
    Even if using the if-statement did improve performance for the multiply by 0 case, that is only 35% of your data, do you'd be adding an extra if-statement for the other 65% of the cases and slowing them down.
    Sure. So you really need to have a SLOW multiplier on the machine for there to be a benefit. And the smaller the proportion of zeros there are, the slower the multiplier has to be. A modern processor does a multiply in a couple of cycles (3-7, depending on mode, on the latest Athlon for example). I'd expect Intel's timing to be within a cycle or two of that timing. To compare the value, it will take at least two instructions: a compare (or test) instruction, and a conditional jump instruction. Whilst the ideal case is that this takes 2 clock-cycles, it is highly likely that the branch prediction isn't ALWAYS accurate, so it will sometimes have to refetch the code itself.

    And of course, making the loop itself more complex means that the optimizer will have a harder time to make "perfect" code.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  14. #14
    and the hat of copycat stevesmithx's Avatar
    Join Date
    Sep 2007
    Posts
    587
    Quote Originally Posted by laserlight View Post
    I suggest reading this article, and those it cites, for a more balanced view: Mature Optimization.
    Darn!. Every time i learn some software philosophy, somebody always has something to say against it!.
    Seriously though, thanks for the link dude.
    Not everything that can be counted counts, and not everything that counts can be counted
    - Albert Einstein.


    No programming language is perfect. There is not even a single best language; there are only languages well suited or perhaps poorly suited for particular purposes.
    - Herbert Mayer

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 9
    Last Post: 05-22-2009, 07:03 AM
  2. Help me find a multiplication toy.
    By QuestionC in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 08-24-2007, 12:27 PM
  3. ...multiplication using stacks
    By iiwhitexb0iii in forum C Programming
    Replies: 1
    Last Post: 10-09-2006, 01:28 AM
  4. multiplication table
    By SpEkTrE in forum C Programming
    Replies: 2
    Last Post: 12-09-2003, 04:46 PM
  5. Matrix Multiplication
    By davidvoyage200 in forum C++ Programming
    Replies: 4
    Last Post: 11-20-2002, 04:24 PM

Tags for this Thread