LWN: Comments on "Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks"

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

jwakely — 2013-04-02T22:56:40+00:00

It should be called -Over9000 though

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

hummassa — 2013-04-02T21:18:39+00:00

It's on my default makefile since forever, because clang does not like -O5 and beyond and I am too lazy to look up which is the biggest effective level for each compiler...

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

nix — 2013-04-02T20:08:02+00:00

I've seen people use -O4, -O6, -O64 ("it's a nice round number and higher than 3" he said, so at least he knew what he was aiming for), and of course glibc, of all things, used -O99 for donkey's years. GCC obviously needs an "-Olots" for these people.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

jwakely — 2013-04-02T19:17:20+00:00

You know GCC doesn't have a -O4 optimisation level, right? ;)

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

hummassa — 2013-04-02T17:30:50+00:00

I am answering to my own comments in this subthread, and it really feels like I am losing my mind... :-D
anyway, I tried this with -O4 and both


for(auto x: d) satd += abs(x);

and


auto satd = accumulate(begin(d), end(d), 0, [](int a, int x) { return a+abs(x); });

generated the same code, roughly:


movl	(%rax), %edx
movl	(%rax), %ecx
addq	$4, %rax    
sarl	$31, %edx   
xorl	%edx, %ecx  
subl	%edx, %ecx  
leaq	64(%rsp), %r
addl	%ecx, %ebx  
cmpq	%rax, %rdx  
jne	.L3	#,

which seemed nice to me.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

hummassa — 2013-04-01T16:57:20+00:00

Actually, "properest" version would be

auto satd = accumulate(begin(d), end(d), 0, [](int a, int x) { return a+abs(x); });

But I suppose that has the potential to be less efficient, at least it involves some function calls here...

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

hummassa — 2013-04-01T16:19:32+00:00

isn's the "proper" c++ version

for(auto x: dd)
satd += abs(x);

?? (generates the same code, no errors and READABLE...)

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

khim — 2013-04-01T14:51:48+00:00

Screen real estate is not measured in tokens. Inches, centimeters, may be pixels, but most definitely not tokens. But this measure it's shorter. Is it worth it? That's debatable and depends very much on the individual, but of course it's separate issue.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

HelloWorld — 2013-03-27T22:27:45+00:00

> and the mistake in the chain of reasoning is the very first one where it assumes that the loop variable will never be out of range.
That's not the chain of reasoning. The reasoning is that if the loop variable is out of range, the program's behaviour is undefined, thus not testing the variable is just as valid as testing it or doing something else entirely.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

HelloWorld — 2013-03-27T19:23:25+00:00

Use the string.h, Luke!

static inline int framelen(char s[]) {
  return strnlen(s, 256);
}

;)

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

HelloWorld — 2013-03-27T19:17:04+00:00

> It may not run faster, but it certainly is shorter
Uh, no it's not. The obfuscated version is 25 tokens, the sensible one is 22 tokens. Sure, if you use conventional formatting, you'll end up with one more line for the normal version, but nobody says you have to do that...

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

dlang — 2013-03-27T17:43:29+00:00

The balance between clear and concise will vary depending on how familiar you are with the language in question.

the obfuscated C contest shows clear examples where concise is far more important than clear.

But the line itself if rather fuzzy.

hijacking an example from elsewhere. If you have a bucket filled with water and start punching holes in the bottom, when does it stop being a bucket that leaks and start being a sieve? At some point it will be very clear that you have passed the line, but exactly where the line is is hard to define.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

redden0t8 — 2013-03-27T15:16:22+00:00

Interesting observation, it really made me think.

I'm definitely a C-thinker, but over-shortening code (like in this article's example) really makes me cringe. I really don't understand the drive to make pieces of code as short as possible. I'm more along the lines of "clear and concise", with "clear" being more important than "concise". I guess you could think of it as writing code so as to optimize the time it takes to read and follow, rather than optimizing the line count.

Then again maybe this comes from being a hobbyist programmer and not a professional... maybe I just have a different definition of "clear" lol.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

nye — 2013-03-27T13:32:39+00:00

Oh please. Take your macho trolling somewhere else.

access off end of array

brouhaha — 2013-03-26T16:52:35+00:00

Yes, but the 6809 came along much later than the PDP-11, so it's not relevant to discussion of where the C pre/post-increment/decrement operators came from.

access off end of array

tjc — 2013-03-26T16:26:16+00:00

I think a warning flag would be a step in the right direction, and maybe as far as things should to go. -Wall doesn't warn against this sort of thing, but since the "all" in -Wall is not really all, there might already be a flag for this.

access off end of array

hummassa — 2013-03-26T16:04:28+00:00

I know for a fact the 6809 microprocessors had some instructions "load/store from pointer with post/pre-auto-increment/decrement" so that one of:

a = *b++
a = *++b
a = *b--
a = *--b
*b++ = a
*++b = a
*b-- = a
*--b = a

was a single instruction; they made easy to implement real fast stacks and queues, and zero-terminated strings (because "a = *b++" &c set the Z flag if the char was zero).

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

khim — 2013-03-26T09:44:13+00:00

It may not run faster, but it certainly is shorter and a lot of guys (including me) always try to make code shorter.

It's funny, really: it looks like I've finally found where these clashes come from. Less them two years ago I had no idea and struggled to understand, but now, after a lot of discussions with other guys on an important piece of code in our project, I know that there are two types of programmers: the ones who think about their program in C (C++, C#, Java, JavaScript (uh-oh), PHP (ugh), Python, etc) and the ones who think about their program in English (Hebrew, Mandarin, Russian, whatever).

For the "C thinkers" size of the code is very important (the shorter it is the easier to observe large chunks of code at once) and most comments are just useless distraction (and/or admission of defeat: what, you mean this piece of code is so convoluted and cryptic that you can't understand it just from a C code... gosh I think it's time to give up and add couple of comments). Sure, high-level interface must be described in human language (C is great for low-level bit manipulations, but for description of relationship between HTML document and DOM tree, created from said document it's too low-level), but everything below it must be understandable from the code.

For "English thinkers" comments are vital piece of the information: they expect to fully understand the program from comments alone and perceive the need to actually read C code as something degrading (or as necessary evil when something does not work). Even if they read C code they usually just compare it to the comment near it (and they become angry when they found no comments to compare the code to). For them size of code is less important (because they only ever perceive it in small pieces) and verbose style is, actually, better (it makes it easier to compare code to comments).

I'm not sure which style is better, but I found that C thinkers usually produce fast and efficient code which may contain small, localized bugs (the code in article is prime example) while English thinkers produce code which is verbose and slow yet still contain plethora of bugs - but these bugs are distinctly different: instead of off-by-one errors or simple "++" vs "--" mixup we have cases where one module produces subtly broken object which is mishandled by another module and then everything blows up in a third one.

Easy to understand why: there are no "safety net" in C thinkers code thus localized bugs are easy to miss, but interfaces are very narrow and well-defined while English thinkers produce the code which is locally correct but globally they are hopeless because there are so many interactions between different pieces of code. Think XBox or Wii bootloader code (few bugs in the initial runs which were eventually ironed out and now there are no new bugs in sight) vs JVM code (there are endless bugs without the end in sight - and most of them are because different pieces of code interact "quirckly").

access off end of array

khim — 2013-03-26T09:00:29+00:00

Actually, the ++/PDP-11 connection is urban legend -- see "More History", paragraph 2 at this link:

The Development of the C Language

Well, your own link shows that it's not an "urban legend" but more like oversimplification: This is historically impossible, since there was no PDP-11 when B was developed. The PDP-7, however, did have a few `auto-increment' memory cells, with the property that an indirect memory reference through them incremented the cell. This feature probably suggested such operators to Thompson; the generalization to make them both prefix and postfix was his own.

While factually incorrect (C design predates PDP-11) both "++" in C and "(RX)+" in PDP-11's assembler come from the same source.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

mlopezibanez — 2013-03-26T08:39:32+00:00

No, the assumption is how C programs work. It is in general impossible to tell if there is going to be an out-of-bounds access without checking every access. If you want code that checks that, then wrap every array access in the equivalent of vector.at() and let the compiler try to remove redundant checks.

Of course, GCC could do better at static analysis and warning about such cases, but that is a different problem from optimization, and GCC needs new developers that are interested in such things.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

mlopezibanez — 2013-03-26T08:26:20+00:00

The code that is always true might not have been even written by the user, but come from a system header file, a macro expansion (but not a constant expression), or generated code (very common in C++), from transformations of the code that don't match any original code, etc.

Regardless, there are very few GCC developers, so if you think you could do something better, you should give it a try. Sometimes you realize how difficult your obvious thing turns out to be, and other times you realize that it was indeed obvious but nobody had time to do it before. I can tell you from personal experience that there is a lot of the latter in GCC.

access off end of array

alankila — 2013-03-26T08:09:51+00:00

I guess there would be many ways to improve C, which largely are about breaking expressions that used to work but which are ugly, confusing and sometimes semantically broken. Perhaps GCC can slowly over time nudge people away from doing multiple things in a single statement -- that definitely sounds like an improvement.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

jezuch — 2013-03-26T08:02:09+00:00

> Exactly. Looks like obfuscated C contest stuff ...

I guess it's a result of a *very* popular misconception that the more you cram into a single statement the faster it is ;)

Seeing how the compiler unwinds all of this stuff is an eye-opening experience. We, humans, have a very limited operating memory; the compiler can analyze much, much larger structures than we imagine it can.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

bronson — 2013-03-26T05:31:07+00:00

I think ifdefs would fall apart too quickly to be of much use.

Compiler warnings would too... If the compiler emits 22 "might be true" warnings, and 21 of them are spurious, what are the chances I'll catch the meaningful one? Knowing me, probably next to nil.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

dlang — 2013-03-26T05:10:23+00:00

and the mistake in the chain of reasoning is the very first one where it assumes that the loop variable will never be out of range..

The rest of the optimizations make sense, but that first one is optimistic thinking on the part of the compiler writer.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

iabervon — 2013-03-26T04:12:28+00:00

It's not actually able to prove that (or, really, it's not set up to consider proving that type of thing). It's actually just making a series of optimizations: first, it assumes that there won't be an out-of-bounds access, then it determines that this means that the loop can't exit normally (like in my example), then it finds that the return is unreachable, then it finds that the value being calculated is unused, then it finds that nothing is needed except for the infinite loop. Each of these optimizations improves the performance of some correct code, and it doesn't have the deeper analysis to notice that it can prove that the loop executes 16 times in violation of the assumption.

It doesn't really have an overall knowledge set that could find contradictions; it's got patterns that produce warnings and patterns that produce optimizations, and so it can't tell when optimizations are leading to total nonsense.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

butlerm — 2013-03-26T03:28:54+00:00

The difference is that in the original example the compiler can prove that an out of bounds array access will occur under all input conditions. This should be considered an error. Dividing by a constant zero is a similar example. What possible good could come from the compiler just making something up in a situation like that?

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

nix — 2013-03-26T00:57:33+00:00

The 'nonsense', btw, is that the optimization pass which is coming to conclusions about the conditional test does not care where that test is located: in particular, it doesn't know nor care that it might be bounding a for loop. Generality in optimizations is generally a good thing...

access off end of array

tjc — 2013-03-26T00:34:27+00:00

Actually, the ++/PDP-11 connection is urban legend -- see "More History", paragraph 2 at this link:

The Development of the C Language

I think i++ is fine from a syntax point of view, so long as it's a stand-along statement, where it produces the same code as i += 1. But I try to avoid embedding increment operators within expressions that produce easily overlooked side effects.

access off end of array

HelloWorld — 2013-03-25T23:13:07+00:00

The only reason i++ and --i were invented is that that made it possible to generate more efficient code for the PDP-11 with simple-minded compilers. There's no reason for them nowadays as i +=1 is almost as short and most languages today also feature a proper for loop.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

mansr — 2013-03-25T21:09:16+00:00

The problem is that the source code is self-contradicting when interpreted strictly. While your observation is correct, the source also implicitly (through the d[k] array access) promises that k < 16. When given conflicting information like this, the interpretation is unpredictable. That is (part of) what undefined behaviour means. Get over it.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

xorbe — 2013-03-25T20:37:32+00:00

OTOH, the compiler should know:
#1 k starts as zero
#2 k is incremented every loop, which is its only assignment point.
#3 k is 16 when the loop stops.

Therefore, it also can't be an infinite loop.

> It doesn't know that the test is used for exiting the loop.

What nonsense is this. "k<16" is the exact test in the for loop! Anyways, glad to know the situation is better than the initial blog post.

access off end of array

tjc — 2013-03-25T19:27:39+00:00

If you trace this back to the root problem you may come to the conclusion that changing the state of a variable in a non-assignment expression can be more trouble than it's worth, especially if you're dealing with concurrency. A language that allows

i++;

as a stand-alone statement would be a useful compromise, since it could still be used as the increment statement in a for loop, which is by far the most common idiom for this construct.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

hthoma — 2013-03-25T15:43:29+00:00

> > for (dd=d[k=0]; k<16; dd=d[++k])

> That's.... horrifying.

Exactly. Looks like obfuscated C contest stuff ...

I would guess that if you write it the "normal" way, i.e.

for(k = 0; k < 16; k++) {
dd = d[k];
satd += (dd < 0 ? -dd : dd);
}

the compiler would not optimize the code to an infinite loop and get a better chance to optimize.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

dlthomas — 2013-03-25T13:41:43+00:00

It's not constraining the lookup, which would make valgrind miss it, but constraining its later assumptions about the variable.

int d[16];

d[k] = 10; /*A*/

if(/*B*/ k < 16) {
...
}

The idea is that when it hits A, if that expression would be false, behavior is already undefined because of what happened at B, so let's optimize for the case that didn't segfault (or corrupt data).

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

dlthomas — 2013-03-25T13:37:52+00:00

Fortunately, GCC 4.8 also keeps track of what code is the result of expansion of what macros...

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

jezuch — 2013-03-25T10:12:05+00:00

> "Because the SPEC CPU benchmarks are drawn from the compute intensive portion of real applications"

Well...

> for (dd=d[k=0]; k<16; dd=d[++k])

That's.... horrifying.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

jakub@redhat.com — 2013-03-25T07:53:52+00:00

BTW, if you want some testcase where -fno-aggressive-loop-optimizations still makes a difference even in GCC 4.8.0 release, one testcase is e.g.:
int a[4];

__attribute__((noinline, noclone)) int
foo (int x)
{
int i, r = 0, n = x & 31;
for (i = 0; i < n; i++)
r += a[i];
return r;
}

int
main ()
{
int x = 255;
__asm volatile ("" : "+r" (x));
return foo (x);
}
. With -O3 and not -fno-aggressive-loop-optimizations, GCC from the loop determines the high bound to be 4 and completely unrolls the loop into 4 reads from a (+ additions for 2nd and up iteration) preceeded each by test of the n variable, so the code won't actually read beyond end of a array, while with -O3 -fno-aggressive-loop-optimizations GCC won't compute the upper bound estimate so low (VRP can figure out it is 32, while other passes just estimate INT_MAX), so the loop happily will read beyond end of a, is vectorized (which is unlikely desirable for such small number of iterations), etc. Even without the "& 31" the situation is similar, and certainly for that case I don't see why a warning would be ever useful, the routine just can be valid only when called with a parameter 0 to 3, but there is no reason not to assume all the callers don't do that (the asm is optimization barrier, the compiler isn't supposed to look through it).

access off end of array

cesarb — 2013-03-25T05:09:26+00:00

Except that it is not an "exam question". It is supposed to be real code, in this case from a reference implementation of the H.264 codec.

It was not written to stress test compilers. It is just not very optimized (and since it is only a reference implementation, it does not have to be).

access off end of array

iabervon — 2013-03-24T19:02:39+00:00

Probably the real reason to have this in a benchmark is because it's stupid. Unless your compiler does particularly good flow control analysis, it'll generate a read of d[16], which is a likely cache miss (if the compiler aligns the array, there's a good chance that d[16] will be in a different cache line from d[15] and anything else that's hot). If the compiler can figure out that dd isn't used outside the loop, and that it can therefore be set after the test instead of before, you'll get code that runs faster than if the compiler is less clever. Of course, if you wanted to get a fast result, you'd just write it the obvious way and get the optimal result on any compiler, but they want to have some compilers do better than other compilers.

It's like writing an exam question: it would be easy to write a question that everybody would get right, but you want to write a question that people who know the material will get right more often than people who don't. Obviously, in ordinary life, you want to ask questions which will be more likely to get correct answers, and you want to write code that all compilers will make as fast as possible, but that's not the situation here.