5 ms·

What kind of uses cases do people have for this? Since rust already pretty tightly controls mutability, my normal reasons for using immutable data structures do

What kind of uses cases do people have for this? Since rust already pretty tightly controls mutability, my normal reasons for using immutable data structures don't apply there.

vvanders 9y ago
That was one of the interesting side-effects of digging into Rust that I wasn't expecting. I find that I get the same level of "no mutation surprises" I commonly see in Elm/functional code but with the benefit of breaking out mutation when I need performance in a way that I don't normally shoot myself in the foot with. Having written C++ for quite a while it's really a refreshing feeling. Heck, I wish I had similar constrains available to me in Java for parts of an architecture that I know is going to be gnarly.
Groxx 9y ago
>Why Immutable Data Structures >... Rust, being what it is, does a good job of discouraging this kind of behaviour, and keeping it strictly controlled when it's necessary, but the standard library doesn't provide collection data structures which are optimised for immutable operations. This means, for instance, that if you want to add an item to a Vec without modifying it in place, you first need to clone the whole thing before making your change. >Data structures exist which are designed to be able to make these copies much cheaper, usually by sharing structure between them, which, because this structure is also immutable, is both cheap and safe. ... Seems pretty straightforward. You'll still have some benefits to immutable-data coding-patterns because it requires only read access on a value, not write, all the way up to the moment you want to swap values (if ever). Making that faster is a worthwhile goal.
- taeric 9y ago
  Seems misguided, though. Specifically, this has the implicit claim that the shared structures will be faster than the alternative. The whole "is both cheap and safe." However, Rust uses other mechanisms to provide the safety, such that it may be "cheaper," but only compared to copying the full data structure. It will not be cheaper than just modifying in place. The question, then, is how often is that strategy truly idiomatic and a net win in Rust?
  - steveklabnik 9y ago
    We had a talk at RustConf previously about the Xi editor; it uses an immutable data structure to handle text. It's a video but the author lays out the details here: https://www.youtube.com/watch?v=SKtQgFBRUvQ https://www.youtube.com/watch?v=SKtQgFBRUvQ They make an interesting argument about how Rust makes it easier and nicer to write these kinds of structures. It's still an area of exploration in Rust generally though; I wouldn't say immutable data structures are idiomatic, but that's also just because we haven't had a ton of easy ones to use, so nobody uses them. So we'll see!
    - taeric 9y ago
      I saw downthread a link to someone talking about how you can already treat the standard collections as values. Has a good argument for how it can be beneficial to keep the same interface regardless. Has a good concession that there are definitely use cases where persistent collections make sense. I'd imagine they are not as common as one could expect. (I grant they are also likely more common than I expect. :) )
    - raphlinus 9y ago
      Thanks for the shout-out. You can also read the docs[0] about the rope data structure (the release is a bit old, if you're really curious git master is better). I admit this is a fairly specialized use case, for most things xi uses mutability in a controlled way. [0] https://docs.rs/xi-rope/0.2.0/xi_rope/tree/index.html https://docs.rs/xi-rope/0.2.0/xi_rope/tree/index.html
  - cryptonector 9y ago
    With an immutable data structure the only synchronization cost is that of atomic reference count increment/decrement, but it feels like you're mutating shared objects, so the API is very easy to use. For an example API I'm familiar with, see https://github.com/stedolan/jq/wiki/C-API:-jv https://github.com/stedolan/jq/wiki/C-API:-jv
- winstonewert 9y ago
  Ok, but I repeat: what is the use case? Yes, this allows me to do things like add an item to a Vec without modifying it in place, but why would I want to do that? What's the situation where that's helpful? In other languages I do that, specifically to avoid mutability hell, but that doesn't apply to rust. EDIT: Thanks to the responders for the great examples!
  - masklinn 9y ago
    > Yes, this allows me to do things like add an item to a Vec without modifying it in place, but why would I want to do that? What's the situation where that's helpful? The context is obviously shared concurrency (hence the library using Arc period), so you can cheaply get a shared immutable structure and manipulate it on your side (without sharing it back), and if necessary share/swap it in at some point, they provide cheap read/copy/update cycles. With regular collections Rust would preclude misuses but that would still require either deep copies upfront or fairly large exclusive critical sections.
  - the8472 9y ago
    It might be useful for RCU data structures in multithreaded code
    - cryptonector 9y ago
      Absolutely. This is one very good use case. Say you have a configuration to read and share with all threads. Each thread can make local changes that will not be visible to the others. The API looks like it's mutating the shared object, but it's actually mutating a copy.
  - caconym_ 9y ago
    One example: storing a large text buffer in a persistent data structure (e.g. a rope) can allow you to maintain a space-efficient history of "snapshots" simply by keeping pointers to older versions of the buffer.
  - Groxx 9y ago
    No ability to mutate -> no mutable ownership complications. Ever. And that's probably the biggest pain-point for people using Rust. Not necessary, but can simplify things, by encouraging(/forcing) simpler use of data by default.
cryptonector 9y ago
If this is at all like jq's libjq's jv API [0], then this it will be great. The C-coded jv API gives you immutable JSON-ish data structures, with the illusion (and sometimes truth) that they are actually mutable. For example, say you have jv foo(jv a) { return jv_array_append(a, jv_string("foo")); } Here `jv_array_append()` looks like it must mutate `a`. What actually happens under the covers is that if `a` has just one reference, then indeed, `a` will be mutated, but if it has more than one reference then a new array will be constructed as a copy of `a`, `a`'s reference count will be decremented, the copy will be mutated, and lastly the copy will be returned. This might make it a bit clearer: jv a = jv_array(); a = jv_array_append(a, jv_true()); a = jv_array_append(a, jv_false()); a = jv_array_append(a, jv_null()); Each assignment to `a` here can be a brand new array, though since in this code snippet `a` will always have just one reference, in fact `a` will always be mutated. Now, look at this: jv a = JV_ARRAY(jv_true(), jv_false(), jv_null()); set_thingy(jv_copy(a)); a = jv_array_append(a, jv_number(10)); here at the third line `a` might have two references, depending on what `set_thingy()` might have done with its reference. Perhaps `set_thingy()` saved its reference in a global or thread-local variable, or some object reachable from a global or thread-local variable, in which case the last call to `jv_array_append()` in this example will produce a brand new array. See the jq jv wiki[1]. Now, this is all C. But in Rust all of this would be even more powerful. [0] https://github.com/stedolan/jq/blob/master/src/jv.h https://github.com/stedolan/jq/blob/master/src/jv.h [1] https://github.com/stedolan/jq/wiki/C-API:-jv https://github.com/stedolan/jq/wiki/C-API:-jv
Tarean 9y ago
Immutable strucutres allow you to sharing or keeping multiple versions. For instance moddeling gamestate as an immutable tree so the ai can cheaply try different options. Also sometimes it's still simpler. Exception handling on windows uses a thread local immutable linked list of handlers.
elihu 9y ago
Immutability can be nice when writing server logic. Suppose all you data structures are immutable and the only mutable state you have is a pointer to the root of your immutable data structures. To create a new state, you build a new state by allocating what you have to and using pointers into the old state for those things that haven't changed, and then you update the pointer to point at the new state. Depending on the data structures used, updating state could require a lot of allocations. However, there are a couple really compelling benefits. Error handling is very easy because you can bail out at any point before swapping pointers and the server state remains unaffected. Also, readers can continue to read the old state without being blocked by writers -- basically, all reader threads can just go right in and read the state with no locking at all. I've used this approach before in Haskell and it seemed to work pretty well. I used the lens library to make data structure updates easier (syntactically, they look a lot like the sort of data structure updates you'd make in an imperative language, except that they do a copy-on-write behind the scenes), and also paired it with the acid-state library to make the Haskell data structures persistent across application restarts.
blaisio 9y ago
So honestly they probably do. This is useful whenever you want to share and optionally modify some data (especially if it's large). Eg. in a multi-threaded video game, for each frame, you probably have some big block of state, which some threads will mutate. Instead of making a copy of the data for every thread, you could pass around a big immutable data structure and only make copies when writing. Each thread can own their own data, so there won't be lock contention, and when all the threads are done, a quick merge operation can recombine the modified pieces back into a single block of state for the next frame.
Karliss 9y ago
I don't see anyone mentioning here is that properly implemented persistent data structures where the increase in space is low and predictable can be used to efficiently store and query the history of data structure's state. One example is querying which polygon from known set contains a point. If all the points are known it can be done using regular sweep line algorithm. Using a persistent ordered tree instead of normal one allows storing it's state over the sweeping process, that removes requirement of knowing all the points at the start. After performing sweeping using persistent data structure query any point can be answered in O(log(n)) time. Similar technique can be applied to convert other offline algorithms that rely on sorting all the data to partially online (queries can be answered one by one without knowing all of them).

What kind of uses cases do people have for this? Since rust already pretty tightly controls mutability, my normal reasons for using immutable data structures don't apply there.

vvanders 9y ago

That was one of the interesting side-effects of digging into Rust that I wasn't expecting. I find that I get the same level of "no mutation surprises" I commonly see in Elm/functional code but with the benefit of breaking out mutation when I need performance in a way that I don't normally shoot myself in the foot with. Having written C++ for quite a while it's really a refreshing feeling. Heck, I wish I had similar constrains available to me in Java for parts of an architecture that I know is going to be gnarly.

Groxx 9y ago

>Why Immutable Data Structures >... Rust, being what it is, does a good job of discouraging this kind of behaviour, and keeping it strictly controlled when it's necessary, but the standard library doesn't provide collection data structures which are optimised for immutable operations. This means, for instance, that if you want to add an item to a Vec without modifying it in place, you first need to clone the whole thing before making your change. >Data structures exist which are designed to be able to make these copies much cheaper, usually by sharing structure between them, which, because this structure is also immutable, is both cheap and safe. ... Seems pretty straightforward. You'll still have some benefits to immutable-data coding-patterns because it requires only read access on a value, not write, all the way up to the moment you want to swap values (if ever). Making that faster is a worthwhile goal.

taeric 9y ago
Seems misguided, though. Specifically, this has the implicit claim that the shared structures will be faster than the alternative. The whole "is both cheap and safe." However, Rust uses other mechanisms to provide the safety, such that it may be "cheaper," but only compared to copying the full data structure. It will not be cheaper than just modifying in place. The question, then, is how often is that strategy truly idiomatic and a net win in Rust?
- steveklabnik 9y ago
  We had a talk at RustConf previously about the Xi editor; it uses an immutable data structure to handle text. It's a video but the author lays out the details here: https://www.youtube.com/watch?v=SKtQgFBRUvQ https://www.youtube.com/watch?v=SKtQgFBRUvQ They make an interesting argument about how Rust makes it easier and nicer to write these kinds of structures. It's still an area of exploration in Rust generally though; I wouldn't say immutable data structures are idiomatic, but that's also just because we haven't had a ton of easy ones to use, so nobody uses them. So we'll see!
  - taeric 9y ago
    I saw downthread a link to someone talking about how you can already treat the standard collections as values. Has a good argument for how it can be beneficial to keep the same interface regardless. Has a good concession that there are definitely use cases where persistent collections make sense. I'd imagine they are not as common as one could expect. (I grant they are also likely more common than I expect. :) )
  - raphlinus 9y ago
    Thanks for the shout-out. You can also read the docs[0] about the rope data structure (the release is a bit old, if you're really curious git master is better). I admit this is a fairly specialized use case, for most things xi uses mutability in a controlled way. [0] https://docs.rs/xi-rope/0.2.0/xi_rope/tree/index.html https://docs.rs/xi-rope/0.2.0/xi_rope/tree/index.html
- cryptonector 9y ago
  With an immutable data structure the only synchronization cost is that of atomic reference count increment/decrement, but it feels like you're mutating shared objects, so the API is very easy to use. For an example API I'm familiar with, see https://github.com/stedolan/jq/wiki/C-API:-jv https://github.com/stedolan/jq/wiki/C-API:-jv
winstonewert 9y ago
Ok, but I repeat: what is the use case? Yes, this allows me to do things like add an item to a Vec without modifying it in place, but why would I want to do that? What's the situation where that's helpful? In other languages I do that, specifically to avoid mutability hell, but that doesn't apply to rust. EDIT: Thanks to the responders for the great examples!
- masklinn 9y ago
  > Yes, this allows me to do things like add an item to a Vec without modifying it in place, but why would I want to do that? What's the situation where that's helpful? The context is obviously shared concurrency (hence the library using Arc period), so you can cheaply get a shared immutable structure and manipulate it on your side (without sharing it back), and if necessary share/swap it in at some point, they provide cheap read/copy/update cycles. With regular collections Rust would preclude misuses but that would still require either deep copies upfront or fairly large exclusive critical sections.
- the8472 9y ago
  It might be useful for RCU data structures in multithreaded code
  - cryptonector 9y ago
    Absolutely. This is one very good use case. Say you have a configuration to read and share with all threads. Each thread can make local changes that will not be visible to the others. The API looks like it's mutating the shared object, but it's actually mutating a copy.
- caconym_ 9y ago
  One example: storing a large text buffer in a persistent data structure (e.g. a rope) can allow you to maintain a space-efficient history of "snapshots" simply by keeping pointers to older versions of the buffer.
- Groxx 9y ago
  No ability to mutate -> no mutable ownership complications. Ever. And that's probably the biggest pain-point for people using Rust. Not necessary, but can simplify things, by encouraging(/forcing) simpler use of data by default.

cryptonector 9y ago

If this is at all like jq's libjq's jv API [0], then this it will be great. The C-coded jv API gives you immutable JSON-ish data structures, with the illusion (and sometimes truth) that they are actually mutable. For example, say you have jv foo(jv a) { return jv_array_append(a, jv_string("foo")); } Here `jv_array_append()` looks like it must mutate `a`. What actually happens under the covers is that if `a` has just one reference, then indeed, `a` will be mutated, but if it has more than one reference then a new array will be constructed as a copy of `a`, `a`'s reference count will be decremented, the copy will be mutated, and lastly the copy will be returned. This might make it a bit clearer: jv a = jv_array(); a = jv_array_append(a, jv_true()); a = jv_array_append(a, jv_false()); a = jv_array_append(a, jv_null()); Each assignment to `a` here can be a brand new array, though since in this code snippet `a` will always have just one reference, in fact `a` will always be mutated. Now, look at this: jv a = JV_ARRAY(jv_true(), jv_false(), jv_null()); set_thingy(jv_copy(a)); a = jv_array_append(a, jv_number(10)); here at the third line `a` might have two references, depending on what `set_thingy()` might have done with its reference. Perhaps `set_thingy()` saved its reference in a global or thread-local variable, or some object reachable from a global or thread-local variable, in which case the last call to `jv_array_append()` in this example will produce a brand new array. See the jq jv wiki[1]. Now, this is all C. But in Rust all of this would be even more powerful. [0] https://github.com/stedolan/jq/blob/master/src/jv.h https://github.com/stedolan/jq/blob/master/src/jv.h [1] https://github.com/stedolan/jq/wiki/C-API:-jv https://github.com/stedolan/jq/wiki/C-API:-jv

Tarean 9y ago

Immutable strucutres allow you to sharing or keeping multiple versions. For instance moddeling gamestate as an immutable tree so the ai can cheaply try different options. Also sometimes it's still simpler. Exception handling on windows uses a thread local immutable linked list of handlers.

elihu 9y ago

Immutability can be nice when writing server logic. Suppose all you data structures are immutable and the only mutable state you have is a pointer to the root of your immutable data structures. To create a new state, you build a new state by allocating what you have to and using pointers into the old state for those things that haven't changed, and then you update the pointer to point at the new state. Depending on the data structures used, updating state could require a lot of allocations. However, there are a couple really compelling benefits. Error handling is very easy because you can bail out at any point before swapping pointers and the server state remains unaffected. Also, readers can continue to read the old state without being blocked by writers -- basically, all reader threads can just go right in and read the state with no locking at all. I've used this approach before in Haskell and it seemed to work pretty well. I used the lens library to make data structure updates easier (syntactically, they look a lot like the sort of data structure updates you'd make in an imperative language, except that they do a copy-on-write behind the scenes), and also paired it with the acid-state library to make the Haskell data structures persistent across application restarts.

blaisio 9y ago

So honestly they probably do. This is useful whenever you want to share and optionally modify some data (especially if it's large). Eg. in a multi-threaded video game, for each frame, you probably have some big block of state, which some threads will mutate. Instead of making a copy of the data for every thread, you could pass around a big immutable data structure and only make copies when writing. Each thread can own their own data, so there won't be lock contention, and when all the threads are done, a quick merge operation can recombine the modified pieces back into a single block of state for the next frame.

Karliss 9y ago

I don't see anyone mentioning here is that properly implemented persistent data structures where the increase in space is low and predictable can be used to efficiently store and query the history of data structure's state. One example is querying which polygon from known set contains a point. If all the points are known it can be done using regular sweep line algorithm. Using a persistent ordered tree instead of normal one allows storing it's state over the sweeping process, that removes requirement of knowing all the points at the start. After performing sweeping using persistent data structure query any point can be answered in O(log(n)) time. Similar technique can be applied to convert other offline algorithms that rely on sorting all the data to partially online (queries can be answered one by one without knowing all of them).