Tree Borrows
plf.inf.ethz.ch562 points by zdw a day ago
562 points by zdw a day ago
Recent blog post from Ralf Jung providing some extra context: https://www.ralfj.de/blog/2025/07/07/tree-borrows-paper.html
Bonus: recent talk from Ralf Jung on his group's efforts to precisely specify Rust's operational semantics in executable form in a dialect of Rust: https://youtube.com/watch?v=yoeuW_dSe0o
> On the one hand, compilers would like to exploit the strong guarantees of the type system—particularly those pertaining to aliasing of pointers—in order to unlock powerful intraprocedural optimizations.
How true is this really?
Torvalds has argued for a long time that strict aliasing rules in C are more trouble than they're worth, I find his arguments compelling. Here's one of many examples: https://lore.kernel.org/all/CAHk-=wgq1DvgNVoodk7JKc6BuU1m9Un... (the entire thread worth reading if you find this sort of thing interesting)
Is Rust somehow fundamentally different? Based on limited experience, it seems not (at least, when unsafe is involved...).
I would agree that C's strict aliasing rules are terrible. The rules we are proposing for Rust are very different. They are both more useful for compilers and, in my opinion, less onerous for programmers. We also have an actual in-language opt-out: use raw pointers. And finally, we have a tool you can use to check your code.
But in the end, it's a trade-off, like everything in language design. (In life, really. ;) We think that in Rust we may have found a new sweet spot for this kind of optimizations. Time will tell whether we are right.
As someone who has been writing a lot of unsafe Rust (mostly in an embedded context), I'm thrilled about and thankful for the work that you, your students, and the opsem team are doing.
When you're working with anything below the application level, C's confusing and underspecified rules about UB are almost impossible to keep track of, especially when it comes to aliasing and volatile/MMIO. The spec is so difficult to read and full of complicated cross-references that to actually get a practical answer you have to look for a random Stack Overflow post that may or may not have a correct interpretation of the spec, and may or may not address your specific problem.
Rust right now feels a lot harder to work with, because the spec isn't done. When you have a concrete question about a piece of code, like "is this conversion from an &mut to a *mut and back sound", and you try to look for documentation on it, you get either "Nobody knows, Rust aliasing model isn't defined"; a hand-wavy explanation that is not rigorous or specific; or a model like Stack Borrows or Tree Borrows that's defined a little too formally for easy digestion :)
But when I really started digging, I realized just how much cleaner Rust's semantics are. References aren't actually hard, Tree Borrows basically boils down to "while an &mut reference is live, you can only access the value through pointers or references derived from that reference". Pointer operations have straightforward semantics, there's no confusing notions of typed memory, and no UB "just because" for random things like integer overflow. It's just so much less complicated to understand than C's abstract machine.
I'm really looking forward to things like MiniRust, and to an aliasing model making it into the Reference / other documentation, because at that point I feel like unsafe Rust will be way easier to write confidently and correctly than C.
Congrats on the publication, and thanks again for the work you all have put into this.
In C, you can alias pointers if they have compatible types. Not the case in Rust for mutable references. And the rules of Rust have tripped up even senior Rust developers.
https://github.com/rust-lang/rust/commit/71f5cfb21f3fd2f1740...
Without MIRI, a lot of Rust developers would be lost, as they do not even attempt to understand unsafe. And MIRI cannot and does not cover everything, no matter how good and beloved it is.
It should have been possible for senior Rust developers to write UB-free code without having to hope that MIRI saves them.
The situation is not that bad. The rules of unsafe code were pretty badly defined back then, but they are in process of becoming a lot clearer, and like the grandparent argues, with a well-defined aliasing model like Tree Borrows, they are easier to understand than C's.
If you look into the code you linked, the problem was about accessing undefined bytes though an aliased, differently-typed pointer – something you would have hard time doing in C to begin with. MaybeUninit was a new thing back then. I think that nowadays, a senior Rust developer would clear the hurdles better.
I am very sorry, but you do not address that TBAA, like C has by default, generally is easier than just no aliasing, like what Rust has for mutable references. This is a major difference. C code can opt into a similar kind of aliasing, namely by using _restrict_, but that is opt-in, while it is always on for Rust.
And there is newer UB as well in Rust stdlib
> TBAA, like C has by default, generally is easier than just no aliasing [note: I assume no aliasing here to refer Rust's mutable references, not C's restrict]
I don't accept that statement. Rust's mutable references are statically checked, so they are impossible to get wrong (modulo compiler bugs) if you aren't using unsafe code. Using raw pointers has no no-aliasing requirements, so again, it's easier than in C.
The hard part is mixing mutable references and raw pointers. In 95% of Rust code, you are not required to do that, and you shouldn't do that. In the remaining 5%, you should understand the aliasing model. In that case, indeed, you need to know more than what TBAA requires you to know. But that's for the case where you can also _DO_ more than TBAA would allow you to do.
Yes, exactly. I'd be surprised if it's 5% -- that's about the ratio of all unsafe code, and most unsafe code does not mix references and raw pointers. I think it's less than 1% of the overall code that has to worry about this, but unfortunately I don't have hard data.
Ycombinator/Hacker News is giving me trouble regarding replying, maybe the debate is not going the way that some people want it to go. Sad.
I think HN is (intentionally) delaying the ability to reply to deeply nested comments.
> And the rules of Rust have tripped up even senior Rust developers.
Yeah, even senior Rust devs make mistakes. Thanks to Miri, we can catch such mistakes. No reasonable person would expect even senior Rust devs to be magic superheroes that can write tricky unsafe code without making any mistake.
How confident are you that glibc has zero Undefined Behavior? I rather doubt it. The Rust standard library has its entire test suite (well, almost everything, except for some parts in std::fs and std::net) run through Miri. That's not a proof there's no UB in corner cases not covered by the tests, but it means we are much, much more likely to find such bugs and fix them than comparable C code.
C has an opt-out that works sometimes, if a compatible type exists. Rust has an opt-out that works always: use raw pointers (or interior mutable shared references) for all accesses, and you can stop worrying about aliasing altogether.
I think that way of describing it is really weird.
In C, you do not use any special keywords to opt into or opt out of TBAA, instead it is the rule by default that one must follow. I do not consider that 'opting out'. One can disable that in some compilers by disabling 'strict aliasing', as the Linux kernel does, but that is usually on a whole-program basis and not standard.
In Rust, using raw pointers is using a different mechanism, and mutable references are always 'no aliasing'.
An example of opting in would be C's "restrict" keyword, where one opts into a similar constraint to that of Rust's 'no aliasing' for mutable references.
>use raw pointers (or interior mutable shared references) for all accesses, and you can stop worrying about aliasing altogether.
And dereferencing a raw pointer requires 'unsafe', right? And if one messee the rules up for it, theN UB.
Can you confirm that the interaction between raw pointers and mutable references still requires care? Is this comment accurate?
>It is safe to hold a raw pointer, const T or mut T, at the same time as a mutable reference, &mut T, to the same data. However, it is Undefined Behaviour if you deference that raw pointer while the mutable reference is still live.
> Can you confirm that the interaction between raw pointers and mutable references still requires care?
Yes, that still requires care.
> In C, you do not use any special keywords to opt into or opt out of TBAA, instead it is the rule by default that one must follow
That's exactly the problem: sometimes you need to write code where there's more aliasing, and C just makes that impossible. It tells you to use memcpy instead, causing extra copies which cost performance.
In Rust, you can still write the code without the extra copies. Yes, it requires unsafe, but it's at least possible. (Remember that writing C is like having all code be unsafe, so in a comparison with C, if 10% of the Rust code needs to be unsafe that's still 90% less unsafe than C.)
the opt-out in C is to use char*, which is specifically allowed to alias other types.
There are also GCC extensions to build other types that may alias.
That doesn't let you treat data in-place at two different types, unless one of them happens to be char. So you still need to make a copy in many cases, e.g. to convert between an array of uint32_t and an array of uint16_t.
In some cases you can use unions, but that, too, is very limited, and I am not sure it would let you do this particular case.
Not if you use may alias.
Also yes, that's the point of the C++ object model, only one type may exist in one location at a time.
Since usually different register banks are used for different types, having to copy makes sense.
One example of MIRI not being guaranteed to handle all cases.
https://github.com/rust-lang/rust/pull/139553#issuecomment-2...
The above issue was part of diagnosing UB in Rust stdlib.
Yeah, concurrency bugs that only occur in very specific situations are hard to track down with a pure testing tool. However, we have some ongoing work that should make Miri a lot better at this... we are just not sure yet whether we can get it to have usable performance. ;)
>Yeah, concurrency bugs that only occur in very specific situations are hard to track down with a pure testing tool.
It would have been better to have prevented it in the first place, and it is inconsistent with "fearless concurrency" when the Rust stdlib has UB.
And there are categories of cases that Miri does not handle either, FFI being a clear example as far as I know.
> it is inconsistent with "fearless concurrency" when the Rust stdlib has UB.
It is not. "fearless X" only applies to safe code. Rust was always very clear about that. It turns out that in practice, if >90% of your code are "fearless", that actually significantly reduces the amount of bugs you have to worry about, even if the remaining 10% can still have UB. (I don't have hard numbers on how much code is unsafe, AFAIK it is much less than 10%.)
But yeah, Miri cannot find all UB bugs. We are also very clear about that. But you don't have to find all UB bugs to make progress in this space compared to the status quo in C/C++.
Thanks for replying Ralf. I'm barely qualified to have an opinion about these things, if I am at all :)
> The rules we are proposing for Rust are very different. They are both more useful for compilers and, in my opinion, less onerous for programmers.
My question was too vague, what I meant to ask was: what aliasing optimizations will be possible in Rust that aren't possible in C?
Example 18 in the paper is one, if I'm understanding it. But that specific example with a pointer passed to a function seems analogous to what is possible with 'restrict' in C, I'm struggling to come up with more general examples that don't involve gratuitous globals.
It seems to me like having to allow for the possibility of unsafe constrains the ability to do "heroic" optimizations such as what jcranmer described elsewhere in the thread. If that is true to some extent, is there a future where Rust might optimize more aggressively if the programmer promises not to use unsafe anywhere in the program? That's something I've always been curious about.
Rust's aliasing rules are very different from C's.
In C you have a nuclear `restrict` that in my experience does anything only when applied to function arguments across clang & gcc, and type-based aliasing which is both not a generally-usable thing (don't have infinite different copies of the int64_t type (and probably wouldn't want such either)), and annoying (forces using memcpy if you want to reinterpret to a different type).
Whereas with Rust references you have finely-bounded lifetimes and spans and mutability, and it doesn't actually care about the "physical" types, so it is possible to reinterpret memory as both `&mut i32`/`&i32` and `&mut i64`/`&i64` and switch between the two for the same memory, writing/reading halves of/multiple values by the most bog standard Rust safe reads & writes, as long as the unsafe abstraction never gives you overlapping `&mut` references at the same time, or split a `&mut` into multiple non-overlapping `&mut`s.
> don't have infinite different copies of the int64_t type
You can make some, though!
Basically, the idea is to define a class template NoAlias<T, Tag> that contains a single value of type T. Implement operators etc. to make the type useful in practice for working with the wrapped value. Type-based alias rules mean that an access to the value wrapped in NoAlias<int64_t, Tag1> can never alias a value wrapped in NoAlias<int64_t, Tag2>. (Tag1 and Tag2 can just be forward-declared structs that are never defined.)
One time, I even encountered a situation where this was mildly useful.
Typescript ecosystem calls these "branded types" (branded like cattle, presumably) which I found to be a good evocative name.
Of course this is substantially less doable in C :(
Fair point, yeah. The general concept should still apply, you could maybe wrap it in some macros, but it is going to be more awkward mostly because of the lack of operator overloading.
Yeah, I meant specifically C in an ergonomic way with operators working on them and being passable to existing functions.
Though wrapping in different structs doesn't seem to even make gcc & clang properly optimize utilizing the types as non-aliasing: https://godbolt.org/z/r1MT9W9db. Clang just completely fails to do anything, but gcc somehow manages to reorder the load but not do the trivial part of constant-propagating afterwards..
Take anything Linus says about compilers with a grain of salt--he writes OS kernels, not compilers, and those are pretty different domains.
Alias analysis is extremely important for getting good performance these days--but it should also be remembered that the biggest benefits accrue from the simplest heuristics (like two loads that use the same SSA value as the pointer must alias each other). In LLVM terms, that's BasicAA: a collection of very simple heuristics that primarily amounts to "if we can track down the allocation sites of objects, we can definitively resolve these alias queries; otherwise, we don't know."
The real question that you're trying to ask, though, is what is the value of alias analyses that go beyond the most basic, obvious tests. At the point where the alias queries are no longer trivial to solve, then it's generally the case that what you can do as a result of those queries also shrinks dramatically, pretty much to looking for code motion hazards, and the benefits you get from that are much reduced. One of the experiments I would like to do is measure the total speedup you'd get from a theoretically perfect alias analysis, and my guess is that it's somewhere in the 20% range even on non-HPC code like the Linux kernel [1].
[1] This doesn't account for the heroic optimizations, such as data-layout transformations, that you wouldn't attempt to write without a very high-quality alias analysis. But since we already know that alias analysis doesn't exist in practice, we're not going to attempt those optimizations anyways, so it's not worth including such stuff in prospective speed gains.
> Take anything Linus says about compilers with a grain of salt
I think he's making an argument about CPU behavior here more than about compilers: if we call loads and stores which aliasing optimizations might remove "redundant", he's saying that modern machines with big caches and store buffers make those "redundant" operations so cheap they don't matter in practice for most workloads.
Of course, it's admittedly an oversimplification to reduce aliasing optimizations to simply eliminating loads and stores, you described things which go beyond that.
However, I just ran a silly little test where I added `-fno-strict-aliasing` to CFLAGS and rebuilt the world on one of my gentoo build machines, it only got 1.5% slower at compiling an allmodconfig linux kernel (gcc-14):
Before: 14m39.101s 14m42.462s 14m41.497s 14m44.540s
After: 14m54.354s 14m54.415s 14m55.580s 14m55.793s
Here's another data point: https://lobste.rs/s/yubalv/pointers_are_complicated_ii_we_ne...
> I spoke to Apple folks when their compiler team switched the default to strict aliasing. They reported that it made key workloads 5-10% faster and the fixes were much easier to do and upstream than I would have expected. My view of -fstrict-aliasing at the time was that it was a flag that let you generate incorrect code that ran slightly faster. They had actual data that convinced me otherwise.
OTOH we have https://web.ist.utl.pt/nuno.lopes/pubs/ub-pldi25.pdf which shows that on a range of benchmarks, disabling all provenance-based reasoning (no strict aliasing, no "derived from" reasoning, only straight-forward "I know the addresses must be actually different") has a much smaller perf impact than I would ever have expected.
I don't understand how they convinced him that code with limited set of aliasing patches remained 'correct'. Did they do 'crash ratio' monitoring? Disclaimer I had to do that in gamedev on 'postlaunch' for couple of projects. Pretty nasty work.
The counterpoint to this is that if you're willing to accept patching upstream as an option to make "key workloads" (read: partial benchmarks) perform better, what's stopping you from adding the necessary annotations instead?
The answer is basically that you were never going to, you're just externalizing the cost of making it look like your compiler generates faster code.
Maybe Linus by writing kernels, not compilers, has even more to say, because his use-case is much more practical than anything that compiler designers could imagine.
That's kind of a rude thing to say, suggesting that compilers aren't real programmers. Nevertheless, it is the case that most optimizations in the compiler are motivated by real issues with somebody's code, as opposed to compiler engineers thinking up optimizations in their heads.
So, if my sentence is rude, and "take anything Linus says about compilers with a grain of salt" isn't, then I definitely quit this discussion.
Your statement
> by writing kernels... his use-case is much more practical than anything that compiler designers could imagine.
States that compiler designers cannot even imagine the practicalities needed to write kernels. Which is quite a blanket statement to try to make and defend.
I'm suggesting that Linus isn't the best person to be used as an expert in compilers because his field isn't in compilers.
You're suggesting that someone who works on compilers shouldn't be used as an expert in compilers because their field is in compilers.
There is a difference between those two statements, and that difference is what makes one rude where the other isn't.
>How true is this really?
I’d be interested to see a more thorough analysis, but there is a simple way to gauge this - rip out all the parts of the compiler where aliasing information is propagated to LLVM, and see what happens to performance.
I found a claim that noalias contributes about 5% performance improvement in terms of runtimes[0], though the data is obviously very old.
https://github.com/rust-lang/rust/issues/54878#issuecomment-...
> I found a claim that noalias contributes about 5% performance improvement
Note that that comment is implying a range, from 0% improvement on some benchmarks to 5% improvement on others. It suggests that 5% is generally in the ballpark of the upper bound of what you should expect from putting noalias on mutable references, but that some specific cases could see better results.
While both involve aliasing, C's strict aliasing and Rust's aliasing are two different things. Rust pretty explicitly did not adopt the C style.
C's aliasing is based on type alone, hence its other name "type based alias analysis" or TBAA.
And TBAA is much easier for programmers to wrangle than the aliasing of Rust, right? The corresponding aliasing feature for C would be _restrict_, which is rarely used.
Though Linus and Linux turns off even strict aliasing/TBAA.
I don't think TBAA is easier to wrangle at all, or rather, it's almost never relevant except for allowing the compiler to make obviously, trivially true assumptions. Without it (all pointers could alias all the time), any C function taking more than one pointer argument would compile to a very surprising series of instructions, reloading from memory every single time any pointer is dereferenced.
Rust's rules are very simple and easy to get right - not least because breaking them is a compiler error.
Hmmm.
How is your comment consistent with some C compilers enabling users to disable TBAA/strict aliasing? Like the Linux kernel does. Do those codebases fit "compile to a very surprising series of instructions,"?
When unsafe is involved, sure, but that's a pretty small fraction of Rust code as a whole. As far as I can tell, a lot of his argument seems to be more against needing language changes in C to take advantage of strict aliasing that come at the cost of expanding the circumstances where UB can occur, but I don't really see how those would apply to safe Rust when it already has a perfectly safe way to express a reference guaranteed to not have any alias, i.e. `&mut T`. If the compiler authors came up with better ways to generate optimized code with unaliased pointers, I don't see why Rust would need to make any language changes in order to take advantage of them. That doesn't necessarily mean that there there is any significant untapped potential for these sorts of optmizations of course, or that the amount of effort to identify and implement them would be worthwhile for a toolchain like LLVM that is used for far more than just Rust, but it's not clear to me why the arguments he gives would be relevant to Rust.
Personally, I would like compilers to better exploit vectorization, which can get you 2x to 10x faster on random things within typical workloads, rather than worry about dubious optimizations that have performance improvements that may or may not be caused by changing the alignment of code and data blocks.
I would like to see more effort dedicated to basic one liners that show up in real code like counting how many of a given character are in a string. E.g. `for (str) |e| count += e == '%'`. For this, LLVM spits out a loop that wants to do horizontal addition every iteration on x86-64 targets with vectors, at least. Let's focus on issues that can easily net a 2x performance gain before going after that 1-2% that people think pointer aliasing gets you.
Pointer aliasing information is often crucial for vectorization. So in that sense TB is a big boost for vectorization.
Also, note that the paper discussed here is about the model / language specification that defines the envelope of what the compiler is allowed to optimize. Actually getting the compiler to optimize concrete real-world cases is an entirely separate line of work, and needs completely different expertise -- expertise me and my group do not have. We can only lay the framework for compiler wizards to have fun with. :)
Pointer aliasing is necessary for auto vectorization, because you can't perform SIMD if the data you're modifying overlaps with the data you're reading and since the compiler is only allowed to modify the code in a way that is legal for all inputs, it will be conservative and refuse to vectorize your code rather than break it in situations with pointer aliasing.
Maybe this was a too convoluted way of saying this:
Loading something from main memory into a register creates a locally cached copy. This mini cache needs to be invalidated whenever a pointer can potentially write to the location in main memory that this copy is caching. In other words, you need cache synchronization down to the register level, including micro architectural registers that are implementation details of the processor in question. Rather than do that, if you can prove that you are the exclusive owner of a region in memory, you know that your copy is the most up to date version and you know when it gets updated or not. This means you are free to copy the main memory into your vector register and do anything you want, including scalar pointer writes to main memory, since you know they are unrelated and will not invalidate your vector registers.
Strict aliasing rules are useful conditional on them being sufficiently expressive and sensible, otherwise they just create pointless headaches that require kludgy workarounds or they are just disabled altogether. I don't think there is much disagreement that C strict aliasing rules are pretty broken. There is no reason a language like Rust can't be designed with much more sensible strict aliasing rules. Even C++ has invested in providing paths to more flexibility around strict aliasing than C provides.
But like Linus, I've noticed it doesn't seem to make much difference outside of obvious narrow cases.
>There is no reason a language like Rust can't be designed with much more sensible strict aliasing rules.
The aliasing rules of Rust for mutable references are different and more difficult than strict aliasing in C and C++.
Strict aliasing in C and C++ are also called TBAA, since they are based on compatible types. If types are compatible, pointers can alias. This is different in Rust, where mutable references absolutely may never alias, not even if the types are the same.
Rust aliasing is more similar to C _restrict_.
The Linux kernel goes in the other direction and has strict aliasing optimization disabled.
> The aliasing rules of Rust for mutable references are different and more difficult than strict aliasing in C and C++.
"more difficult" is a subjective statement. Can you substantiate that claim?
I think there are indications that it is less difficult to write aliasing-correct Rust code than C code. Many major C codebeases entirely give up on even trying, and just set "-fno-strict-aliasing" instead. It is correct that some types are compatible, but in practice that doesn't actually help very much since very few types are compatible -- a lot of patterns people would like to write now need extra copies via memcpy to avoid strict aliasing violations, costing performance.
In contrast, Rust provides raw pointers that always let you opt-out of aliasing requirements (if you use them consistently); you will never have to add extra copies. Miri also provides evidence that getting aliasing right is not harder than dealing with other forms of UB such as data races and uninitialized memory (with Tree Borrows, those all occur about the same amount).
I would love to see someone write a strict aliasing sanitizers and run it on popular C codebases. I would expect a large fraction to be found to have UB.
I am very sorry, but your arguments here are terrible.
Unless casting or type punning through unions are used, the type system should help a lot in terms of avoiding using pointers to types that are not compatible in C. And then special care can be taken in any cases where casts are used. C++ is probably better at avoiding type casts, with all the abstractions it has.
This is different from no aliasing of Rust, where mutable references of even the same type may not alias.
Your own tool, Miri, reports that this fairly simple code snippet is UB, even though it is only the raw pointer that is dereferenced, and "a2" is not even read after assignment.
https://play.rust-lang.org/?version=stable&mode=debug&editio...
And you know better than me that Miri cannot handle everything. And Miri is slow to run, which is normal for that kind of advanced tool, not a demerit against Miri but against the general kind of tool it is.
I am very surprised that you come with arguments this poor.
You are not testing what you think you are testing.
"let &mut a2 = &mut a;" is pattern-matching away the reference, so it's equivalent to "let a2 = a;". You're not actually casting a mutable reference to a pointer, you're casting the integer 13 to a pointer. Dereferencing that obviously produces UB.
If you fix the program ("let a2 = &mut a;"), then Miri accepts it just fine.
> Unless casting or type punning through unions are used, the type system should help a lot in terms of avoiding using pointers to types that are not compatible in C
This is simply wrong. For once, C's type system does not help you here at all. Consider the following code:
float* f = ...;
void* v = f;
long* i = v;
// Code using both *i and *f
Further, you just can't seriously argue that C's type system helps you avoid UB in a thread about Rust. Rust's type system is the one that helps you avoid UB, and it's just so much better at that.
The code you mentions has UB, yes, but for reasons entirely unrelated to aliasing. You're reading from the address literal 0x0000000b, which is unsurprisingly not a live allocation. It's equivalent to the following C code (which similarly has UB).
printf("%d", *(int*)(0x0000000b));
But the implications of the second rule are also that you should know the aliasing model, or at least the over-approximation of "do not mix references and pointers." If you use raw pointers everywhere, you won't run into aliasing bugs.
> This is different from no aliasing of Rust, where mutable references of even the same type may not alias.
Aliasing in Rust is simpler when you follow the first rule, since everything is checked by the compiler. And if you use unsafe code with raw pointers, things are still simpler than in C since there is no TBAA. Only if you mix references and pointers do you get into territory where you need to know the aliasing model.
> This is different from no aliasing of Rust, where mutable references of even the same type may not alias.
It is different, yes. I never said it was the same. Your claim was that the Rust model is more difficult, that needs more justification than just "it is different".
Rust allows pointers of arbitrary types to alias if you use raw pointers. That kind of code is impossible to write in C. So there is a very objective sense in which the Rust variant is more expressive, i.e., it lets you do more things. That's not necessarily a measure of difficulty, but it is at least an objective way to compare the models. (But arguably, if something is impossible to do in C, that makes it more difficult than doing the same thing in Rust... ;)
Compare that to Rust, where if you hit aliasing limitations, there's always a way to change your code to still do what you need to do: use raw pointers. In other words, every UB-free C program can be translated to a UB-free Rust program that does substantially the same thing (same in-memory representation), but the other direction does not hold: translating a UB-free Rust program to UB-free C is not always possible, you might have to do extra copies.
Objectively comparing difficulty is going to be hard, so I gave some anecdotal evidence based on what we know about making real-world Rust code compatible with our aliasing models. Do you have any evidence for your claim of the C model being simpler?
(Other people already replied very well to the other points, I will not repeat them.)
> Compiler people think aliasing matters. It very seldom does. And VLIW will never become practical for entirely unrelated reasons (read: OoO is fundamentally superior to VLIW in general purpose computing).
I love how long Linus has been right about this.
Linus worked for Transmeta in 2003. That company built a VLIW CPU.
I don’t think you were a visionary if you stated VLIW is not practical for general purpose computing after that time.
Also “VLIW will never become practical” is a stronger claim than “VLIW will never become practical for general purpose computing”, and may be up for debate. https://en.wikipedia.org/wiki/Very_long_instruction_word says
“Since the number of transistors on a chip has grown, the perceived disadvantages of the VLIW have diminished in importance. VLIW architectures are growing in popularity, especially in the embedded system market, where it is possible to customize a processor for an application in a system-on-a-chip.”
That may be untrue or no longer true, but clicking around looking a the Wikipedia pages for several of the mentioned VLIW designs, I couldn’t find conclusive evidence for that (but, as with that VLIW page, the pages I looked at may be out of date, weren’t clear as to whether chips still were in production, whether newer generations actually still are VLIW, etc.)
It is mostly useful on arrays/numeric code, probably next to useless otherwise. Numerics people was the ones who sponsored much of compiler/optimization work in the first place, that's how strict aliasing came to be.
I don't think the usefulness is that skewed towards numerics?
Both clang/llvm and gcc can do alias checking at runtime if they can't at compile-time, which makes loops vectorizable without alias info, at the cost of a bit of constant overhead for checking aliasing. (there's the exception of gather loads though, where compile-time aliasing info is basically required)
And on the other hand there's good potential for benefit to normal code (esp. code with layers of abstractions) - if you have a `&i32`, or any other immutable reference, it's pretty useful for compiler to be able to deduplicate/CSE loads/computations from it from across the whole function regardless of what intermediate writes to potentially-other things there are.
> pretty useful for compiler to be able to deduplicate/CSE loads/computations
Yes, but is it a performance improvement significant enough? L1 latency is single cycle. Is the performance improvement from eliminating that worth the trouble it brings to the application programmer?
While I can't name the product I work on, we also use -fno-strict-aliasing. The problem with these optimisations is that they can only be done safely if you can prove aliasing never happens, which is equivalent to solving the halting problem in C++. In Rust I suspect the stronger type system can actually prove that aliasing doesn't happen in select cases. In any case, I can always manually do the optimisations enabled by strict aliasing in hot code, but I can never undo a customer losing data due to miscompilation.
> actually prove that aliasing doesn't happen in select cases
In the safe subset of Rust it's guaranteed in all cases. Even across libraries. Even in multi-threaded code.
To elaborate on that some more, safe Rust can guarantee that mutable aliasing never happens, without solving the halting program, because it forbids some programs that could've been considered legal. Here's an example of a function that's allowed:
fn foo() {
let mut x = 42;
let mut mutable_references = Vec::new();
let test: bool = rand::random();
if test {
mutable_references.push(&mut x);
} else {
mutable_references.push(&mut x);
}
}
fn bar() {
let mut x = 42;
let mut mutable_references = Vec::new();
let test: bool = rand::random();
if test {
mutable_references.push(&mut x);
}
if !test {
mutable_references.push(&mut x); // error: cannot borrow `x` as mutable more than once at a time
}
}
It requires that the libraries you use do not have UB. If you have no unsafe, but your library does, you can get UB.
https://github.com/rust-lang/rust/pull/139553
This is why it may be a good idea to run MIRI on your Rust code, even when it has no unsafe, since a library like Rust stdlib might have UB.
Isn't this a pretty trivial observation, though? All code everywhere relies on the absence of UB. The strength of Rust comes from the astronomically better tools to avoid UB, including Miri.
Miri is good, but it still has very significant large limitations. And the recommendation of using Miri is unlikely to apply to using similar tools for many other programming languages, given the state of UB in the Rust ecosystem, as recommended by
https://materialize.com/blog/rust-concurrency-bug-unbounded-...
https://zackoverflow.dev/writing/unsafe-rust-vs-zig
>If you use a crate in your Rust program, Miri will also panic if that crate has some UB. This sucks because there’s no way to configure it to skip over the crate, so you either have to fork and patch the UB yourself, or raise an issue with the authors of the crates and hopefully they fix it.
>This happened to me once on another project and I waited a day for it to get fixed, then when it was finally fixed I immediately ran into another source of UB from another crate and gave up.
Further, Miri is slow to run, discouraging people to use it even for the subset of cases that it can catch UB.
>The interpreter isn’t exactly fast, from what I’ve observed it’s more than 400x slower. Regular Rust can run the tests I wrote in less than a second, but Miri takes several minutes.
If Miri runs 50x slower than normal code, it can limit what code paths people will run it with.
So, while I can imagine that Miri could be best in class, that class itself has significant limitations.
> So, while I can imagine that Miri could be best in class, that class itself has significant limitations.
Sure -- but it's still better than writing similar code in C/C++/Zig where no comparable tool exists. (Well, for C there are some commercial tools that claim similar capabilities. I have not been able to evaluate them.)
> which is equivalent to solving the halting problem
Most worthwhile undefined behaviour is. If the compiler could tell whether it was happening or not, it would be defined as an error. Surely detecting whether a tree borrow violation happens is also equivalent to solving the halting problem?
The Stacked Borrows mentioned had threads in 2020 and 2018
The PLDI talk is also available: https://www.youtube.com/watch?v=CJi_Fcs4bak
Here's the implementation in Miri for those interested: https://github.com/rust-lang/miri/tree/master/src/borrow_tra...
Hmm i just tested out the claim that the following rust code would be rejected ( Example 4 in the paper).
And it seams to not be the case on the stable compiler version?
fn write(x: &mut i32) {*x = 10}
fn main() {
let x = &mut 0;
let y = x as *mut i32;
//write(x); // this should use the mention implicit twophase borrow
*x = 10; // this should not and therefore be rejected by the compiler
unsafe {*y = 15 };
}Stacked borrows is miri's runtime model. Run it under miri and you will see the error reported for the `*x = 10;` version but not the `write(x);` version - "Undefined Behavior: attempting a write access using [...] but that tag does not exist in the borrow stack for this location".
rustc itself has no reason to reject either version, because y is a *mut and thus has no borrow/lifetime relation to the &mut that x is, from a compile-time/typesystem perspective.
The paper is describing the behavior under the proposed Tree Borrows model, not the current borrow checker implementation which uses a more limited analysis that doesn't detect this particular conflict between the raw pointer and mutable reference.
Amazing work, I remember reading the Tree Borrows spec? on Nevin's website a couple years ago and being thoroughly impressed by how it solves some pretty gnarly issue quite elegantly. And in my experience [1] [2] it does indeed allow for sensible code that is illegal under Stacked Borrows.
[1] https://github.com/Voultapher/sort-research-rs/blob/main/wri... Miri column
[2] https://github.com/rust-lang/rust/blob/6b3ae3f6e45a33c2d95fa...
I wonder if Rust or future PL would evolve into allowing multiple borrow checker implementations with varying characteristics (compile speed, runtime speed, algorithm flexibility, etc.) that projects can choose from.
Rust already supports switching between borrow checker implementations.
It has migrated from a scope-based borrow checker to non-lexical borrow checker, and has next experimental Polonius implementation as an option. However, once the new implementation becomes production-ready, the old one gets discarded, because there's no reason to choose it. Borrow checking is fast, and the newer ones accept strictly more (correct) programs.
You also have Rc and RefCell types which give you greater flexibility at cost of some runtime checks.
I think GP is talking about somehow being able to, for example, more seamlessly switch between manual borrowing and "checked" borrowing with Rc and RefCell.
The new borrow checker is not yet all that fast. For instance, it was 5000x slower, according to a recent report.
https://users.rust-lang.org/t/polonius-is-more-ergonomic-tha...
>I recommend watching the video @nerditation linked. I believe Amanda mentioned somewhere that Polonius is 5000x slower than the existing borrow-checker; IIRC the plan isn't to use Polonius instead of NLL, but rather use NLL and kick off Polonius for certain failure cases.
We already have that by having multiple approaches via affine types (what Rust uses), linear types, effects, dependent types, formal proofs.
All have different costs and capabilities across implementation, performance and developer experience.
Then we have what everyone else besides Rust is actually going for, the productivity of automatic resource management (regardless of how), coupled with one of the type systems above, only for performance critical code paths.
> affine types (what Rust uses)
I'd just like to interject for a moment. What you’re referring to as "affine types", is in fact, Uniqueness Types. The difference has to do with how they interact with unrestricted types. In Rust, these "unrestricted types" are references (which can be used multiple times due to implementing Copy).
Uniqueness types allow functions to place a constraint on the caller ("this argument cannot be aliased when you pass it to me"), but places no restriction on the callee. This is useful for Rust, because (among other reasons) if a value is not aliased you can free it and be sure that you're not leaving behind references to freed data.
Affine types are the opposite - they allow the caller to place a restriction on the callee ("I'm passing you this value, but you may use it at most once"), which is not something possible to express in Rust's type system, because the callee is always free to create a reference from its argument and pass that reference to multiple functions..
I would say it is perfectly accurate to call Rust's type system affine. At its core, "affine" means that the type system has exchange and weakening but not contraction, and that exactly characterizes Rust's type system. See <https://math.stackexchange.com/questions/3356302/substructur...> for an explanation of what those terms mean (that's in the context of a logic, but it's the same for type systems via the Curry-Howard correspondence).
This is often explained via the "do not use more than once rule", but that's not the actual definition, and as your example shows, following that simplified explanation to the letter can cause confusion.
> because the callee is always free to create a reference from its argument and pass that reference to multiple functions..
Passing a reference is not the same thing as passing the actual value, so this does not contradict affinity.
> Passing a reference is not the same thing as passing the actual value, so this does not contradict affinity.
I agree that passing a reference is not the same thing as passing the actual value. If it were, there would really be no point to references. However, it does contradict affinity. Specifically, the fact that multiple references can be created from the same value, combined with the properties of references, contradicts affinity.
> At its core, "affine" means that the type system has exchange and weakening but not contraction, and that exactly characterizes Rust's type system.
Well, the rust type system certainly does support contraction, as I can use a reference multiple times. So what is that if not contraction? It seems like rust at least does support contraction for references.
But in practice, having absolutely no contraction is not a very useful definition of affine, because no practical programming language would ever satisfy it. It prohibits too much and the language would not even be turing complete. Instead, there is usually an "affine world" and an "exponential world". (Exponential meaning "unrestricted" values that you can do whatever you want with). And the convention is that values can go from the exponential world to the affine world, but not back. So a function taking an affine value can be passed any value, but must use in in an affine way, and meanwhile but a function taking an exponential (unrestricted) value can only be passed exponential and not an affine value.
If you don't believe me, you can try using linear haskell, and notice that a function taking a linear argument can be passed a non-linear argument, but not the other way around.
If you interpret Rust's type system this way, it's natural to interpret references as exponentials. But references have the opposite convention. You can go from owned values to references, but not the other way around, which is precisely the opposite situation as the convention around linear/affine type systems. Because these systems feel very different to use and enforce very different properties, I do think it's important that we have separate names for them rather than referring to both as "affine". And the usual name for the rust-like system is "uniqueness types", see https://docs.idris-lang.org/en/latest/reference/uniqueness-t... or https://en.wikipedia.org/wiki/Uniqueness_type .
The paper "Linearity and Uniqueness: an entente cordiale" by Marshall,Vollmer,Orchard offers a good discussion and explanation of the "opposite convention" you describe.
There is a dual nature of linearity and uniqueness, and it only arises when there are expressions that are not linear/not unique. At the same time, they have a lot in common, so we do not have a situation that warrants separate names. It is even possible to combine both in the same type system, as the authors demonstrate.
Taken from the paper:
"Linearity and uniqueness behave dually with respect to composition, but identically with respect to structural rules, i.e., their internal plumbing."
> Well, the rust type system certainly does support contraction, as I can use a reference multiple times. So what is that if not contraction? It seems like rust at least does support contraction for references.
Good question! For shared references, the answer is that they are `Copy`, so they indeed have contraction. Affinity just means that contraction is not a universal property, but some types/propositions may still have contraction. For mutable references, you can't actually use them multiple times. However, there is a desugaring phase going on before affinity gets checked, so uses of mutable references `r` get replaced by `&mut *r` everywhere. That's not using contraction, it's not literally passing `r` somewhere, it is calling a particular (and interesting) operating on `r` ("reborrowing").
Rust is not just an affine system, it is an affine system extended with borrowing. But I think it is still entirely fair to call it an affine system, for the simple fact that the language will prevent you from "using" a variable twice. "reborrowing" is just not a case of "using", it is its own special case with its own rules.
> But in practice, having absolutely no contraction is not a very useful definition of affine,
Obviously Rust has a class of "duplicable" types, called `Copy`. That's besides the point though.
> If you interpret Rust's type system this way, it's natural to interpret references as exponentials.
Why would that be natural? Mutable references are not even duplicable, so what you say makes little sense for references in general. Maybe you mean shared references -- those are just an example of a duplicable type.
Rust doesn't have a modality in its type system that would make every type duplicable, so there is no equivalent to exponentials. (In particular, `&T` isn't a modality around `T`. It's a different type, with a different representation. And as you noted, even if it were a modality, it wouldn't correspond to exponentials.)
But a type system can be affine/linear without having exponentials so I don't understand the point of this remark.
Uniqueness types seem to be all about how many references there are to a value. You can use linear/affine types to enforce such a uniqueness property (and that is indeed what Rust does), but that doesn't take away from the fact that you have a linear/affine type system.
> Because these systems feel very different to use and enforce very different properties,
I can't talk about the "feel" as I never programmed in an affine language (other than Rust ;), but in terms of the properties, what Rust does is extremely closely related to affine logics: the core property being enforced is that things do not get duplicated. My model of Rust, RustBelt, uses an affine separation logic to encode the properties of the Rust type system, and there's a lot of overlap between separation logic and linear logic. So we have further strong evidence here that it makes perfect sense to call Rust an affine language.
The main point of Affine logic is that it doesn't allow contraction, and the Rust type system does allow different forms of contraction. How exactly is Rust an "affine language"?
Also, the claims about Curry-Howard correspondence are wrong. It does not prove that rust is an affine language: https://liamoc.net/forest/loc-000S/index.xml
But Swift DOES have affine types with the "Non copyable" types that doesn't allow contraction.
> The main point of Affine logic is that it doesn't allow contraction, and the Rust type system does allow different forms of contraction. How exactly is Rust an "affine language"?
The point of Affine logic is that it doesn't allow universal, unconstrained contraction, not that you can never do an operation that has the same properties that contraction would have in some circumstances. The same is true of Rust's type system.
Rust has types that don't allow contraction, too: e.g., String, vectors and boxes.
Their being that way is essential for the borrow checker to provide the memory-safety guarantees it provides.
Yep, that's true. But multiple immutable shared references are a form of contraction, while mutable references are actually affine.
Swift doesn't have references like Rust, and you can't even have unsafe raw pointers to variables without producing a dangling pointer, but this makes Swift more restrictive and less powerful than Rust.
> multiple immutable shared references are a form of contraction
No, they are not. You're not using a value more than once, you are borrowing it, which is an extension of affine logic but keeps true to the core principles of affinity. I have modeled multiple shared references in an affine logic (look up RustBelt), i.e. in a logic that doesn't have contraction, so we have very hard evidence for this claim.
An affine type system is one in which some things don't have contraction, not one in which nothing has contraction.
I brought up Curry-Howard to explain why I am using an SO post about "affine logic" to make an argument about the definition of "affine language". Both are defined the same way: no (universal) contraction. That claim is obviously correct, so you are going to have to be a more more concrete about which claim you disagree with.
(The other part you said about contraction and affine logics has already been successfully rebutted in some other replies so I won't repeat their points.)
Yeah, that makes sense. The Rust type system isn't "affine" as in affine logic. Rust allows different forms of contraction, which affine logic strictly prohibits.
And some people like to claim that the Curry-Howard correspondence proves something about their type system, but this is only true for dependently typed languages.
And the proofs aren't about program behavior.
> Rust allows different forms of contraction, which affine logic strictly prohibits.
That's just wrong. Affine logic totally can have contraction for some propositions.
Also, CH totally exists for non-dependently-typed languages -- for instance, there is a beautiful correspondence between the simply-typed lambda calculus and propositional logic. Please stop repeating claims that you apparently do not understand.
I would love some sort of affine types in languages like Kotlin, it just makes cleaner code organization in my opinion.
Doesn't matter if it's purely "syntaxical" because the language is garbage collected, just the fact of specifying what owns what and be explicit about multiple references is great imo.
Some sort of effects systems can already be simulated with Kotlin features too.
Programming language theory is so interesting!
Rust's borrow checker has a fairly minimal compile time cost and does not impact codegen at all. Most of the compile time is spent on trait resolution, monomophization, optimization passes in LLVM, and linking.
What you actually want is the underlying separation logic, so you can precisely specify function preconditions and prove mid-function conditions, and the the optomizer can take all those "lemmas" and go hog-wiled, right up to but not past what is allowed by the explicitly stated invariants.
"Rust", in this context, is "merely" "the usual invariants that people want" and "a suite of optimizations that assume those usual invariants, but not more or less".
Can you help me understand your comment with a simple example? Take slice::split_at and slice::split_at_mut:
fn split_at(&self, mid: usize) -> (&[T], &[T])
fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T])
See Ralf's answer but let me give you a bit of extra flavor:
These functions do not memory accesses, they are both from an operational perspective essentially:
p, n -> (p, p + n)
The separation logics I've seen have all have what we might call a strong extensional calculi / shallow DSL embedding flavor. What that means is roughly that there is strong distinction between the "internal" program under scrutiny, and fairly arbitrary external reasoning about it.
I bring this up in order to say that we're very far from "what is the principal type of this expression?" type questions. There are many, many, ways one might type split_at/_mut depending on what the context requires. The interesting thing about these in Rust is really not the functions themselves, but & and &mut. Those types are stand-ins for some family of those myriad potential contexts, in the way that interfaces are always reifications of the possibilities of what the component on the other side of the interface might be.
In the "menagerie of separation logics" I was originally thinking of, there may not be singular & and &mut that work for all purposes. The most reusable form split_at indeed may be tantamount to the simple arithmetic pure function I wrote above, leaving to the caller the proof of showing whatever properties it needs are carried over from the original pointer to the new ones. Given the arithmetic relations, and the knowledge that nothing else is happening (related to the famous frame rule), the caller should be able to do this.
The long answer to this question can be found in https://research.ralfj.de/thesis.html. :)
I'm guessing you're referring to being able to change models without needing to change the code, but it's worth mentioning that there already is a mechanism to defer borrow-checking until runtime in Rust in the form of RefCell. This doesn't change the underlying exclusivity rules to allow aliasing mutable borrows, but it does allow an alternative to handling everything at compile time.
Deferring to runtime is not always great, since not only can it incur runtime overhead, the code can also panic if a violation is detected.
Using `try_borrow`/try_borrow_mut` should avoid panics, but yes, the overhead is why it's the exception rather than the rule, and it has to be done manually with these types. I'm not making a value judgment on the utility of working with that model, only pointing out in response to the parent comment that one of the things they mention is somewhat possible today, at the cost of having to update code. Even if it were possible to do it seamless as I'm assuming they're talking about, I don't really think it would be possible to do without incurring _any_ runtime overhead, but I think that's kind of their point; it might be nice to be able to switch between models when doing different types of development.
As I understand it the borrow checker only has false negatives but no false positives, correct?
Maybe a dumb question but couldn't you just run multiple implementations in parallel threads and whichever finishes first with a positive result wins?
> As I understand it the borrow checker only has false negatives but no false positives, correct?
The borrow checker is supposed to be a sound static analysis, yes. I think Ralf Jung's comment at https://news.ycombinator.com/item?id=44511416 says soundness hasn't been proved relative to tree borrows yet.
> Maybe a dumb question but couldn't you just run multiple implementations in parallel threads and whichever finishes first with a positive result wins?
IIUC when you're compiling reasonably-sized programs you're already using all the cores, so parallelizing here doesn't seem like it's going to net you much gain, especially if it means you're doing a lot of extra work.
Thanks, didn't see that!
> when you're compiling reasonably-sized programs you're already using all the cores
Only on full rebuilds. I would assume most build jobs with a human in the loop only compile a handful of crates at once.
In fact as CPUs get more and more parallel we'll cross the threshold where thread count surpasses work items more often and then will come the time to get creative ;)
This presumes that checking composes which may not if you have orthogonal checker implementations. You might end up risking accepting an invalid program because part of it is valid under one checker, part under another, but the combination isn't actually valid. But maybe that's not actually possible in practice.
Borrow checking is function-local, so if the opsem model is the same and you run the different checkers per-function, there is no such risk.
I’ll take your word for that although it feels like there may be other cases. Even still there is the subtle problem that bugs in the proof checkers now result in O(n^m) safety issues because an incorrectly accepted program is more likely to get through 1 of the borrow checkers (similar to how in a distributed system adding single points of failure results in exponentially decreasing reliability).
I cannot imagine how that would work. You couldn't combine code that expect different borrowing rules to be applied. You'd effectively be creating as many sub-dialects as there are borrow checker implementations.
FWIW technically the rules are the same. How they go about proving that the rules are upheld for a program is what would be different.
From the paper:
> The problem with unsafe code is that it can do things like this:
fn main() {
let mut x = 42;
let ptr = &mut x as *mut i32;
let val = unsafe { write_both(&mut *ptr, &mut *ptr) };
println!("{val}");
}
The point of this work is to pin down the exact boundaries of undefined behavior. Certainly the code above is accepted by the Rust compiler, but it also breaks rules. What rules? In essence, we know that:
- Anything accepted by the borrow checker is legal
- Unsafe can express illegal / undefined behavior
- There's some set of rules, broader than what the borrow checker can check, that is still legal / defined behavior
The goal of this line of work is to precisely specify that set of rules. The outlines are clear (basically, no writable pointers should alias) but the details (interior pointers, invalidation of iterators, is it creating or using bad pointers that's bad, etc) are really hard. The previous paper in this series, on Stacked Borrows, was simpler but more restrictive, and real-world unsafe code often failed its rules (while still seeming correct). Tree Borrows is broader and allows more while still being provably safe.
> Using pointers to coexist multiple mutable references to the same variable is undefined behavior.
Yes, but which exact rule does it violate? What is the exact definition that says that it is UB? Tree Borrows is a proposal for exactly such a definition.
"code can do things like this" here means "you can write this code and compile it and run it and it will do something, and unless we have something like Tree Borrows we have no argument for why there would be anything wrong with this code".
You seem to have already accepted that we need something like Tree Borrows (i.e., we should say code like this is UB). This part of the paper is arguing why we need something like Tree Borrows. :)
> Unless I'm just misunderstanding the point they're trying to make here.
You misunderstand the word "can". Yes, you can, in unsafe code, do that. And yes, that is undefined behaviour ;)
https://play.rust-lang.org/?version=stable&mode=debug&editio...
You're already getting a lot of replies, and I don't want to pile on, but I think the clearest way to see the intent there is at the start of the following paragraph:
> Given that aliasing optimizations are something that the Rust compiler developers clearly want to support, we need some way of “ruling out” counterexamples like the one above from consideration.
Just realised that one of the author, Neven Villani, is Cédric Villani's (Fields Medal 2010) son. Apples don't fall far from the tree, indeed.
This looks excellent. I will probably implement this model for my own language.
It can't be a dejavu. I keep seeing this post every 2-3 months...
[dead]
_Tree Borrows_
"I want my fuckin' money back."
"Hoom, hmm, let us not be hasty!"
"You got 48 hours to deliver or the sapling gets it, Treebeard."