Why isn't this C program optimized?

This is a discussion on Why isn't this C program optimized? within the C Programming forums, part of the General Programming Boards category; Code: for (j=1; j<=3120; j++) { for (i=1; i<=j-1; i++) { T = 0.0; for (k=1; k<=i-1; k++) T += ...

  1. #1
    Registered User
    Join Date
    Jul 2005
    Posts
    98

    Why isn't this C program optimized?

    Code:
     
    for (j=1; j<=3120; j++) { 
      for (i=1; i<=j-1; i++) { 
        T = 0.0; 
        for (k=1; k<=i-1; k++) 
           T += 0.0; 
      } 
    } 
    printf("T=%f\n", T);
    I use gcc 3.4.1 (with -O3) on an AMD Opteron dual-code dual-processor machine running Solaris 10 to compile and run the above code. It takes about 30 seconds. But if I replace
    T += 0.0 with either
    T *= 1.0 or
    T += 12.345 * 54.321 or
    T = 0.0
    it takes about 6 seconds.
    1. What prevents gcc from optimizing the code with T+=0.0 such that running the program would also take 6 seconds?
    2. What prevents gcc from optimizing the code such that it would take much less than 6 seconds? For example, with T=0.0 in the k loop, one should know T is zero without doing any computation. Why can't gcc detect it?
    3. If I remove the last printf(), the timings do not change. I thought without printing T, the computation of T is irrelevant because T's value will never be used. So gcc should have optimized away the entire computation!

  2. #2
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,062
    Maybe it's spending 24 seconds scratching its head wondering why you're doing a loop with the statement T+=0.0 in the first place.
    Sent from my iPadŽ

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,045
    You can examine the assembler code if you're really curious. Compile with the -S option for gcc to do so.

    [edit] I don't think the designers of gcc spent much time optimising statements like that. Who uses +=0 anyway? [/edit]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    Registered User
    Join Date
    Oct 2004
    Posts
    151
    Quote Originally Posted by dwks
    Who uses +=0 anyway?
    http://en.wikipedia.org/wiki/Sanity_check ?
    System: Debian Sid and FreeBSD 7.0. Both with GCC 4.3.

    Useful resources:
    comp.lang.c FAQ | C++ FQA Lite

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by hzmonte
    3. If I remove the last printf(), the timings do not change. I thought without printing T, the computation of T is irrelevant because T's value will never be used. So gcc should have optimized away the entire computation!
    Why on earth should it do that?


    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    Quote Originally Posted by quzah
    Why on earth should it do that?


    Quzah.
    Because the value of T has no effect on the output of the program. If the variable has no effect, why should the processor be bothered in calculating it?
    (Better: why do you have an unused variable in your code.)

    There was a thread awhile ago where a guy had this problem. His whole loop was being optimized into the void by the compiler. Rightly so, however.

    This code seems to exhibit such behavior: (Disclaimer: I haven't checked the assembly.)
    Code:
    #include <stdio.h>
    #include <sys/timeb.h>
    
    int main()
    {
    	double d = 0, timetotal;
    	int x;
    	struct timeb t1, t2;
    
    	ftime(&t1);
    
    	for(x = 0; x < 50000000; ++x)
    	{
    		d += 1.278197234;
    		d *= 0.982841924;
    		d /= 1.848739275;
    		d += 1.278197234;
    		d *= 0.982841924;
    		d /= 1.848739275;
    	}
    
    	ftime(&t2);
    
    	timetotal = (double) t2.time + (double) t2.millitm / 1000.0;
    	timetotal -= (double) t1.time + (double) t1.millitm / 1000.0;
    
    	//printf("%g\n", d);
    	printf("Runtime: %6.3g", timetotal);
    
    	return 0;
    }
    Compiled using "gcc -O2 -o opti.exe opti.c", with and without the printf(), the one with the printf() takes 12-17 seconds to run, whereas without, it takes ~0.2 seconds to run.

    To the OP: While I nod my head in agreement with SlyMaelstrom, worry about optimizations when they're needed. The compiler's optimizations are there to help you - better algorithms and coding practices will (usually) trump anything a compiler can eek out. If something is running too slow, find the bottleneck, and see what you can do to fix it.

    To me, "optimization" is usually, "Holy cow, this thing runs a lot quicker when we're not doing debug versions! (And it's smaller to boot!)"
    long time; /* know C? */
    Unprecedented performance: Nothing ever ran this slow before.
    Any sufficiently advanced bug is indistinguishable from a feature.
    Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
    The best way to accelerate an IBM is at 9.8 m/s/s.
    recursion (re - cur' - zhun) n. 1. (see recursion)

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Cactus_Hugger
    Because the value of T has no effect on the output of the program. If the variable has no effect, why should the processor be bothered in calculating it?
    (Better: why do you have an unused variable in your code.)
    Keep your statements straight. It isn't unused. It is used inside the loop. You don't say a variable is considered unused just because you haven't printed or displayed. Otherwise, all loop counters would be considered unused by your definition, because you aren't printing them any place. See how stupid that is?


    Quote Originally Posted by Cactus_Hugger
    There was a thread awhile ago where a guy had this problem. His whole loop was being optimized into the void by the compiler. Rightly so, however.
    People actually use loops to intentionally delay a program occasionally. It's not as common as it once was, but it is done occasionally.


    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    >It takes about 30 seconds.
    Here's my results:
    Without -O3 -> 52 seconds
    With -O3 -> 9 seconds

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,892
    "Unread" then, quzah. Cactus_Hugger is right. The C++ standard says that the semantics of a program are defined by the calls to I/O functions it makes and the sequence of reads and writes of volatile variables, but not the timing of either. Thus, any amount of reads and writes to a non-volatile variable will not, by themselves, influence the semantics of the program, and the compiler is free to do whatever it wants with these instructions. Including, of course, simply removing them.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by CornedBee
    The C++ standard says that the semantics of a program are defined by the calls to I/O functions it makes and the sequence of reads and writes of volatile variables, but not the timing of either.
    Who the ........ are you again? Oh, wait, a better question should be: "Why the ........ should I care what the C++ standard says?" This is the C forum.


    Quzah.
    Hope is the first step on the road to disappointment.

  11. #11
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,892
    Oops. Whatever. C standard probably says the same thing.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  12. #12
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Actually it's close. However, the standard doesn't say optimization has to take effect. It, from everything I'm seeing, says "optimizaiton may..." do this or that.

    Which is why I said, "why should it"? It doesn't have to.

    However, since this has been drug out so much, and I've nothing better to do than to drag it out more...

    We don't actually see the declaration of any of those varaiables. Now, had he actually posted the code in its entirety, we might be at a different conclusion. Or rather, I might be agreeing here. However, because I like to argue points of the standard, we don't know how any of those variables are declared. They could be volatile.

    In which case, they won't be optimized out, even if they're never part of any output. Also, there are fun little things with optimization, where if it can't be sure, it won't remove it.

    Anyway, the key with optimization is the word may.


    Quzah.
    Hope is the first step on the road to disappointment.

  13. #13
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,892
    Oh yeah, they just might be volatile

    Why, though? Well, because any good compiler should have good enough flow analysis to do it, of course!
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  14. #14
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote Originally Posted by CornedBee
    Oops. Whatever. C standard probably says the same thing.
    FWIW
    Last edited by Dave_Sinkula; 09-05-2006 at 08:00 PM. Reason: Fixed link, but it can be pokey.
    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.*

  15. #15
    ... kermit's Avatar
    Join Date
    Jan 2003
    Posts
    1,528
    Quote Originally Posted by swoopy
    >It takes about 30 seconds.
    Here's my results:
    Without -O3 -> 52 seconds
    With -O3 -> 9 seconds
    Hey Swoopy, what version of gcc are you running. Also, what processor?

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

Similar Threads

  1. Issue with program that's calling a function and has a loop
    By tigerfansince84 in forum C++ Programming
    Replies: 9
    Last Post: 11-12-2008, 12:38 PM
  2. Need help with a program, theres something in it for you
    By engstudent363 in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 12:41 PM
  3. Replies: 4
    Last Post: 02-21-2008, 09:39 AM
  4. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM

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