Hacker News Reader

Comment by cperciva | Hacker News Reader

On the topic of compilers being hard: In my repositories I'm carrying around a 5 year old workaround (https://github.com/Tarsnap/libcperciva/commit/92e666e59503de...) for a 6 year old bug (https://bugs.llvm.org/show_bug.cgi?id=21183) in clang/LLVM.

You might think that "incorrect code gets generated" would be a maximum-priority must-fix-before-the-next-release bug in a compiler, but apparently not.

View on HN

Wow, this is the first time I've seen the computed goto extension. Delightfully gross!

https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html

Computed gotos are commonly used in main loops of bytecode interpreters to get a separate dispatch (indirect jump) at the end of handling each bytecode, so the CPU's branch target buffer has a better chance of predicting the indirect jump target for the next bytecode based on the previous bytecode. For instance, CPython's dispatch loop uses computed goto on supported platforms, and Erlang's BEAM VM (in non-JIT mode) uses computed branch labels to convert bytecodes into branch addresses at bytecode load time.

I suppose, for twice the latency, CPU designers could implement (a hash of) the previous branch address from the source instruction pointer as part of the BTB tag, similar to using the global branch history as part of the state in the branch predictor. Presumably, the global branch history could also be used in the BTB tag to give some hint as to which bytecode we've just finished executing.

Though, where it really counts, interpreter writers are already often using computed gotos, reducing the reward to cost ratio for implementing such specialized BTB improvements.

On the other hand,

   while (1) {
       switch (...) {
           ...
       }
  }

is probably rare enough (and almost certainly in a hot loop) that a very specific optimization flag might be better than a syntactic extension. Granted, an optimization flag doesn't work for Erlang's threaded code use case.

You'll also find them used in CPython's ceval.c

I use them in both my C befunge implementations:

https://github.com/serprex/Befunge/blob/c97c8e63a4eb262f3a60...

Actually shocked to hear this considering the number of people and companies currently working on LLVM.

The code in question is related to setjmp/longjmp. As a general rule of thumb, this is something where the gut reaction to any bug report is going to be "you're doing it wrong"--the C standard actually provides a lot less guarantees here than most people believe it does. I haven't read the verbiage and the bug report in question in enough detail to ascertain if this is true or not, but it isn't in the least bit surprising that most people see setjmp/longjmp and immediately table the issue as being low-priority.

Having read the comments in the llvm bug report, it seems pretty clear that it is a real bug and that they have at least an idea of where the bug is.

Not that surprising given that it seems specific to asan mode and only in the presence of setjmp/longjmp. I.e. this cant be that important unless the same bug shows also in non-asan Setjmp/longjmp case. Setjmp/longjmp are often a source of trouble for the register allocator or related optimization due to its unique properties. Often the optimizing compilers treat set/longjmp as "give up almost everything around those functions" but maybe llvm is trying hard to model it precisely and failing. But I haven't personally looked at the relevant code in llvm so this is mostly a speculation.

The bug shows up without asan. We literally tripped over it in production with code compiled with "clang -O2".

Then I agree that this is surprising. That means clang/llvm is not modeling set/longjmp correctly in general and that is not acceptable as a C compiler.

That's apparent from your ticket (which is marked as a duplicate) but on the one you linked to, all the offending compiler lines contain asan. Is there a chance this is impacting prioritization?

Could be. I'm not an LLVM developer so I don't know how they prioritize issues.

Regarding asan bugs, if you do not free all of your memory before exiting main it will complain about stuff and end up calling _exit I think which does not flush the buffers.

No, performance is maximum priority.

That's a "great on the surface, bad when you think about it" thing if I've ever seen one.

Who cares how fast the code is, if it isn't the correct code?

I have solved the halting problem. Every program you write compiles and executes as HALT; and therefore it's possible to determine if a program halts! It might not be correct but it sure is fast!

https://en.wikipedia.org/wiki/Full_employment_theorem

You've broken the full employment theorem for compiler writers.

The practical effect isn't what you think it is.

Many compiler writers are employed by hardware companies, and these companies are employing them to sell their hardware chips. For these companies, even a 1% boost in performance on $BENCHMARK can drive measurable impact on sales. Even if you're not worried about driving hardware sales, performance tends to be the major benchmark that gets mentioned in comparisons--note how the "Benchmarks Game" (what used to be called the Programming Language Shootout) compares languages solely on the basis of performance.

In other words, if you look at actual customer behavior, performance tends to be one of the most dominant factors in choosing one compiler over another (language compliance is probably more dominant, however). Surety of correctness is not a major factor at all.

Now, in order to actually report benchmarks correctly, you have to implement them correctly, so to some degree you have a basic guarantee that the compiler will usually work. But someone pointing out a soundness issue using a hypothetical example (as opposed to real code) is going to end up low priority because the evidence is that it doesn't matter in practice for the real, large applications that customers care about (as no one else has complained about it for the past several years).

In summary, practical performance will win out over theoretical correctness, but not practical correctness.

> …"Benchmarks Game" … compares languages solely on the basis of performance.

Not true.

1) source code size is compared

https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

2) correctness is checked

https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

3) time "to complete and log all make actions" (build the program) is also logged

> 1) source code size is compared

This is new to me (the Benchmarks Game has been around for well over a decade).

> 2) correctness is checked

This is par for the course of benchmarks. A benchmark that is incorrectly compiled provides no useful information whatsoever about performance. It's not really what people mean when they complain about correctness issues in the compiler (which is generally referred to as soundness in literature).

> 3) time "to complete and log all make actions" (build the program) is also logged

Performance in a compiler is usually taken to be a combination of runtime, code size, and compile time, although all three components are not weighted equally.

Back on May 23 2006, a sortable column of GZip source code size measurements:

https://web.archive.org/web/20060523195137/http://shootout.a...

https://web.archive.org/web/20060519213743/http://shootout.a...

> Performance in a compiler is usually taken to be a combination of runtime, code size, and compile time

The benchmarks game shows source code size, not compiled code size.

If people cared about correctness, they would use CompCert instead of GCC or Clang.

Or create OSes where applications are all written in managed languages, and the use of GCC and clang is gate keeped to the OS vendor and native libraries, just an idea.

Bit of a nitpick, but the real value is in safe languages, rather than managed languages, no? The distinction is a little blurry, admittedly, but as an example, I figure that verified SPARK counts as safe but unmanaged.

Because as you might have guessed, I was speaking of iOS, Android and ChromeOS, while SPARK as much as I like it, is a very niche technology.

I should have gone with a less niche example: the safe subset of Rust. D also has a safe subset.

Still niche, Rust is not up to the stuff that app developers expect in terms of tooling and D still has quite a few @safe bugs to sort out, among its current adoption issues.

Unfortunely regardless of their own reports regarding CVEs, Microsoft, Apple and Google keep turning to C and C++ for their bottom layers + managed languages, instead of going full speed in some of those alternatives.

So it appears to be the long term solution to mitigate security issues, while keeping compatibility with existing code and tooling.

Why use managed languages when you can prove your code correct?

With what, Frama-C? Good luck getting it adopted outside domains that enforce its use for code certification.

Frama-C is a specific compiler. It has not much to do with proving your own code. (And C ain't a good language for writing code you want to prove correct in.)

You are right that after having proven your code correct, you might want to use an implementation (compiler or interpreter), that is also proven correct. But those are still two different things.

Frama-C is a framework for code analysis. It can help proving code with the aid of ACSL (JML-like notation for C contracts).

But I agree that C is not the best language for writing critical code.

CompCert doesn’t guarantee these two functions will work. Thanks, didn’t know about that project.

I do; low level, OS and library code should be both. It's not an either or; you start with the correct code (and code to verify), then if needs be you optimize.

So you're saying maximum priority is correctness, and performance second place? Because if you don't have correctness you can't "start with correct code"

If you have a broken compiler, you can have broken generated code, and not even know it. This isn't about whether or not your C code is correct, this is about whether the assembly that's generated matches the behavior in your code.

How is this not confirming the point you're replying to?

Anyone who's decided to use C has already made that choice, so it makes sense that C compiler writers would follow their priorities.

In my opinion, a program that is wrong is always worse than a slow program that is correct. Full stop, no exceptions.

Almost every commercially successful product I've worked on has been known to be wrong at every point in its useful life. I've worked on a lot of microservices that had no known bugs for most of their deployed life, but they were simple parts of more complex systems that did have known bugs. The computing world is built top to bottom mostly out of programs that are broken.

If this had not been possible, the industry would have gone the way Dijkstra advocated, with mathematical rigor applied to all programming.

Queue pedantic counterexamples.

Anyway, in this day of just-in-time software we're not going in that direction any more.

What direction is that? The direction of correct software?

Right. Mostly-correct and on-time is all we're getting paid for. That's what agile is all about.

Hmm, so no floating point math ever, only use arbitrary precision? As far as I know most 3D games do correct-enough math because it'll be replaced in a couple frames anyway.

Of course not. Correctness doesn't mean that everything has to be perfect. It means that things work as defined. A C program should operate as specified.

Performance of the compiler, that is.

Are you sure it's not fixed? https://reviews.llvm.org/D11495 was fixed on 29/7/2015.

That's marked as being Asan-specific, and the bug isn't. So... I don't think so?

Reply on news.ycombinator.com