Rust data structures with circular references (2021)
eli.thegreenplace.net
eli.thegreenplace.net
I've used this in an interpreter and it's quite convenient.
I wonder what a modern language would look like if it had manual memory management exclusively through isoheaps. Fil-C[1] attempts to retrofit isoheaps to C.
Now one can argue that isoheaps still allow access to wrong value and that this can potentially cause security issues. But the same also happens with indices or object pools in GCd languages. And if we go by this logic then Rust is less safe than Java (even without unsafe) because Rust requires indices to express what can be expressed with just references in Java.
Increasingly, I find it hard to justify systems like the borrow checker that force the programmers to contort their programs in a certain way. Unfortunately, a lot of newer languages (eg., Hylo, Austral, Circle) are experimenting with something similar to the borrow checker. Take Hylo for instance. The language has no reference type at all. So one has to use indices everywhere. Why not just embrace isoheaps instead?
[1] - https://github.com/pizlonator/llvm-project-deluge/blob/delug...
You can almost fake something that gets you some of the way there in normal C++ by making the allocator giving you a randomly-placed arena for each type. Yes, you can jump from one address to another, but in a 64-bit address space you're much more likely to segfault than to end up in a different isoheap's arena.
Fil-C uses fat pointers to retain bounds and type information to make existing C code safe (typical C is filled with pointer arithmetic and casts).
Languages like C++/Zig/D have bounds checked slices and containers (or at least have facilities to create them). So fat pointers are not necessary. Slice types can also fit into 128-bit (start+end pointers), so they can be atomic.
This is a big oversimplification. Rust can express a lot more than indices, and a lot more than what's in this post.
The actual requirement is that you capture your choice in the type system. But this is possible for anything from indices/handles to reference counting to arenas to GC.
&'a Node<'a>
I'm pretty sure that at least some instances of aggregation could be expressed as composition if you took a crowbar to the architecture and squinted a little bit. For instance, a child object can survive the death of a parent by being adopted by another.
This is loosely speaking what the qcell crate provides already, via TCell. But the "adoption" protocol involves the use of complex patterns where compile-time "token" types (which one could also see as capabilities for the underlying object) are passed to the relevant code.
Rust data structures with circular references - https://news.ycombinator.com/item?id=29207397 - Nov 2021 (42 comments)
First, we take some of the safety into our own hands. While this approach won't result in corrupted memory, double frees or accessing freed pointers, it can lead to run-time panics and other problems because we deal in "raw" indices to a vector.
(If you use u32 for the indices, you also save some space.)
I think I remember a discussion a while back lamenting that we just tacitly accepted wide pointers. If anyone has a link going over that, I'd be delighted to read it again. I'm 90% sure I did not understand it when I first saw it. :D
The idea is that every game of poker is a walk through a tree. Keeping track of probabilities and outcomes allows for exploration of the correct way to play. Using indices made building the tree easier (though I am still one bug away from it all working).
[1] - https://github.com/pizlonator/llvm-project-deluge/blob/delug...
Perhaps true in a very narrow sense, but you could say the same thing about all of Rust. "It's just laundering unsafe stuff behind a safe interface." And indeed, the ability to encapsulate unsafe internals inside a safe interface is one of the primary selling points of the language. It is also one of the key characteristics that differentiate it from languages that do not currently have this ability, such as C and C++. Whether you think this is an actual advantage or not is I suppose up to you, but I certainly think it is. And I think your use of the word "just" is papering over a lot of stuff.
For a more concrete code-level comparison with C, I did the leg work to translate a C program to a number of different Rust programs by varying some constraints. One of those Rust programs does indeed use indices instead of pointers. The README talks about the trade offs. See: https://github.com/BurntSushi/rsc-regexp/
That seems to be a very common position, and one that's super weird to me. C and particularly C++ absolutely have that ability with library support if you know what you are doing.
The only material difference, from my point of view, is that the default behavior of the language is different.
I will fully grant that the path of least resistance being dangerous is a huge issue in C/C++, and one that Rust addresses, but extending that all the way to saying that the language lacks the ability is really excessive.
Rust has a safety culture, and C++ does not. In Rust's safety culture it was obvious that std::mem::unintialized (an unsafe function) should be deprecated because it's more dangerous than it appears, it's actually hard to use it correctly. That's why today we have the MaybeUninit type. In C++ it was apparently equally obvious that std::span, a brand new type in C++ 20, should not have a safe index operation.
Technically the safe/ unsafe distinction being at the language level makes it hard to fake. You can say your C++ only uses your safe abstractions, but the language itself doesn't care, so without inspecting every part of it to check you're never more than one slip away from catastrophe.
Most importantly in this context, at the language level Rust is committed to this safety distinction. If you write code where Rust's compiler can't see why it's OK, the compiler rejects your program. C++ requires that a conforming compiler must instead accept programs unless it can show why they're wrong. These are two possible ways to cut the Gordion knot of Rice's Theorem, but they have very different consequences.
Now if I were to say something like, "Rust's safety means that you can never have UB anywhere ever and CVEs will never happen for anything if you use Rust." Then yes, that's excessive. But to say that Rust can encapsulate `unsafe` and C and C++ cannot? I don't see how that's excessive. It's describing one of the most obvious differences between the programming languages.
You can restrict yourself to particular subsets of C (I'm thinking about MISRA) or C++, but these usually come with even more significant trade offs than Rust. And I'm not aware of any such subset that provides the ability to encapsulate safety in a way that lets folks not using that subset benefit from it in a way that is impossible to misuse (as a matter of an API guarantee).
Burroughs B5000 had an additional feature for executables using unsafe code that we only have nowadays on managed runtimes like Java and CLR, binaries with unsafe code were tainted and required someone with admin access to enable them for execution.
Regarding C and C++, Visual Studio, Clion and clang tidy are the best we have in terms of tooling for the general public supporting the Core Guidelines (including lifetime checks), and they are still relatively basic in what they can actually validate.
I think that's fundamentally different---although related---to just having an `unsafe` keyword. To take something I know well, Go has an `unsafe` package that acts as a sort of unsafe keyword. If we ignore data races, you can say that a Go program can't violate memory safety if there is no use of the `unsafe` package.
The problem though is that you can't really build new `unsafe` abstractions. You can't write a function that might cause UB on some inputs in a way that requires the caller to write `unsafe`. (You can do this by convention of course, e.g., by putting `Unsafe` in the name of the function.)
In Rust, `unsafe` doesn't just give you the ability to, e.g., dereference raw pointers. It also is required in order to call other `unsafe` functions. You get the benefit of composition so that you can build arbitrary abstractions around `unsafe` with the compiler's support.
My understanding is that Modula-3 supported this style of encapsulation (which is what I was talking about in this thread). What languages prior to Modula-3 supported it, or was Modula-3 the first?
Since Unisys still sells Burroughs, nowadays ClearPath MCP, you can get the latest NEWP manual here, section 8.
https://public.support.unisys.com/framework/publicterms.aspx...
Followed by Mesa/Cedar (CHECKED, TRUSTED, UNCHECKED), Modula-2 (IMPORT SYSTEM), the languages of Oberon linage (which follow up on the IMPORT SYSTEM approach), Ada (using Unchecked),....
In the languages that use the IMPORT SYSTEM approach, the compiler can mark the module as unsafe, and anything that might depend on it.
Some the Modula-3 folks worked previously on Cedar at Xerox, by the way.
Mesa - http://www.bitsavers.org/pdf/xerox/mesa/5.0_1979/documentati...
Cedar - http://www.bitsavers.org/pdf/xerox/parc/cedar/Cedar_7.0/09_C...
I won't speak to C++, as it's a very different language now since the last time I used it. I've been writing C for more than 20 years, and I still make mistakes. And there's nothing keeping me from accidentally doing something unsafe outside my unsafe abstraction, aside from my own perfection at never making mistakes (yeah, right).
Rust requires you to be explicit about the unsafe things you do. And, realistically, even when I'm building a safe interface on top of necessarily-unsafe code, the unsafe portions aren't even that large compared to the entirety of the abstraction. That makes things much easier to audit, and the compiler tells me which sections of code I need to pay more attention to.
To me, this is lacking the ability. "If you know what you are doing" is a laughable constraint. Even people who theoretically do (and I suspect programming ability is a lot like people's self-reported skill at driving a car) still make mistakes sometimes.
No, as long as you don't use the unsafe keyword, an out-of-bounds vector access won't lead to use-after-free or other memory safety bugs.
When writing such an emulator the natural way to set up the memory is to use an array, and the natural way to implement pointers is indices into that array. In other words, this pattern is part-ways there to creating an emulator with internal safety issues.
However guaranteeing that any corruption will be contained to the array is certainly a lot better than nothing.
Rust's borrow checker doesn't account for when you re-implement parts of memory management as array indexes.
One workaround is to make the backing Vec hold Option of Node instead so that deleting a node can set the hole to None, in which case the bug I described above has the opportunity to unwrap() and panic instead of silent UAF. Though you'll also need additional tracking for those holes so that you can fill them with new nodes later, at which point you'd be better off using a proper freelist / slab instead of a Vec anyway (as TFA also mentions).
You use scare quotes around "freed" for a reason: the data has not actually been freed.
The bug you're talking about is a logic error. It could be a bad bug, depending on circumstances, but there's no memory safety issue here.
Who said it hasn't? I would assume such a node to have been given to `std::ptr::drop_in_place`. Not doing that would be a leak until the list as a whole was dropped.
To have a UAF, there has to be memory that is actually freed, and you have to attempt to access that memory. No memory is freed here (in the OP's implementation). Even if it was, at worst you'd get a panic for trying to access past the end of the Vec.
None of that is a UAF or a memory safety issue. It's just a logic bug.
Could you please read the link I shared? There's all sorts of nuance in the README. And there is absolutely no pretending in my comment or in the link I shared that using indices instead of pointers has zero downsides.
Writing that using normal pointers is impossible in safe rust (barring a compiler bug, which do exist but are rare).
Please also consider what I was responding to:
> you’re just laundering the unsafe pointer arithmetic behind array indexing
It would be easier to discuss whatever non-UB failure modes you have in mind, in the context of Rust, if you used a different term.
"memory safety bugs" -> "for example, UAFs" -> "I don't mean a literal UAF" -> "use array index after free" -> 'memory safety is not "code that does not result in UB"'
I mean, you can define "memory safety" to be whatever you want it to be, but the definition everyone else uses (including Rust) is absolutely connected with undefined behavior. More than that, the entire context of this thread assumes that definition. Rust certainly does. And if you are going to use a different definition than everyone else, at least have the courtesy to provide it.
If people used your definition, then it would be wrong to, for example, say that "Java is a memory safe programming language." But that is, as far as I know, widely regarded to be a true statement.
This sort of disagreement is profoundly irritating, because I made it exceptionally clear what I meant from the get-go. All you had to do was respond and say, "oh, it sounds like we are just using different definitions of the term 'memory safety.' if we use your definition, I agree with what you said."
Rust's goal was never to exclude all shared mutability. (Otherwise why support things like locks?) Rather, it excludes only the kinds of shared mutability that open the door to undefined behavior. The point of all these sorts of "workarounds" is that, because there is no longer a single unrestricted kind of shared mutability, you now get to pick which version of restricted mutability you want: reference counting vs bounds checking vs ghostcell's higher-rank lifetimes vs whatever else.
Not in the sense of ownership that matters in Rust. The Vec owns the data. A node with an index in it does not own that data. It merely refers to it.
The key here is when you answer the question, "what happens when I screw it up the indices?" And the answer is logic errors or a panic. Neither of those are memory safety issues.
You may think that's a difference without distinction, but "memory safety" and "use after free" have specific definitions, and this ain't them.
The particular difference is noted in the fragment you quoted. What may not be obvious, is why corrupted memory etc. are a much bigger problem than panics. In fact it is usually the _lack_ of panics that is problem in them: they will lead to silent memory corruption. This will lead to unexpected behaviors of your code. Ones you just never even assumed possible - due to basic contracts being broken. Such problems with then silently propagate through your system, poisoning it without you knowing. Whereas a panic is a clear cut alarm/canary behavior: something's wrong, let's crash loudly and make it immediately visible. This will protect against the corruption spreading out. And in a typical system, will restart the panicked binary, allowing the system to resume operation with minimal disruption.
Don't.
You do not need to.
Rust does stop you creating self referential structures (easily)
In the case of a binary tree that is not a problem
There might exist some specialised case where there is no more memory to allocate at run time, but in the common case it is more efficient in every respect to use algorithms with your data structures and dispense with back links
I have been working on a C program built by a (mostly brilliant) programmer that put back links in every structure (parent links in trees, doubly linked lists) and the waste of resources, in a constrained environment, is frustrating
Just don't
If the language doesn’t let you then the language sucks.
This is the whole point for me. There are loads of reasons fundamental data structures want to use behaviour the compile can't prove is sound, but humans can burn time discussing, proving the algorithms and testing the implementation. Then, you ask the compiler to prove all the simple glue stuff on top.
You know that popcount bit counting device that treats a word of memory as a short SIMD instruction using the 32 or 64 bit ALU? I learned recently that compilers can detect that and emit popcount instructions if those are faster on the target architecture.
I suspect if you can detect that, you could detect a safe parental reference device and let it pass the checker.
For trees some, not very good, algorithms require parent pointers
One of the main points is that there are very few algorithms that require back links that create cycles.
Cyclic data structures, rare as they are, are also hard to reason about. Even for garbage collectors!
If you have to implement one in Rust (I have) it is a bother, a big hassle.
It is a good thing that in the general case when a programmer is implementing back links they are doing the Wrong Thing.
Weird to justify this kind of language limitation when a great technology exists that obviates the need for it.
[1] Trying to wean myself off the archaic “whom”.
One easy fix is using the modern 'whomst' everywhere. It has the all the faux-sophistication of 'whom' (with some extra borrowed from 'amongst' and 'whilst') while being equitably wrong to everyone rather than special groups like whom-pedant toffs and who-everywhere anarchists.
There are few people using Rust who don't have experience in other languages. It's wild that you think you know about their use cases better than they do.
Your comment says "I have never worked on a problem where GCs are problematic". That is great for you, but it has little to do with the value of improving the situation for native, no runtime, performant languages.
The biggest downside of naive reference counting usually isn't the cost of reference counting itself, it's being left stuck holding the bag when you're unlucky enough to be the last deref on a giant object graph. You can move the destruction onto a separate finalizer thread like what most runtimes that use tracing GCs do, but then you end up running into CPU scheduling issues if you're not overprovisioned.
The real problem is most GCs are built with a “throughput first” mindset and determinism is bolted on.
The details of how to build a deterministic GC are beyond the scope of a HN post lol
Obviously there's a lot of problems where a GC would be a real performance issue, but I think that people will reach to "rewrite in Rust" too quickly sometimes. Manual memory management is hard, and most software engineers, sort of by definition, are "average".
Still, the point I was making is that it's possible to have garbage collectors that get very low pause times (sub millisecond in Go's case [1]). It might still be an issue for a kernel or microcontroller, I'm not suggesting we always use a GC for every project, I don't think most people would, but I am suggesting that there are a lot of projects (most projects?) that would be better off using a low-latency GC instead of trying to handle memory directly.
Even the JVM is getting better about this; there's already experimental support for a low-latency GC in some distributions of OpenJDK [2], which reportedly gets sub-millisecond pauses as well. If you have JVM support then you have access to good languages like Clojure.
Personally, I actually think I'm reasonably-ok with manually managing memory, I've cut my teeth on enough C to write code that doesn't generally crash, but I still reach for a garbage collector whenever possible. Just because I think I'm capable of doing manual memory management doesn't mean that I think it's worth it for most things; nearly everything I do touches a network at some point, which means that avoiding latency is not really possible a lot of the time.
[1] https://groups.google.com/g/golang-dev/c/Ab1sFeoZg_8 [2] https://wiki.openjdk.org/display/shenandoah/Main
Forgive some ignorance on this, but does this mean you have literally zero millisecond pause times? What kind of additional overhead/throughput does this incur? This just seems like the holy grail!
See PTC and Aicas, the two main vendors still in business.
And even if I am not a big Go fan, TinyGo and TamaGo show what is possible regarding using Go for bare metal deployments, OS like.
It isn't for lack of alternatives with nice type systems, automatic memory management and AOT tooling.
Personally I like Scala a lot, and I used it quite a lot as a hobby for 10+ years, but my impression is that it's dying (or dead) so I'm not really motivated to play with it anymore. Kotlin always felt to me like a subpar Scala, so I never enjoyed it.
There is something about Rust that makes me feel it's a smart language and make me enjoy writing it (most of the time at least, it can absolutely be frustrating at times too). But it's certainly a matter of taste before all.
GC being any kind of automatic memory management, tracing GC, reference counting, mixed scheme with reference counting and cycle collectors.
Take any systems language that uses that approach to automatic resource management, coupled with ability to use stack allocation, registers and what have you, and there are very few use cases where something else is required.
Like kernels, drivers on hard real time constraints.
Even for GPUs I think shading languages are much more ergonomic than trying to fit classical languages into them.
What we really need is an ergonomic way to opt into different kinds of memory allocation and management. The borrow checker is great for when you need no extraneous allocation. GCs are great for many linked lists. Bump allocators are great for web template rendering with lots of temporary strings.
Call me a crank, but while a lot of people say that you don't need to go without a garbage collector for most problems, I believe the converse: that there aren't many problems where you actually need a garbage collector (if you have some other way of freeing yourself from having to manually manage your memory and manually avoid use after free and so on). I think once your mind gets adjusted to working without one and within the constraints of the borrow checker, it's really not that much of a drag, and if you really need to do something outside those bounds (or just want to ignore it and hack something together quickly) that's what Gc and Arc are for.
And honestly, in general I like the unique intersection of features that Rust offers as a language, totally independent from its performance or the presence or absence of a garbage collector at all. Even if it was garbage collected and about 2x slower, I think I would still prefer it to most of the 40 or so languages that I've tried over the years. It feels like a version of OCaml with a much better standard library and ecosystem, a much better build system, a vastly better and cleaner way of doing parametric polymorphism, and much better metaprogramming facilities in comparison.
Not only that, but I genuinely find the constraints of the borrow checker — most especially only allowing either one mutable reference or multiple read-only references at a time — to be a great help in making my code clearer and more straightforward: it essentially helps me reach a lot of the same benefits as pure functional programming (where the data flow of my application is carefully threaded and there is no spooky action at a distance) while still allowing me to have imperative programming and mutation where I need it, by just forcing me to only have one place in my code be able to mutate anything at a given time, to explicitly mark it whenever I'm giving any piece of my code mutable access to anything, and essentially preventing me from having any persistent mutable access to a data structure be held in some other data structure or portion of code that can then continue to mutate it without my explicit permission and knowledge. So why give up the uniquely productive constraints of the borrow checker, which again to reiterate give me 90% of the benefits of pure functional programming with only 50% of the annoyance, and add in all of the unnecessary bloat and non-determinism of a garbage collector, when I have never really found myself to need it?
Furthermore, Rust is significantly more performant than even very fast and systems oriented garbage collected languages with their own runtime such as Go or OCaml or Java, which has the added benefit of allowing me to not really have to worry about performance at all beyond picking reasonable algorithms, and sometimes not even then since the language is often fast enough to make brute force feasible, which paradoxically means that when I am programming in rust, this high performance systems language, it often frees me from the burden of having to worry about performance like I would in something like python. For instance, I've actually implemented programs in Python that end up being so hilariously and frustratingly slow that I eventually gave up on working on them.
Moreover, if I do have to concern myself with performance in rust, I feel like working in a language that uses RAII and doesn't wrap everything in pointers for GC by default provides a significantly clearer mental model for me of what my program is actually doing with its memory, and how my data is actually laid out, and I also typically have a clearer mental model of what CPU operations my program is actually doing as well. And in fact just having this clear mental model of what my program is actually doing helps me Implement more efficient algorithms and make cleaner and less wasteful programs in general, which I quite like.
So yes, in essence I would turn the question back on the questioner and ask why they think they need a garbage collector and a language runtime and all of this extra stuff. Yes it does make the language marginally easier and quicker to write things in, but if I am sitting down to write a large scale program or long running project then being slowed down slightly in return for increased productivity.
In all seriousness though, I'd say I only have 2 real projects that needed Rust's speed, and the rest I've done is because I bring the other type safety benefits Rust brings.
Rust achieves correctness at scale, over time, more than most GC languages.
A modern "fast" GC has latencies similar to disk I/O on modern storage. We don't make a habit of randomly dropping a blocking disk I/O in the middle of a performance critical path, and disk I/O is less likely to pollute your CPU cache as a side effect than a GC. Given that performance-optimized code is routinely designed to eliminate the overhead of even context switches (e.g. thread-per-core architectures) to great benefit and GC pauses are much more expensive than a context switch even when "fast", it is difficult to develop a theory of how a GC does not have an adverse impact on performance.
You could try to make the argument that most people writing Rust don't care about performance so it doesn't matter, but that is likely to be controversial at the least.
This doesn't address the issue with GCs in high-performance systems, it just turns it into a different kind of problem.
I'm not ready to assume again that every popular GC-based language will be able to keep up with the available memory on cloud instances, let alone be able to vertically scale to a full bare metal machine. The value of Rust's tradeoffs gets bigger the higher you vertically scale, does it not?
To add more context: I tried the articles suggestion and used integer handles some years back and shared my feedback on HN [1]. It wasn't a good experience as integer handles are just pointers the borrow checker doesn't know about. It made the implementation far more cumbersome than it needed to be.
That's a key difference - the article has a focus and your comment is generic and repetitive programming-language-war adjacent. There's even a guideline exactly about that - "Comments should get more thoughtful and substantive, not less, as a topic gets more divisive."
You argue that you would use a higher-level language for that part. Fair. But I don’t see the objective argument for using C for the low-level part. You just say that you want to use C. That’s preference and has nothing to do with Rust being a language that can do multiple things.