9 ms·
Rust data structures with circular references (2021)
- LAC-Tech 3y agoRaw 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.
- gumby 3y agoUnfortunately, despite all that effort, deletion leaks memory.
- deleted 3y ago[deleted]
- rjeli 3y agoFirst, 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
- deleted 3y ago[deleted]
- agalunar 3y agoUsing 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.)
- taeric 3y agoIt is hilarious how much space you can save by using smaller indexes than a pointer. Especially on modern architectures.
- burntsushi 3y agoYes! The regex crate does this and it saves quite a bit of memory.
- taeric 3y agoIt is the kind of low hanging optimization that I used to think was greatly oversold. And, to be fair, for many programs I would still wager it probably is. If you are chasing a ton of pointers, though, it is definitely worth considering how many more you can hold in memory with smaller sizes. 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
- eclark 3y agoI am currently writing a CFR Tree that has nodes that can be self-referential. https://github.com/elliottneilclark/rs-poker/pull/92 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).
- deleted 3y ago[deleted]
- 10000truths 3y agoThe 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 3y agoThe 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 3y agoThe 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.
- alexchamberlain 3y agoArray bounds are essentially unchecked in C, unless you go so far over as to hit a guard page.
- empath-nirvana 3y agoYou can have bugs with that style of coding, but they're not going to be bugs of the "remote code execution" type.
- googh 3y agoIf 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/deluge/Manifesto.md https://github.com/pizlonator/llvm-project-deluge/blob/delug...
- burntsushi 3y 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/ https://github.com/BurntSushi/rsc-regexp/
- Chabsff 3y 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.
- tialaramex 3y agoThere's a big cultural problem and there are several big technical problems. 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.
- akavel 3y agoThere'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.
- kelnos 3y agoThere's a big difference, though: the array indexing code is still safe from memory errors. I would much prefer a panic over a segfault.
- alilleybrinker 3y agoAlways 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/ https://rust-unofficial.github.io/too-many-lists/
- keybored 3y agoThe writing style is also fun IMO.
- alilleybrinker 3y agoOh yeah Aria’s writing is excellent. https://faultlore.com/blah/ https://faultlore.com/blah/
- deleted 3y ago[deleted]
- smasher164 3y agoAnother approach is to use a Gc<T> smart pointer: https://docs.rs/gc/latest/gc/ https://docs.rs/gc/latest/gc/ I've used this in an interpreter and it's quite convenient.
- foldr 3y agoNice! This seems way more appealing than every other approach I've seen in this domain.
- celeritascelery 3y agoThat 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 https://docs.rs/gc/0.5.0/src/gc/lib.rs.html#495-498
- paholg 3y agoNote: the two of you are linking to different crates. Samsara provides a Gc type, but it is not the gc crate.
- celeritascelery 3y agoIt looks like you intended to say that on the sibling comment.
- paholg 3y agoYep! Sorry.
- rendaw 3y agoIt 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.
- zozbot234 3y agoYes, 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 https://github.com/chc4/samsara Samsara.
- kldx 3y agohttps://plv.mpi-sws.org/rustbelt/ghostcell/ 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.
- worik 3y 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
- pizlonator 3y agoSome algorithms need the parent or bidirectional pointers. If the language doesn’t let you then the language sucks.
- empath-nirvana 3y agoThis 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.
- alexchamberlain 3y ago> you can isolate that dangerous code to one part of your code base. 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.
- hinkley 3y agoI suspect there's a type theory here where many cases of parent links essentially represent the exact same problem, and if you solve one, you can restate most/all of the others in this form and then it's proven too. 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.
- dmitrygr 3y ago[flagged]
- anon291 3y agoRealistically, other than cool factor I'm having a real hard justifying the use of rust. It either devolves into using reference counting (fine but we have lots of languages that do that without borrow checking), or dynamics (i.e refcell). The type system is nice with the algebraic data types, but lacking the higher orderedness of languages like Haskell, it just seems sad. So basically, to me it seems like you're getting the worst of both worlds. You don't get the freedom of c/c++ and you don't get the actual type safety of a language like Haskell (refcell kills the notion of compile time checking). Realistically what needs to happen is some system for circular references like Haskell has (let bindings).
- empath-nirvana 3y agoThere's so much you can do in rust without messing with any of that, and the only time you have to get deep in the weeds arguing with the compiler is _exactly_ the sort of code that you _should_ be spending a lot of time carefully thinking about. That C allows you to write that code without thinking about it much is _not_ a benefit to using C.
- anon291 3y agoComing from a mostly Haskell background, I assure you I think about my code a lot.
- jeremyjh 3y agoI don't see what let bindings have to do with solving the circular reference problem, those are just local bindings. A Haskell doubly-linked list would use IORef, but no one would ever actually do that.
- anon291 3y agoHaskell doubly linked list: data DLList a = DLList a (DLList a) (DLList a) | End make_dllist :: [a] -> DLList a make_dllist = go (\_ -> End) where go mkPrev [] = mkPrev End go mkPrev (x:xs) = go (\next -> let me = DLList x (mkPrev me) next in me) xs No need for IORef. Too many people misunderstand the meaning of 'let' in Haskell. It doesn't mean what you think it does. It defines, not assigns. In rust, let 'declares' and assigns in one go. It does not define.
- theLiminator 3y agoCurious if you could implement the tree with qcell or ghostcell for zero runtime cost and having compile time safety?
- aidenn0 3y agoIsn't raw pointers only needed for the parent reference, not all references?
- pizlonator 3y agoThe 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.
- keybored 3y agoFrustrating for who?[1] 99% of Rust users have likely used languages that use GC. [1] Trying to wean myself off the archaic “whom”.
- pjmlp 3y agoWhich kind of GC though.
- pvg 3y agooff 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.
- keybored 3y agoPerfect :)
- _se 3y agoThe 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.
- deleted 3y ago[deleted]
- dang 3y agoRelated: Rust data structures with circular references - https://news.ycombinator.com/item?id=29207397 https://news.ycombinator.com/item?id=29207397 - Nov 2021 (42 comments)
- hgs3 3y agoThis 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 3y agoYour comment is about rust, but not at all related to the article.
- hgs3 3y agoThe "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 https://news.ycombinator.com/item?id=32907482
- pvg 3y agofocus of the article 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."
- 3y ago
- pkulak 3y agoThis 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 3y agoHonestly 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 3y agoI 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.
- hinkley 3y agoTo 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.
- zozbot234 3y 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 3y 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 3y agoAdding 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 3y agoInteresting 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 3y agoStoring 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.
- googh 3y agoThere 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/deluge/Manifesto.md https://github.com/pizlonator/llvm-project-deluge/blob/delug...
- Rusky 3y 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.
- cozzyd 3y agoThis 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.