Rust data structures with circular references (2021)

https://eli.thegreenplace.net/2021/rust-data-structures-with-circular-references/

by thunderbong • 2 years ago

111 133 2 years ago

eli.thegreenplace.net

gumby• 2 years ago

Unfortunately, despite all that effort, deletion leaks memory.

rjeli• 2 years ago

  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.

Yeah, I’ve often seen people in discussions about c/zig/rust memory saying “manual memory management is fine, just use an arena and handles!” It’s a strange statement to me because you’re just laundering the unsafe pointer arithmetic behind array indexing

agalunar• 2 years ago

Using indices is a (slight) improvement over pointers, since in Rust you will benefit from bounds checking (restricting you to the memory allocated for that tree).

(If you use u32 for the indices, you also save some space.)

taeric2• 2 years ago

It is hilarious how much space you can save by using smaller indexes than a pointer. Especially on modern architectures.

eclark• 2 years ago

I am currently writing a CFR Tree that has nodes that can be self-referential. https://github.com/elliottneilclark/rs-poker/pull/92

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

10000truths• 2 years ago

The laundering is the point. It's much easier for the user to handle out-of-bounds array accesses and uninitialized array elements, compared to tracking the lifetime and validity of data at arbitrary memory addresses.

favorited• 2 years ago

The arena + handles approach doesn't solve the memory management issue, but it can be beneficial for storing nodes in a list, graph, etc. from a data locality perspective.

bbatha• 2 years ago

The difference is that the array bounds are checked and the behavior is defined whereas bad unsafe pointer athematic if you’re lucky gives you a segfault and at worst an RCE.

alexchamberlain3• 2 years ago

Array bounds are essentially unchecked in C, unless you go so far over as to hit a guard page.

empath-nirvana2• 2 years ago

You can have bugs with that style of coding, but they're not going to be bugs of the "remote code execution" type.

googh3• 2 years ago

If preventing remote code execution is the goal, then C/C++/Zig can also achieve this using isoheaps (see Fil-C[1] for example). Even without isoheaps, CFI mitigations are able to prevent jumps into code not known at compile time. Why bother with Rust or any other language with borrow checkers then? Just a honest question.

[1] https://github.com/pizlonator/llvm-project-deluge/blob/delug...

burntsushi8• 2 years ago

you’re just laundering the unsafe pointer arithmetic behind array indexing

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/

Chabsff2• 2 years ago

languages that do not currently have this ability

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.

cmeacham984• 2 years ago

I think you're missing the point - abusing a vector in this way is not a safe interface and is instead a good way to introduce several memory safety bugs (for example, UAFs) that the normal rust memory model explicitly prevents.

akavel• 2 years ago

There's a huge difference in the outcomes those can lead to, that's why it's not just a simple "laundering", but a serious gain. On top of that, C vs. Zig vs. Rust give you a different level of that gain still.

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.

kelnos7• 2 years ago

There's a big difference, though: the array indexing code is still safe from memory errors. I would much prefer a panic over a segfault.

alilleybrinker2• 2 years ago

Always worth plugging “Learning Rust with Entirely Too Many Linked Lists,” the canonical writing on the type of iterative approach for implementing data types with circular references in Rust: https://rust-unofficial.github.io/too-many-lists/

keybored5• 2 years ago

The writing style is also fun IMO.

alilleybrinker2• 2 years ago

Oh yeah Aria’s writing is excellent. https://faultlore.com/blah/

smasher164• 2 years ago

Another approach is to use a Gc<T> smart pointer: https://docs.rs/gc/latest/gc/

I've used this in an interpreter and it's quite convenient.

foldr• 2 years ago

Nice! This seems way more appealing than every other approach I've seen in this domain.

celeritascelery2• 2 years ago

That is just using a RefCell under the hood[1] so it is effectively the same trade-offs as the RefCell example from the article.

[1]https://docs.rs/gc/0.5.0/src/gc/lib.rs.html#495-498

rendaw• 2 years ago

It doesn't require you to differentiate weak and strong references, so there's no risk of memory leaks due incorrect choice in Gc, unlike Rc IIUC.

paholg2• 2 years ago

Note: the two of you are linking to different crates. Samsara provides a Gc type, but it is not the gc crate.

zozbot2343• 2 years ago

Yes, garbage collection seems to be the only viable solution for dealing with spaghetti reference graphs in their full generality, including possible cycles. In that context it's worth trying a high-performance concurrent GC implementation such as https://github.com/chc4/samsara Samsara.

kldx2• 2 years ago

https://plv.mpi-sws.org/rustbelt/ghostcell/ uses higher rank lifetimes to implement circular linked lists. The downside is that a linked list is stuck inside a closure.

zozbot2343• 2 years ago

Nice, there are also many other variants of this pattern, such as are implemented in the qcell crate.

kldx2• 2 years ago

Right! LCell (qcell) is similar to GhostCell but I like the flexibility the other cell types in qcell provdie

worik3• 2 years ago

Now suppose we want to add a parent link to every node.

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

pizlonator4• 2 years ago

Some algorithms need the parent or bidirectional pointers.

If the language doesn’t let you then the language sucks.

empath-nirvana2• 2 years ago

This post shows 3 ways of doing it, including essentially the same way you'd do it in C. And it's exactly as dangerous as doing it in C is, but at least you can isolate that dangerous code to one part of your code base.

worik3• 2 years ago

Some algorithms need the parent or bidirectional pointers.

For trees some, not very good, algorithms require parent pointers

fhood• 2 years ago

I think it's best to think of this as a good toy example, and not get caught up in the specific utility of a "parent" node.

worik3• 2 years ago

It is just a bad example.

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.

theLiminator• 2 years ago

Curious if you could implement the tree with qcell or ghostcell for zero runtime cost and having compile time safety?

aidenn0• 2 years ago

Isn't raw pointers only needed for the parent reference, not all references?

pizlonator4• 2 years ago

The frustrating thing is that GCs have come far enough that for most of what folks use Rust for, they’d have been happier using a GC’d language.

Weird to justify this kind of language limitation when a great technology exists that obviates the need for it.

keybored5• 2 years ago

Frustrating for who?[1] 99% of Rust users have likely used languages that use GC.

[1] Trying to wean myself off the archaic “whom”.

pjmlp7• 2 years ago

Which kind of GC though.

pvg2• 2 years ago

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.

_se2• 2 years ago

The frustrating thing is that people say this without realizing that GCs haven't, and by necessity cannot provide the type of deterministic and predictable performance that would lead someone to use Rust/C++ and friends.

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.

pjmlp7• 2 years ago

Only for those that put the word GC on the same bag, without understanding there are tons of approaches, and many languages with automatic resource management also provide deterministic features.

hgs34• 2 years ago

You can make garbage collection deterministic. Tracing collectors can be designed to accept a timeout so you can "collect" during downtime and resume execution on a predictable schedule. And with reference counting the cost of RC bookkeeping is smeared predictable across the run of the program. The real problem is many GC implementations lack customization and you're stuck with whatever GC algorithm the language implementers pick.

IncreasePosts• 2 years ago

I realize this is a biased sample, but about 99% of rust projects I see on hn or lobsters wouldn't have been encumbered by a GC

tombert4• 2 years ago

Most people aren't writing a kernel. I've seen plenty of Rust projects writing things like web servers, where a low-latency GC (like Go's) would work just fine.

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

pizlonator4• 2 years ago

I am saying that GCs can do it as a GC engineer

pjmlp7• 2 years ago

They have been great for decades, it has been mostly a religion thing.

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.

vlmutolo• 2 years ago

The thing is that most code has a straightforward, tree-like ownership model. It’s overkill to use a GC for everything. It also sometimes leads to memory bloat.

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.

logicprog2• 2 years ago

This is my position as well.

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.

pornel• 2 years ago

I don’t mind GC per se, but languages based around a GC tend to lack other useful properties that Rust has, like deterministic destruction for resource management, and exclusive ownership that prevents surprising mutation of objects without making them immutable.

swsieber• 2 years ago

I came for the speed, I stayed for the lack of `ConcurrentModificationException`s.

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.

sunshowers• 2 years ago

Which popular GC languages have mutexes owning the state they guard, such that it is structurally impossible to access that inner state without holding the lock? To do that you must have single ownership.

Rust achieves correctness at scale, over time, more than most GC languages.

jandrewrogers2• 2 years ago

GCs have not come far enough if you care about performance.

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.

pebal5• 2 years ago

You can have completely concurrent GC, without pausing threads.

https://github.com/pebal/sgcl

hinkley3• 2 years ago

One of the hills I will die on is the somewhat bold assertion that memcached primarily exists because Java got stuck at 1-2GB max heap sizes when obtainable servers started having 4-8 and then 16GB of memory. They got stuck there for long enough that a cottage industry of off-process lookup tables became tenable (also at the time Java was still UCS-16 encoded so you could save 25% of your memory by shoving text out of process)

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?

dang• 2 years ago

Rust data structures with circular references - https://news.ycombinator.com/item?id=29207397 - Nov 2021 (42 comments)

LAC-Tech• 2 years ago

Raw pointers and unsafe all the way. Sure a few of the more... radical elements of the rust community might try some safety shaming, but it really is the most pragmatic choice here.

hgs34• 2 years ago

This is what bothers me about using Rust: it seems like Rust is trying to be both a systems language and a higher-level glue language in one, but (for me) it is cumbersome at both. If I need to write higher-level code then I'd rather use Go, Python, or whatever else and interface with C as needed. If I'm writing low-level code then I can use C and an embeddable scripting language for any high-level bits. This multi-language approach is not discussed enough. Recently, I completed a project that used cgo to interop C and Go code and the experience was very pleasant. No need for language workarounds or other code contortions. Just two languages doing what they do best.

tupshin• 2 years ago

Your comment is about rust, but not at all related to the article.

hgs34• 2 years ago

The "workarounds or other code contortions" I'm talking about is the focus of the article. The point of the article is that safe Rust cannot directly represent circular data structures and therefore you need workarounds to represent them. My point is rather than fighting the borrow checker you could use two complimentary languages to achieve the same goal.

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.

[1] https://news.ycombinator.com/item?id=32907482

keybored5• 2 years ago

It’s a systems language (whatever that means). It can also be a glue language if you want it to be since it has high-level capabilities. Since being an austere systems programming language is kind of a defunct 90’s thing.

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.

pkulak• 2 years ago

This is always brought up as the Achilles heel of Rust but, like... it's not that bad. You just need a weak reference. In fact, it's no different than a language like Swift, where everything is always reference counted. However, Swift will happily let you do it the wrong way and leave finding the resulting memory leak up to you. I prefer the way Rust handles it.

zamalek• 2 years ago

Honestly it has taught me that we need circular refs far less often than we thought. I consider it one of the best features of Rust. The lack of circular refs makes code far easier to reason about, and makes it more difficult to produce spaghetti code.

jupp0r• 2 years ago

I don't see the problem in having a separate container that manages ownership and representing links between graph nodes in terms of that. The resulting overhead can be quite minimal and it's probably good practice to do this even in C.

hinkley3• 2 years ago

To a moderately informed spectator, it does seem like Rust should be able to reasonably handle complex (cyclic) data structures - but only when the design can be expressed as composition. With aggregation you have a gnarly potentially undecidable state tree.

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.

zozbot2343• 2 years ago

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.

josephcsible• 2 years ago

  &'a Node<'a>

This (from the non-working "obvious" way) seems to be a common mistake, where the lifetime of a reference is the same one in the type parameter of what it refers to. Does anyone know if this has a name, or if there's some useful resource that talks about it in particular, outside of the context of circular references?

tempaccount420• 2 years ago

Adding more lifetimes is not convenient in Rust so developers tend to reuse them. I wish it wasn't such a (refactoring) pain to add more lifetimes to a struct.

binary132• 2 years ago

Interesting article. It got me thinking about what invariants could be proven for these data structures with a proof assistant having knowledge of things like lifetime or ownership. One thing that bothers me about Rust is that these properties are hardwired into the syntax in a very specific way. Sometimes I might want these properties to be exactly the way they are in Rust. Sometimes less, sometimes more, sometimes other semantics. This article makes me think that the tools Rust offers aren’t very good for this task. They’re not bad! But it seems like something better could be devised.

nurettin• 2 years ago

Storing references in integer arrays is how people used to program data structures in BASIC. I still use this method with vectors in order to make data structures easy to serialize and inspect.

googh3• 2 years ago

There is hardly any difference between indices into vectors and isoheaps (ie. an allocator that reuses the same pool for the given type). Except that the latter is faster and much more ergonomic. Both prevent remote code execution.

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

cozzyd• 2 years ago

This seems easier to retrofit onto C++ due to stronger type guarantees, no? (As described in that implementation, you basically can't use malloc but instead need a typed version of malloc). I would say that you w ant more than 32 bit pointers though because you can easily require a working set bigger than 4GB. I'd think something like 40-bit (1 TB of memory / type )pointers would be fine in a 64-bit address space.

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.

googh3• 2 years ago

I would say that you want more than 32 bit pointers

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.

Rusky3• 2 years ago

Rust requires indices to express what can be expressed with just references in Java.

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.

Rust data structures with circular references (2021)

Related Stories