Comment by tialaramex | Hacker News Reader

Comment by tialaramex | Hacker News Reader

Parent Full thread

There's a CPPCon talk - which I'm sure somebody else can remember and link - where Matt explains how this started. IIRC He was initially wondering whether C++ iterators are actually the same price as the C-style for loops you'd once have used instead with an index counting up or a pointer increasing. If it was slower then in Matt's industry that's useless, but if it's the same speed then the improved clarity of what you mean is valuable.

Obviously the results will be identical but because the iterators look fancy (and are easier to think about) maybe there's some object getting constructed, it might be a lot heavier - right? Nope, same machine code. Matt initially did this much more manually, the Godbolt web site is just that same idea getting further enriched over time.

This is even more striking for something like Rust's iterators that don't look at all like it's just the C-style for loop, there's a call to make the iterator IntoIterator::into_iter() and then repeated calls to its next() method, sounds expensive - but nope, once again the optimiser can see what's going on here and emit the same machine code. Having a tool like Godbolt to confirm (or sometimes refute) the belief that these things are actually the same is really useful, as even after confirming that optimisation is needed if the proposed "optimisation" doesn't change the machine code it wasn't an optimisation, just making the program needlessly harder to understand.

It's the CppCon 2017 talk with the title "What has my compiler done for me lately? Unbolting the compiler's lid".

The Compiler Explorer backstory starts here: https://youtu.be/bSkpMdDe4g4?t=4m57s

> This is even more striking for something like Rust's iterators that don't look at all like it's just the C-style for loop, there's a call to make the iterator IntoIterator::into_iter() and then repeated calls to its next() method, sounds expensive - but nope, once again the optimiser can see what's going on here and emit the same machine code.

> Having a tool like Godbolt to confirm (or sometimes refute) the belief that these things are actually the same is really useful, as even after confirming that optimisation is needed if the proposed "optimisation" doesn't change the machine code it wasn't an optimisation, just making the program needlessly harder to understand.

I'm not sure I understand this. Wouldn't you expect higher-order code to be easier to optimise, since it comes closer to telling the compiler what you want to do, so that the compiler can figure it out, rather than forcing the compiler to divine the big-picture intention of a bunch of low-level instructions?

And, if high-level code generates exactly the same machine code as low-level code, isn't that an argument in favour of high-level code—it lets you code declaratively, saying what you mean—rather than against high-level code? An optimisation might be optimising for intelligibility, not just run-time … and, while an experienced low-level C programmer might find the low-level code more readable, surely the non-expert maintenance programmer who comes afterwards will be grateful not to have to recognise the low-level patterns but rather have them spelled out in high-level code?

> Wouldn't you expect higher-order code to be easier to optimise, since it comes closer to telling the compiler what you want to do, so that the compiler can figure it out, rather than forcing the compiler to divine the big-picture intention of a bunch of low-level instructions?

Optimization is an NP-hard problem. What compiler backends do these days is mostly to pattern match known optimizable code blocks. Some of the other optimizations are an approximation of the actual solution. The order of optimization type being made also affects the result.

So in a perfect world where we could solve NP-hard problems, higher-level code (with more constraints put on it -- as in Rust traits, not C++ templates) would be easier to optimize. But since we don't live in that utopia, nope.

Perfect optimization is at the very least Turing complete.

> > Wouldn't you expect higher-order code to be easier to optimise, since it comes closer to telling the compiler what you want to do, so that the compiler can figure it out, rather than forcing the compiler to divine the big-picture intention of a bunch of low-level instructions?

> Optimization is an NP-hard problem. What compiler backends do these days is mostly to pattern match known optimizable code blocks. Some of the other optimizations are an approximation of the actual solution. The order of optimization type being made also affects the result.

Right, and that's what I meant—although I certainly see why it sounded like I was referring to some infallible and perfect optimisation process.

To be precise—and sticking with the theme of iterators from my parent, though there's nothing particularly special except that it's a familiar pattern—if there's one high-level iterator construct, isn't it more likely that the average programmer will write each invocation of an iterator in the way that the compiler expects; whereas, if each user has to roll their own iterator, then different average programmers will roll different iterators, and it's more likely that a programmer will write something so baroque that the compiler doesn't realise it can apply a known optimisation?

> I'm not sure I understand this. Wouldn't you expect higher-order code to be easier to optimise, since it comes closer to telling the compiler what you want to do, so that the compiler can figure it out, rather than forcing the compiler to divine the big-picture intention of a bunch of low-level instructions?

This assumes a "sufficiently smart compiler", whereas if you write the exact low level basic for loop (or unroll it manually or whatever) you want you can be confident that even a pretty dumb compiler is still going to output something close to optimal.

It just seems like most compilers are "sufficiently smart" for this sort of thing nowadays (and have been for quite some time). But it's not always the case, and the code you think would obviously be optimized by the compiler isn't always. So it pays to check these things if you're writing code for something where potentially eking out extra performance really matters.

What a nested rust iterator is doing, semantically, is creating a struct containing a struct containing a struct... that calls a method that calls a method that calls a method. The compiler has to do a lot of work to make that into anything approaching a C for loop. Just try running unoptimized rust code and you'll see.

Reply on news.ycombinator.com