4 ms·

> 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

by JadeNB 4y ago

> 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?

generichuman 4y ago
> 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.
- saagarjha 4y ago
  Perfect optimization is at the very least Turing complete.
- JadeNB 4y ago
  > > 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?
p1necone 4y ago
> 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.
mastax 4y ago
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.

by JadeNB 4y ago

generichuman 4y ago

> 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.

saagarjha 4y ago
Perfect optimization is at the very least Turing complete.
JadeNB 4y ago
> > 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?

p1necone 4y ago

> 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.

mastax 4y ago

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.