Bubble sort is also good for keeping a list close-enough-to-sorted with only small incremental costs. It was an old graphics engine trick to run just a few passes of bubblesort over your sorted triangles array before rendering each frame. Occasionally you'd get artifacts but generally it worked well enough and was fast.
I've seen all the O(n^2) worst case algorithms that reduce to O(n) on nearly sorted lists used, for example, in sweep and prune algorithms in computational geometry.
A common optimization is to use insertion sort for small arrays (less than 64) and quicksort/heapsort/introsort for larger ones. Usually because better algorithms in terms of Big O have worse constant factors.
I think we need to get away from this attitude, that I used to hold, that O() is everything. It isn't. It isn't even close. We should instead wonder why an algorithm was chosen without regard for the nature of the data on which it will be applied. For sorting O(n lg n) only makes sense as a selection criteria if you have absolutely no idea about what data is being sorted. Why is that?
If the answer is you just don't care about the perfromance and can say why it isn't important (at least yet) as long as you avoid the pathological then that's a good answer. It's a really bad answer to assume it when you can't. IMHO.
Others have pointed out that bubble sort is great when your data is already mostly sorted. The textbook example is check stub ids, which are sequential - probably an outdated example nowadays. The benefit is greater than a O() analysis would have you believe because running sequentially through contiguous memory is something computers are just great at doing due to memory caching and prefetching. Minimising cache misses /may/ dominate the number of passes of the data in performance analysis. If you don't care about performance then an O(N^2) algorithm may be also something you don't care about.
Hu. Bubble Sort. And not only that; a buggy version!
And if you believe sequential access is gonna save you from O()... you're so wrong its not even funny. Of course the curves will cross latter. But they will cross. Especially on a sort.
I'm not sure you've demonstrated anything here about the topic under discussion. You might like to try achieve a better result around here, people tend to appreciate it.
You're misidentifying the attitude. The problem is that Bubble Sort is a terrible algorithm, there's no reason not to use Insertion Sort or better instead except for some reason CS programs still inflict BS on students so that's what they remember when they just need to sort something.
"Bubble sort always performs n-1 passes through the data (where n is the amount of elements), and it always performs (n-1)+(n-2)+...+1 comparisons regardless of how the data is organized to begin with."
That is just false. 1 pass and n-1 comparisons then stops for already sorted data is what you get. An implementation that doesn't show that characteristic has been either deliberately or accidentally pessimized to behave poorly. You can gimp any algo to make it look bad. Quicksort without randomization on a pathological case is O(n^2) for example and nobody cares for the overwhelming majority of practical purposes. If your definition of bubble sort is that it must be O(n^2) always then we're not using "bubble sort" to mean the same thing and it's pointless to continue the discussion.
Bubble sort is usually operates on data in place. I don't know how to do an efficent in-place selection sort for mostly sorted data, maybe it's possible? You pay for additional copies in both space and cpu cycles. 2xn space for selection usually - but maybe this can be avoided without paying a very high time overhead, (eg find the spot, ripple all data below the spot down to the hole where you selected to open a slot for insert or similar).
Count the memory operations, ie number of memory reads and number of memory writes for a given set of data comparing the two algorithms.
Suggestions: Write 50 odd lines of C code to see the actual effect in cpu cycles. Craft data to make each algorithm dominate the other, it's really interesting to see.
I'm disinclined to say "Never uses algo X, always use algo Y!" Because it's really hard for that to be sensible given all the various shapes and sizes input data takes. Know your data is always really, really good advice.
> Bubble sort is usually operates on data in place. I don't know how to do an efficent in-place selection sort for mostly sorted data, maybe it's possible?
What about insertion sort? Which always performs fewer comparisons and swaps than bubble sort for any array, by the way.
So I made the case with evidence that it doesn't always perform fewer comparisons and it it doesn't always perform fewer swaps. While it probably does, depending on implementation details use more memory. Do feel free to actually make your case with evidence, that I would be interested in reading.
What is it with this thread and "nyer, you're wrong" responses? It's not helpful, not clever, not useful and not pleasant to read for anybody. Finding out you're wrong is great, I learn stuff.
> While it probably does, depending on implementation details use more memory
Have you actually looked at the insertion sort algorithm? It doesn't allocate any additional memory. Neither does bubble sort or selection sort.
Knuth does some analysis of Bubble Sort in Volume 3 of the Art of Computer Programming, which proves bubble sort performs more comparisons and more swap operations than insertion sort. To quote the conclusion: "[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn't really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!"
6 comparisons, 1 swap with bubble and it stops.
I make it 7 memory reads and 2 memory writes.
Insertion and selection sorts are going to run in half that time? I'd really like to see that! I think Knuth might be talking about a general case of any data rather than the topic being discussed here, but no, I haven't read Knuth on bubble sort so I can't be sure. I may do so now so thank you for the pointer. Arguments from authority really can be informative and useful despite their other shortcomings.
Bubble sort performs 11 comparisons and 13 memory reads in this case, actually. Because on the first pass through the array it performed a swap, it has to loop through the array a second time to verify the array is completely sorted.
To avoid confusion, here's the bubble sort algorithm:
procedure bubbleSort( A : list of sortable items )
n = length(A)
repeat
swapped = false
for i = 1 to n-1 inclusive do
if A[i-1] > A[i] then
swap(A[i-1], A[i])
swapped = true
end if
end for
n = n - 1
until not swapped
end procedure
As you can see, after performing a swap during the first pass through the array it has to go through again (though it can skip the last element because we know the last element must contain the largest element in the array)
Insertion sort will perform 7 comparisons, 1 swap, 7 memory reads and 2 writes.
No, you can't, because at the end of the first pass you have no way to know that it is in sorted order. Go ahead and try to write the pseudocode for your bubble sort implementation that avoids the second pass.
The other reply thread is great and has a SmarterBubbleSort implementation -- it's important to note that the early stopping rule is an enhancement, not vanilla bubble sort (I had to learn both, maybe curricula these days jumps straight to the smarter version?), but even so it complicates the implementation and still isn't ever better than vanilla insertion sort.
Here is insertion sort
void insertion_sort(int s[], int n) {
int i, j;
for (i = 1; i < n; i++) {
for (j = i; j > 0 && s[j] < s[j-1]; j--) {
swap(&s[j], &s[j-1]);
}
}
}
You can even improve this further (some improvements have new names), however its base form is not in the class of bad algorithms to never use. Besides Bubble sort, Bogosort comes to mind. And there are of course nice algorithms to use if your data works for them, Radix sort comes to mind. Knowing your data is good advice, knowing never to use bubble sort is also good.
> Others have pointed out that bubble sort is great when your data is already mostly sorted
It really isn't, compared to insertion sort.
https://users.cs.duke.edu/~ola/papers/bubble.pdf shows insertion sort performs 5x better. I also like Knuth's Quote in TAOCP: "[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn't really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!"
> running sequentially through contiguous memory is something computers are just great at doing due to memory caching and prefetching
Name one sorting algorithm that doesn't involve purely running sequentially through contiguous memory.
For me it's that they aren't testing it. This sort of functionality is so trivial to write unit tests for, so simple that it's the fastest and easiest way to write and debug the sort method.
It'd make me question the stability of the rest of their product too.
Actually, that's a fascinating part of the story. We run the entire test262 ECMAScript Conformance Suite (https://github.com/tc39/test262) against our JS-Interpreter fork. We don't pass the whole thing yet, but it ensures we only ratchet toward conformance to the language spec.
We checked, and this particular bug was not caught by the test262 suite - the broken sort worked for enough cases to slip past the Array.prototype.sort tests there. We've added a regression test for this issue in the layer that consumes the interpreter, but I've thought about proposing more aggressive validation of sort behavior to the test262 project.
It was a great reminder to me that while tests may be necessary for quality, they are not always sufficient!
I once used a bubble sort when I knew the typical array size would be 4. I think someone later replaced that code when the original assumption became outdated and we were sorting larger arrays.
In over a quarter century of programming, I've twice found interpreter errors. Once a function performed the inverse of the documented behaviour (returning "true" for "false" and vice versa) in a proprietary system, the second was a gawk bug of some description I don't recall but proved to be an actual bug.
That first one reminded me of the gripe at the top of perl's Configure script https://perl5.git.perl.org/perl.git/blob/HEAD:/Configure#l36 --
"SCO csh still thinks true is false. Write to SCO today and tell them that next year Configure ought to "rm /bin/csh" unless they fix their blasted shell. :-)"
which only gets printed if the shell it's running in egregiously mishandles &&...
We should consider separate bugs in the language spec from the implementation. In JS it's insane not to K&R brace as it will try to infer missing semi-colon terminators in your code, silently, to your doom. That's surprising if you have the misfortune. It's a massive bug in the language spec but the implementation of the JS interpreter is 100% correct as it kicks you, hard.
Parent comment makes sense to me as a general comment about getting good at JS. Especially given JS has so many new and exciting libraries that get used in production. Ultimately you must fix your code, JS & libraries aren't likely to change in a timely fashion. And of course what I call a bug in the spec must have been considered a feature at one time, some may still consider it so. That's a question of taste and you can always consider yourself 100% correct on any matter of taste simultaneously with those who disagree. :-)
Edit: add this comment you have provided approximately nothing in support of your assertion, you can and should do better. I note this thread is JS and a whole lot of this kind of thing going on here I don't usually see elsewhere on HN. It's a shame, discussion is useful to learn things I don't already know. "Nyer, your wrong" not so useful to me, you or anyone else.
No, JS will never never insert a semicolon after “if(foo)” no matter what comes after it. Putting the braces on your control structures on the same or the next lines has no interaction whatsoever with the semicolon insertion rules.
I’ve written a ridiculously detailed blog post about automatic semicolon insertion if you want to know all the specifics.
Yes, those are different, but K&R brace is a style of where you put the braces in a function body or a block. The braces in your example are creating an object literal.
The K&R brace style is not about putting an object literal on the same line with a return statement or on another line, but about how control structures are formatted.
The reason I said that K&R brace style has nothing to do with semicolon insertion is that it’s possible to write all your control structures with K&R braces and still be bitten by the places in the grammar where line breaks are not allowed, like after a return statement, if you’re unaware of it.
It’s also possible to use Allman braces everywhere and never have that problem with return statements.
Although with javascript there have been a lot of different interpreters with a lot of different bugs over the years.
I'm thinking mainly of browsers and their implementation bugs, there have been quite a few instances in which what I thought was my own mistake turned out to be a browser bug of some kind.
While true, the use of sort() to sort an array of numbers in JS is ... complicated. It works for the single-digit-number case, but if you can have multi-digit numbers you better remember to pass a comparator function to get numeric sorting, because JS sort() defaults to lexicographic sort. So it will sort 10 before 2 by default.
I'm kicking Javascript/Node because the entire stack is amateurish and one constantly runs across unexpected behaviours/build breaks in even fairly high profile libraries.
My understanding (and usage) of `__attribute__((aligned(N)))` has been that it applies differently when used in the declaration of a `struct` type vs. the declaration of a variable (And applies the same whether or not the variable is of type `struct`). Thus my understanding is:
When declaring variables, `__attribute__((aligned(N)))` indicates you want the variable in whatever format it was defined in aligned to that value. If it is less then the default alignment, it will be allowed to be aligned to that instead. For `struct`s, this would mean that the `struct` is kept in the exact same format (with the same padding, in particular) as the declaration would require, but the entire entity itself is instead aligned to whatever alignment you give.
When declaring a `struct` type, however, the individual members all still have their own alignment constraints, which is where `struct` padding comes in. So when you just apply `__attribute__((aligned(N)))` to a `struct` type declaration, it's not clear how you want to achieve that alignment. If that alignment is a multiple of the required alignment for the `struct` then there is no problem, because you implicitly meet the alignment requirements already.
If it is less, however, then it is not clear when you want alignment requirements met and when you do not (IE. Where should the compiler insert the padding bytes in the `struct`? Should it unalign the first member and then correctly align all the rest? Or pack it as though everything is correctly aligned, and then allow the entire thing and all the members to be unaligned?).
There is already an attribute to solve this problem, `__attribute__((packed))`. All `packed` does is force the alignment of all the members in a`struct` to be 1, which both tells the compiler no padding bytes are necessary, and also means that `__attribute__((aligned(N)))` always works, because every `N` will always be some multiple of 1.
So with that in mind, in my opinion the bug largely on EMACS' side (Assuming I'm reading those messages and code correctly). In my opinion, they shouldn't be using the `aligned` attribute on the variable declaration at all, and instead they should just ensure the `struct thread_state` type itself already has the proper alignment. The fact that they are using `__attribute__((aligned(8)))` seems to indicate to me that somewhere align the line a `struct thread_state` type was defined with the incorrect alignment, and it was fixed by adding the alignment to the variable declaration. But if you just apply the attribute to the declaration of the `struct thread_state` type instead, then everything would be fine, and architectures with a `struct thread_state` with a higher-alignment (like 32, in this example) wouldn't be affected by the alignment requirements of architectures with a lower alignment.
That said, there is something I found very interesting in those posts, though I don't believe it is a `gcc` bug. But it is this syntax:
struct __attribute__((aligned(N))) s var;
I didn't actually know you could even put the attribute in-between the `struct` and the structure name. That said, it does make some sense when you realize what it is doing, even though the syntax is kinda screwy - it is for applying `struct` attributes after-the-fact. So while this does work for `aligned(N)` (which has variable and `struct` variants) it would also probably work for `packed`. This would likely make most sense to use in a `typedef`, which would allow you to declare the 'normal' version of a `struct`, and then `typedef` a `packed` version or `aligned` version as well. I've never really had a need to do that, but it is interesting to see. It does technically fix the problem here, but it is the same as attaching an `aligned` attribute to the `struct` type declaration after-the-fact, and I really do think if possible they should be looking at putting it on the declaration of `struct thread_state` instead.
Sorry for responding again, but I was really curious about that "inline" struct type attribute format so I figured I would do some tests. It looks like it actually doesn't do anything! And the warnings are definitely wrong in at least one case. To get straight to the point, some code:
The outputs of this program (Just the numbers) are 4, 4, 4, 32, 4. If the 'inline' attributes were actually respected, the results would be 2, 4, 32, 32, 4. Meaning, the attributes in test's 1 and 3 are completely ignored but do not produce warnings. Also interesting, test 4 actually produces a warning about the `aligned` attribute being ignored even though it actually respects it (as it should). I think this is a just weird issue edge-case with the `alignof` operator specific to `gcc`, since `alignof` takes a 'type' as input, but it's definitely a bug. If you declare a variable with that type there is no warning.
Besides the warnings this doesn't surprise me too much, AFAIK it is not legal to put anything between the `struct` and the structure name in usages of a `struct` type. But from the response gotten over at the `gcc` Bugzilla I would wager the 'inline' versions are in the uncharted waters of "Nobody really knows what that should do anymore, don't do that". Reading the `gcc` bug report again, it seems the last response does actually indicate the error I'm pointing out above, where the attribute is silently ignored, I missed that when I skimmed it the first time.
With that said, the fix EMACS implemented was the same as just removing the attribute completely. If the EMACS code really does need that alignment forced for one of its architectures, it should probably take a look at that fix again and apply the `aligned` attribute on the `struct thread_state` for the architecture(s) that need the 8-byte alignment (If they actually exist), and then remove the attribute completely from the variable declaration.
Of course, there's also the point that if utterly pathological behavior is documented, then it's not a compiler error. I remember a c++ compiler that had a hard limit on the number of objects allowed in the programs it compiled. It's documented, "not an error".
The compiler actually crashes rather than returning anything? Well, that's more likely to happen when your code has lots of errors in it. "Don't look at me like that. Go fix your code and then come and complain..."
QNX 6.6 GCC had a bug where any use of initializer lists with objects would crash the program. Funny bug, that. Stumped me for half an hour. It has been patched now.
In userland, if some fraction of the user base misuses a feature, that could be considered a bug, even if it is working as designed.
Obviously things like forward and backward compatibility are much more important in the programming context, so you can't just "fix" things like weird side effects or not throwing an error on assignment in an if statement.
Sadly, I've lost count of how many compiler bugs I've tripped over through the years. Often it's compiler crashes -- those are usually easy to get fixed, especially when (as tends to be the case with LLVM) they are caused by assertions failing -- but I've also tripped over compiler hangs (there's a variable in the tarsnap code with an utterly bogus volatile specifier in order to avoid the problematic optimization on some versions of llvm) and outright miscompilations -- one of which has had several LLVM bug reports opened by different people over the years and remains unfixed.
If you’re the kind of programmer who is likely to find compiler errors, you probably know who you are. For 99% of programmers, the chances that you have discovered one is small.
The chance isn't that small, many people stumble over them and just use the first workaround SO turns up or think its actually their fault and work around it in other ways.
I had some bad experiences with visual studio's compiler recently (last two years.) I was working on OpenGL code and discovered a couple different constructs that would crash the compiler. The first time I figured it was a fluke, but by the third distinct case I became rather alarmed; the code should have produced errors, not compiler failures. I concluded that MS's compiler is decidedly less robust than GCC and clang; I've seen one compiler crash from a release GCC compiler in the last 10-odd years.
Yeah working on FreeSWITCH, upgrading to VS2015 and we encountered an issue with a long series of else branches. Ended up having to split and nest for the code to compile.
When I was in my first year of Computer Science (17 years ago), I had this CodeWarrior error that still makes me chuckle. I think I had a comment, assignment, and a System.out.println(); It wouldn't compile, had an error every single time. The tutors took a look at my code, and one-by-one gathered around until they were all there.
Eventually, someone (Natalie) moved the comment below the assignment, and it worked normally. I tried putting it back above, and it wouldn't compile. Can't remember what happened if I left the moved comment in place and put another above the assignment. I found two like that - one in CodeWarrior, one in Turbo Pascal a few years before that simply returned "error 0: no error."
It wasn't anything complicated in either case, just very basic stuff.
Something similar happened to me a while back in Mono/C#. I think it was the order of assignments for an unused variable changed the results of the code. Something like:
int x = 0;
int y = 2;
DoSomething(); // Didn't run with x before y
I can't recall if I ever reported it or bothered looking into it, but a friend ran into a similar issue around the same time and it was really confusing, but it was resolved by changing some configuration (different compiler version or flags I think).
Only other time I bumped into it was in Idris, which is to be expected frankly.
From what I remember of a deep dive post I read on this once, the ordering type bug / no-bug situations tend to be the result of incorrect optimizations. Changing the ordering will sometimes make the code look just different enough to go down a different (not bugged) optimization path.
If you ever catch them still there with a "no optimizations" flag, then that's a pretty serious bug!
I've used a lot of C/C++ compilers over the years, and the two compilers marked in my memory as having enough bugs to be noticeable and disturbing were Visual C++ 4.1 (so notably bad that MS essentially apologized for its screwup and conceded that 4.2 was largely about fixing 4.1's problems) and CodeWarrior for Mac (pretty much any version, I think...I never tried the Windows version, but the thought of it makes me shiver).
CW had a pretty nice environment to develop in compared to its contemporary competitors, but it just didn't have a solid compiler.
This was pretty common in Turbo Pascal, your program would just suddenly stop working when you added a new blank line. (It would compile, but something would usually be off in the output causing the program to fail or crash).
Removing the offending line or adding a different mix of blanks/instructions would get you back to a working state again. Very frustrating.
That was true-er when by compilers one meant GCC or some such.
Now everybody and their dog write compilers and transpilers for young and/or obscurer languages (I'd include Go and Rust in there), and with the immaturity of these environments compiler bugs are a fact of life.
Nope. Wasn't true then, either. Found bugs in Lattice, gcc, egcs, Borland, Aztec, and probably a few more that I'm forgetting.
They're never common, but "it's never the compiler" doesn't apply either. It is, however, a helpful reminder that the most likely source of problems is with the author of the code :)
Obviously broken code generation, in the sense that the code provably does not behave as it should under the spec. Usually as a result of optimization gone wrong.
If you're asking for actual examples - sorry, you're out of luck. The 80's and 90's are a bit too long ago for me to remember details.
If you prefer to believe in the magically flawless compiler fairy, knock yourself out.
Not necessarily. Could be a problem with passing 64-bit values to varadic functions generally. I could definitely imagine this happening on a 32-bit platform.
This has bitten me on QNX. I was porting UQM for fun, and it was failing when entering a dialogue,
Turns out, on QNX you can't pass short int into variadic function, which is expected behavior as far as C is concerned (you should only pass int or full size types), but it worked on every other arch so it took me a while.
The generated assembly was garbage, so I assume it was a compiler bug. It also got fixed in later revisions, but since the compiler is shipped with the CRT... :)
I don't actually recall if we were using the shipped CRT or not, I'm guessing only minimal parts of it were used, if any, since embedded projects tend to write their own subset of the needed standard library functions.
I worked a compiler backend for 5 years. Despite the insane amount of testing, fuzzing, standards tests, etc that we did, there were always bugs coming in, and not always in code that looked dodgy. Sometimes an optimization interacts with another in JUST the right way to cause incorrect code to get generated.
Honestly, I'm surprised that I haven't run into more of them in the wild.
A compiler in particular is a very extreme case. Most software is used to its fullest extent by its developer, 90% of bugs are likely to be found by said developer in their normal usage. Another step out, library developers often use their work, but often build in functionality they're not as interested in by request or as a result of generalizing beyond their specific use cases. They might not be the heaviest users of that software, and so aren't as likely to find some of the bugs.
Compilers are the most extreme case. Anything Turing complete is almost certain to have vast swathes of functionality which aren't used by the developer. If a compiler doesn't already have a large user base, then unless you're using it exactly like someone else has, you're almost guaranteed to find some bugs. Honestly that's true for most software, going back to the maxim "don't be the biggest user of any given software unless you're already capable of writing it yourself."
> If you’re the kind of programmer who is likely to find compiler errors, you probably know who you are.
I'm one of those that routinely find a bug in a library during the very first use of its API. Every "quick weekend project" turns into "let's learn the build system of this library and send a patch/bug report to the maintainer".
Does anybody know how can I turn this annoying superpower of mine into a job that is not basic Q/A?
Go into security and turn that free bugreport into big budget bug bounties ;)
If you can find bugs in libraries used in IOS/Android or something, that's worth money and gives you the chance to increase security for millions (billions?) of people.
I have a similar thing with typos. Give me a page of printed text, and there's a surprisingly high chance I will spot a typo within the first few seconds of looking at the page, no matter where the typo occurs on the page.
(Might be confirmation bias, but I have been proofreading a lot of theses for my friends while in college, so it might be trained.)
<quote>Does anybody know how can I turn this annoying superpower of mine into a job that is not basic Q/A?
</quote>
What would you say, if I told you that this superpower was not basic Q/A? because basic Q/A is what the compiler is passing, all the time. The part you meant with vigour was the <b>job</b> part right? how do you make somebody want your awesome enough to pay you a living wage? It's either apple or Intel, because they are the two people financially vested in llvm.
It's likely that your weekend projects are things you find interesting and it seems likely that the things you find interesting are bleeding edge. It's never going to get better. On the other hand, any good dev team would value someone who can not only find the bug, but patch it.
You need to get somewhere where using the latest and greatest is encouraged..
It's a terrible idea to assume that other humans don't make mistakes. When encountering a bug, start at the top, and work your way down when you conclude that the current level is correct. There is no level of development that is immune.
Sometimes you are to blame. Others, it might be a library. It might be the standard library, or the compiler. A faulty optimization, perhaps. Could also be the OS kernel, or even the hardware (CPU, USB controller, network card, ...). It's all chock-full of bugs.
I've hit a handful of miscompilations while writing boring JavaScript web apps, some only when the JIT kicks in for extra fun. I have a handful of outstanding Linux kernel bugs, one of which cause memory corruptions, has existed at least since 2.6 and is dead simple to reproduce. I have a significant GCC performance degradation bug, triggered by calling "pthread_exit(3)" after an infinite loop. I've had what seemed to be software problems turn out to be PCIe problems.
You might think that, as a developer, you're building a card-house on a solid foundation. But no, it's card-houses all the way down.
“It is never a compiler error” means don't waste your time blaming the compiler, first assume it's your fault. For every person who genuinely ran into a compiler bug, there are orders of magnitude more who think they did, but didn't. If you start saying "it could be a compiler bug," you're encouraging them to waste their time.
> When encountering a bug, start at the top, and work your way down when you conclude that the current level is correct.
I agree wholeheartedly. Saying "it is never a compiler error" doesn't preclude this; it encourages this behavior. Even thinking "it could be a compiler error" invites laziness.
I strongly disagree with your point of view: "it is never a compiler error" not only precludes suspicion of the lower levels—voicing your suspicion of problems in lower layers will generally result in ridicule!—but it reducing critical thinking, bars people from looking into "complicated" projects, and makes them overall less efficient and skilled developers. I also disagree that encouraging a bit of wasted time is a problem. What is a few hours, or even days "wasted" learning your lesson once and for all if it greatly improves your debugging skill and efficiency? You do not learn without mistakes.
"It is never a compiler error" is a detrimental mindset to have, in that it suggests a mentality where you shut your eyes for anything you did not author. After all, it is too complex, too well-tested, too well-designed, and implemented by much smarter people than you. Compiler, library, application, hardware, train, bridge, it doesn't matter.
Not only does this mean that you often won't find the bug you hit, as you won't start instrumenting the faulty LargePopularLibrary—after all, it obviously can't be to blame—but it also means that you won't as much as read library|compiler|kernel|etc source code, much less do development on it, as you think it is above you, despite it by no means being some magical black art.
"It could be a compiler error" invites you to consider all possibilities. Immediately blaming the compiler without reasonable evidence would, despite such a mantra, be a result of terrible debugging skills. These debugging skills should be improved through other means than intentionally teaching falsehoods, and if the subject is not an entirely lost cause, it should correct itself in much more valuable ways if a little time is "wasted" on improper debugging.
Teach proper debugging techniques instead of lying to others, or yourself.
> Even thinking "it could be a compiler error" invites laziness.
Or worse it could invite curiosity and now you are spending time wondering how could you tell if it's a compiler bug and how would you go about debugging it.
The OP simply said that the chances of finding a compiler bug are small. You seem to have found a few minor bugs, and that's cool, but how does that change the fact that chances an average C developer finding a compiler bug are minuscule? There are probably around a million C developers, do we even have one compiler bug per 10 developers?
> You seem to have found a few minor bugs, and that's cool
I'm sorry, how are total miscompilations and memory corruptions "minor bugs"?
I am arguing against the mentality of dismissing compiler bugs, with the idea that "you will never hit one". Hence my examples of when I hit them during something as high-level as web development. I am not arguing that you'll hit such bug every day, or even every month.
I only have myself and those around me as reference. I have been a software developer for less than 10 years, but with the current total, I have been hitting a few "lower layer" (vm, stdlib, compiler, kernel, hardware) bugs a year.
Maybe I'm just "unlucky". If you want to find real numbers, take a look at GCC/LLVM/libstdc++/glibc/linux bug tracker statistics. I'm sure you will be surprised.
> If you’re the kind of programmer who is likely to find compiler errors, you probably know who you are.
A Swift developer?
Just yesterday I found myself compiling a new part of code in increments because all of the new code together wouldn't compile but adding the code and import first, compiling it before adding @UIApplicationMain would compile just fine. Exactly the same code that didn't build before.
I can't imagine what I would have done if I would have trusted that this was my error because the compiler would not make mistakes.
Though nothing compared to Swift 1.x, things tend to work generally and if the compiler does crash it'll crash on weird programming mistakes (like referencing type(of: self) before init() was called)
clang/llvm makes the gcc developers look like amateurs when it comes to reckless optimizations for that extra percent in the synthetic benchmark. My goto approach for when something breaks in clang but works in gcc is to disable optimization, and when I can narrow it down to a single offending function, that gets optnone slapped on it and done.
... is in the eye of the beholder. They exploit every corner of undefined behavior to the benefit of performance. Indeed other compilers might be "safer."
Keep in mind that they also provide you with UBSan to help you detect when you're doing it wrong.
That argument would make more sense if they actually were faster, which they often aren't. Last I checked (and I don't keep up with this, to be fair) they still lagged gcc on most macrobenchmarks on x86.
Oh, I thought the GP was accusing GCC devs of reckless optimizations. But UBSan is a clang project, so maybe you're interpretation makes more sense. Very confusing thread. :)
I mean, if you use GCC does recklessly optimize away (some) security/safety code. This is one of the reasons why we don't use it for code we ship. I work in a safety-conscious industry, where an overeager compiler can literally kill people.
Well, the last case I can recall where I had to resort to this used inline NEON assembly for what is essentially a fancy 2D memcpy. With optimization on textures were corrupted. I spent an hour diffing objdump output and got nowhere.
Essentially, it was not worth more of my time to figure out how aggressive optimizations were breaking the parts of a memory bandwidth constrained function that aren't worth optimizing in the first place.
For GCC inline assembly means "take your grubby hands off". For clang it's essentially an invitation to do whatever.
Based off of your description you probably just needed to add the "memory" clobber to tell the compiler that any registers it might have kept are no longer valid.
I think I had only a single compiler error in my entire career that wasn't about robustness (ex: code crashing the compiler instead of producing an error). Updating the compiler fixed it.
I seem to be cursed with the ability to crash any language interpreter I play with. My favorite so far was when I tried Smalltalk, mixed up / and //, and asked for a window that was 3/2 pixels wide (maybe not 3/2, but some non-integer rational width). The maintainers: "Wow! That bug must have been lurking in the bytecode interpreter since Xerox PARC."
You might think this is a curse, but as someone writing a language, people like yourself are a blessing. Exercising the weird cases that the original people overlooked and filing a bug is really, truly helpful.
I immediately thought of this work when I saw the title. Of course, you're actively and effectively hunting down bugs, not accidentally running into them while doing other things ;)
Yes, but for example I remember at least one anecdote where one of our bugs we encountered was closed as a bug that manifested itself as a crashing bug in x264 or ffmpeg (I forget which) and ours was closed as a duplicate, so people do actually encounter bugs.
This goes for other things as well, not just compilers.
As of this moment I am begrudgingly creating a support ticket with AWS for an issue which I am 99.99999999% confident is in our VM and has nothing to do with AWS itself.
For some reason, "AWS issues" is one of the first things raised, even though we are unlikely to be hitting AWS edge cases, not being Netflix-scale.
AWS is nowhere near as reliable as a compiler. We've seen things ranging from "S3 intermittently takes 60 or 120 seconds (or some multiple thereof)" (but apparently only for my buckets…) to spatial indexes in Aurora just flat out didn't work when they were released, to S3 acknowledges writes prior to them being available to be read (causing a reader who picks up the item to receive a 404), to ELBs corrupting the HTTP connection depending on packet timings.
That's aside from the more common issues of "this VM is just going to bite the dust", which is something I feel is just inevitable.
The kernel is more reliable, IMO (except when it comes to the Thinkpad TrackPoint drivers).
And very visible in practice. In one case we had a bucket with about 50,000 documents posted to s3 the with 204 created replies. A separate process runs to verify the uploads has 10 or so outliers taking 30s or longer to for a GET to see them. One took 10 tries spaced 30s apart (so 5 minutes) to show up. The next 50k the biggest outlier was only 5s.
Huh. TIL. I swear we searched the docs when we ran into that, and found the same consistency guarantee minus that rather large caveat, but Wayback says that was there at the time. Perhaps we were looking at a different page, but it does appear this is and was documented behavior.
That's a hugely unuseful caveat in practice though. I'd really love to have consistent reads.
Just a week ago I remembered reading an article several years ago about someone who ended up digging in the compiler (probably GCC) and against all odds unearthed a bug in there. As I recall it was quite involved and an interesting read but I can’t seem to find it again. If anyone has a recollection of such an article I’d be grateful to be sent a link in my general direction.
The only error I found where the code compiled but was wrong was from it assuming a particular symmetry in the instruction set. It tried to use an addressing mode on an instruction that didn't support it and consequently output two completely different instructions.
Errors in the run-time library and errors that crash the compiler are much more common. While many eyes cover a lot of search space. The space they have to cover has grown immensely.
If you step off the trodden path you can find problems much more often. Just recently I encountered a function in a run-time library that freed the amount of memory the alloc asked for instead of the amount of memory the alloc function actually returned (Sometimes it returned slightly more if the remaining space was not enough to hold a free-memory structure).
It would not surprise me if the population using that particular compiler/platform combination numbered less than a thousand.
I have worked in a domain where "it is often a compiler error" -- scientific simulation. In particular, Intel's C and Fortran compilers generally produce the fastest binaries on Intel hardware but they also seemed to break builds a lot. The answer to "the validation suite no longer passes" was often "use this specific point release of the compiler."
I wasn't personally developing the core simulation software itself at the time, just building it from source and writing extensions. I don't know if these frequent breakages were actually outright compiler bugs or just relying on conventions that weren't guaranteed by language specs. But I do know that switching to one particular blessed compiler revision was often the fastest way to pass validation and move on to your actual research problems.
Having to use a specific point release of the compiler to work does not necessarily means later version have a bug. It could also mean that the program is (accidentally) depending on implementation details that are not guaranteed by the language, and that the compiler is supposed to be free to change behavior about. For languages like C with a significant amount of undefined behavior, that's actually quite likely.
IIRC the intel compiler has the equivalent of gcc -ffast-math on by default, i.e. it explicitly breaks some the C and IEEE 754 floating point specs in some places in exchange for performance.
This reminds me of my favorite "bug" in my language. I was trying to show off string representations of arithmetic expressions, so I typed in this.
<feep> .neatex string-of 2+2
<feepbot> 23
That took a little figuring! Turns out, I'd forgotten my own precedence rules, and it'd interpreted it as (string-of 2) + 2; string-of, being a compile-time operator, yielded a string literal "2", which then implicitly cast to a string pointer, which then got incremented by two right past the end and into the next string, which happened to be "23".
> but the maintainers' response was something like "Yeah right. Closed."
That sounds pretty horrifying! But reading the issue (linked from the github issues linked by sibling), the actual response seems pretty reasonable. He looked into it and determined it was an issue with your setup, and asked for more information (if he couldn't reproduce it, what else could he do?). He also made a guess at what was wrong. You provided more information and a workaround (nice!) and a few weeks later he closed it saying he believes its now fixed. Seems ok to me.
I have hit a number of C/C++ compiler bugs in GCC, MS VC, Code Warrior and various in other languages (for example shader compilers). I agree it is the sort of the last thing you blame, but at the same point, sometimes it really is, so I get a couple of sanity checks from skilled friends or colleagues, making a tiny repro, submit and move on!
There are more compiler bugs than many ever think. From mainframe COBOL compilers to gcc, I have encountered bugs in programs that were a result of what the compiler did.
The original source code did nothing special - it was simple code and due to specific optimisations that the compiler performed, inexplicable seemingly random errors would arise. One would have to constrain the optimisations the compiler would do to get the code to execute correctly.
No compiler is bug free. The bugs can manifest in strange ways and sometimes they will manifest only on specific kinds of data (edge case data).
Certainly there are many programs that are written incorrectly and give rise to apparently inexplicable errors that are due to misunderstood language features or specified compiler limits.
However, there are also many programs that do not have such source code errors that end up being rewritten in some way to avoid compiler based errors.
The worst I have seen is when dummy statements have to be put in to the source code in order to get the program to work correctly. I have seen compilers change the precision of numbers from one version to the next and you have to add additional code to restrict those numbers back to the specified range. I have seen compilers allocate multiple i/o buffers as an optimisation that causes a program to fail when a single i/o buffer allocation works fine - one has to turn off the optimisation - no documentation available as to how the compiler generated code uses those buffers.
All I can say is that it takes a fair amount of investigation to determine what kind of bug it is when it is subtle and randomly occurring. It can be everything from errors in the source to errors in the libraries to errors in code generation to errors in the o/s (including driver errors or memory errors).
Anyone who blanket says the compiler is not to blame is living in a rose coloured glasses world. Compilers are complex programs and the source code for them can be just as wrong as for any other program. The code generated for compilers can be just as bug ridden as any other program.
C++ is notorious for exploiting what is technically undefined behavior to produce unexplainable optimization bugs. Undefined behavior is extraordinarily easy to write into your code without knowing it, and once it's there the compiler is free to do any crazy thing it wants. You think it's a compiler bug because turning off the optimizations fixes it, but it's not.
C++ (and its ilk) is a language that I don't touch with a 40 ft barge pole. Irrespective of the aficionados of the language, it is poorly designed in oh so many ways. I would rather program in BF, befunge, or remorse than C++.
1) Borland Turbo Pascal, where code would not execute correctly in the presence of a comment near the top of a loop. Deleting the comment caused the correct loop execution.
2) Texas Instruments DSP C-compiler sometimes failed to unroll loops correctly. Certain loop forms needed to be avoided as a result.
3) Recently I've been working on a C-compiler written in Golang, and the grammar definition was raw enough that it definitely had bugs. The bugs were fortunately obvious in that it would refuse to compile valid C code.
We've found compiler errors frequently. An absolute hot-spot for compiler errors for us was (relatively) obscure platforms, so we found SDKs for embedded MIPS processors that broke basic gcc intrinsics. No-one had ever noticed that really basic intrinsics (at the level of popcount/count leading zeros) were wrong.
C++ was another hotspot of brokenness for early gcc 4.x.
I've run into tons of compiler errors, especially compilers generated by Yocto project. I've also had weird behavior from compilers when running in a VM.
I remember using g++ on Windows (via cygwin or something) and writing a function that was supposed to return a Boolean, but sometimes didn't return any value at all. Real spaghetti, in university, no less. Throwaway code, in my defense. Turns out the code not only escaped detection, but the resulting binary always returned the same Boolean value when the code path where no return should be made were run.
Don't think I've seen one since, though I have found a nasty footgun in Scala where if you do a fold of a parallel collection, you can give the fold a starting value, which will be supplied to all the executing threads. The result therefore depends on how many cores you have running. Sadly I suspect that one's in spec.
How did that bug pass testing? Isn't the first test of correctness that you generate the 3.5 million permutations of 1..10 and sort every single one correctly?
279 comments
[ 3.1 ms ] story [ 250 ms ] threadhttps://github.com/code-dot-org/JS-Interpreter
If the answer is you just don't care about the perfromance and can say why it isn't important (at least yet) as long as you avoid the pathological then that's a good answer. It's a really bad answer to assume it when you can't. IMHO.
Others have pointed out that bubble sort is great when your data is already mostly sorted. The textbook example is check stub ids, which are sequential - probably an outdated example nowadays. The benefit is greater than a O() analysis would have you believe because running sequentially through contiguous memory is something computers are just great at doing due to memory caching and prefetching. Minimising cache misses /may/ dominate the number of passes of the data in performance analysis. If you don't care about performance then an O(N^2) algorithm may be also something you don't care about.
And if you believe sequential access is gonna save you from O()... you're so wrong its not even funny. Of course the curves will cross latter. But they will cross. Especially on a sort.
http://warp.povusers.org/grrr/bubblesort_eng.html
http://warp.povusers.org/grrr/bubblesort_misconceptions.html (Bubble sort is not great when your data is almost sorted. Insertion sort is, though.)
"Bubble sort always performs n-1 passes through the data (where n is the amount of elements), and it always performs (n-1)+(n-2)+...+1 comparisons regardless of how the data is organized to begin with."
That is just false. 1 pass and n-1 comparisons then stops for already sorted data is what you get. An implementation that doesn't show that characteristic has been either deliberately or accidentally pessimized to behave poorly. You can gimp any algo to make it look bad. Quicksort without randomization on a pathological case is O(n^2) for example and nobody cares for the overwhelming majority of practical purposes. If your definition of bubble sort is that it must be O(n^2) always then we're not using "bubble sort" to mean the same thing and it's pointless to continue the discussion.
Bubble sort is usually operates on data in place. I don't know how to do an efficent in-place selection sort for mostly sorted data, maybe it's possible? You pay for additional copies in both space and cpu cycles. 2xn space for selection usually - but maybe this can be avoided without paying a very high time overhead, (eg find the spot, ripple all data below the spot down to the hole where you selected to open a slot for insert or similar).
Count the memory operations, ie number of memory reads and number of memory writes for a given set of data comparing the two algorithms.
Suggestions: Write 50 odd lines of C code to see the actual effect in cpu cycles. Craft data to make each algorithm dominate the other, it's really interesting to see.
I'm disinclined to say "Never uses algo X, always use algo Y!" Because it's really hard for that to be sensible given all the various shapes and sizes input data takes. Know your data is always really, really good advice.
What about insertion sort? Which always performs fewer comparisons and swaps than bubble sort for any array, by the way.
What is it with this thread and "nyer, you're wrong" responses? It's not helpful, not clever, not useful and not pleasant to read for anybody. Finding out you're wrong is great, I learn stuff.
Have you actually looked at the insertion sort algorithm? It doesn't allocate any additional memory. Neither does bubble sort or selection sort.
Knuth does some analysis of Bubble Sort in Volume 3 of the Art of Computer Programming, which proves bubble sort performs more comparisons and more swap operations than insertion sort. To quote the conclusion: "[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn't really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!"
6 comparisons, 1 swap with bubble and it stops. I make it 7 memory reads and 2 memory writes.
Insertion and selection sorts are going to run in half that time? I'd really like to see that! I think Knuth might be talking about a general case of any data rather than the topic being discussed here, but no, I haven't read Knuth on bubble sort so I can't be sure. I may do so now so thank you for the pointer. Arguments from authority really can be informative and useful despite their other shortcomings.
To avoid confusion, here's the bubble sort algorithm:
As you can see, after performing a swap during the first pass through the array it has to go through again (though it can skip the last element because we know the last element must contain the largest element in the array)Insertion sort will perform 7 comparisons, 1 swap, 7 memory reads and 2 writes.
Perhaps harry8 was thinking of the bubble sort implementation in the OP, which would indeed stop after one pass in these cases.
Here is insertion sort
You can even improve this further (some improvements have new names), however its base form is not in the class of bad algorithms to never use. Besides Bubble sort, Bogosort comes to mind. And there are of course nice algorithms to use if your data works for them, Radix sort comes to mind. Knowing your data is good advice, knowing never to use bubble sort is also good.It really isn't, compared to insertion sort. https://users.cs.duke.edu/~ola/papers/bubble.pdf shows insertion sort performs 5x better. I also like Knuth's Quote in TAOCP: "[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn't really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!"
> running sequentially through contiguous memory is something computers are just great at doing due to memory caching and prefetching
Name one sorting algorithm that doesn't involve purely running sequentially through contiguous memory.
It'd make me question the stability of the rest of their product too.
We checked, and this particular bug was not caught by the test262 suite - the broken sort worked for enough cases to slip past the Array.prototype.sort tests there. We've added a regression test for this issue in the layer that consumes the interpreter, but I've thought about proposing more aggressive validation of sort behavior to the test262 project.
It was a great reminder to me that while tests may be necessary for quality, they are not always sufficient!
Brad, Code.org Engineering
The other bugs were all mine.
I still always blame my own code first though
which only gets printed if the shell it's running in egregiously mishandles &&...
* https://github.com/code-dot-org/JS-Interpreter/pull/23
Parent comment makes sense to me as a general comment about getting good at JS. Especially given JS has so many new and exciting libraries that get used in production. Ultimately you must fix your code, JS & libraries aren't likely to change in a timely fashion. And of course what I call a bug in the spec must have been considered a feature at one time, some may still consider it so. That's a question of taste and you can always consider yourself 100% correct on any matter of taste simultaneously with those who disagree. :-)
if(foo) { <- js cannot insert semicolon there
Edit: add this comment you have provided approximately nothing in support of your assertion, you can and should do better. I note this thread is JS and a whole lot of this kind of thing going on here I don't usually see elsewhere on HN. It's a shame, discussion is useful to learn things I don't already know. "Nyer, your wrong" not so useful to me, you or anyone else.
I’ve written a ridiculously detailed blog post about automatic semicolon insertion if you want to know all the specifics.
http://inimino.org/~inimino/blog/javascript_semicolons
The K&R brace style is not about putting an object literal on the same line with a return statement or on another line, but about how control structures are formatted.
The reason I said that K&R brace style has nothing to do with semicolon insertion is that it’s possible to write all your control structures with K&R braces and still be bitten by the places in the grammar where line breaks are not allowed, like after a return statement, if you’re unaware of it.
It’s also possible to use Allman braces everywhere and never have that problem with return statements.
gcc's __attribute__(aligned(N))
Whenever you see it if you assume it doesn't do what you think it does from reading the docs that's probably a sound strategy.[1][2]
I'd love it if I'm wrong and there is a way of understanding what it is meant to do and successfully predicting behavior.
[1] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82914 [2] https://gcc.gnu.org/ml/gcc/2014-06/msg00308.html
When declaring variables, `__attribute__((aligned(N)))` indicates you want the variable in whatever format it was defined in aligned to that value. If it is less then the default alignment, it will be allowed to be aligned to that instead. For `struct`s, this would mean that the `struct` is kept in the exact same format (with the same padding, in particular) as the declaration would require, but the entire entity itself is instead aligned to whatever alignment you give.
When declaring a `struct` type, however, the individual members all still have their own alignment constraints, which is where `struct` padding comes in. So when you just apply `__attribute__((aligned(N)))` to a `struct` type declaration, it's not clear how you want to achieve that alignment. If that alignment is a multiple of the required alignment for the `struct` then there is no problem, because you implicitly meet the alignment requirements already.
If it is less, however, then it is not clear when you want alignment requirements met and when you do not (IE. Where should the compiler insert the padding bytes in the `struct`? Should it unalign the first member and then correctly align all the rest? Or pack it as though everything is correctly aligned, and then allow the entire thing and all the members to be unaligned?).
There is already an attribute to solve this problem, `__attribute__((packed))`. All `packed` does is force the alignment of all the members in a`struct` to be 1, which both tells the compiler no padding bytes are necessary, and also means that `__attribute__((aligned(N)))` always works, because every `N` will always be some multiple of 1.
So with that in mind, in my opinion the bug largely on EMACS' side (Assuming I'm reading those messages and code correctly). In my opinion, they shouldn't be using the `aligned` attribute on the variable declaration at all, and instead they should just ensure the `struct thread_state` type itself already has the proper alignment. The fact that they are using `__attribute__((aligned(8)))` seems to indicate to me that somewhere align the line a `struct thread_state` type was defined with the incorrect alignment, and it was fixed by adding the alignment to the variable declaration. But if you just apply the attribute to the declaration of the `struct thread_state` type instead, then everything would be fine, and architectures with a `struct thread_state` with a higher-alignment (like 32, in this example) wouldn't be affected by the alignment requirements of architectures with a lower alignment.
That said, there is something I found very interesting in those posts, though I don't believe it is a `gcc` bug. But it is this syntax:
I didn't actually know you could even put the attribute in-between the `struct` and the structure name. That said, it does make some sense when you realize what it is doing, even though the syntax is kinda screwy - it is for applying `struct` attributes after-the-fact. So while this does work for `aligned(N)` (which has variable and `struct` variants) it would also probably work for `packed`. This would likely make most sense to use in a `typedef`, which would allow you to declare the 'normal' version of a `struct`, and then `typedef` a `packed` version or `aligned` version as well. I've never really had a need to do that, but it is interesting to see. It does technically fix the problem here, but it is the same as attaching an `aligned` attribute to the `struct` type declaration after-the-fact, and I really do think if possible they should be looking at putting it on the declaration of `struct thread_state` instead.All that said, I wouldn't conside...
Over two years and no forward progress! Admittedly, I haven't re-tested this with a newer compiler. But apparently neither has anybody else.
Besides the warnings this doesn't surprise me too much, AFAIK it is not legal to put anything between the `struct` and the structure name in usages of a `struct` type. But from the response gotten over at the `gcc` Bugzilla I would wager the 'inline' versions are in the uncharted waters of "Nobody really knows what that should do anymore, don't do that". Reading the `gcc` bug report again, it seems the last response does actually indicate the error I'm pointing out above, where the attribute is silently ignored, I missed that when I skimmed it the first time.
With that said, the fix EMACS implemented was the same as just removing the attribute completely. If the EMACS code really does need that alignment forced for one of its architectures, it should probably take a look at that fix again and apply the `aligned` attribute on the `struct thread_state` for the architecture(s) that need the 8-byte alignment (If they actually exist), and then remove the attribute completely from the variable declaration.
The compiler actually crashes rather than returning anything? Well, that's more likely to happen when your code has lots of errors in it. "Don't look at me like that. Go fix your code and then come and complain..."
Obviously things like forward and backward compatibility are much more important in the programming context, so you can't just "fix" things like weird side effects or not throwing an error on assignment in an if statement.
Eventually, someone (Natalie) moved the comment below the assignment, and it worked normally. I tried putting it back above, and it wouldn't compile. Can't remember what happened if I left the moved comment in place and put another above the assignment. I found two like that - one in CodeWarrior, one in Turbo Pascal a few years before that simply returned "error 0: no error."
It wasn't anything complicated in either case, just very basic stuff.
Only other time I bumped into it was in Idris, which is to be expected frankly.
If you ever catch them still there with a "no optimizations" flag, then that's a pretty serious bug!
CW had a pretty nice environment to develop in compared to its contemporary competitors, but it just didn't have a solid compiler.
Removing the offending line or adding a different mix of blanks/instructions would get you back to a working state again. Very frustrating.
Now everybody and their dog write compilers and transpilers for young and/or obscurer languages (I'd include Go and Rust in there), and with the immaturity of these environments compiler bugs are a fact of life.
They're never common, but "it's never the compiler" doesn't apply either. It is, however, a helpful reminder that the most likely source of problems is with the author of the code :)
If you're asking for actual examples - sorry, you're out of luck. The 80's and 90's are a bit too long ago for me to remember details.
If you prefer to believe in the magically flawless compiler fairy, knock yourself out.
Not that hard to stumble upon, but it took us awhile to figure out what the heck was going on.
Turns out, on QNX you can't pass short int into variadic function, which is expected behavior as far as C is concerned (you should only pass int or full size types), but it worked on every other arch so it took me a while.
I don't actually recall if we were using the shipped CRT or not, I'm guessing only minimal parts of it were used, if any, since embedded projects tend to write their own subset of the needed standard library functions.
Honestly, I'm surprised that I haven't run into more of them in the wild.
Compilers are the most extreme case. Anything Turing complete is almost certain to have vast swathes of functionality which aren't used by the developer. If a compiler doesn't already have a large user base, then unless you're using it exactly like someone else has, you're almost guaranteed to find some bugs. Honestly that's true for most software, going back to the maxim "don't be the biggest user of any given software unless you're already capable of writing it yourself."
So many bugs. So many crashes. So many performance issues.
I'm one of those that routinely find a bug in a library during the very first use of its API. Every "quick weekend project" turns into "let's learn the build system of this library and send a patch/bug report to the maintainer".
Does anybody know how can I turn this annoying superpower of mine into a job that is not basic Q/A?
If you can find bugs in libraries used in IOS/Android or something, that's worth money and gives you the chance to increase security for millions (billions?) of people.
(Might be confirmation bias, but I have been proofreading a lot of theses for my friends while in college, so it might be trained.)
It's likely that your weekend projects are things you find interesting and it seems likely that the things you find interesting are bleeding edge. It's never going to get better. On the other hand, any good dev team would value someone who can not only find the bug, but patch it.
You need to get somewhere where using the latest and greatest is encouraged..
It's a terrible idea to assume that other humans don't make mistakes. When encountering a bug, start at the top, and work your way down when you conclude that the current level is correct. There is no level of development that is immune.
Sometimes you are to blame. Others, it might be a library. It might be the standard library, or the compiler. A faulty optimization, perhaps. Could also be the OS kernel, or even the hardware (CPU, USB controller, network card, ...). It's all chock-full of bugs.
I've hit a handful of miscompilations while writing boring JavaScript web apps, some only when the JIT kicks in for extra fun. I have a handful of outstanding Linux kernel bugs, one of which cause memory corruptions, has existed at least since 2.6 and is dead simple to reproduce. I have a significant GCC performance degradation bug, triggered by calling "pthread_exit(3)" after an infinite loop. I've had what seemed to be software problems turn out to be PCIe problems.
You might think that, as a developer, you're building a card-house on a solid foundation. But no, it's card-houses all the way down.
> When encountering a bug, start at the top, and work your way down when you conclude that the current level is correct.
I agree wholeheartedly. Saying "it is never a compiler error" doesn't preclude this; it encourages this behavior. Even thinking "it could be a compiler error" invites laziness.
I strongly disagree with your point of view: "it is never a compiler error" not only precludes suspicion of the lower levels—voicing your suspicion of problems in lower layers will generally result in ridicule!—but it reducing critical thinking, bars people from looking into "complicated" projects, and makes them overall less efficient and skilled developers. I also disagree that encouraging a bit of wasted time is a problem. What is a few hours, or even days "wasted" learning your lesson once and for all if it greatly improves your debugging skill and efficiency? You do not learn without mistakes.
"It is never a compiler error" is a detrimental mindset to have, in that it suggests a mentality where you shut your eyes for anything you did not author. After all, it is too complex, too well-tested, too well-designed, and implemented by much smarter people than you. Compiler, library, application, hardware, train, bridge, it doesn't matter.
Not only does this mean that you often won't find the bug you hit, as you won't start instrumenting the faulty LargePopularLibrary—after all, it obviously can't be to blame—but it also means that you won't as much as read library|compiler|kernel|etc source code, much less do development on it, as you think it is above you, despite it by no means being some magical black art.
"It could be a compiler error" invites you to consider all possibilities. Immediately blaming the compiler without reasonable evidence would, despite such a mantra, be a result of terrible debugging skills. These debugging skills should be improved through other means than intentionally teaching falsehoods, and if the subject is not an entirely lost cause, it should correct itself in much more valuable ways if a little time is "wasted" on improper debugging.
Teach proper debugging techniques instead of lying to others, or yourself.
Or worse it could invite curiosity and now you are spending time wondering how could you tell if it's a compiler bug and how would you go about debugging it.
If it's really a compiler bug, you'll find out in the process of debugging your code.
The OP simply said that the chances of finding a compiler bug are small. You seem to have found a few minor bugs, and that's cool, but how does that change the fact that chances an average C developer finding a compiler bug are minuscule? There are probably around a million C developers, do we even have one compiler bug per 10 developers?
I'm sorry, how are total miscompilations and memory corruptions "minor bugs"?
I am arguing against the mentality of dismissing compiler bugs, with the idea that "you will never hit one". Hence my examples of when I hit them during something as high-level as web development. I am not arguing that you'll hit such bug every day, or even every month.
I only have myself and those around me as reference. I have been a software developer for less than 10 years, but with the current total, I have been hitting a few "lower layer" (vm, stdlib, compiler, kernel, hardware) bugs a year.
Maybe I'm just "unlucky". If you want to find real numbers, take a look at GCC/LLVM/libstdc++/glibc/linux bug tracker statistics. I'm sure you will be surprised.
A Swift developer?
Just yesterday I found myself compiling a new part of code in increments because all of the new code together wouldn't compile but adding the code and import first, compiling it before adding @UIApplicationMain would compile just fine. Exactly the same code that didn't build before.
I can't imagine what I would have done if I would have trusted that this was my error because the compiler would not make mistakes.
Though nothing compared to Swift 1.x, things tend to work generally and if the compiler does crash it'll crash on weird programming mistakes (like referencing type(of: self) before init() was called)
... is in the eye of the beholder. They exploit every corner of undefined behavior to the benefit of performance. Indeed other compilers might be "safer."
Keep in mind that they also provide you with UBSan to help you detect when you're doing it wrong.
Isn't the "they" in this thread gcc, or did I misread something?
Note that UBSan is (mostly? totally? originally?) a Google project and it's been ported to both clang and gcc.
The compiler writers write the compiler with the expectation that the program being compiled is correct i.e. to the specification.
Now when the program fails to be correct, optimizations can result in "weird" results, which is not really incorrect since the input was incorrect.
If you're able to narrow it down that far why not then fix your bug?
Essentially, it was not worth more of my time to figure out how aggressive optimizations were breaking the parts of a memory bandwidth constrained function that aren't worth optimizing in the first place.
For GCC inline assembly means "take your grubby hands off". For clang it's essentially an invitation to do whatever.
That's not true at all. Clang respects the clobbers entry on inline assembly and does not do whatever it wants. See GCC's documentation on it: https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html#Clobber...
Based off of your description you probably just needed to add the "memory" clobber to tell the compiler that any registers it might have kept are no longer valid.
I'd rank the likelihood of an error like this :
- My fault
- API bug
- broken environment (ex: corrupted object files)
- hardware problem
- OS bug
- compiler bug
- bug in malloc()/free() ;)
Of course, that was pre-1.0 software..
As of this moment I am begrudgingly creating a support ticket with AWS for an issue which I am 99.99999999% confident is in our VM and has nothing to do with AWS itself.
For some reason, "AWS issues" is one of the first things raised, even though we are unlikely to be hitting AWS edge cases, not being Netflix-scale.
Honorable mention: "Kernel issue"
That's aside from the more common issues of "this VM is just going to bite the dust", which is something I feel is just inevitable.
The kernel is more reliable, IMO (except when it comes to the Thinkpad TrackPoint drivers).
That's exactly documented behavior: http://docs.aws.amazon.com/AmazonS3/latest/dev/Introduction....
That's a hugely unuseful caveat in practice though. I'd really love to have consistent reads.
Errors in the run-time library and errors that crash the compiler are much more common. While many eyes cover a lot of search space. The space they have to cover has grown immensely.
If you step off the trodden path you can find problems much more often. Just recently I encountered a function in a run-time library that freed the amount of memory the alloc asked for instead of the amount of memory the alloc function actually returned (Sometimes it returned slightly more if the remaining space was not enough to hold a free-memory structure).
It would not surprise me if the population using that particular compiler/platform combination numbered less than a thousand.
I wasn't personally developing the core simulation software itself at the time, just building it from source and writing extensions. I don't know if these frequent breakages were actually outright compiler bugs or just relying on conventions that weren't guaranteed by language specs. But I do know that switching to one particular blessed compiler revision was often the fastest way to pass validation and move on to your actual research problems.
I was running under Cygwin and the issue was something about the Java-based readline library.
I filed a ticket (linked in my blog post but the link is broken now), but the maintainers' response was something like "Yeah right. Closed."
You'd think compiler bugs would be more obscure than 1+2. :-)
https://www.google.com/search?q=ios+1+2+3
Apparently the problem is that the '+' character was being thrown out, so Scala only saw '12'.
That sounds pretty horrifying! But reading the issue (linked from the github issues linked by sibling), the actual response seems pretty reasonable. He looked into it and determined it was an issue with your setup, and asked for more information (if he couldn't reproduce it, what else could he do?). He also made a guess at what was wrong. You provided more information and a workaround (nice!) and a few weeks later he closed it saying he believes its now fixed. Seems ok to me.
The original source code did nothing special - it was simple code and due to specific optimisations that the compiler performed, inexplicable seemingly random errors would arise. One would have to constrain the optimisations the compiler would do to get the code to execute correctly.
No compiler is bug free. The bugs can manifest in strange ways and sometimes they will manifest only on specific kinds of data (edge case data).
Certainly there are many programs that are written incorrectly and give rise to apparently inexplicable errors that are due to misunderstood language features or specified compiler limits.
However, there are also many programs that do not have such source code errors that end up being rewritten in some way to avoid compiler based errors.
The worst I have seen is when dummy statements have to be put in to the source code in order to get the program to work correctly. I have seen compilers change the precision of numbers from one version to the next and you have to add additional code to restrict those numbers back to the specified range. I have seen compilers allocate multiple i/o buffers as an optimisation that causes a program to fail when a single i/o buffer allocation works fine - one has to turn off the optimisation - no documentation available as to how the compiler generated code uses those buffers.
All I can say is that it takes a fair amount of investigation to determine what kind of bug it is when it is subtle and randomly occurring. It can be everything from errors in the source to errors in the libraries to errors in code generation to errors in the o/s (including driver errors or memory errors).
Anyone who blanket says the compiler is not to blame is living in a rose coloured glasses world. Compilers are complex programs and the source code for them can be just as wrong as for any other program. The code generated for compilers can be just as bug ridden as any other program.
1) Borland Turbo Pascal, where code would not execute correctly in the presence of a comment near the top of a loop. Deleting the comment caused the correct loop execution.
2) Texas Instruments DSP C-compiler sometimes failed to unroll loops correctly. Certain loop forms needed to be avoided as a result.
3) Recently I've been working on a C-compiler written in Golang, and the grammar definition was raw enough that it definitely had bugs. The bugs were fortunately obvious in that it would refuse to compile valid C code.
Of course, 99.98% bugs were mine.
C++ was another hotspot of brokenness for early gcc 4.x.
For example: https://stackoverflow.com/questions/45424272/gnu-gcc-bug-whe...
Don't think I've seen one since, though I have found a nasty footgun in Scala where if you do a fold of a parallel collection, you can give the fold a starting value, which will be supplied to all the executing threads. The result therefore depends on how many cores you have running. Sadly I suspect that one's in spec.
In 10 years, I've seen 3 compiler bugs. That's just enough to leave the door cracked open for "y'know, it could be a compiler bug..."