Rust Optimizations That C++ Can't Do
robert.ocallahan.org
robert.ocallahan.org
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.
" 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.
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.
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)
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?
>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;
}
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 :(
That's what profile guided optimization is for!
Whole program optimization could help though.
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!
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.
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.
> 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.
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.
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
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 :)
IE
if (a bunch of stuff is true)
execute perfect loop
else
whatever was there before.... 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...
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.
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 want you to know how much I appreciate this, Huon. :)
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
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.
This is a fantastic idea but maybe we need to make it more visible?
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.
Yes, but both are considered increasingly redundant by a writer depending on how sure they are.
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.
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
.LBB0_1:
inc ebx
call r14
add r12, r15
cmp ebx, 100
jl .LBB0_1
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
([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)
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
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...)
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.
> 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.
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.
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.
As a trivial example, the point about const is wrong (at least as far as i understand it). you can const cast stuff, but you still can't modify it, to do so is UB: Modifying a const object through a non-const access path and referring to a volatile object through a non-volatile glvalue both result in undefined behavior. So yeah.
As for the abi, any abi arguments are silly. really. the compiler can always clone the function, rename it, and do what you want. or inline it. or ....
If it really matters, you'd also just change the ABI. There is no C++ standard ABI. There's one a lot of compilers use. If we could get x% better performance using a different one, people would do that :)
The corollary is "If you think you can only get x% better performance by doing that, you are probably wrong".
(I'm excluding things that are low level abis, like x32, etc, since we are talking about language abis)
Seriously, I'm getting sick of these Rust/Go/Hype is better than $competitor because $edgecase. Yes, but what if I want to do sparse matrix manipulation? What if I want to interact with hardware, and set registers? What if I want to use the library Bob wrote back in 2001, because it is really well tested and we've never encountered a bug since 2003?
Check out the zinc project for some great examples.
Likewise, linking to external libraries is trivial.
I'm not saying that rust is better than any other language. But those examples aren't factors in this religious debate
const int n = 1;
const_cast<int&>(n) = 2;
int n = 1;
void foo() { n = 2; }
int bar(const int& x) { int y = x; foo(); return y + x; }
bar(n);
Worse yet, the function can often change it itself via aliasing:
int n = 1;
int bar(const int& x, int& y) { y = x; return x; }
bar(n, n);
The problem is that both C and C++ lack a way to say "this is a pointer or reference to something that is immutable", as opposed to "... something that you can't mutate". The other problem is that C++ (but not C, thanks to "restrict") lacks a way to say "the object referenced by this pointer or reference is not aliased in any other respect that matters to this function".
Rust, OTOH, does let you say that something that's referenced is immutable. In fact, it is the case by default. So the compiler can aggressively optimize around the fact.
In C++, they can only optimize as well when the compiler can do a full program analysis, and determine that the referenced value is immutable in practice. Which can be hard to do for non-trivial programs, and outright impossible to do across dynamic library boundaries.
const_<T>& freeze(T&); T& thaw(const_<T>&);
do_something(const_<T>& x) { /* the language guarantees that x can't be mutated from anywhere */ }
Note that the trick still doesn't help much in practice: GCC conservatively still won't optimize based on const qualification of values.
So you'd discover your error pretty quickly if it did :P
That's what i said, actually: " Modifying a const object through a non-const access path and referring to a volatile object through a non-volatile glvalue both result in undefined behavior. So yeah."
"he other problem is that C++ (but not C, thanks to "restrict") lacks a way to say "the object referenced by this pointer or reference is not aliased in any other respect that matters to this function"."
"In C++, they can only optimize as well when the compiler can do a full program analysis"
Which is why i said anyone who cares hands it the whole program anyway. Because even in rust, not having the whole program but claiming to pretend about performance is just silly. "I care tremendously about performance, but i refuse to give you enough of the program for you to do anything with it :P"
That said, you can actually do it without fully program analysis. It suffices to have summaries.
" and determine that the referenced value is immutable in practice. Which can be hard to do for non-trivial programs, " With no offense, this isn't the early 2000's anymore. Whole program LTO is not some esoteric feature, it's the default for anyone who actually cares about performance. Same with the type of mod/ref analysis you are talking about. It's done already. We whole program optimize binaries with hundreds of millions of lines of code in them. So do plenty of people.
It also doesn't actually require full program,only the ability to see the allocation site and the call. It doesn't have to prove it's always immutable, if it can prove it at least once it can just specialize that function (and do so in a way that it would be reused with anywhere else that specializes).
But yes, you could also try to prove it is always immutable (and gcc does that too).
" and outright impossible to do across dynamic library boundaries." This is actually not right, though admittedly not common, fwiw. First, you can summarize it, and include it in a section of the .so, assuming you are just doing dynamic linking.
If you are doing dynamic loading, yes, you'd need to JIT it. But still doable.
(i won't point out that dynamic loading is not actually legal in any of these languages :P)
If you have a struct/class type union wrapper for SIMD instrinsics which contains something like __m128 and pass that by reference, GCC and LLVM will often implement this as an effective pointer onto the stack (or wherever the struct is). ICC can often detect this, and keep it as a by-value __m128, which is often more efficient and keeps stuff in the registers.
"Criticizing the Rust Language, and Why C/C++ Will Never Die"
https://www.viva64.com/en/b/0324/
Not sure why certain members of the Rust community aren't happy with just having a neat language. Making one false claim after another isn't doing them any favors. It's just aggravating, especially when people who should know better start to believe the hype.
FAKE NEWS!
Fortunately the overwhelming majority of the community isn't afraid to call this post out, judging by the comments at https://www.reddit.com/r/rust/comments/63ijkw/rust_optimizat... :) I've never seen the author engage with the Rust community in any great capacity (they're not a regular in any forum that I frequent, and I can't name any libraries that they've written), so I wish he'd take the time to learn Rust more before blogging about it.
There is an opportunity to do some very cool things with Rust and I think most people would love to see a "better together" mindset being shared.
Saying this isn't going to do my karma any good, but it's almost certainly because they're feeling competitive pressure from the even more numerous Go developers doing the exact same thing with their language. A lot of people feel like it's time to move on from C and C++, especially to something with better memory-safety properties. (This is for low-level infrastructure code, mostly. Other kinds of code have been better written in higher-level languages for a long time.) Rust developers/advocates feel that it has the best current answer to that need. They might even be right. Then they see the total deluge of Go propaganda, encouraging people to adopt what they feel is a less-good approach. They know that "just having a neat language" won't be enough to overcome that. Therefore, out of a completely laudable desire to help others avoid a mistake, they ratchet up their own rhetoric to match. Some get a bit carried away.
If the goal is to discourage overly ardent advocacy for Rust, we also need to discourage the same for other languages as well - not just Go but also Swift, Erlang/Elixir, *ML, and so on. The pattern of people becoming tiresome about their choice of programming language (or paradigm) has existed for a long time.
> Rust is safe indeed but, unfortunately, far from fast.
Today's version of that graph: http://benchmarksgame.alioth.debian.org/u64q/which-programs-...
Rust appears second, after C and before C++.
> And what actually makes Rust safe, by the way?
Yes, a company that makes static analysis tooling is going to claim that their static analysis tools give you the same degree of safety. They don't, generally, due to language semantics. If this was truly a viable path, we wouldn't have created (okay this is a bad word, I mean "Mozilla probably wouldn't be looking to create Servo and instead would have gotten the guarantees for Firefox by using those tools rather than sponsoring Rust's development) Rust in the first place; we would have just used them. (That doesn't mean they're bad of course, but they can't do what rustc can.)
> Even apart from that speed/safety compromise issue, I'm also skeptical about the language's design as such. In particular as regards to the five types of pointers used in it.
This was already outdated information when the article was originally created; that all went away half a year earlier than the post. Doesn't give much confidence that the author actually spent any significant time with Rust.
> Macros used as a crutch to make up for the excessive verbosity caused by the absence of normal exceptions.
This is not what macros are for. One of these macros did exist, and today is a language feature (?). But there are lots of reasons why exceptions aren't used, including by many C++ programs.
> People are idiots and cargo actively encourages downloading packages directly from git repositories, bypassing Crates.io.
I can't speak to this problem at that time, I don't remember it being a thing, but maybe it could have been. Included for completeness :p
> I can generally understand why it doesn't have a decent inheritance and exceptions, but the fact itself that someone is making decisions for me regarding things like that makes me feel somewhat displeased. C++ doesn't restrict programmers regarding what they can or cannot use.
C++ includes or doesn't include lots of language features, this feels like a real stretch.
> Now, since we have taken the path of simplification, why not throw away all those language extensions? The current state of things resembles the Haskell world where every programmer is coding in their own dialect.
I _think_ this is referring to the stability markers, as we have nothing like Haskell's language extensions. If so, well, they exist due to the way the release process works, and so did and were steadily going away when this was written.
> Smart pointers, for you to know, are far not free of charge and do not ensure a fixed time of garbage collection.
"smart pointer" is not synonymous with "reference counting". The answer to this problem is "use an arena", which you can use in Rust just like C++.
> Has anyone seen a strict description of Rust's semantics? Does it have a memory model at least?
This is true, with lots of ongoing work, including millions of Euro of grants to academics working on it. Not quite there yet though. C and C++ had over a decade before they had their respective standards, so we've still got eight years, by that measure.
> I can't but remind you for one more time that the source of troubles is usually in humans, not technology.
This is just straight-up opinion and so isn't really refutable.
Anyway, just saying. In the moment, that article wasn't very good, but today, it's pretty much entirely irrelevant.
In context: "You can see that the order would be different if it was based on the median scores instead of the [pdf] geometric mean scores."
http://benchmarksgame.alioth.debian.org/u64q/which-programs-...
If there is one thing there isn't enough of on hn, it's discussions about Go
C++ can't do the same thing Rust does because it would be a breaking change to have finer-grained distinctions between the types of references.
This is a matter of language semantics, not compiler implementation. rustc isn't doing anything new here, LLVM already knows how to make this optimization and is making it.
In general it does unlock a lot of opportunities when it comes to optimization.
This doesn't mean the compiler can't make this optimization. Unless we are talking about multiple threads here (which we aren't), there is no other code that is executing that can change what this const reference is pointing to. If we are talking about threads, then data races like this are UB in C++, and the compiler can do anything it wants, including emitting nonsense code.
... except if your code calls potentially 'impure' functions.
void f(const int& value)
{
const int a = value;
g();
const int b = value;
assert(a == b);
One can't tell if the assertion will succeed.
Indeed, 'value' might have been modified as a consequence of calling 'g'.
You don't have this uncertainity if 'value' is marked as immutable.
If value was originally a const object (IE immutable), it is well defined and guaranteed to always succeed.
IE const char* myString = "Hallo World!"; const_cast<char*>(myString)[1] = 'e';
This is illegal, the same as anything modifying value would be if it was originally const.
If value was originally not a const object, it wasn't immutable, so anything goes.
"You don't have this uncertainity if 'value' is marked as immutable. " You can, in C++ mark the original immutable in a way that you can tell if the assertion will succeed.
That's crazytown.
"Please optimize this as hard as you can with two hands tied behind your back".
So like i said, i don't disagree that it's a useful thing to do, i just am not sure i believe it matters in practice to people who care about performance.
IE the purported benefit is already achievable and achieved, quite regularly.
Again, doesn't make it less useful in general, i'm just not sure i believe it is somehow amazing for performance to people who care about performance.
Traits, while cool, ate not potent enough at times.
I'm not sure where one would get the idea that `unsafe` would be entirely forbidden in idiomatic Rust. "Idiomatic" Rust acknowledges the danger and subtle pitfalls of unsafe code, and thereby discourages the use of `unsafe`, but also acknowledges that it is still possible to build safe abstractions out of internally-unsafe code.
> in order to get similar performance to C++ data structures
By Rust's definition, every line of code in a C++ codebase counts as unsafe code. :P If Rust can get equivalent performance to C++ while only using exposing 1% of the code to unsafety, that's an enormous win.
This is just not true. Unsafe != performance. sometimes it does, but not always. For example, the Benchmarks Game programs that are currently fastest have very little unsafe, one of them is entirely for FFI to GMP. Several 100% safe programs have replaced slower programs that used unsafe.
So it's more than just sufficient cleverness. It is also about the language providing you the tools to express certain invariants that the compiler can mechanically verify and then use in an optimization pipeline.
Edit: This is mostly out of context now and can be ignored.
You can often inline it. Now that may or not yield improvements in speed, but more to the point: It's quite possible that it's used in a context where x is bounded sensibly, and you can optimize further from there.
That is factually false. People called you on it. Rather than say "yeah, i was wrong, but i meant that in general, one doesn't get a guarantee that it will always turn out fast" or something, you seem to be just dodging it.
So please, can you start with exactly what you would like to talk about? If it's about inlining, yes, those are heuristics in a lot of compilers, but they also do make guarantees a lot of the time (particularly around tail calling), and in fact, provide the ability to guarantee inlining happens to users.
Fact: If always_inline doesn't always inline, the linux kernel fails to compile and link.
So people rely on it in real software.
> It is also about the language providing you the tools to express certain invariants that the compiler can use.
Compiled code is useless if it is never called. The moment it's called, whether the caller is known during compilation or not, the caller can pass down any additional information it has, whether for that call or to help the callee optimize future calls. Heck, if it really wants to, the compiler could simply let the "compiled" code be the AST or source code itself (plus a JITter), and make the program generate code on the fly when the caller calls it, optimized using whatever information the caller is willing to provide. Again, nothing fundamentally in a language preventing this. It a tradeoff between implementation difficulty, execution latency, program size, and the like.
Compilers, optimizations, type systems, and proof systems are all very closely related and if you want correct optimizations then you must annotate your code with types that the compiler can verify and use as assumptions in an optimization pipeline. These things are not easy to engineer. Saying just JIT it doesn't make much sense.
This is just trivially wrong. You can always add checks that it is a thing that lets you optimize better. You can always just JIT in addition to static compilation.
Guess I can also solve all pointer aliasing problems by just adding "if p != q {...}".
Yeah.
> I wonder then why all these compiler writers spend so much time on getting the type system right if all they need to do is just add some if statements then add a JIT.
Because (1) JIT has a latency hit users like to avoid, and (2) you still have to solve the same problem during JIT time, it doesn't magically go away.
Note: I'm one of these compiler writers. In fact, i'm one of the compiler writers who wrote the current aliasing implementations for the two major compilers everyone uses, among other things. If you are going to disagree, please be concrete. I'm stating that good enough aliasing algorithms exist to do what you want, and where you can't, you can do runtime checks.
People who truly care about performance hand the compiler the whole program, and want it to do a great job. It can and will. Your counter argument is what, exactly.
That because people spend time getting type systems right, this must be false?
If so, that's just silly. People spend time on getting type systems right to make it easier to reason about for people. Not because it's impossible at the compiler level. But because they'd rather not have to do it if they can avoid it. That doesn't mean it can't be done, and isn't done.
Seems like all I need to do is bone up on alias analysis, JITing, and inlining and I'm good to go.
In the meantime, i'll just point out, you can have the nicest type system in the world. It still has to translate into concrete aliasing info about pointers that is usable by both high and lower levels, and is queryable in O(1) time, without taking up a ton of space. Otherwise, it's just sitting there making guarantees no one can use.
"Seems like all I need to do is bone up on alias analysis, JITing, and inlining and I'm good to go."
For most code, yes, actually, that's probably just about right.
Instead you made a bunch of disparaging remarks, trivialized large swaths of CS theory, and failed to see the actual point of my comment in connecting type annotations as mechanically verifiable invariants/assumptions that can be used in optimization pipelines.
1. wrong 2. just not understanding you.
When pressed, you change your arguments and become super-snarky.
I would re-evaluate the way you are communicating here. IMHO, it is not effective at communicating whatever interesting and useful insights you may have here.
Information for optimization passes doesn't come for free and as terminating programs compilers can only fill-in so many holes before the programmer must fill-in the rest or barring that pay a performance penalty which is what happens in dynamic languages even with a JIT.
You keep using this phrase, as if the halting problem has any real bearing on what compilers do. Certainly you realize it's solvable for machines with finite bounded memory (IE all real machines. Especially since, for example each intel chipset/processor has finite bounded memory they can even be hooked up to)
The problem there is it takes too long. Not that it's impossible.
The fact that you don't know if "collatz(n)" is always 1 or not means you are limited by the compiler's termination limit for inling and simplifying certain expressions. So the fact that the compiler terminates indeed has a lot of bearing on what kinds of optimizations are allowed and derivable in the absence of an expressive enough type system.
Some people might object to that example but the fact remains that logic and type systems are intimately tied to program analysis and optimization. In the domain of pointer alias analysis there is something known as separation logic which allows for statically analyzing aliasing relations. Now if this information is encoded as part of the type system then certain mechanical derivations about aliasing become much simpler which leads to more optimization opportunities. Rust's type system I believe is more related to affine logic but similar arguments still apply. You can not express the invariants that can be expressed with Rust's type system in C++. Actually I take that back. You could in theory encode affine or separation logic with the template system and then encode your program using those templates but that's basically the same work as re-implementing Rust in C++. This means Rust's type system allows for program optimizations that would not be possible otherwise. Similar to how knowing "collatz(n)" always being 1 allows you to elide that condition entirely. No amount of inlining and simplifying will allow you to perform that same optimization.
(See also: partial evaluation, Futamura projection)
Oh, nm. I can edit.
It means that it's not a reply anymore, it's at the top level, on its own, usually at the bottom of the page. Think of comments as a tree: this was a leaf, then was detached from its sub-tree.