4 ms·

"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 extre

• DannyBee 10y 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 10y 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 10y 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)
      • flamedoge 10y ago
        > tend not to be translatable into usable metadata LLVM tbaa honestly seems so straight-forward and not language-specific... actually you're the one who taught me this! I mean how many ways can you describe one-to-many aliasing relations?
        • DannyBee 10y ago
          >> tend not to be translatable into usable metadata >LLVM tbaa honestly seems so straight-forward and not language-specific" It also represents a very non-complex aliasing relationship :) IE type dags. I could also point out it's horrendously broken and about to be redesigned (but to be fair, this was just 'unions were a hack in tbaa, nobody realized how much of a hack until they started really digging') https://bugs.llvm.org/show_bug.cgi?id=32056 https://bugs.llvm.org/show_bug.cgi?id=32056 The result will just look like gcc's. But this is also subject to fairly simple rules, and those rules fail to let you optimize in a lot of cases. IE the language itself says what the rules are. I can't use the type system to say "circle types never alias square types" if it's not in the language rules instead, if i do this: struct circle { int radius; int x; int y; }; struct square { int size; int x; int y; } There is actually no way in C, translated to llvm, to say pointers to these things these do not alias (i don't remember all the versions of the common initial sequence rules off the top of my head to know whether it's possible at all. Assume for our purposes it's not) in fact, in llvm, it's worse. It has a "type system" that is useless (literally), and in that type system, you can't even distinguish or prove that a given access is to a different field (because it allows negative offsets). We have no metadata that specifies it (remember the struct tbaa info is about types of fields, not access paths in generals) So TBAA will not help with that. Thus, in the above case, a pointer to any field will may-alias every other field. (This is what llvm will do, other compilers are much better) The best you get in C is restrict, which is pretty weak. This is the use case a type system helps, where you want to be able to assert things that you can't easily express. But then you have to translate that assertion, again, into something the compiler understands. Compiler type systems and language type systems are pretty much never identical. This is also info that requires translation from high level to low level :(
    • ori_b 10y ago
      > At what point does adding runtime checks become too expensive? That's what profile guided optimization is for!
      • kibwen 10y ago
        I love PGO and think it's basically magic, but I'd be very surprised if PGO alone would let you ever elide runtime aliasing checks!
        • gpderetta 10y ago
          In fact PGO will probably help you find out where to add those aliasing checks! Whole program optimization could help though.
        • flamedoge 10y ago
          You are right that even with PGO you are still speculating if you remove runtime checks.
        • ori_b 10y ago
          It lets you decide when there's more overhead in versioning your loop versus not versioning it.
  • kibwen 10y 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 10y 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 10y 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 10y 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.