Hacker News Reader

Comment by kllrnohj | Hacker News Reader

> More pertinent to this, modern CPUs have multi-stage pipelines and branch prediction.

A correctly predicted branch is still slower than no branch. An incorrectly predicted branch is one of the slowest things you can have happen on a modern CPU.

> Third, just the possibility of throwing an exception has a cost as the program has to have the code to unwind the stack.

Incorrect. The exception handling code does not execute in the normal path.

-fno-exceptions ~never makes your code faster. It does, however, shrink your binary size. Which is a non-trivial cost, but not the focus of the discussion.

View on HN

> An incorrectly predicted branch is one of the slowest things you can have happen on a modern CPU

Per Agner Fog, misprediction on Ryzen will cost you 18 cycles. On Haswell family, 15 to 20. Floating point division can cost you more cycles, both in latency and throughput. Even just plain old L3 latency can be worse than misprediction.

That’s oversimplified. If the falsely predicted branch issues a load instruction for example, you might use up valuable memory bandwidth, trash cache lines, etc. There are way more side effects that can make false branch predictions more expensive. It’s also extremely microarchitecture dependent, proprietary and undocumented what exactly happens, which is why we need to benchmark the actual code under consideration.

Yes. Also a misprediction affects all instructions in flight after the branch, a floating point operation or slow load only affects instructions that depend on it.

> Floating point division can cost you more cycles, both in latency and throughput

No, on Ryzen, 32-bit float division, divps instruction, has latency 10 cycles, throughput 3 cycles. 64-bit float division, divpd instruction, has latency up to 13, throughput up to 5. Both faster than a cache miss, in latency and especially throughput.

> Even just plain old L3 latency can be worse than misprediction.

Yes. BTW, the slowest thing that can happen on modern CPU is not L3 access, it’s access to a cache line modified by another CPU core. Even slower than main memory latency.

> plain old L3 latency can be worse than misprediction.

true but the instruction fetcher is driven by the branch predictor, so a misprediction to rarely executed code in practice also implies a cache miss.

> Incorrect. The exception handling code does not execute in the normal path.

This is true only if only exceptional things throw exceptions. In some APIs normal, but not successful things throw exceptions. Things like file not found are often pretty normal, but may throw an exception.

I often hear this argument, but I find it misleading. First, is suggests that we need to have two systems: for "normal" errors and for exceptional ones. Second, the programmer now has to classify the conditions into normal and exceptional without any real criteria to do that. Is out of memory exceptional? For many applications it is, but not for Phothoshop where it's a normal state and you just have to free some memory and try again.

Exceptions are exactly same as errors, they're just a different way to handle them. Errors are natural to programming, because nearly every function may end up in two states: it successfully carried out the task (no error) or it failed to carry it out and here's the reason why (error).

The reason we have exceptions instead of errors is generally because we want the code to look syntactically sweet. A mere "a.b + c.d" in modern language may involve three method calls: to get "a.b", to get "c.d", and to add them using some custom definition of "+". Each of these methods may run into an error and exceptions provide a syntactically sweet way to handle this.

Not two systems, two APIs; like Int32.Parse(String): Int32 and Int32.TryParse(String, out Int32): Boolean in .NET.

It's quite rare to want to handle an error condition half-way up the stack and do anything more than log / cleanup and resume unwinding (whether implicitly via exceptions or monadic errors or automatically via exception unwinding library).

You normally handle errors like file not found, couldn't connect, etc. near the leaf call which failed, if you want to handle them at all. So it makes sense to decide what error condition you want; do you abort the whole task (exception works great!), or do you do something interesting like retries or alternatives (exceptions not so hot, booleans or some kind of error code better reflects that the handler code is conditional rather than exceptional).

Yes, I see the reasoning now. But isn't this pure syntactic sugar? I.e. if exceptions weren't costly, a good way to implement TryParse() would be to simply call Parse(), catch the exception and dress it up as a boolean.

If exceptions were free then yes, but there's not really any language/platform where that's the case. It'd instead be the reverse - Parse() calls TryParse() and throws an exception on false.

A reverse approach would lose exception details; you cannot recover what exactly happened from a mere boolean and you may need it.

It may not be possible to make exceptions totally free, but the rest of the language may be slow enough so they won't stick out :) Example: Python.

Typically "try_parse" returns more than a bool on failure. What it does return is then wrapped and thrown.

The context switch and device i/o will dwarf the cost of the exception. So it's a bad example - "file not found" is a pretty reasonable exception.

There certainly are APIs that abuse exceptions, but IMHO far fewer than most Go (et al) programmers claim.

Not sure about the current state but not too long ago the unwind information wasn't stored separately from the regular path which meant that they used up valuable instruction cache.

At least on GCC since 3.x, unwind info has been on a separate section. It is not even machine code (dwarf unwind opcodes are run by an interpreter), so it is unlikely to be in the instruction cache.

The unwind info might end up calling destructors or exception handlers, which might or might not be on a separate page. You are probably referring to that.

>> Third, just the possibility of throwing an exception has a cost as the program has to have the code to unwind the stack.

> Incorrect. The exception handling code does not execute in the normal path.

But it does need to undo all allocations and such that were made between the exception and the nearest exception handler, doesn't it? Isn't this "unwinding the stack"?

Simply returning from a function is also "unwinding the stack" but nobody writes blog posts & articles about avoiding return ;)

But what you're referring to is a cost, yes, but only a cost when an exception happens which should be rare. And it's not that much more expensive of an unwind than what would happen if you `if (err = thing()) { return err; }` everywhere in your call stack anyway.

> But it does need to undo all allocations and such that were made between the exception and the nearest exception handler, doesn't it? Isn't this "unwinding the stack"?

it should do so if you use error codes too - else you've got an incorrect program which leaks things like memory (not too bad on our current computers), file handles (really sucks on windows), sockets (really sucks on linux).

I agree, I was just failing to grasp how the execution path of exception handling code is not "unwinding the stack". The compiler will have to prepare each stack frame and mark what needs to be deallocated and the exception handling code won't just jump straight to the nearest handler, but will visit each stack frame and undo the allocations, calling destructors and such.

On the other hand unwinding the stack is not complex and won't add much to program size.

why would an error checking branch ever be mispredicted. more to the point why would error checking or exceptions ever be in an optimized inner loop.

If they're rare enough that they are ~never mispredicted then why does the cost of exceptions matter when they do happen? If they are common, then they're going to be mispredicted.

The demo benchmark, for example, would produce basically always missed branches. Well, if would if the compiler didn't just strip the empty branch, invalidating the entire benchmark.

Because the branch prediction cache puns an error check with a loop predicate and some other random branch.

Branch predictors steadily get better, sure, but they're not infallible. Remember that reducing the total number of branches in a program helps the branch predictor predict better.

Reply on news.ycombinator.com