He Who Gives Up Correctness for Performance Deserves Neither | Hacker News Reader

He Who Gives Up Correctness for Performance Deserves Neither

gavinhoward.com

37 pointsgavinhoward18 comments

I think that this post is motivated by a comment thread involving me in this thread: https://news.ycombinator.com/item?id=37967257

I don't think I've ever been the recipient of a diss track before. Here I'm called a Useful Idiot. Other folks can read the thread if they want.

The problem with C is that it has the same problem as hardware development but people blame the developer instead. With HDLs you have both simulation and synthesis and these two can have different behaviour, exactly like C.

The primary difference however is that say VHDL's std_ulogic type explicitly encodes what is considered undefined behaviour in C such as accessing uninitialised memory. So called U and X propagation turns expressions that depend on uninitialised values into U and X respectively. This means that your simulation tells you where the undefined behaviour is lurking. You can still synthesize your buggy hardware, nobody is stopping you, but it's not hidden.

Meanwhile with C you get into the "when did you stop beating your wife" scenario, where you are assumed guilty until proven innocent.

The difference being that when C code goes wrong, most developers just shrug their shoulders unless they work on a regulated industry.

Whereas when hardware goes wrong, usually people deal with it like any faulty product.

The real problem of "correctness" is at a higher semantic level. But it is certainly true that it doesn't matter how fast you get the wrong answer.

Machine learning begs to differ. Code doesn't have to be right in order to be useful.

There was a talk about UB that proved to me there is no way out of this UB box for C++.

Specifically how calculating an int aka signed 32 bit integer index was more performent than calculating a uint aka unsigned 32 bit integer index.

Because the former because an assembly intrinsic and the later can't because uint wraps at 32 bits not 64 bits.

So whether you choose wrapping or UB you are going to piss somebody off.

After all everybody wants the intrinsic. After all you are triggering UB anywhere the wrapping matters.

I'm not following you here. Most systems (if not all) are byte-addressable 2's complement systems, and in a 2's complement system, you use the same instructions for math for both signed and unsigned integers. Compiler writers aren't using different instructions for signed vs. unsigned, they're using different assumptions about interpretations, along the lines of "if X is signed, then x = x + 1 will never wrap, because that is UB, and as we all know, programmers will never intentionally or unintentionally, invoke UB, so we can skip some checks and if the program blows up, it's the programmers fault for not being perfect."

Depends on the target. If you have a 32 bit unsigned integer and your hardware wraps at 64 bit, you need special logic to wrap correctly at 32 bits. This also can prevent some vectorization since you don't have the guarantee that the result of x + 1 is one larger than x.

Or just use size_t like was mentioned in that talk.

Certainly you can refactor your code to avoid performance pitfalls but that is effectively always true for large programs...

The reality is the number of similar UB based optimisations has grown considerably and even divesting of them would involve likely close to a man-decade worth of effort (unless you just discarded all of those performance improvements).

Same applies to C, Objective-C and Objective-C++.

Changing C to have less extensive UB doesn't give you correctness. It gives you slightly less wrong code with possibly slightly different performance properties.

Correct code looks something like write the thing in a theorem prover, where it mostly suffers existentially.

So give you can't/won't write correct code, all you have is a Pareto surface denoted by performance and correctness aspects, and the distance between what you're shipping and that bounding optimum.

Author here.

While you are technically correct, the key is your own statement:

> where it mostly suffers existentially.

Yes, theorem provers exist, and they work. But proving that the end result, the actual machine code, corresponds to the proven code, is the big problem.

When I talk about correctness in the post, I'm really referring to two things:

1. Correctness as you have defined it,

2. The compiler artifact being as faithful as possible to the input source code.

Avoiding UB is an excellent way to improve the latter.

I feel like this is one of those things you learn pretty early on in your life as a programmer and then just accept it without question and then start adding in superfluous variable declarations and assignments to preserve the behavior you expect in those odd scenarios where you know your compiler might decide it knows better than you.

I had no idea it was a thing that could be debated or changed, very interesting.