6 ms·

I find it funny and think it's pretty telling that there are bold claims made that are only crossed out after the author is corrected. I feel like a C++ compile

I find it funny and think it's pretty telling that there are bold claims made that are only crossed out after the author is corrected. I feel like a C++ compiler (or any compiler, really) could do practically any optimization that any other one can do, unless that language has explicit restrictions prohibiting such an optimization (e.g. like if the language prohibits the implementation from generating multiple copies of code). The question is just how smart the compiler would need to be, and that changes as a function of how strict the language is. The more loose the language is, the more smart the compiler needs to be. The more information you encode in the type (or make easy to infer), the less smart the compiler needs to be. Whether it's practical to develop a smart-enough compiler in a reasonable amount of time is probably the real issue.

Galanwe 9y ago
"unless that language has explicit restrictions prohibiting such an optimization" It is indeed true that C++ is not able to easily express aliasing. It is extremely cumbersome and error prone to properly specify the aliasing rules when using pointers (especially when you start using char* and void*). So either you force the programmers to place a lot of `restrict` everywhere (expect 1/100 programmer is able to understand/do this properly), or you just fallback to not optimize these cases to their maximum (safe), or allow the compiler to aggressively try to guess the aliasing by itself (and enjoy mind crushing debug sessions later on).
- DannyBee 9y ago
  We used to have languages, like fortran, that were incredibly explicit, and people didn't like that either :) " or you just fallback to not optimize these cases to their maximum (safe), " No, you fallback to runtime aliasing checks if it's important enough. If something can later prove they alias or not, it eliminates the conditional.
  - flamedoge 9y ago
    Question is when do you stop? At what point does adding runtime checks become too expensive? I doubt you want to end up with gazillion checks for non-overlap. C and C++ both seem to lack user-specified type aliasing relations. You have to work with standard base types. I want to be able to declare my own type that is unique on its own and aliasing relations with other types.
    - DannyBee 9y ago
      Sure, and that's a reasonable thing, i'm just saying "the world where nothing aliased and users specify all possible aliasing" didn't turn out to be a fun one either. Honestly, while it seems a good idea, most languages that allow you to specify complex aliasing relationships tend not to be translatable into usable metadata by anything but very high level compilers in a lot of cases. Either they have to evaluate the language-level aliasing rules in the compiler (which requires a high enough level IR for them to still be correct on the IR, and means your compiler is language specific), try to translate them into something more generic (which almost always loses info), or fall back to (n^2)/2 space pair aliasing (IE for each n pointer, specify which n pointers it aliases or no aliases with). They also have to be queryable in essentially constant time for a pointer pair or a memory location and a pointer to have a reasonable speed compiler. This means, for example, if your rule says "they don't alias if every field of every subobject is in blah relationship", that ain't gonna work well unless the answer to that is precomputed and doesn't take up a lot space to represent for the objects. Most choose the middle ground to make all this happen (or have a high level ir, optimize some at high cost, then choose the middle ground). So the problem is not usually coming up with cool things you can say at a high level, it's making them usable to the compiler. I believe, in fact, rust has had precisely this problem with various features, and added a higher level IR to attempt to ameliorate this. The downside is if you don't find a way to transfer it to the lower levels, you miss optimization at the high level due to not-exposed operations (IE things that are lowered), and then the lower level doesn't have the info the higher level did, so you still miss some optimizations So you can have the nicest, most complete aliasing specification in the world, and making it help an optimizer may just not work at all. The late 80's are littered with languages where this was true. Then the early 90's to mid 90's did the same thing with parallelization. see, e.g, https://en.wikipedia.org/wiki/High_Performance_Fortran https://en.wikipedia.org/wiki/High_Performance_Fortran The paper ken kennedy wrote on it before he passed away is a great read, and led to later compilers, etc, being much better about this sort of thing. (Rust should pay attention to the "different optimizations", etc parts and hope there is never a second compiler for rust that gains traction :P)
  - kibwen 9y ago
    > We used to have languages, like fortran, that were incredibly explicit, and people didn't like that either :) I like to think that language design is oscillating around the sweet spot, with a general trend towards convergence. :P First too strict, then too loose, then too-strict-again-but-a-bit-less-strict-than-the-first-time, and so on and so on. Eventually we'll get there... I hope!
- pif 9y ago
  > expect 1/100 programmer is able to understand/do this properly Personally, I'll never accept such an argument as a valid reason to judge the quality of a programming language, unless we stop considering the amateurish programmers when computing the average. For example, a professional camera is meant to be used by a professional photographer, and it is judged exclusively by the quality of the pictures the best photographers in the world can take with it, not by the quality of my kid's birthday. In a similar way, I'd expect programming languages to be judged by what best programmers can do with them: if the average programmer is your company can't fully exploit the power of a mature, professional tool like C++, question the programmer, not the tool. Sure, you may say that, from certain points of view, C++ is rotten rather than mature, but it was never meant to be used by people who consider "C++ for dummies" a valid reference.
  - simias 9y ago
    C aliasing rules are far from simple though. If I review some code and encounter a "restrict" keyword it's going to give me great pause. It's very easy to get it subtly wrong and those types of bugs are generally pretty tricky to track down (it will generally only fail with a certain level of optimization and can be very compiler-dependent). Since "restrict" is often used in function parameters you need to make sure every caller gets this right. And the compiler will do very little to help you track down incorrect usage. So in my opinion it's more like a professional camera featuring a "format storage" button prominently on top. A pro should know not to press it, doesn't mean that it's good design.
  - Galanwe 9y ago
    >> expect 1/100 programmer is able to understand/do this properly > Personally, I'll never accept such an argument as a valid reason to judge the quality of a programming language, unless we stop considering the amateurish programmers when computing the average. When I say 1/100 C++ programmers are able to properly understand aliasing rules, and confidently use `restrict`, I was already talking about professional senior programmers. If you consider the whole set of C++ programmers that would drop to 1/1000. We can discuss the numbers, but from my experience working in some very low level areas where you would expect C++ (or C) developers to know that kind of thing, I would say 1/10 would understand really how `restrict` works. On that basis, I would say that, yes, C++ does not a good job at handling the aliasing of memory locations, since the required mental mumbo jumbo required to declare aliasing properly is too consuming for even experts.
DannyBee 9y ago
"Whether it's practical to develop a smart-enough compiler in a reasonable amount of time is probably the real issue. " These issues have been solved pretty much forever (in terms of what is possible) at the compiler level. You just select your engineering tradeoff. There is no more magic in this area :) We can scale the algorithms better than we used to, but the precision tradeoffs, completely fixed at this point. In any case, most of the languages have to be able to express these properties in a more generic way (or else have a rust-specific IR/compiler, which has it's own issues), and if they can do that, you can usually make the other language express the same thing. This is, in fact, one of the ways things get standardized. People build an extension, formalize it later.
- adrianN 9y ago
  I disagree that there is no magic left in compiler construction. It's still an active area of research with many papers published every year.
  - DannyBee 9y ago
    That's not what i said. I fund research grants and review papers for a lot of these conferences and areas :) What i said was quite specific: We are talking about aliasing here, and in the area of aliasing, we pretty much know all of the tradeoffs, upper and lower bounds. We know how good we can make algorithms, we know how to make them scale as well (single cpu, gpu, parallel, you name it). On demand, ahead of time, etc. You can engineer inside these tradeoffs all you want, and come up with amazingly nice hybrid algorithms that do all the right things. It's about how much time and energy you want to put into it. But here, there is no magic left.We know precisely what we can and can't do, and how it will turn out. Put another way: Given me a budget ( money, compile time, amount of memory and number machines that can be used at once to compile, etc), i will give you your choices, and implement them :) Additionally, I can also tell you that no matter what your choice, when it comes to aliasing, you are talking maybe 6-8 months of work to build an initial version for someone with experience in the area, assuming what you want is super-complex. The two current CFL implementations (on demand pointer analysis) in LLVM, for example, were developed by two interns, each in 3 months. Building a very large scale "as precise as it gets" context-sensitive field-sensitive pointer analysis that worked across 10k machines took me about 6 months (to be fair: starting point was a well functioning distributed graph processing infrastructure. Obviously, that would have taken a lot longer to build :P). Honestly, the reason you don't see more done here is because it's not the low hanging fruit for most compilers, for most apps people care about. I'm saying that as a guy who really loves aliasing, but also owns google's compiler performance teams. Like most areas of compilers, alias analysis hits a good enough point, you leave it alone for a while, you run out of other things you can improve that are bigger bang for buck, you come back and improve it, repeat. In fact, humorously, improving aliasing significantly often makes the compiler generate worse code to start because it now has a lot more freedom to go crazy with optimizations than it used to. So then you have to spend time coming up with better cost models for those optimizations, etc
dbaupp 9y ago
> I find it funny and think it's pretty telling that there are bold claims made that are only crossed out after the author is corrected ... What else would you expect? The author observed something, drew a mistaken conclusion, wrote it up, and then had the mistake pointed out, and so retracted. I can't imagine the author realised their claims were wrong before it was pointed out, so of course they're only going to cross them out after being corrected. Of course, it's rather unfortunate that an incorrect write-up is being upvoted to the top of HN but that's not the author's problem (other than the choice of the rather clickbaity title...). For the specifics of this post, there's some subtle differences between how Rust and C++ behave that could easily explain how the author observed differing behaviour and thus jumped to the conclusion, as explored on /r/rust: https://www.reddit.com/r/rust/comments/63ijkw/rust_optimizations_that_c_cant_do/ https://www.reddit.com/r/rust/comments/63ijkw/rust_optimizat...
- nebabyte 9y ago
  > are bold claims made Probably a lack of bold claims of things the author doesn't actually know to be true? i.e. 'lurk moar' in an educational context. Correcting false assertions isn't as praiseworthy as not making false assertions in the first place. The former is a monkey-patch for a flawed mindframe; the latter is better for all actors in knowledge acquisition and dissemination.
  - dbaupp 9y ago
    I agree 100% that authors should be very sure before making aggressive/clickbaity/bold claims (and I take a slightly perverse pleasure in cutting wild claims down to size, like this case), but (a) as an author, it can be hard to distinguish whether one is very sure about a true thing, or very sure about a false thing (which is why things like kibwen's offer of proof-reading is good), and (b) once the mistake is made, how should the author respond? The parent comment seems to making a deal of the author crossing out the claims after the mistake was pointed out, as if there was something else they could do?! The blog would've been much better if it had been written in a less confrontational style, so the mistake becomes more of a learning experience for everyone instead of this finger-pointing match.
demarq 9y ago
> I find it funny and think it's pretty telling that there are bold claims made that are only crossed out after the author is corrected crossed out? have you seen the follow up post... http://robert.ocallahan.org/2017/04/rust-optimizations-that-c-cant-do_5.html http://robert.ocallahan.org/2017/04/rust-optimizations-that-... The error was in his example not his assertion.
- MaulingMonkey 9y ago
  > have you seen the follow up post... Yes. By adding a single __restrict__ (between the ampersand and the v) I can make the inner loop of the C++: .LBB0_1: # =>This Inner Loop Header: Depth=1 call rbx dec ebp jne .LBB0_1 Which has hoisted the sum out of the loop, which is even better than the Rust version which wasn't smart enough to turn the add into an out-of-loop imul, making the Rust version two instructions longer: .LBB0_1: inc ebx call r14 add r12, r15 cmp ebx, 100 jl .LBB0_1 This makes the author technically right: restrict is only standard C99, and a compiler extension in C++. EDIT: I might as well share the godbolt link: https://godbolt.org/g/jFmiRV https://godbolt.org/g/jFmiRV EDIT x2: And of course one can cheat and simply pass by value like a reasonable person. Ahh, the pitfalls of microbenchmarking... EDIT x3: Also, unless I've misunderstood modern processor architecture, with register renaming and physical registers potentially (often? usually?) outnumbering architectural registers on modern x86 processors, the initial "bad" C++: .LBB0_1: # =>This Inner Loop Header: Depth=1 add rbx, qword ptr [r15] call r14 dec ebp jne .LBB0_1 May still be using a physical register for [r15], despite the slow-looking dereference. If it isn't, it's likely because the callback was complex enough to require so many registers that the callback would be saving out this loop's registers and restoring them anyways. In that context, the pre-restrict C++ could actually be more efficient (4 instructions to Rust's 5, 4 persisted architectural registers[1] to Rust's 4, ditto for physical register requirements...?) Now I'm curious what the best approach to "defeating" the processor's register renaming hardware to force N registers of the inner loop out of physical registers (via increasing the callback's complexity) and what the actual performance impact is on these dueling disassembly snippets. The post-restrict C++ with the hoisted imul, of course, is a clear winner at 3 instructions, and only 2 persisted architectural registers... ([1] ebx, r12, r14, r15 - not counting e.g. the flags the jumps are conditional on, which would not need persisting for any of the snippets)

Galanwe 9y ago

"unless that language has explicit restrictions prohibiting such an optimization" It is indeed true that C++ is not able to easily express aliasing. It is extremely cumbersome and error prone to properly specify the aliasing rules when using pointers (especially when you start using char* and void*). So either you force the programmers to place a lot of `restrict` everywhere (expect 1/100 programmer is able to understand/do this properly), or you just fallback to not optimize these cases to their maximum (safe), or allow the compiler to aggressively try to guess the aliasing by itself (and enjoy mind crushing debug sessions later on).

DannyBee 9y ago
We used to have languages, like fortran, that were incredibly explicit, and people didn't like that either :) " or you just fallback to not optimize these cases to their maximum (safe), " No, you fallback to runtime aliasing checks if it's important enough. If something can later prove they alias or not, it eliminates the conditional.
- flamedoge 9y ago
  Question is when do you stop? At what point does adding runtime checks become too expensive? I doubt you want to end up with gazillion checks for non-overlap. C and C++ both seem to lack user-specified type aliasing relations. You have to work with standard base types. I want to be able to declare my own type that is unique on its own and aliasing relations with other types.
  - DannyBee 9y ago
    Sure, and that's a reasonable thing, i'm just saying "the world where nothing aliased and users specify all possible aliasing" didn't turn out to be a fun one either. Honestly, while it seems a good idea, most languages that allow you to specify complex aliasing relationships tend not to be translatable into usable metadata by anything but very high level compilers in a lot of cases. Either they have to evaluate the language-level aliasing rules in the compiler (which requires a high enough level IR for them to still be correct on the IR, and means your compiler is language specific), try to translate them into something more generic (which almost always loses info), or fall back to (n^2)/2 space pair aliasing (IE for each n pointer, specify which n pointers it aliases or no aliases with). They also have to be queryable in essentially constant time for a pointer pair or a memory location and a pointer to have a reasonable speed compiler. This means, for example, if your rule says "they don't alias if every field of every subobject is in blah relationship", that ain't gonna work well unless the answer to that is precomputed and doesn't take up a lot space to represent for the objects. Most choose the middle ground to make all this happen (or have a high level ir, optimize some at high cost, then choose the middle ground). So the problem is not usually coming up with cool things you can say at a high level, it's making them usable to the compiler. I believe, in fact, rust has had precisely this problem with various features, and added a higher level IR to attempt to ameliorate this. The downside is if you don't find a way to transfer it to the lower levels, you miss optimization at the high level due to not-exposed operations (IE things that are lowered), and then the lower level doesn't have the info the higher level did, so you still miss some optimizations So you can have the nicest, most complete aliasing specification in the world, and making it help an optimizer may just not work at all. The late 80's are littered with languages where this was true. Then the early 90's to mid 90's did the same thing with parallelization. see, e.g, https://en.wikipedia.org/wiki/High_Performance_Fortran https://en.wikipedia.org/wiki/High_Performance_Fortran The paper ken kennedy wrote on it before he passed away is a great read, and led to later compilers, etc, being much better about this sort of thing. (Rust should pay attention to the "different optimizations", etc parts and hope there is never a second compiler for rust that gains traction :P)
- kibwen 9y ago
  > We used to have languages, like fortran, that were incredibly explicit, and people didn't like that either :) I like to think that language design is oscillating around the sweet spot, with a general trend towards convergence. :P First too strict, then too loose, then too-strict-again-but-a-bit-less-strict-than-the-first-time, and so on and so on. Eventually we'll get there... I hope!
pif 9y ago
> expect 1/100 programmer is able to understand/do this properly Personally, I'll never accept such an argument as a valid reason to judge the quality of a programming language, unless we stop considering the amateurish programmers when computing the average. For example, a professional camera is meant to be used by a professional photographer, and it is judged exclusively by the quality of the pictures the best photographers in the world can take with it, not by the quality of my kid's birthday. In a similar way, I'd expect programming languages to be judged by what best programmers can do with them: if the average programmer is your company can't fully exploit the power of a mature, professional tool like C++, question the programmer, not the tool. Sure, you may say that, from certain points of view, C++ is rotten rather than mature, but it was never meant to be used by people who consider "C++ for dummies" a valid reference.
- simias 9y ago
  C aliasing rules are far from simple though. If I review some code and encounter a "restrict" keyword it's going to give me great pause. It's very easy to get it subtly wrong and those types of bugs are generally pretty tricky to track down (it will generally only fail with a certain level of optimization and can be very compiler-dependent). Since "restrict" is often used in function parameters you need to make sure every caller gets this right. And the compiler will do very little to help you track down incorrect usage. So in my opinion it's more like a professional camera featuring a "format storage" button prominently on top. A pro should know not to press it, doesn't mean that it's good design.
- Galanwe 9y ago
  >> expect 1/100 programmer is able to understand/do this properly > Personally, I'll never accept such an argument as a valid reason to judge the quality of a programming language, unless we stop considering the amateurish programmers when computing the average. When I say 1/100 C++ programmers are able to properly understand aliasing rules, and confidently use `restrict`, I was already talking about professional senior programmers. If you consider the whole set of C++ programmers that would drop to 1/1000. We can discuss the numbers, but from my experience working in some very low level areas where you would expect C++ (or C) developers to know that kind of thing, I would say 1/10 would understand really how `restrict` works. On that basis, I would say that, yes, C++ does not a good job at handling the aliasing of memory locations, since the required mental mumbo jumbo required to declare aliasing properly is too consuming for even experts.

DannyBee 9y ago

"Whether it's practical to develop a smart-enough compiler in a reasonable amount of time is probably the real issue. " These issues have been solved pretty much forever (in terms of what is possible) at the compiler level. You just select your engineering tradeoff. There is no more magic in this area :) We can scale the algorithms better than we used to, but the precision tradeoffs, completely fixed at this point. In any case, most of the languages have to be able to express these properties in a more generic way (or else have a rust-specific IR/compiler, which has it's own issues), and if they can do that, you can usually make the other language express the same thing. This is, in fact, one of the ways things get standardized. People build an extension, formalize it later.

adrianN 9y ago
I disagree that there is no magic left in compiler construction. It's still an active area of research with many papers published every year.
- DannyBee 9y ago
  That's not what i said. I fund research grants and review papers for a lot of these conferences and areas :) What i said was quite specific: We are talking about aliasing here, and in the area of aliasing, we pretty much know all of the tradeoffs, upper and lower bounds. We know how good we can make algorithms, we know how to make them scale as well (single cpu, gpu, parallel, you name it). On demand, ahead of time, etc. You can engineer inside these tradeoffs all you want, and come up with amazingly nice hybrid algorithms that do all the right things. It's about how much time and energy you want to put into it. But here, there is no magic left.We know precisely what we can and can't do, and how it will turn out. Put another way: Given me a budget ( money, compile time, amount of memory and number machines that can be used at once to compile, etc), i will give you your choices, and implement them :) Additionally, I can also tell you that no matter what your choice, when it comes to aliasing, you are talking maybe 6-8 months of work to build an initial version for someone with experience in the area, assuming what you want is super-complex. The two current CFL implementations (on demand pointer analysis) in LLVM, for example, were developed by two interns, each in 3 months. Building a very large scale "as precise as it gets" context-sensitive field-sensitive pointer analysis that worked across 10k machines took me about 6 months (to be fair: starting point was a well functioning distributed graph processing infrastructure. Obviously, that would have taken a lot longer to build :P). Honestly, the reason you don't see more done here is because it's not the low hanging fruit for most compilers, for most apps people care about. I'm saying that as a guy who really loves aliasing, but also owns google's compiler performance teams. Like most areas of compilers, alias analysis hits a good enough point, you leave it alone for a while, you run out of other things you can improve that are bigger bang for buck, you come back and improve it, repeat. In fact, humorously, improving aliasing significantly often makes the compiler generate worse code to start because it now has a lot more freedom to go crazy with optimizations than it used to. So then you have to spend time coming up with better cost models for those optimizations, etc

dbaupp 9y ago

> I find it funny and think it's pretty telling that there are bold claims made that are only crossed out after the author is corrected ... What else would you expect? The author observed something, drew a mistaken conclusion, wrote it up, and then had the mistake pointed out, and so retracted. I can't imagine the author realised their claims were wrong before it was pointed out, so of course they're only going to cross them out after being corrected. Of course, it's rather unfortunate that an incorrect write-up is being upvoted to the top of HN but that's not the author's problem (other than the choice of the rather clickbaity title...). For the specifics of this post, there's some subtle differences between how Rust and C++ behave that could easily explain how the author observed differing behaviour and thus jumped to the conclusion, as explored on /r/rust: https://www.reddit.com/r/rust/comments/63ijkw/rust_optimizations_that_c_cant_do/ https://www.reddit.com/r/rust/comments/63ijkw/rust_optimizat...

nebabyte 9y ago
> are bold claims made Probably a lack of bold claims of things the author doesn't actually know to be true? i.e. 'lurk moar' in an educational context. Correcting false assertions isn't as praiseworthy as not making false assertions in the first place. The former is a monkey-patch for a flawed mindframe; the latter is better for all actors in knowledge acquisition and dissemination.
- dbaupp 9y ago
  I agree 100% that authors should be very sure before making aggressive/clickbaity/bold claims (and I take a slightly perverse pleasure in cutting wild claims down to size, like this case), but (a) as an author, it can be hard to distinguish whether one is very sure about a true thing, or very sure about a false thing (which is why things like kibwen's offer of proof-reading is good), and (b) once the mistake is made, how should the author respond? The parent comment seems to making a deal of the author crossing out the claims after the mistake was pointed out, as if there was something else they could do?! The blog would've been much better if it had been written in a less confrontational style, so the mistake becomes more of a learning experience for everyone instead of this finger-pointing match.

demarq 9y ago

> I find it funny and think it's pretty telling that there are bold claims made that are only crossed out after the author is corrected crossed out? have you seen the follow up post... http://robert.ocallahan.org/2017/04/rust-optimizations-that-c-cant-do_5.html http://robert.ocallahan.org/2017/04/rust-optimizations-that-... The error was in his example not his assertion.

MaulingMonkey 9y ago
> have you seen the follow up post... Yes. By adding a single __restrict__ (between the ampersand and the v) I can make the inner loop of the C++: .LBB0_1: # =>This Inner Loop Header: Depth=1 call rbx dec ebp jne .LBB0_1 Which has hoisted the sum out of the loop, which is even better than the Rust version which wasn't smart enough to turn the add into an out-of-loop imul, making the Rust version two instructions longer: .LBB0_1: inc ebx call r14 add r12, r15 cmp ebx, 100 jl .LBB0_1 This makes the author technically right: restrict is only standard C99, and a compiler extension in C++. EDIT: I might as well share the godbolt link: https://godbolt.org/g/jFmiRV https://godbolt.org/g/jFmiRV EDIT x2: And of course one can cheat and simply pass by value like a reasonable person. Ahh, the pitfalls of microbenchmarking... EDIT x3: Also, unless I've misunderstood modern processor architecture, with register renaming and physical registers potentially (often? usually?) outnumbering architectural registers on modern x86 processors, the initial "bad" C++: .LBB0_1: # =>This Inner Loop Header: Depth=1 add rbx, qword ptr [r15] call r14 dec ebp jne .LBB0_1 May still be using a physical register for [r15], despite the slow-looking dereference. If it isn't, it's likely because the callback was complex enough to require so many registers that the callback would be saving out this loop's registers and restoring them anyways. In that context, the pre-restrict C++ could actually be more efficient (4 instructions to Rust's 5, 4 persisted architectural registers[1] to Rust's 4, ditto for physical register requirements...?) Now I'm curious what the best approach to "defeating" the processor's register renaming hardware to force N registers of the inner loop out of physical registers (via increasing the callback's complexity) and what the actual performance impact is on these dueling disassembly snippets. The post-restrict C++ with the hoisted imul, of course, is a clear winner at 3 instructions, and only 2 persisted architectural registers... ([1] ebx, r12, r14, r15 - not counting e.g. the flags the jumps are conditional on, which would not need persisting for any of the snippets)