6 ms·

”dynamically updated graphs are nearly impossible to write in Rust” Can you expand on this? I’ve taken only a cursory look on Rust and it’s not obvious to me w

• PaulHoule 3y ago
  You can fall back to https://doc.rust-lang.org/book/ch15-04-rc.html https://doc.rust-lang.org/book/ch15-04-rc.html for things that are too dynamic for borrow checking. Reference counting works great for the things it is good for but it does get into trouble with cycles and many of us would say that Java's memory allocator/garbage collector is worth what it costs. My opinion is that automated memory management is a key concept for software reuse and if you look at the problems of the C/C++ world this is pivotal. That is, the range of memory management relationships you might want between a library and its client is pretty wide, I mean sometimes you want a library to make its own buffers, other times you want to hand it an existing buffer, if it is building graphy structures it needs to allocate stuff, do you really want it to use malloc? do you want to pass it your own malloc? etc. The Java answer of providing a standard answer to allocation and garbage collection makes libraries composable with code in a way that Rust struggles with. (In the end rust libraries have to fall back to RC when complexity gets too high)
  • atemerev 3y ago
    You start with Rc, and you end with fn new<'a>(datum: &'static str, arena: &'a TypedArena<Node<'a>>) -> &'a Node<'a> (or Rc<RefCell<T>> and the like). (and basically implementing your own cycle-aware garbage collector, which again is not my idea of a good time).
  • fsloth 3y ago
    Ah, I see. IMO indices are a good way to implement all data structures, gc or no gc. I.e array for storage, indices for links. Referring the array via indices is not slower than following pointers.
    • rixed 3y ago
      Have you reimplemented malloc and free for your arrays yet?
      • fsloth 3y ago
        No, really, using arrays for internal storage of trees, graphs etc is much better from performance point of view. Among other things, allocations and finalizations are considerably faster. When a non-trivial payload is construed mostly of large linked structures where each element is malloced, using platform memory management may results in performance profile where over quarter of the run time is spent on malloc and free. Am not kidding. Of course you don't malloc anything. You do have "newNode" method or such that increments size. When size reaches capacity, you allocate a new larger array and copy data to it. When nodes "finalize", you store the index, and gc at the resize time (if you want to - there are lots of algorithms where you actually always only want to add data to the datastructure). Deep copy everything, you say? Hell yes, it's way way faster to have few large memory allocate/copy operations than a datastructures worth of node pointers. And if you don't care about performance, you probably shouldn't be using a systems programming language in the first place :D The above of course only makes sense if you have really large business critical datastructures - it's not an endorsement to rewrite every dictionary, set or a linked list. But the message to which I replied to was about "when writing your own datastructure".
      • cozzyd 3y ago
        I made basically the same joke (observation?) to another post, but it made me think, being able have a malloc where you can select one of many virtual memory regions probably would be a neat feature.
• itishappy 3y ago
  The borrow checker really does not like recursive structures. https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/
  • atemerev 3y ago
    And I really like recursion, I come from Scala and Common Lisp.