Bugs popping up only under optimization

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
LucasBrown
Posts: 299
Joined: Thu Apr 15, 2010 2:57 am UTC
Location: Poway, CA

Bugs popping up only under optimization

Postby LucasBrown » Fri Dec 20, 2013 5:46 am UTC

I've been around programming long enough to have heard horror stories of code that does exactly what it's supposed to when fed into a plain compiler but, when compiled with -O2 or -O3 enabled, starts misbehaving.

I have not been around programming long enough to have actually encountered such code.

Does anyone have examples they can share so I know what I should be wary of?

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6579
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Bugs popping up only under optimization

Postby Thesh » Fri Dec 20, 2013 6:50 am UTC

This *should* only happen if you are relying on undefined behavior. If you are entirely using defined behavior and it still causes problems, then it is a bug. There was a recent paper on compiler optimization introducing security holes here:

http://pdos.csail.mit.edu/~xi/papers/stack-sosp13.pdf
Summum ius, summa iniuria.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Bugs popping up only under optimization

Postby korona » Fri Dec 20, 2013 9:26 am UTC

Yeah they should only happen if you rely on undefined behavior. There were a few gcc bugs in the past that broke your code even if you didn't do that. But the first rule if you think that your compiler is buggy is that your compiler is not buggy.

I always compile with -O3 and -g -O3 for debugging. I only switch off -O3 if it is necessary to debug the application. But that might not be a good idea for everyone. At work I'm mostly developing programs that rely on high performance so not enabling -O usually decreases the runtime from a few seconds to a few minutes. Strangely I sometimes encounter bugs when NOT compiling with -O3 because it optimizes away buggy parts :D.

EDIT: Interesting paper. I quickly skimmed over it. It seems that they are using SMT (satisfiability modulo theories) to find undefined behavior in programs. SMT has been used in the past to prove the correctness of programs and hardware circuits but I didn't know any application to compiler optimization. Thanks

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Bugs popping up only under optimization

Postby You, sir, name? » Sat Dec 21, 2013 10:29 am UTC

There are a few compiler flags that are there purely to break your code. -ffast-math, for example. But that isn't enabled on any of the -O-levels.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
3rdtry
Posts: 152
Joined: Sat Feb 16, 2013 1:46 pm UTC

Re: Bugs popping up only under optimization

Postby 3rdtry » Mon Dec 23, 2013 5:07 pm UTC

On the other hand, I once saw a project that would only compile with -O2 or -O1. O3 gave weird bugs (understandably, since it was an OS doing low-level stuff with lots of assumptions about how the code is compiled), and -O0 gave a syntax error related to an asm() keyword.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Bugs popping up only under optimization

Postby korona » Mon Dec 23, 2013 6:31 pm UTC

Well written low level code should compile fine with -O3. The Linux kernel does and all hobby kernels I wrote also did.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Bugs popping up only under optimization

Postby EvanED » Tue Dec 24, 2013 3:58 pm UTC

korona wrote:Well written low level code should compile fine with -O3. The Linux kernel does and all hobby kernels I wrote also did.
To be fair, the Linux kernel explicitly disables certain legal optimizations, such as those based on the strict-aliasing requirement (-fno-strict-aliasing), and doesn't work properly if they are enabled (IIRC).

Though I'd be hard-pressed to come up with something that produces a syntax error at -O3 only.

Carnildo
Posts: 2023
Joined: Fri Jul 18, 2008 8:43 am UTC

Re: Bugs popping up only under optimization

Postby Carnildo » Wed Dec 25, 2013 10:52 am UTC

LucasBrown wrote:Does anyone have examples they can share so I know what I should be wary of?


The most common cause is using uninitialized variables.

Code: Select all

int foo()
{
    int x;
    return x;
}


With optimizations turned off, especially if it's compiled in debug mode, it's a good bet this function will return "0". With them turned on, it'll probably return whatever value was left on the stack/in a CPU register by earlier code.

lgw
Posts: 437
Joined: Mon Apr 12, 2010 10:52 pm UTC

Re: Bugs popping up only under optimization

Postby lgw » Thu Dec 26, 2013 10:24 pm UTC

I've seen two somewhat common ways that bugs pop up only under optimization.

The first I've only seen in C++, and isn't really about optimization, but about debug vs retail builds. The standard libraries (for the compilers I've seen) do lots of error checking in debug mode that is gone in a retail build. This can cause errors to move - from early detection with debug to late detection in retail. If you have a typical commercial C++ legacy codebase with half-assed error handling, then errors can "appear" only when building retail, or only when building debug (because they move to a place that has good error detection and reporting from a place that doesn't).

The second happens in many languages: you have a race condition, and building optimized changes who wins the race, or perhaps destabilizes it, and so you only see the error with some build setting (again, it could be optimized or debug that tickles the bug), even though the error always there in your multi-threaded code.

I've never seen a bug in the compiler's optimization logic itself, but there are plenty of ways for a bug to be revealed when you change build settings.
"In no set of physics laws do you get two cats." - doogly

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Bugs popping up only under optimization

Postby korona » Sat Dec 28, 2013 1:25 pm UTC

EvanED wrote:
korona wrote:Well written low level code should compile fine with -O3. The Linux kernel does and all hobby kernels I wrote also did.
To be fair, the Linux kernel explicitly disables certain legal optimizations, such as those based on the strict-aliasing requirement (-fno-strict-aliasing), and doesn't work properly if they are enabled (IIRC).

Yes, you're right and the strict aliasing requirement can be really annoying if you're writing low level code.

Other bugs that I've seen pop up under optimization are reads/writes to non-volatile variables that work correctly without optimization but are omitted completely when optimization is enabled.

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Bugs popping up only under optimization

Postby Jplus » Thu Jan 09, 2014 9:53 am UTC

"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

Derek
Posts: 2181
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Bugs popping up only under optimization

Postby Derek » Sat Jan 11, 2014 12:02 am UTC

Oh I've got a good one.

To start with, here is a fun fact: The floating point registers on x86 are 80 bits wide.

I was writing a raytracer using a kd-tree. A kd-tree partitions space (3d in this case) into boxes, and for my raytracer each box contained lists of polygons and vertices in that box. To perform a ray trace, you check if a ray intersects a box, and then check if the ray intersects any polygons in that box, with the intersection within the box (there is a good reason for this last condition, though I can't remember it right now). This last step is performed by calculating some values, which I'll call t-values, that indicate where on the ray the ray-box intersection occurs, and then comparing these t-values with the t-value for the ray-polygon test.

One last note you need to know: To build the kd-tree I would partition on vertices. This means that the boxes of the kd-trees would sometimes overlap with polygons. I just defined that these polygons would always fall on one side of the parition and moved on. This worked fine in -O0, but in -O3 these polygons started disappearing.

It took some digging, but I eventually found the problem: Double precision arithmetic is performed in the 80-bit wide floating point registers. In -O0, all intermediate calculations are stored on the stack as 64-bit doubles. But in -O3 these values are kept in registers if possible. When I calculated the t-values for the ray-box intersection, these were returned on the stack (or maybe in a struct, I'm not sure), so they were truncated to 64-bits. But when I compared these to the ray-polygon t-value, the ray-polygon t-value was still stored in an 80-bit register. The result is that even if the exact same calculation was performed (because the box and polygon align), the polygon can be compared as lying outside of the box and therefore not render.

There are a couple solutions to this problem. One is to turn on a GCC flag that forces all floating point values to be stored in memory (and thus truncated to 64 bits). Another (which I went with in the end) was to store the polygon on both sides of the partition. I'm sure there are others as well.

The moral of the story: When they tell you that floating point arithmetic is fuzzy, they aren't kidding. The exact same calculation may return different results if one is stored in memory and the other in a register.

alessandro95
Posts: 109
Joined: Wed Apr 24, 2013 1:33 am UTC

Re: Bugs popping up only under optimization

Postby alessandro95 » Sat Jan 11, 2014 6:56 am UTC

Derek wrote:Oh I've got a good one.

To start with, here is a fun fact: The floating point registers on x86 are 80 bits wide.



That is because intel decided to use an extended format (IEEE 754 if I remember correctly) and not the "usual" 64 bit double precision format to have better accuracy in calculations.
I don't know about other languages but assemblers provide an 80 bit wide data type so that you can store floating point results in memory without loss of precision and I'm surprised you cannot do that in C as well!
The primary reason Bourbaki stopped writing books was the realization that Lang was one single person.

Derek
Posts: 2181
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Bugs popping up only under optimization

Postby Derek » Sat Jan 11, 2014 8:04 am UTC

alessandro95 wrote:
Derek wrote:Oh I've got a good one.

To start with, here is a fun fact: The floating point registers on x86 are 80 bits wide.



That is because intel decided to use an extended format (IEEE 754 if I remember correctly) and not the "usual" 64 bit double precision format to have better accuracy in calculations.
I don't know about other languages but assemblers provide an 80 bit wide data type so that you can store floating point results in memory without loss of precision and I'm surprised you cannot do that in C as well!

It wouldn't surprise me if there are compiler specific types for it, but it's not part of the C spec and I was using standard doubles in my code.

EDIT: Apparently "long double" is a standard that supports this option, although it can also represent even larger floating point types.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Bugs popping up only under optimization

Postby jestingrabbit » Sat Jan 11, 2014 3:23 pm UTC

alessandro95 wrote:(IEEE 754 if I remember correctly)


Nah, IEEE 754 only specifies binary 16, 32, 64 and 128 bit formats. You need the extra precision during calculations to get the end result right, but I don't see why you would have the extra wide registers.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Bugs popping up only under optimization

Postby korona » Sat Jan 11, 2014 3:26 pm UTC

I don't see how the increased floating point precision of 80 bits can break calculations. Can you elaborate on what went wrong when working with higher precision?

wumpus
Posts: 546
Joined: Thu Feb 21, 2008 12:16 am UTC

Re: Bugs popping up only under optimization

Postby wumpus » Sat Jan 11, 2014 5:31 pm UTC

jestingrabbit wrote:
alessandro95 wrote:(IEEE 754 if I remember correctly)


Nah, IEEE 754 only specifies binary 16, 32, 64 and 128 bit formats. You need the extra precision during calculations to get the end result right, but I don't see why you would have the extra wide registers.


Nope. At least IEEE754-1985 included "extended precision formats" that allowed 80 bit floats. The 8087 was pretty much designed in parallel with the IEEE-754 and the format tends to match the 8087.

Note that the entire x87 floating point system has been deprecated by Intel after the Pentium2/3 systems and by AMD shortly thereafter. Use the SSE/2/3/4 instructions (which are 64 bits) for anything running on remotely current hardware.

alessandro95
Posts: 109
Joined: Wed Apr 24, 2013 1:33 am UTC

Re: Bugs popping up only under optimization

Postby alessandro95 » Sat Jan 11, 2014 5:46 pm UTC

wumpus wrote:
jestingrabbit wrote:Note that the entire x87 floating point system has been deprecated by Intel after the Pentium2/3 systems and by AMD shortly thereafter. Use the SSE/2/3/4 instructions (which are 64 bits) for anything running on remotely current hardware.


Now that you pointed it out what surprises me is that with -O3 the compiler used FPU instructions instead of SSE
The primary reason Bourbaki stopped writing books was the realization that Lang was one single person.

Derek
Posts: 2181
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Bugs popping up only under optimization

Postby Derek » Sat Jan 11, 2014 6:28 pm UTC

korona wrote:I don't see how the increased floating point precision of 80 bits can break calculations. Can you elaborate on what went wrong when working with higher precision?

In short, I performed the same calculation twice and expected the same result, but intermediately one of those calculations was stored in 64 bits of memory forcing it to round, while the other was held in 80-bit registers. The subsequent comparison therefore unexpectedly failed. If both numbers were rounded to 64 bits (as in -O0), then the problem went away.

wumpus wrote:Note that the entire x87 floating point system has been deprecated by Intel after the Pentium2/3 systems and by AMD shortly thereafter. Use the SSE/2/3/4 instructions (which are 64 bits) for anything running on remotely current hardware.

Interesting, I didn't know this. I did some looking into it and found that apparently x87 has trig instructions and SSE does not, so x87 can be faster for those (ray-plane intersection tests are just addition and multiplication though).

heatsink
Posts: 86
Joined: Fri Jun 30, 2006 8:58 am UTC

Re: Bugs popping up only under optimization

Postby heatsink » Tue Jan 28, 2014 5:53 pm UTC

There was a bug of this kind in the SPEC benchmarks, which are used by compiler developers to show how good their compiler optimizations are.

http://www.spec.org/cpu2006/Docs/faq.html#Run.05

The bug is an out-of-bounds array read in a loop. A certain version of GCC would compile it to an infinite loop. The compiler assumed that out-of-bounds array reads do not happen, inferred that the loop would never reach the condition that would cause an out-of-bounds read, and generated an infinite loop. That is permitted according to the definition of C, which is a reminder that C is a weird and complicated language.

http://blog.regehr.org/archives/918

User avatar
hotaru
Posts: 1045
Joined: Fri Apr 13, 2007 6:54 pm UTC

Re: Bugs popping up only under optimization

Postby hotaru » Tue Jan 28, 2014 10:15 pm UTC

heatsink wrote:There was a bug of this kind in the SPEC benchmarks, which are used by compiler developers to show how good their compiler optimizations are.

http://www.spec.org/cpu2006/Docs/faq.html#Run.05

The bug is an out-of-bounds array read in a loop. A certain version of GCC would compile it to an infinite loop. The compiler assumed that out-of-bounds array reads do not happen, inferred that the loop would never reach the condition that would cause an out-of-bounds read, and generated an infinite loop. That is permitted according to the definition of C, which is a reminder that C is a weird and complicated language.

http://blog.regehr.org/archives/918

i find this a bit odd:
It would be reasonable to ask the larger question of whether a compiler should be breaking code like this, but it’s late to be opening that can of worms, so I’ll leave this discussion for another day (or for the comments).


the compiler isn't breaking the code. if there's undefined behavior, the code is already broken, and should be fixed. changing the compiler to try to fix broken code at the expense of performance for good code seems backwards to me.

Code: Select all

factorial product enumFromTo 1
isPrime n 
factorial (1) `mod== 1

heatsink
Posts: 86
Joined: Fri Jun 30, 2006 8:58 am UTC

Re: Bugs popping up only under optimization

Postby heatsink » Tue Jan 28, 2014 10:55 pm UTC

hotaru wrote:if there's undefined behavior, the code is already broken, and should be fixed.

The author of that blog believes that undefined behavior should not be exploited for optimization because the practical cost of run-time errors and software vulnerabilities outweighs the benefit of faster compiled code. He's written other blog posts to justify that position. That's where he's coming from when he says the compiler is breaking the code.

Divinas
Posts: 57
Joined: Wed Aug 26, 2009 7:04 am UTC

Re: Bugs popping up only under optimization

Postby Divinas » Mon Feb 03, 2014 2:56 pm UTC

As a game dev, I'm fairly well acquainted with such bugs.

In my experience, most of those are not caused by undefined behavior, but because of bad synchronization between stuff. When running the code optimized, stuff happens faster. Things which have a fixed update time (for example, once every frame) get desynced with stuff that happens based on real time. Some issues like 'is A, which depends on B, get loaded before B, and therefore breaks', and so on. Basically - a lot of race conditions, that only manifest as the FPS is higher :)

nomadiq
Posts: 18
Joined: Wed Apr 27, 2011 8:57 pm UTC

Re: Bugs popping up only under optimization

Postby nomadiq » Sat Mar 15, 2014 3:38 pm UTC

I have some code with this bug. I'll post it at the end. It is basically code to simulate a lottery. You set what numbers to match and you test to see how many times you get the numbers you ask. I loop through the process 10x the expectation. So the probability is about 1 in 76767600 so I loop 767676000 times and expect about 10 hits.

This code works when compiled without -O3 on my intel based systems (Linux box, Mac OS X machine) but fails when I compile with -O3, suddenly it never matches. The weird thing is, if I compile this on my raspberry pi (ARM CPU) it works just fine with -O3 or without -O3, and with -O3 it is about twice as fast.

I'll also add that the numbers I use to test a match are sequential... so they are 1, 2, 3, 4, 5, 6 (just as likely as any other set of numbers). Now, if I don't select '1' but say change it to '10' it works fine with -O3 compilation option on my intel processors.

I am no coder so I don't know if my code is "correct" but feel free to pick over it.....

Code: Select all

#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>



void shuffle(int *array, size_t n)
{
    int i, j, t;
    if (n > 1)
    {
        size_t i;
        for (i = n - 1; i > 0 ; i--)
        {
          size_t j = (unsigned int) (drand48()*(i+1));
          int t = array[j];
          array[j] = array[i];
          array[i] = t;
        }
    }
}


int main (int argc, const char * argv[])
{
    int poolsize = 40;
    int choosesize = 6;
    int pool[poolsize];
    int chosen[choosesize];
    int supsize = 20;
    int sup[supsize];
    int i,oi,ii = 0;
    int counter = 0;
    int win = 0;
    int done = 0;
       
    unsigned long long repeat;
 
    chosen[0] = 1;
    chosen[1] = 2;
    chosen[2] = 3;
    chosen[3] = 4;
    chosen[4] = 5;
    chosen[5] = 6;

    int supchosen = 1;

    struct timeval tv;
    gettimeofday(&tv, NULL);
    int usec = tv.tv_usec;
    srand48(usec);


   for (repeat = 0; repeat < 767676000; repeat++) {

        counter = 0;

        for (i = 0; i <= poolsize; i++) {
                pool[i] = i+1;
        }

        for (i = 0; i <= supsize; i++) {
                sup[i] = i+1;
        }

        shuffle(pool, poolsize);
        shuffle(sup, supsize);

        for (oi=0; oi < choosesize; oi++) {
                for (ii=0; ii < choosesize; ii++) {
                        if (chosen[oi] == pool[ii]) {
                                counter++;
                        }
                }
        }
        if ((counter == choosesize) && (sup[0] == supchosen)) {
                win++;
                printf("holly crap!\n");

        }
   }
   printf("%i,", win);
   return 0;
}

User avatar
Xenomortis
Not actually a special flower.
Posts: 1448
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Bugs popping up only under optimization

Postby Xenomortis » Sat Mar 15, 2014 4:10 pm UTC

You have instances of undefined behaviour. In particular, go past array bounds a few times.

Code: Select all

for (i = n - 1; i > 0 ; i--)
{
    size_t j = (unsigned int) (rand()*(i+1));
    int t = array[j];
    array[j] = array[i];
    array[i] = t;
}

I'm pretty sure it's possible for j to exceed the m, the size of the array passed to shuffle.

Code: Select all

for (i = 0; i <= poolsize; i++) {
    pool[i] = i+1;
}

for (i = 0; i <= supsize; i++) {
    sup[i] = i+1;
}

Two clear overflows; the loops should use '<' instead of '<='.

With undefined behaviour, all bets are off. The compiler can do anything.
I'm a little surprised you don't crash; MSVC's output crashed.

And please be consistent with your indentation.
Image

nomadiq
Posts: 18
Joined: Wed Apr 27, 2011 8:57 pm UTC

Re: Bugs popping up only under optimization

Postby nomadiq » Sat Mar 15, 2014 5:28 pm UTC

Thanks for pointing out the problems in my code! I figured someone would correct me in short time. And yes my indentation is terrible. Code written in between other tasks (not coding) so I wasn't paying much attention.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 4 guests