5 ms·

> Most of these data structures support in-place copy-on-write mutation, which means that if you're the sole user of a data structure, you can update it in plac

• masklinn 9y ago
  FWIW Clojure already has that concept as "transients" but it requires explicit invocation (creation of the transient then conversion back to persistent). I think Swift also commonly uses CoW but does so for regular collections not persistent ones.
  • millstone 9y ago
    What is the advantage of persistent collections over value-type collections?
    • karavelov 9y ago
      Structural sharing. It means you don't have to copy the whole data structure but just the path to the root.
      • millstone 9y ago
        I don't know - that sounds more like an implementation detail available to both. Obviously if you modify the first element of a value-type list, it's not going to copy the rest. Persistent data structures are really about the interface: functions that would be traditionally mutating instead return new versions. Is there an advantage of that interface over mutable value-type collections? One advantage is that it works better with e.g. folds. But overall I think it's more awkward.
        • elihu 9y ago
          It seems like it would be nice to just use the immutable interface and have it be mutable in the case that there's only one owner, but be able to fall back to immutability when you need it. It could make refactoring and debugging easier. For instance, let's say you're part way through some operation and it fails, and the error recovery logic is buggy and leaves the data structure in an inconsistent state. You could debug the problem, but if you're in a hurry and you just need something that works right now, you can store a reference to the data structure at the beginning of the operation and revert to that if anything goes wrong. You'd pay a performance cost since all the direct in-place edits would turn into copies and allocations, but it would at least work. Similarly, you could develop a program initially in an all-immutable multi-owner style, and then selectively convert codepaths to single-owner style to get better performance in the parts where performance matters.
          • kbsletten 9y ago
            This, of course requires tracking of owners. If you're on the JVM, that's not so cheap. If you're already tracking pointers or can do compiler-aided RAII like python, or c++ then it's relatively simple unless you also need recursive data structures which "own" themselves.
        • nine_k 9y ago
          Lack of defensive copying (widespread e.g. in Java) may alone be worth it, performance-wise. Also, shared data are much easier to reason about if it's immutable (not necessarily even in a concurrent execution context).
        • mookid11 9y ago
          The point is to share intermediate state of your data structure without headache. For instance, if you write an interpreter, representing variable bindings with a functional map allows to reason about scope super easily; when you change scope, you just create a new map with the new variable bindings, and when the scope ends you just get back the map at the scope beginning which is still valid. With a stateful hashtable, you need to undo the changes you did in you scope; the value of the table when opening the scope that you want to get back to is gone forever. Now it ties you program to a certain execution order. One way to see that is that if you want to collect environment to each scope in some data structure for some reason, you need to make deep copies everywhere.
• eridius 9y ago
  FWIW this is exactly what Swift does with all of its heap-allocated value types (e.g. Array, Dictionary, Set, String, etc).
  • sfrank 9y ago
    And what the OPAL functional language [1] did since the mid 80s. Though the concept there is expanded from simple reference counting by additional static analysis during compile time (making use of the functional semantics of the language) to avoid reference counting when for example the compiler can find/prove sequential increment/decrement counts, then the reference counting code is eliminated. [1] https://github.com/TU-Berlin/opal https://github.com/TU-Berlin/opal
• hinkley 9y ago
  That feels a bit like software transactional memory. I was wondering if someone would try that in Rust.
• jcelerier 9y ago
  > That's a really interesting approach. ... isn't this just basic copy-on-write ? that's something you learn to implement in first year of comp-sci. Old C++ types used to work like this - and some still do, for instance Qt's collection types are all COW.
  • kibwen 9y ago
    Rust actually provides a COW type in the stdlib for augmenting any of your types with such behavior: https://doc.rust-lang.org/std/borrow/enum.Cow.html https://doc.rust-lang.org/std/borrow/enum.Cow.html
  • nightcracker 9y ago
    No, this is a bit different. This is copy-on-write-unless-we're-alone-then-just-mutate-without-copy. That is, it's possible to write without copying if it has been determined that there are no other readers that would be referring to the old value (thus no copy is needed).
    • slavik81 9y ago
      That's exactly what the Qt collections do: > Implicit sharing automatically detaches the object from a shared block if the object is about to change and the reference count is greater than one. (This is often called copy-on-write or value semantics.) [source: http://doc.qt.io/qt-5/implicit-sharing.html http://doc.qt.io/qt-5/implicit-sharing.html] The C++ language is sometimes a little cruel, though. It's easy to accidentally call the mutable version of a function when the const version would have been sufficient. That can be a performance problem if it causes unnecessary copies.
    • pavanky 9y ago
      That is a natural extension of copy on write if you are keeping reference counts. I implemented something similar for a C++ library a couple of years ago.
    • barrkel 9y ago
      It's what Delphi has been doing with strings since 1995. It really is just copy on write, which normally has an assumption that the thing is shared before you copy. It's easily implemented with a refcount. It makes heap allocated types behave a lot like value types.
• Manishearth 9y ago
  Arc::make_mut is really nice and is something we use a bunch in Stylo to safely mutate possibly-shared styles. Across threads.
  • deleted 9y ago
    [deleted]
  • seeekr 9y ago
    But isn't it an anti-pattern to wrap something in an `Arc` when some of your use cases for it are purely single-threaded, and as such you're wasting a certain (potentially very significant) amount of performance on upholding memory visibility and such even when it's not needed? I have only dabbled in Rust, so I may be misunderstanding the implications of Arc and how it is implemented, and how it behaves in the absence of multiple threads. To me it feels a bit like some of the relatively early Java days when even the Standard Library was using `synchronized` (which is of course way worse than `Arc`) in lots of places like StringBuffer (used for String concatenation), just to be safe in case anyone ever wanted to use that code in a multi-threaded context. Only later folks began to realize that maybe that's not such a great idea and that you need to be able to not pay any synchronization costs when you know you're not going to be sharing a data structure across threads.
    • masklinn 9y ago
      These collections are of somewhat limited use outside of concurrent scenarios, and I don't think you can (currently?) be generic over allocation in Rust. Since these structures need some sort of automatic memory management for structural sharing, you need to use a GC of some sort, having both atomic and non-atomic Rc would require duplicating the entire thing, once with Rc nodes and one with Arc node, for more or less no value. > I may be misunderstanding the implications of Arc and how it is implemented, and how it behaves in the absence of multiple threads All Arc means is that refcounting operations use atomic increment/decrement instead of regular ones.
      • seeekr 9y ago
        So that means that the synchronization cost would only be paid when making a new copy of the Arc and releasing each of those. Ok, that extends the set of use cases where it's acceptable to use Arc then. Thanks for clarifying. EDIT: wording