9 ms·

Immutable-cpp: persistent immutable data structures for C++

42 points by jiyinyiyong 10y ago

hyperbovine 10y ago
Sorry, I am lost: why is this a big deal? I use std::array and it's fine.
- eyelidlessness 10y ago
  Immutability makes reasoning with state and concurrency much easier. Persistent data structures help make immutability practical in terms of performance and memory overhead.
- deleted 10y ago
  [deleted]
- akubera 10y ago
  Their Array class is perhaps unfortunately named, as it behaves as a vector or list (i.e. you can push things to the collection) rather than fixed size memory block. The important thing to notice in their example is the assignment to 'a' when pushing items (`a = a->push(1);`), and the ability to reassign the new change to a new variable (`auto b = a->push(4);`). That last command keeps 'a' the same (hence "immutable" data structure), but creates a new variable 'b' to hold the new data. This technique allows you to, for example, pass the same data structure to multiple threads without worrying that they will simultaneously change data (race conditions). More information can be found here https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure (check out the linked list and tree diagrams in examples). For this to work properly in C++, I think you'd need to const all types for it to be effective (immutable::Array<const MyStruct>). I'd really like to see benchmarks comparing these structures implemented in C++ vs those in functional languages; I don't know if the compiler optimization algorithms produce similar code.
  - mmierz 10y ago
    Naive question: even so, what's the advantage over using, say, a const std::array<MyStruct>?
    - iofj 10y ago
      Well, when you pass a variable around, it doesn't and cannot change. This means that different threads can't get in eachothers' way anymore, for instance, but also that you can't make a big chunk of mistakes at all. They also have serious disadvantages : they can't be memory managed in the traditional way (since they tend to reuse other instances' memory in complex ways), and thus require a GC (refcounting can work, but ...). They are VERY allocation intensive, and they are worse than most non-persistent data structures. Assuming an O(1) allocator they can match non-persistent data structures in O-ness (ie. when making an invalid assumption that is quite popular in academia. In practice memory allocation is O(1) for small values, then O(n^2) once you get close to the system's memory capacity (scanning for holes in a long list) but don't go over it, and then O(oh fuck it let's just reboot this bloody BOAT ANCHOR) when crossing that line). Clojure is famous for having good persistent data structures. Rich Hickey went touring academia touting the benefits of immutable/persistent/functional data structures : https://www.youtube.com/watch?v=dGVqrGmwOAw&feature=youtu.be&t=1265 https://www.youtube.com/watch?v=dGVqrGmwOAw&feature=youtu.be... There's also a famous book: https://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...
      - GFK_of_xmaspast 10y ago
        > Well, when you pass a variable around, it doesn't and cannot change Yeah but how's that different than a const?
        iofj 10y ago
        It's not, but it still has update methods. It's a const with update methods. Example for a map: x = map{"five": 5} y = x.put("six": 6} Now x is map{"five": 5} and y is map{"five": 5, "six": 6}. If any other tread was using x, it hasn't changed.
- jasonjei 10y ago
  Is there anything in C++11/14/17 that contains this? Could you use locks, or is that less performant? I'm very interested in using this since I do have a multithreaded Windows app that appends and processes a queue (a long poll client to a web app that does work for the web app by gathering data from the local desktop).
Rexxar 10y ago
Nice to see more immutable data structures for C++. I recently implement a persistent list inside a personal project, it's quite easy using shared_ptr (a set of persistent list forms a DAG, so no loop). It would be nice to have a persistent version of all standard containers. It seems that implementing "Finger Tree" would be a good start as a basic building block. But I didn't find any c++ implementation.
TillE 10y ago
"Practically O(1)" is meaningless. If it's not actually constant time, then how does it grow?
- Tuna-Fish 10y ago
  Every operation that is not actually constant time grows by log32. Or in other words, by no more than the constant factor 5. In practice, these data structures live and die by your memory allocator. They do so many allocations that unless you are using a world-class GC, the memory allocation costs completely overshadow any other time costs. Using the typical platform malloc, or even jemalloc or it's ilk, this will be very slow indeed.
  - Syzygies 10y ago
    Yes. This begs for a port to Rust, to see if the fine-grained memory support there pays off. While Rust can do anything, it wants to be bare-metal Haskell.
    - izym 10y ago
      C has just as much fine-grained memory support as Rust. Rust does however have better memory safety with its borrow checker, but I'm not sure if you could implement something like this without unsafe.
      - izym 10y ago
        It seems I was a bit too fast. I meant to write C++ and not C.
  - Kutta 10y ago
    Yes. Copying GC with bump pointer allocation is critical for pretty much any persistent data structure. In C++ and Rust one should use memory pools/arenas for them instead.
- saasinator 10y ago
  "Practically O(1)" == amortized constant time?

42 points by jiyinyiyong 10y ago

hyperbovine 10y ago

Sorry, I am lost: why is this a big deal? I use std::array and it's fine.

eyelidlessness 10y ago
Immutability makes reasoning with state and concurrency much easier. Persistent data structures help make immutability practical in terms of performance and memory overhead.
deleted 10y ago
[deleted]
akubera 10y ago
Their Array class is perhaps unfortunately named, as it behaves as a vector or list (i.e. you can push things to the collection) rather than fixed size memory block. The important thing to notice in their example is the assignment to 'a' when pushing items (`a = a->push(1);`), and the ability to reassign the new change to a new variable (`auto b = a->push(4);`). That last command keeps 'a' the same (hence "immutable" data structure), but creates a new variable 'b' to hold the new data. This technique allows you to, for example, pass the same data structure to multiple threads without worrying that they will simultaneously change data (race conditions). More information can be found here https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure (check out the linked list and tree diagrams in examples). For this to work properly in C++, I think you'd need to const all types for it to be effective (immutable::Array<const MyStruct>). I'd really like to see benchmarks comparing these structures implemented in C++ vs those in functional languages; I don't know if the compiler optimization algorithms produce similar code.
- mmierz 10y ago
  Naive question: even so, what's the advantage over using, say, a const std::array<MyStruct>?
  - iofj 10y ago
    Well, when you pass a variable around, it doesn't and cannot change. This means that different threads can't get in eachothers' way anymore, for instance, but also that you can't make a big chunk of mistakes at all. They also have serious disadvantages : they can't be memory managed in the traditional way (since they tend to reuse other instances' memory in complex ways), and thus require a GC (refcounting can work, but ...). They are VERY allocation intensive, and they are worse than most non-persistent data structures. Assuming an O(1) allocator they can match non-persistent data structures in O-ness (ie. when making an invalid assumption that is quite popular in academia. In practice memory allocation is O(1) for small values, then O(n^2) once you get close to the system's memory capacity (scanning for holes in a long list) but don't go over it, and then O(oh fuck it let's just reboot this bloody BOAT ANCHOR) when crossing that line). Clojure is famous for having good persistent data structures. Rich Hickey went touring academia touting the benefits of immutable/persistent/functional data structures : https://www.youtube.com/watch?v=dGVqrGmwOAw&feature=youtu.be&t=1265 https://www.youtube.com/watch?v=dGVqrGmwOAw&feature=youtu.be... There's also a famous book: https://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...
    - GFK_of_xmaspast 10y ago
      > Well, when you pass a variable around, it doesn't and cannot change Yeah but how's that different than a const?
      - iofj 10y ago
        It's not, but it still has update methods. It's a const with update methods. Example for a map: x = map{"five": 5} y = x.put("six": 6} Now x is map{"five": 5} and y is map{"five": 5, "six": 6}. If any other tread was using x, it hasn't changed.
jasonjei 10y ago
Is there anything in C++11/14/17 that contains this? Could you use locks, or is that less performant? I'm very interested in using this since I do have a multithreaded Windows app that appends and processes a queue (a long poll client to a web app that does work for the web app by gathering data from the local desktop).

Rexxar 10y ago

Nice to see more immutable data structures for C++. I recently implement a persistent list inside a personal project, it's quite easy using shared_ptr (a set of persistent list forms a DAG, so no loop). It would be nice to have a persistent version of all standard containers. It seems that implementing "Finger Tree" would be a good start as a basic building block. But I didn't find any c++ implementation.

TillE 10y ago

"Practically O(1)" is meaningless. If it's not actually constant time, then how does it grow?

Tuna-Fish 10y ago
Every operation that is not actually constant time grows by log32. Or in other words, by no more than the constant factor 5. In practice, these data structures live and die by your memory allocator. They do so many allocations that unless you are using a world-class GC, the memory allocation costs completely overshadow any other time costs. Using the typical platform malloc, or even jemalloc or it's ilk, this will be very slow indeed.
- Syzygies 10y ago
  Yes. This begs for a port to Rust, to see if the fine-grained memory support there pays off. While Rust can do anything, it wants to be bare-metal Haskell.
  - izym 10y ago
    C has just as much fine-grained memory support as Rust. Rust does however have better memory safety with its borrow checker, but I'm not sure if you could implement something like this without unsafe.
    - izym 10y ago
      It seems I was a bit too fast. I meant to write C++ and not C.
- Kutta 10y ago
  Yes. Copying GC with bump pointer allocation is critical for pretty much any persistent data structure. In C++ and Rust one should use memory pools/arenas for them instead.
saasinator 10y ago
"Practically O(1)" == amortized constant time?