12 ms·

I tried Rust about five years ago and I had trouble expressing cyclic data structures because there is no clear "owner" in a cyclic data structure. The "safe" s

• gernb 4y ago
  That's a very good point. A pointer dereferences its object, an index does not. So arguably having to switch from pointers to integers is going be a net drag on debugging since it will be no trivial to see what objects are being referenced.
• Fiahil 4y ago
  > The "safe" solution recommended by the rustaceans was to use integers as references to the data in a vec or hashmap. What ? Box, Arc (and weak) are exactly made for this.
  • ajross 4y ago
    Box doesn't solve the problem of cyclic references. And telling people they need to eat the overhead of a per-object reference count and/or weak pointer double-dereference just to write a list that can delete items in place is a pretty tall order for a language that claims to be high performance. No, this is genuinely a big hole in the expressive space of the language. Not a lot of apps really need to do a ton of manual pointer work implementing non-trivial data structures, but some do, and it kinda sucks in Rust.
    • Fiahil 4y ago
      As other pointed out, if Arc is not an option, then a well encapsulated raw pointer might just be what's needed. I've implemented several of such data structures, there is not that many tradeoffs available : safe and easy, or unsafe and fast. The unsafe parts are still much better than raw C. I don't agree that the language and ecosystem is missing a "big piece". Everything is already there.
    • ModernMech 4y ago
      > a pretty tall order for a language that claims to be high performance. Doing this in Rust is still going to be orders of magnitude faster than many other languages. Maybe not C/C++, but then again if you’re chasing pointers in a list maybe squeezing every ounce of performance you can isn’t the #1 priority for the given application. The industry consensus is shifting to the idea that being #1 in security at the expense of being #2 or #3 in performance is a fine trade off.
      • ajross 4y ago
        > The industry consensus is shifting to the idea that being #1 in security at the expense of being #2 or #3 in performance is a fine trade off. Is it? That's where Java was 20 years ago.
• dralley 4y ago
  Juggling (raw) pointers is still an option in Rust, just not the most idiomatic one. But you're right that expressing cyclic data structures is very challenging to do idiomatically in Rust. Using integer handles as pointer replacements does have some universal benefits though outside of Rust. You can make them more compact, they serialize more easily, etc.
• woodruffw 4y ago
  If the last time you tried it was 5 years ago, then you probably didn't experience Rust with non-lexical lifetimes. That was added in around 2018 (IIRC), and radically increased the number of programs that the borrow checker accepted. That being said, you still can't do "naive" cyclical data structures without some additional assistance. But the ecosystem has matured around that: crates like ouroboros[1] provide safe interfaces for creating self-referential structures and datatypes. Edit: NLL was indeed added in the 2018 Edition[2]. [1]: https://docs.rs/ouroboros/latest/ouroboros/ https://docs.rs/ouroboros/latest/ouroboros/ [2]: https://blog.rust-lang.org/2018/12/06/Rust-1.31-and-rust-2018.html#non-lexical-lifetimes https://blog.rust-lang.org/2018/12/06/Rust-1.31-and-rust-201...
  • ChadNauseam 4y ago
    Ghost-cell [0] also lets you create a doubly-linked lists (without you having to use unsafe code, and with no overhead) [0]: https://crates.io/crates/ghost-cell https://crates.io/crates/ghost-cell
    • xavxav 4y ago
      Yea but it’s not really useable in practice as it heavily relies on nesting allocations in closures to simulate “generative lifetimes”. It’s a research artifact, not meant for serious usage. Instead, I would recommend using something like https://crates.io/crates/qcell https://crates.io/crates/qcell, which works on similar principles.
• ajross 4y ago
  That's my take too. Idiomatic Rust is "safe" in the sense that... it disallows most nontrivial data structures. Even a doubly-linked list is impossible to get through the borrow checker. That's... not really that fatal. There's a lot of very useful code that can be written using only runtime-provided[1] containers and straightforward ownership trees. But obviously the big problem is that for applications that do need to do non-trivial reference semantics, Rust doesn't really offer much. Applications with nonstandard allocator paradigms or weak-referenced caches or that need to do complicated graph management are mostly on their own in the world of unsafe. And the somewhat more cynical point is: for applications that can easily fit within standard containers and standard allocation paradigms, C++ actually works really well already. Use your smart pointers. Use your containers. Follow the rules everyone tells you about not using bare new/malloc. And... it's basically just as safe, because anything beyond that would be unsafe in Rust too. I don't dislike Rust, really. But the space between "Need to stay away from C++" and "Should probably just have written it in Go" seems to be getting smaller and not larger. [1] Which in Rust, means "written using a ton of unsafe blocks".
  • junofan 4y ago
    Agreed, having touched browser development circa Rust’s invention, I think there are some good ideas, but the execution fell flat over the years, orthogonality broke, and thus the utility is kind of limited. I’m more excited about some newer languages to be honest.
  • noobermin 4y ago
    Random question, doesn't this then defeat the whole purpose of using rust? Memory errors, that is, pointer issues are the primary source of errors that ownership in rust claims to fix. If the only way you can make nontrivial data structures is use "a ton of unsafe blocks," then you'll still likely get the memory errors, only now it's in an unsafe block...so, now everyone can just blame the unsafe block? This reminds me of those static provers which prove everything correct up until user input, you know, the place where an attacker will inject their payload.
    • stjohnswarts 4y ago
• stouset 4y ago
  Seriously, just use unsafe. “Welp, can’t write a doubly-linked list in safe Rust so I might as well use C” is throwing the baby, the bathtub, and the rest of the greater metro area out with the bathwater.
  • chongli 4y ago
    Sorry to stretch the analogy beyond recognition but a lot of people who would prefer C over Rust want to build a bathtub for the baby without dragging the rest of the greater metro area into the picture.
    • stouset 4y ago
      Yeah, and a ton of people still complain about having to put their seat belt on in the car too.
      • chongli 4y ago
        No, the point is that Rust does not replace C. At best, it’s “safe C++” (and even that’s debatable, given the cyclic references issue discussed here). But for the use cases where even C++ is too much, there is no replacement for C. Zig aspires to be that minimal language. It seems to have a lot of really good ideas. It’s too bad the compiler is so opinionated that a lot of developers will be alienated by it.
        • stouset 4y ago
          > No, the point is that Rust does not replace C. At best, it’s “safe C++”. This is a meaningless distinction. No language in the history of languages has ever strictly "replaced" another. Over time Rust will eat into the market share of every language to differing amounts. C and C++ top the list of languages that Rust will likely eat into the most, but of course they will still continue to exist and people will find reasons to continue using them. > But for the use cases where even C++ is too much, there is no replacement for C. Rust is a significantly less complicated language than C++. But what does this even mean, anyway? Whose use-case is "A systems programming language, but the spec can only be so many pages long?" > (and even that’s debatable, given the cyclic references issue discussed here) struct Node<T> { data: T, left: *mut Node<T>, right: *mut Node<T>, parent: *mut Node<T>, } Wow, so difficult! If the comparison is C, I don't even have to bother writing a safe abstraction around this.
• gpm 4y ago
  The borrow checker has become smarter, but not at handling cyclic data structures. The problem you're describing still exists, though I'd say the advice isn't quite right. Generally the better advice is to use a graph library, or something like slotmap [1] if you're rolling your own, than to use a Vec or HashMap. That's superior to a vec/hashmap for a few reasons. It handles keeping indicies stable/writing your own index allocator. It also makes it possible with a feature flag to detect all use after frees at low-ish cost (instead of only detecting them if no-one is re-using the slot). It makes it convenient to use typed keys instead of integers. The underlying datastructure is basically the same though. You can also use Rc/Weak for cyclic data, for ref counting "GC", it's an approach I have less experience with so I can't speak towards it as well. In the end not that much data is cyclic (especially in idiomatic rust), and this is trading off a small amount of debugging convenience on cyclic data, for guarantees of memory handling correctness in the rest of your code, and for guarantees about the amount of damage that mistakes can do in the code that does need to handle cyclic data (which in turn is a debugging win on cyclic data, so...). I agree it's a bit of a rough edge, but it's a case where rust solved the easy 95% of the problem with only slightly questionable tradeoffs on the remaining 5%, and that's a win in my book. [1] https://crates.io/crates/slotmap https://crates.io/crates/slotmap
  • lenkite 4y ago
    Stuff like Slotmap should be part of the standard library instead of some github project with open issues that isn't updated for over a year.
    • gpm 4y ago
      I just glanced through the small number of open issues, and none seem like actual issues so much as potential improvements. The maintainer seems to still be around, and I've never found that a standard library is faster at merging improvements than third party libraries, rather the exact opposite (for good reason, the standard library needs to avoid breaking changes at nearly all costs). While I think there are valid arguments in both directions for putting more things like this in std, I don't think "non-bug issues have been open for over a year" is one of them. The exact same is true of std.
• adamnemecek 4y ago
  Use generational arenas.
• jupp0r 4y ago
  It's intentionally limiting. If you need an owner, create one (call it a graph struct that holds all you nodes for example). Make lifetime management an explicit and separate concern and unit test it independently. If this is too slow for your performance needs use a library that probably uses unsafe Rust to optimize the parts that matter and that offers safe abstractions for you to interact with. If there's none, roll your own. Be happy that not everybody is slinging dangling pointers all over the place in code where it's really unnecessary.
  • Noe2097 4y ago
    Was about to write this exactly. Keep the lifecycle management in a dedicated component. Unsafe seems vastly overkill for dealing with this use case. I'm even having a hard time seeing how this could be slower than any other alternative. Yes, in the places where creating / deleting is necessary, the "root" structure will have to be passed around, but in the worst case that has the cost of adding one argument to a function (which has the nice side effect of making the lifecycle _visible_).
• laserbeam 4y ago
  Using integers instead of pointers is a cool optimization outside of Rust as well. It lets you serialize data easier (indices are the same when you load data on a different machine, pointers will change) and can use less memory (common choices: 8, 16 or 32 bits per int; 32 or 64 bits per pointer). This is, however, an optimization. I rarely write my code like that on the first pass. It's something I always have in mind that at some point it's worth replacing the pointers. (This is not specific to rust, or any other language)
  • alpaca128 4y ago
    While that is true, using integers as pointers in Rust just makes them invisible to the borrow checker. It's a useful trick but one should be aware this is basically unmarked unsafe code. Though in Rust it has another advantage over pointers: it doesn't force you to suddenly annotate every single type that touches your data structure in any way.
    • ptato 4y ago
      There's nothing unsafe about integer indices because access to the array they index will incur bounds checks.
      • HelloNurse 4y ago
        This means that you have array accesses that cause index out of bounds fatal errors instead of invalid pointer dereferencing that causes fatal segmentation failure errors. Detecting this kind of bugs reliably is a very good thing, but preventing such errors (and optimizing away bounds checking if possible) would be better.
        • halvnykterist 4y ago
          Invalid pointer dereferencing isn't guaranteed to cause segfaults, you might just get garbage memory or nasal demons from LLVM handling undefined behavior. That's the key advantage of using integers (or a GC'd language) - it's memory safe.
• jandrewrogers 4y ago
  In fairness, using integer handles instead of pointers is pretty idiomatic in high-performance C++ too. I've never found it to be onerous or complicated.
  • fsloth 4y ago
    Yes, using integers is not a handicap in many cases but default way of addressing.
    • gerbs 4y ago
      Hey, I'm a college student majoring in Physics and wanted to ask for your email. A lot of my interests mirror yours and I want some guidance from someone who has experience with them. I know this is out of the blue, but I really want to get in contact with you. Thanks.
  • cygx 4y ago
    Sure. But the selling point of Rust is that the compiler will check ownership and lifetimes for you. That goes away if you use integer handles, in which case I might as well use another language.
    • karmakurtisaani 4y ago
      I'm not sure if that's true. The data still has an owner and when the owner goes out of scope the memory should be freed. Without the concept of ownership you might end up leaking that memory. I could be wrong, but I think that's how it goes.
• ohgodplsno 4y ago
  Unsafe is literally made for that. For cases when your wants can only be checked by your brain saying "I did the logic and it's all good". Ten lines of unsafe does not mean your program will blow up. If anything, it's here to encourage you to just be much more careful here.
  • resonious 4y ago
    Right, you don't have to be a purist to get safety benefits from Rust. If a Rust program is 1% "unsafe" code, it still has a far lower vulnerable surface area than an equivalent C program.
• worik 4y ago
  > I had trouble expressing cyclic data structures You cannot do cyclic data structures in Rust because every thing must have one owner, so no cycles. You can do cyclic data structures in Rust with unsafe code or doing your own memory management (e.g. an arena data structure). > The borrow checker worked fine when all I needed to do was pass data up and down the callstack, but anything beyond that was difficult or impossible to express That is not true. It is true at the start of the learning curve, but you get used to it. Cyclic data structures are very far from simple.
  • bobbylarrybobby 4y ago
    The data held by an Rc doesn't have one owner. It would probably be pretty painstaking to do cyclic data structures with them correctly, differentiating between strong and weak Rc as appropriate, but probably doable. If you don't care about leaking memory, or if the graph is static, you don't even need to worry about that.
• baq 4y ago
  Cyclical data structures are difficult to reason about, full stop - not only for the borrow checker. Unsafe is there if you need it. It gives you C pointers for everyone and their debugger to blow up on. The difference is Rust makes you painfully aware that CS 101 is actually hardcore engineering.
  • deleted 4y ago
    [deleted]
• 3836293648 4y ago
  The answer today is to use a GhostCell
• pizza234 4y ago
  > The "safe" solution recommended by the rustaceans was to use integers as references to the data in a vec or hashmap This is not correct advice; not sure why you've been given this answer. There are a couple of solutions. 1. you use a data structure (library) that returns you a handler, which can be an int, but it's not an int as in "position inside a vec" (index), but a symbolic reference, whose management is deferred to the library. You can't use an index directly because if a position is freed, then taken, you will hold an invalid reference (int). This is a handy solution, convenient to work with; if you do something wrong, you'll get an error from the library. 2. the manual solution is to use strong/weak references, which are quite ugly to use :)
• eliben 4y ago
  I ran into the exact same problem and wrote up some potential solutions at https://eli.thegreenplace.net/2021/rust-data-structures-with-circular-references/ https://eli.thegreenplace.net/2021/rust-data-structures-with...
• Narann 4y ago
  unsafe is the feature you need.