Immer: immutable and persistent data structures for C++

The typical way of doing garbage collection in C++ is via reference counting. This is the strategy used in the library by default.

However, this can be customized in the library. There is a brief description here: https://sinusoid.es/immer/memory.html

For example, one may choose between thread safe or thread unsafe reference counting (the later is much faster!). One may also plug in a conservative garbage collector, like `libgc` (https://github.com/ivmai/bdwgc). While reference counting is often considered to be bad for immutable data structures, I found out that this is not the case. They have very interesting interactions with move semantics and _transients_ (this is a feature that is still on the design phase though). I should write more about this somewhere, maybe in a blog or even as a paper.

They may be located somewhere in the forest of continental post-structuralism somewhere between Derrida and Deleuze, even though this is a very structuralist assertion in a way, a contradiction that we shall embrace anyways. I wanted to deconstruct the data post-structures from Clojure and Scala following. The outcome is that I wrote code that I can barely understand, something that while burying my engineering career and speeking poorly of my intellectual abilities, might open me doors of the philosophical heavens.

There is a tension between me wanting to use the fanciest shiniest features and me wanting it to be usable by the widest audience (even people using Microsoft compilers). I know of people that are still migrating their commercial code bases to C++14 that are interested in using them. It is probably in my best interest to support them, so it will take a while until I start using newer standards.

Anyways, the _implementation_ of the data structures themselves does not really benefit that much from C++17 (well, there might be some interesting stuff that I could do with hazard pointers...). However, people using the new concurrency stuff from the standard might really want to look into using immutable data structures to pass data between tasks.

It all depends on the scenario. Consider this situation: a sending object has an internal collection of items and wants to send it to a receiver. With a mutable collection the sender sends a shallow copy of the collection, because the receiver can't be trusted not to modify the original (which is part of the internal state of the sender).

With an immutable collection the sender can send the original, no copy required. The immutable collection can be shared (lock free) by any number of users.

In this case you have both reduced time and memory use.

So while immutable collections are obviously "slower" for general (mutable) scenarios, the win comes when you need less locking, less copying, and so on.

Performance is one of the goals, so I am benchmarking everything. I run benchmarks on Travis, locally on my machine, and sometimes on a Raspberry Pi 3. You can check some of the reports here: https://public.sinusoid.es/misc/immer/reports/ (this is a bit hard to interpret without further comment).

So, the slowdown depends on the operation.

At the moment, comparing `immer::vector` to `std::vector`, example, for reading, using internal iteration (e.f. `for_each`) you get 1.5X, using iterators something like 2.5X, using [] something like 6X iteratively, something like 1.1 in random order.

Updating a single `int` element is like 100X. (This factor decreases with the size of the updated element, though!) But then, for example, `push_back` is only 1.1X std::list, and it does not rely on amortization, making it better for latency. Considering that you get access time similar to std::vector and persistence, it is a good deal. Also, with `flex_vector`, you get logarithmic slicing and concatenation, making these operations faster than for std::vector (when using big-enough vectors). Also, I am working now on _batch updates_ via transients, so if you update 10 elements in a row, you don't pay 10 times 100X (basically, you only pay the 100X once, which is very much ok for most use-cases, think like a 1microsecond tax per mouse click ;)

There are lots of trade offs one can make (in general, one can make updating a bit faster by making access a bit slower). Also, it depends a lot on the memory management strategy, which can also be customized.

I did read the book few years ago. I found his ideas on how amortization vs persistence and exploiting laziness for data structure very interesting.

However, many of the data structures in that book do not translate great outside of the world of Haskell and ML. This library is mostly based on the work of Phil Bagwell, Rich Hickie, Tiark Rompf and others. Phil worked over the last decade on building immutable and/or concurrent data structures that are "pragmatic", ie. cache efficient, and supporting mutable facades. I recommend reading his work on Hash-Array Mapped Tries and Radix Balanced Trees.

I assume the author chose this licence because it reflected his wish for the user's freedoms to run, study, share and modify the software to be guaranteed. He probably doesn't want a permissive licence.

For what's worth, I urge you to keep GPLv3 :)

Thanks for the question, I should add a clarification. It is a term I borrowed from some Scala papers... The idea is that it is actually logarithmic, but the base of the logarithm is very big, so in practice, it is just like a constant (kinda log32 with the default options). With these settings, the biggest vector of ints that fits in 4GB of memory has a depth of 6. And you can store 1M ints in just 4 levels. 1K in 2. This constant is much lower than what you are paying anyways for cache thrashing when working with big vectors. So while from a theorical point of view it is `O(log(n))` considering real programs running on real computers, it is more useful to think of this as a constant factor. Probably I should update the docs with some clarifications or some more honest terminology.

We need more copyleft not less. I'm glad it is GPL and also plan to use it should I need immutable data structures.

Or even LGPL, what copy-left libraries should be using.

Don't get me wrong, the GPL isn't the "worst thing ever" or a "virus", but I feel it's best suited to full applications rather than libraries.

It was meant as a half-joke picking on how everything is now "modern" on C++.

The half-serious part is that there has been a trend in the last few years in the "modern" C++ community against Copy-On-Write, heap allocation, shared pointers, etc. Immutability kind of brings new life to these concepts...

I thought it was clearly a joke poking fun at all the other modern libraries.

Ah, but remember that post-structuralism is a _critique_ of structuralism....

(and yeah postmodernism and post-structuralism are related, but like everything in this area, It's Complicated)

Another java library with persistent/immutable datastructures is javaslang.