Hacker News Reader

Comment by wfunction | Hacker News Reader

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.

View on HN

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

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

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.

> I take a slightly perverse pleasure in cutting wild claims down to size

I want you to know how much I appreciate this, Huon. :)

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

I wholeheartedly agree, both in this specific instance and in general. There's a reason experienced learners generally (in my experience) take a non-assumptive/non-assertive tone. When you've learned enough times how little you know, you've somewhat trained yourself to be open to learning sooner than trying to assert what you 'knew' as certainty.

Though the latter tends to be a more comforting notion, the idea that you "have the measure of things;" when your 'being wrong' leads to a misprediction or failure, and you wish to transition to 'knowing' what was correct with grace, which is easier when you 'weren't being a dick about it', i.e. being nonconfrontational.

I like to think of this SMBC graph on knowledge in relation to this. http://www.smbc-comics.com/?id=2177

> I can't imagine the author realised their claims were wrong before it was pointed out

It should be noted that the Rust community team has an open offer to proofread the draft of any Rust-related blog post to help ensure technical accuracy, specifically to help prevent embarrassing things like this. :P Preventing the generation of misinformation is cheaper than curing its dissemination, after all. I've already reached out to the author to make sure they're aware of this offer for the future.

Is this described anywhere? I've been using Rust for a few years, been hanging around it's subreddit for about as long and this is the first time I hear about it.

This is a fantastic idea but maybe we need to make it more visible?

> ... What else would you expect?

Exactly the same things you already wrote:

> that authors should be very sure before making aggressive/clickbaity/bold claims

> The blog would've been much better if it had been written in a less confrontational style

Both are totally possible regardless of how sure you are. If you take a risk and are proven wrong, get less aggressive/bold/clickbaity in the next post, instead of trying to justify the same claim with a different argument. That's what I'd expect.

>Both are totally possible regardless of how sure you are.

Yes, but both are considered increasingly redundant by a writer depending on how sure they are.

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

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.

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.

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

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)

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

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

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 :(

I do wish compilers were smart enough to differentiate between circle.int* and int*. If I was a C programmer, I would expect my compiler to be able to tell this difference :(.

> At what point does adding runtime checks become too expensive?

That's what profile guided optimization is for!

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!

In fact PGO will probably help you find out where to add those aliasing checks!

Whole program optimization could help though.

You are right that even with PGO you are still speculating if you remove runtime checks.

It lets you decide when there's more overhead in versioning your loop versus not versioning it.

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

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

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.

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

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

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.

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

Insertion of runtime alias checks still appears like magic to me. Maybe there is still work to be done, reducing # of runtime checks with FSM or something alike might be one.

"Insertion of runtime alias checks still appears like magic to me."

ICC does it, gcc does it, etc.

In fact, things like Polly, pluto, etc are built around being able to add the right conditional guards to make loops execute in perfect orders with no dependences :)

  if (a bunch of stuff is true)
    execute perfect loop
  else
   whatever was there before.

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

The error was in his example not his assertion.

> 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

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)

I did try benchmarking the author's two loops (e.g. ignoring my __restrict__ version) at 100m iterations: https://gist.github.com/MaulingMonkey/92f856664094d54bd84a25...

My i7-5930K @ 3.50 GHz chews through 100m iterations in about:

    170±5ms for the rust-style loop
    140±5ms for the c++-style loop

So ~1.7ns versus ~1.4ns per iteration? I'm not 100% confident in my profiling results in that when culled down to just two calls, I've sometimes seen both benchmarks weigh in roughly the same at ~140kus for the 100m loop. Why the rust version ends up faster in this specific circumstance is beyond me (bursting before thermal cutoff?) This may be down to CPU power states, which I'm failing to control here?

That said, anything with a loop seems to consistently favor the C++ loop here (including comparing "cpp" only and "rust" only versions of the benchmarking snippet). Benchmarking disassembly looks equivalent. Pinning to a core doesn't significantly alter my results (keeping one core pegged at 100% this way does slightly improve my results by a few ms - presumably evicting any background system processes from that core?)

TL;DR: What rust did in the follow up post also wasn't actually an optimization, in at least one microbenchmark. Interesting!

EDIT: A key reminder: When optimizing or investigating performance, always be profiling. If you're optimizing without profiling, you're not optimizing! (The minor exaggerations of this paragraph have not been optimized for effectiveness, I lack perf data...)

> TL;DR: What rust did in the follow up post also wasn't actually an optimization, in at least one microbenchmark. Interesting!

This isn't a correct conclusion!

There's more differences between the code that just the optimisation enabled by the aliasing guarantees: hoisting the load outside the loop. The difference is likely to be the choice of the Rust compiler to use inc + cmp, instead of just dec like the C++ one does, which should be independent of the ability to hoist the load (indeed, if I change the Rust to use a while loop and manual incrementing, it results in using dec, and also hoisting the addition outside the loop to a multiplication, and similarly, if the 0..100 is changed to 0_i64..100, i.e. using 64-bit integers, the same hoisting happens... this looks like another case of LLVM not fully untangling Option<i32>).

If one was wanting to compare the actual quality of the generated code between two specific compilers, sure, but the intention is presumably to compare the actual "interesting" optimisation enabled by the language semantics.

Your conclusion would be correct if you got the same results after controlling for the other variables, i.e. make the C++ use inc & cmp, or the Rust use dec.

Fair critique! I should perhaps not be benchmarking at 6AM. Fortunately it's no longer 6AM.

> if the 0..100 is changed to 0_i64..100

I misread this initially as a complaint about the tweak to assembly iteration duration instead of a comment on tweaks to the author's Rust code (not enough caffeine). I did make the rust version worse by encoding a 64-bit immediate value in the inner loop's cmp, when the original was dealing with an 8-bit immediate value, so it's a fair complaint, even if you didn't make it ;). I've updated my code to attempt to correct for this deficiency as well.

> Your conclusion would be correct if you got the same results after controlling for the other variables, i.e. make the C++ use inc & cmp, or the Rust use dec.

V2: https://gist.github.com/MaulingMonkey/870c2fd1dc3e4f1b766199...

Comparing: ..._rust vs ..._rust_ref, the only difference in the assembly is if I dereference inside or outside the loop.

I've included two benchmarking passes of an identical program: In one, the version that dereferences inside the loop tends to actually perform faster (173ns vs 179ns per inner loop and setup/teardown thereof). In the other, performance tends to be identical: 173ns, the lower of the two. In-loop dereferencing performing better makes little enough sense to me that I'm inclined to err on the side of "this is neither an optimization nor a deoptimization", although the pattern is occuring regularly enough even with different stretch values that I'm really curious as to what's going on.

EDIT: I believe I've figured it out - when comparing _cpp_deref vs _cpp (again, only difference being where I dereference, inside or outside the loop): Whichever I place further from stretch_benchmark / just_ret in foo.asm tends to be faster by up to 30ns. This applies to the rust versions too. I'm more likely measuring icache or similar than real performance differences between the two loops.

Great analysis. Thanks for following up.

I guess you realise this, but the benefits of hoisting even simple operations like a dereference outside the loops is enabling other optimisations, such as the addition -> multiplication one here or even fancier like interchanging loops/ifs and vectorisation.

> May still be using a physical register for [r15], despite the slow-looking dereference

I don't think so. I believe register renaming means two explicit uses of a register may not end up in the same physical register, it doesn't mean loads can be promoted into registers, as that would require maintaining cache coherency at a level even deeper inside to an individual core than just L1 cache. It is extremely likely that the load will hit L1 cache, but this isn't quite the same as being in a register.

Reply on news.ycombinator.com