• LogicDaemon (unregistered) in reply to Rene
    Rene:
    I feel dumb. I can't find the integer overflow. :(

    In more or less every DOS compiler you'll find, int defaults to short, aka a 16-bit integer. 0x000F423F > 0xFFFF

    and it is signed int by default, i.e. INT_MAX = 0x7FFF

  • Andy (unregistered) in reply to mallard
    mallard:
    The C# compiler in VS2008 certainly doesn't. Built in release mode with optimisation: Source:
    static void Main(string[] args) { for (int i = 0; i < 100000; i++) ; Console.WriteLine("Hello World!"); }

    Disassembly (from Lutz Roeder's .NET Reflector):

    private static void Main(string[] args) { for (int i = 0; i < 0x186a0; i++) { } Console.WriteLine("Hello World!"); }
    I thought it was the JIT compiler, which compiles CIL (a.k.a. MSIL) into machine code, that does the optimization in .NET.
  • Arancaytar (unregistered)

    ... at least he is honest.

  • (cs) in reply to Zygo
    Zygo:
    Zygo:
    GCC 4.1 (and possibly earlier versions) does optimize away loops...

    ...if used with -O2 (maybe -O1 as well). Without a -O flag, or with -O0, GCC won't do any optimizations at all, not even trivial ones.

    So you're saying that if you turn off all optimization your compiler doesn't optimize?

    I'm shocked!

  • (cs)

    Turbo C++ 3.0, a 1992 compiler, does not optimize the empty loop!

       ;	
       ;	int main(int argc, char **argv)
       ;	
    	assume	cs:_TEXT
    _main	proc	near
    	push	bp
    	mov	bp,sp
    	push	si
       ;	
       ;	{
       ;	        int i;
       ;	
       ;	        printf("Hello\n");
       ;	
    	mov	ax,offset DGROUP:s@
    	push	ax
    	call	near ptr _printf
    	add	sp,2
       ;	
       ;	
       ;	        for(i = 0; i<10000; i++) {;}
       ;	
    	xor	si,si
    	jmp	short @1@86
    @1@58:
    	inc	si
    @1@86:
    	cmp	si,10000
    	jl	short @1@58
       ;	
       ;	
       ;	        return 0;
       ;	
    	xor	ax,ax
       ;	
       ;	}
       ;	
    	pop	si
    	pop	bp
    	ret	
    _main	endp
  • John (unregistered) in reply to Alcari

    You didn't work on Vista, did you?

  • [ICR] (unregistered)

    "for (i=0; i<10; i++) {;}

    would be optimised to NOP x 10 by most compilers set to 'unroll loops'? And would they then remove redundant NOPs? "

    Don't forget to set i to 9 as well.

  • (cs) in reply to [ICR]
    [ICR]:
    "for (i=0; i<10; i++) {;}

    would be optimised to NOP x 10 by most compilers set to 'unroll loops'? And would they then remove redundant NOPs? "

    Don't forget to set i to 9 as well.

    I'd rather set it to 10, but if i is not used outside the loop then I would not want it to even exist!

  • JimM (unregistered) in reply to AdT
    AdT:
    Ben:
    Probably because that loop actually does something?

    It's amazing how many people don't understand the C# syntax although in the case of this loop, it's absolutely identical to that of C or C++.

    And also to Java, javascript, perl, php... anyone else want to add some more? ;^)

  • Bob Holness (unregistered) in reply to Crash Magnet

    You remember "The first 80% of the project take 20% of your time, the last 20% of the project takes 80% of the time." as the 90/10 rule!?

  • AdT (unregistered) in reply to Kiss me I'm Polish
    Kiss me I'm Polish:
    Someone wrote "xor eax, eax" instead of "mov eax, 0". Damn, I love it. You save a cycle!

    You don't save a cycle but some code size. Compilers (and assembler programmers) have used this idiom for a long time to avoid the need for an immediate 0 in the code segment. Basically, when you write

    mov eax, N

    where N is a constant, the assembler will generate the opcode for "mov eax, (immediate)" followed by N as a 32-bit value. If you even use rax, you get a 64-bit immediate. xor eax, eax however does not require an immediate so results in a much smaller instruction.

    Ironically, using xor eax,eax instead of mov eax,0 could actually slow down execution because the false read dependency can stall out-of-order execution as it is used in modern x86 processors. Because the idiom is so widely used, however, processors treat instructions like this as a simple write, thus avoiding this penalty.

    By the way, the nop mnemonic in x86 assembler is just an alias for xchg eax,eax (assuming 32-bit operand mode). It, too, is special-cased in the processor to avoid false read and in this case also write dependencies.

  • Guido (unregistered) in reply to sweavo

    So ... in those days they didn't have optimizing compilers?

    Mind you, I was still dabbling in GWBasic back then...

  • 543 (unregistered) in reply to mallard
    mallard:
    The C# compiler in VS2008 certainly doesn't. Built in release mode with optimisation:

    But C/C++ compile into machine code, everything what is in compiled code will be executed. Isn't C# code optimized on-the-fly like Java in JVM?

  • PAG (unregistered)

    http://blogmiel.blogspot.com/

    Surely it compiles into machine code but it can't always be perfectly optimized for every processor out there.

  • [ICR] (unregistered)

    "I'd rather set it to 10, but if i is not used outside the loop then I would not want it to even exist!"

    Sorry, you're right about it being 10. But from the code fragment you can't tell that it's not used outside the loop, but you can tell it is in scope outside the loop (since it's not "for (int i = 0...")

  • Tottinge (unregistered) in reply to Benjamin Normoyle

    Actually, the two I know are:

    1. Typically 80% of your problems are in 20% of your code/process/etc.
    2. 20% of the people do 80% of the work
  • Mark (unregistered)

    Hilarous.

  • (cs)

    This reminds me of the story on TDWTF about a guy who wrote some scanner software and found a way to speed it up. It was so fast the customer didn't believe the software actually worked because he didn't have to wait, and the programmer had to slow it down. Later he had to speed the software up again.

  • Cloak (unregistered) in reply to Ben
    Ben:
    mallard:
    Mick:
    gcc4ef3r:
    uh, wouldn't the compiler optimize that away? i mean, depending on the intelligence of the compiler...

    I read statements like this again and again, but I'll be damned if I've ever seen a compiler do that. Ok, ok, I've only used the compiler that comes with (various versions of) Visual C++ but it is supposed to optimize some and even with full optimizations on in a release build it's never optimized anything like this away that I've found.

    The C# compiler in VS2008 certainly doesn't. Built in release mode with optimisation: Source:
    static void Main(string[] args) { for (int i = 0; i < 100000; i++) ; Console.WriteLine("Hello World!"); }

    Disassembly (from Lutz Roeder's .NET Reflector):

    private static void Main(string[] args) { for (int i = 0; i < 0x186a0; i++) { } Console.WriteLine("Hello World!"); }

    Probably because that loop actually does something?

    well it increments the counter, doen't it?

  • Cloak (unregistered) in reply to clively
    clively:
    Ben:
    That is a WTF? No

    That's a GREAT IDEA

    I really hope none of you guys work for Microsoft.

    Under Windoze, even counting the counters does take soooo much time, but when the counters are actually counting aie, aie, aie

  • Cloak (unregistered) in reply to AdT
    AdT:
    Matthew:
    Hell, in a system like DOS, you may not even make it to the point of overflowing i before the system hangs because you wrote over some video buffer or something.

    What? I've done some video programming under DOS and if there was a memory area with fixed address that you wanted to overwrite with zeroes, it was the video RAM. And no, the system would not hang if you did this.

    The system would rather hang (or probably crash in a more spectacular way) if you overwrote some hardware interrupt handler or some code/data structures used by such a handler. You could prevent that by executing CLI before the loop. Of course that would only make any sense if you wanted to kick DOS from memory altogether, for example to load your own OS instead.

    but when you start wrting into F000 and above the situation changes

  • Cloak (unregistered) in reply to Intelligent Layman
    Intelligent Layman:
    > Don't forget it's 1987.

    It's not pretend-to-be-a-time-traveler day. You must really be a time traveller.

    A real-time traveller

  • Henry Miller (unregistered) in reply to [ICR]
    [ICR]:
    "I'd rather set it to 10, but if i is not used outside the loop then I would not want it to even exist!"

    Sorry, you're right about it being 10. But from the code fragment you can't tell that it's not used outside the loop, but you can tell it is in scope outside the loop (since it's not "for (int i = 0...")

    Unless you know how the compiler puts things on the stack. In which case

        int *j = (int *)(&j + 1);
        for(int i; i<10 ;++i); 
        // i not in scope
        foo(*j);  // j is a pointer to i.
    
    

    The above is of course undefined behavior if not outright illegal. I'd have to study to standard to be sure which. Come to think of it I think this is one area where C and C++ are different. Your compiler is likely to pass it though, if only because you told it to shut up.

  • Talliesin (unregistered) in reply to Matthew
    Matthew:
    My point is that the OBVIOUS error in that code sample was picking a seemingly arbitrary point in memory to write zeros. The integer overflow was actually rather subtle.
    It could be a known memory address in a fixed-memory system. It could be a special memory address that actually writes to a peripheral of some sort. There are quite a few reasons why this might be done in certain low-level cases.

    It's certainly suspicious code, but it's something to question, not necessarily something to declare a bug.

  • Jimmy the K (unregistered)

    Doesn't i cycle between -32768 and 32767? I.e. always less than 1000000. Infinite loops really slow things down.

  • Mark (unregistered)

    The real WTF is that Al Gore hadn't invented the interwebs yet.

    Otherwise, hilarious story. Loved it.

  • (cs) in reply to MS
    MS:
    I think you mixed them up. The 80/20 says that 80% most useful functionality takes only 20% of the total implementation effort, so you better convince your customer to drop the rest. The 90/10 says that implementing 90% of the system takes 90% of the planned implementation time, but the remaining 10% takes another 90% planned time :-P
    As already mentioned several times, this is the Ninety-Ninety Rule.
  • Mark (unregistered)

    Did Wayne also invent the Bozo Sort?

  • bandit (unregistered) in reply to Crash Magnet

    I always thought it meant 80% of the complexity was in 20% of the code. There's probably 1000000 definitions though...

  • Niki (unregistered) in reply to Benjamin Normoyle
    Benjamin Normoyle:
    I thought 80/20 was how to completely bullshit situations: when you need a percentage, use either 80 or 20 percent as your number. E.g. : "80 % of this department is slacking off," "20% of companies give free soda to their employees," "20% of experts say YO MAMA."
    I always heard that it was 80% of the work was done by 20% of the people working. Actually I usually heard it as the 90/10 rule, but maybe at the time I was in a WTFesque job environment.
  • Reed (unregistered) in reply to Rene

    Think 16 bit man.

  • (cs) in reply to Kain0_0
    Kain0_0:
    I agree with you, to be truly ethical such loops (without another purpose like synchronisation, interfacing with a human, etc) shouldn't be used as a general rule of thumb.

    On the other hand, if your boss is milestone minded and only pays attention to say runtime (or other very small minded and limited statistics) techniques like the above can be useful to show that progress is being made. To be ethical in this case you actually need to have made progress with program faults/refactoring/scaffolding.

    There is still nothing ethical about it. Whether you are doing actual work on not. There are ways of measuring productivity, other than "the program runs faster"

    And on top of that you are writing a Busy Wait loop. Don't do that. Play nice with others and use a Sleep or its equivalent.

  • Arlie (unregistered)

    The really hilarious thing is that a lot of modern C compilers will remove the entire for loop, if they can determine that what's inside the loop has no side effects. And {;} certainly has no side effects.

  • (cs) in reply to Edward Royce
    Edward Royce:
    Hmmmm.

    This is why I always include something very obviously wrong in the UI of any application I'm trying to get accepted by management. For some odd reason management types simply cannot accept a program as-is. Instead they all absolutely must make some sort of change to the program or else the program simply isn't "theirs".

    So I include obvious UI defects that they can easily see and order changed. Otherwise they'll really muck up a program and make life a lot harder.

    Interesting. Scott Adams' "The Joy of Work" suggests something similar:

    "Before making any proposal to your boss, insert some decoy steps. The decoys are elements of your plan that you don't actually intend to do. Make sure the decoys are the most obvious parts of your plan." ... "Your boss will notice that the third bullet 'doesn't fit'. He'll demand that you get rid of that step. Put up some resistance (just for show) and then reluctantly agree."

    The example he gives is:

    • Research the market for new toys
    • Design toy • Assassinate the president of Chile
    • Produce toy
  • widget (unregistered)
    for(i=0;i<1000000;i++) {;}
    

    And the best part is any optimizing compiler worth its salt will remove the effects of this "speed-up loop"

  • AdT (unregistered) in reply to 543
    543:
    But C/C++ compile into machine code, everything what is in compiled code will be executed. Isn't C# code optimized on-the-fly like Java in JVM?

    .NET byte code is optimized on-the-fly. This includes C# but also VB.NET, C++/CLI and numerous other languages.

    Yes, I love threads where I can show off my super-smartass powers. Just keep that kryptonite away from me.

  • [ICR] (unregistered) in reply to AdT

    "VB.NET, C++/CLI" That makes it sound like C++ and CLI are the same :S

  • chrome (unregistered) in reply to widget
    widget:
    for(i=0;i<1000000;i++) {;}

    And the best part is any optimizing compiler worth its salt will remove the effects of this "speed-up loop"

    read back a bit; the conclusion is that it's dependent on the flags and compiler used. GCC doesn't, under any flag.

  • Mickeyd (unregistered)

    Gee and all these years I thought that you figured out the time it would take, divided by two multiplied the result by 4 and added 2. E.G. Task time=((ET/2)*4)+2 Where "ET" equal actual time required.

  • Dave (unregistered) in reply to AdT
    AdT:
    Changing the loop condition to "false", which is equivalent to what Visual C++ does, is, however, invalid with or without a volatile qualifier on someThreadVariable.
    Please cite the relevant section of the C standard that supports your claim. Both the MSVC and gcc teams disagree with you. Here's a free copy of the C99 draft: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf
  • bg (unregistered) in reply to Jay
    Jay:
    Also, it really should check the system clock rather than just counting. That way you'd get consistent performance savings regardless of the speed of the processor.
    But that way you would have to remove zeroes instead of just telling the customers to buy faster hardware ;-)
  • lmb (unregistered)

    This is not WTF. This is BOFH.

  • anon (unregistered) in reply to widget
    widget:
    for(i=0;i<1000000;i++) {;}

    And the best part is any optimizing compiler worth its salt will remove the effects of this "speed-up loop"

    It better bloody not. If go to the effort of adding a loop that increments an integer a million times, I bloody well want that integer incremented a million times.

    Also, in 1990, most compilers were pretty crappy. In fact, in 2008 most compilers are still pretty crappy.

  • (cs) in reply to AdT
    AdT:
    Kiss me I'm Polish:
    Someone wrote "xor eax, eax" instead of "mov eax, 0". Damn, I love it. You save a cycle!

    You don't save a cycle but some code size. Compilers (and assembler programmers) have used this idiom for a long time to avoid the need for an immediate 0 in the code segment. Basically, when you write

    mov eax, N

    where N is a constant, the assembler will generate the opcode for "mov eax, (immediate)" followed by N as a 32-bit value. If you even use rax, you get a 64-bit immediate. xor eax, eax however does not require an immediate so results in a much smaller instruction.

    Ironically, using xor eax,eax instead of mov eax,0 could actually slow down execution because the false read dependency can stall out-of-order execution as it is used in modern x86 processors. Because the idiom is so widely used, however, processors treat instructions like this as a simple write, thus avoiding this penalty.

    By the way, the nop mnemonic in x86 assembler is just an alias for xchg eax,eax (assuming 32-bit operand mode). It, too, is special-cased in the processor to avoid false read and in this case also write dependencies.

    As I recall, and it's been twenty years now, the real point of this idiom is to clear various flags as a side effect. It's been around twenty years now, but that's the way I remember it (either on Z80 or i8086).

    And yes, I could look it up, but it's way past my bed-time.

  • Chris M. (unregistered) in reply to Benjamin Normoyle

    No, it's the rule that says your program spends 80% of its time in 20% of its code (so that's the code you should optimize). Or, alternatively, 20% of your code will take 80% of your development man-hours (not necessarily the same 20% that accounts for 80% of your run time).

  • ko1 (unregistered) in reply to sweavo

    Three months after November 1989 is January 1990.

  • Rhialto (unregistered) in reply to foo
    foo:
    Mike:
    Err, maybe I'm missing something--but given the 16-bit overflow, wouldn't the "speed-up loop" be infinite? Or is that the real WTF?

    On a 16-bit machine the loop should run 16960 times.

    Given a loop like

    for(i=0;i<1000000;i++) {;}
    

    with a 16-bit compiler, the constant given would not fit in an int and therefore automatically be a long int. That is the rule given in K&R second edition (1988). The comparison would then be done by comparing an extension to long of i with 1000000. Then, variable i would overflow before reaching 1000000, and the loop would be infinite.

  • Rhialto (unregistered) in reply to Carnildo
    Carnildo:
    with additional guarantees of

    sizeof(void *) == sizeof(int)

    I don't think there were ever C compilers that guaranteed that. And even if there were, they would be so old that they didn't know about "void" yet.
  • fred (unregistered) in reply to Tom

    It is fake: in 1987, a 1 to 1 million loop would take a very very noticeable amount of time (ie: in the seconds magintude order). Having this for each screen refresh ? I call b*s!t.

    Anyway, empty loops in screen updating code on early PC were common because you had "snow" effects if you update the screen too frequently...

  • Marc K. (unregistered)

    That explains SO much. msiexec.exe must be full of these "speedup loops". That's the only thing that can possibly explain why MSI installs are so excruciatingly slow that you want to gouge your eyes out with a sharp object at the thought of running an MSI install.

Leave a comment on “The Speed-up Loop”

Log In or post as a guest

Replying to comment #:

« Return to Article