Immer is a library of persistent and immutable data structures written in C++ | Hacker News Reader

Immer is a library of persistent and immutable data structures written in C++

github.com

102 pointsfortran7756 comments

Open articleView on HN

Ironically, there's a name clash with a fairly popular immutable update library for JS:

https://github.com/immerjs/immer

Looks like the C++ one started first (2016-05 vs 2017-12).

I assumed it was some sort of port, but they’re totally different things!

OT but it’s worth reading the code for immerjs. It’s super small, super clever and shows the power of proxies in js.

Yep. Michel Weststrate is a genius, and also an all-around nice guy. I hope to have a chance to meet him in person.

(For reference, I'm a Redux maintainer. We now recommend Immer as the best way to write immutable update logic in Redux apps, and use it in our Redux Starter kit package.)

Saw this code in a client's redux project, it was awesome to see that. So much easier than how we were about to do our very complex state updates. It takes away a lot of the complexity. Immediately copied that and showed it to our webdev channel.

Glad to hear it! Please let me know if you have any further feedback from using it.

Here's the current roadmap towards 1.0:

https://github.com/reduxjs/redux-starter-kit/issues/82

I just pushed out a breaking set of changes a few days ago, and will likely make one more set of breaking changes to `createSlice` in the near future. After that, I'm hoping the API will _mostly_ be good to go, and I can push it towards 1.0 in the very near future.

Immer looks awesome but we're relying on Immutablejs shallow object comparison to stop rendering React components when not needed. When I last checked I could not figure out how to achieve the same thing with Immer.

Do you know some reference that addresses this?

And if we're here an additional question: since our store data is currently composed of deep immutable JS data structures, do you know of a way to slowly migrate to Immer?

I've tried to move parts of the store to Immer, but since the root store obejcts are still Immutable js objects, this didn't go well.

Shallow object comparison is not a special property of Immutable.js. It's just a matter of iterating over the keys and values of two objects and comparing them. In fact, that's how React-Redux (and many other React ecosystem libs) work. `connect` decides whether to re-render your component by doing shallow comparisons of the previous and current `mapState` return object to see if the extracted values have changed.

All that's necessary is to do immutable updates of your data, by always making _copies_ of the data and modifying the copies (see [0] and [1] for discussions of immutable updates).

It doesn't matter whether the new object references were produced by manually creating copies ( `{...obj}`, `someArray.map()`, etc), by using Immutable.js's API, or Immer tracking the "mutations" via a proxy and creating the new references internally. As long as you have immutable updates and new references, shallow comparisons work fine.

So, there's nothing special you need to do to make Immer work with comparisons. You literally just use it as described in the docs.

Specifically for comparisons, `PureComponent` and `React.memo()` both do shallow comparisons of `props` by default.

Yes, the pervasiveness of Immutable.js's API is one of the reasons I've long suggested that folks avoid it [2]. I don't have any detailed suggestions for migrating, other than perhaps consistently using Reselect selectors to encapsulate reading values from the store and handling the Immutable.js -> `toJS()` conversion (which you should probably be doing anyway as a perf optimization, since that conversion is relatively "expensive"). That way, as you switch over chunks of reducer logic from Immutable.js to Immer, the code consuming those values _should_ still be getting POJOs out of the selectors, with no actual visible change.

[0] https://redux.js.org/recipes/structuring-reducers/immutable-...

[1] https://daveceddia.com/react-redux-immutability-guide/

[2] https://www.reddit.com/r/javascript/comments/4rcqpx/dan_abra...

ImmerJS is a direct replacement for ImmutableJS.

We recently switched from using ImmutableJS in our Redux store to using ImmerJS.

We took the approach one reducer at a time. We have multiple reducers and we're using combineReducers (the ImmutableJS one until it was completely converted).

We had no issues whatsoever in the change. ImmutableJS doesn't care about plain JS objects (which is what ImmerJS reducers return) so everything worked as expected.

React's shallow comparison worked as expected since ImmerJS produces new objects on mutation (just like ImmutableJS).

Essentially: there is no case where ImmutableJS is needed. All functionality and benefits are available in ImmerJS which is a much easier to use library.

To do the migration, we literally just used the docs on the Github repo. This was back with version 1.0 or something and it wasn't documented very well but we were able to figure it out. The first code example is how to use it with Redux. Also the section on Currying is useful.

Edit to add: This is all within the context of web apps, specifically React apps with Redux. I'm sure there's probably some places where ImmutableJS is desirable, but I don't know of any.

"there is no case" is a strong statement. ImmutableJS is generally the wrong tool for the job in a reducer. It's optimized for if you have a single flat object with 1000s of keys. Immer can't implement the same level of structural sharing

I added a caveat.

Can you explain this scenario further? I’ve not used immutablejs but I’m familiar with both functional data structure concepts and immerjs.

Immerjs just improves the ergonomics updating a native nested structure in a way that the original contents are maintained as much as possible. Because js has dreadful support for equality checks, this definitely comes in useful.

Immutable.js implements a specific set of data structures that internally share references. When you add a new field or copy an object, Immutable.js doesn't have to completely recreate things. For small objects this doesn't matter, but for _very_ large objects and arrays, it does improve performance to some extent.

With Immer and "hand-written" immutable updates, doing a `{...obj}` or `someArray.slice()` will do a "shallow" copy of the object. This is equivalent to what Immutable.js does in that it keeps all the fields pointing to the same references. However, the JS engine does have to do an O(n) processing of all the individual top-level keys, whereas Immutable.js's internal data structure is O(logN) or something like that. So, for _very_ large objects, it is faster for Immutable.js to make a copy than it is for plain JS data.

My take, however, is that

- Most apps will not be dealing with gigantic objects, so there's no perf benefit from using Immutable.js

- Immutable.js is a much larger dependency than Immer

- The fact that Immer works with POJOs _and_ gives you the ability to write trivial "mutative" syntax for updates is a huge improvement over Immutable.js's Java-inspired API

So, to me, the only hypothetical use case where Immutable.js would actually be worth it is if your app is consistently dealing with huge objects, _and_ there is truly serious overhead from copying them that needs to be optimized.

OT: how do you know when it's time to add an immutable library as a dependency (as opposed to following immutable update patterns in vanilla JS)?

For some perspective on why the name was probably chosen: 'immer' means 'forever' or 'always' in German

Could someone provide an actual example use-case for immutable data structures in C++?

The linked document only mentions high-level examples, all of which seem to be trivially implementable via mutable data structures and a bit of being careful.

Does this buy anything beyond peace of mind that if you pass an immutable DS to another thread, they won't be able to change it?

Immutable data structures are great for undo-redo.

Sean Parent has a conference video out there about how undo in Photoshop is implemented by breaking the image into tiles then making a list of the history of each tile. This allows the “History Brush” to reach into the past and paint old pixels over new ones.

I wrote something similar for a resource system for a game engine. If you had a ResourceHandle<T> you knew that the T inside it would never change, and it was safe to pass to any other system. You could always make a mutable copy of the RH<T> to get a T out (and as an optimization if you held the last handle, skip the copy). Once you were done writing to the T, you could tell the resource system to harden it into a handle to give to other systems again (which included serializing it to give it a static hash for the T). There was other cleverness to make it ergonomic that I've since forgotten. Across a large codebase it _was_ nice to ensure that immutable data wasn't going to change, and that you could load up data with the same hash again later and get the same results. It _is_ possible to do via mutable data structures, but you can't always ensure that every person on your team will be careful in the right way.

The author has created a text editor which uses immutable data structures s.t. he can do fast undo / redo [1]

[1] https://github.com/arximboldi/ewig

I saw a demonstration where he copy pasted a file into itself until it was larger than whatever memory he had in the computer. He could still efficiently edit it (the data pointers were duplicated, not the data).

Pretty impressive.

Do you have the URL to the video?

Yes, immutable data structures can be used for capturing a temporal aspect without actually needing to model it explicitly in the underlying data.

Here's a document[1] explaining how to make a tree-like data structures persistent along with a motivating example of their use (at the end). The wikipedia page[2] for the problem also goes into other techniques and has some diagrams too.

tl;dr a naive approach to the point location query problem achieves O(N^2) space and O(logN) time per query, while simply modifying the data structure to be persistent achieves O(N) space while retaining O(logN) time per query.

[1] https://saco-evaluator.org.za/presentations/camp3_2017/persi... [2] https://en.wikipedia.org/wiki/Point_location

Try implementing a scheme on top of this. Stack and env management suddenly becomes trivial.

The same simplicity applies analogously to various other use cases which would be tedious and error prone to implement without immutable data structures.

In C++, we usually copy the resources that we want to share, so as that accidental modification of a resource doesn't take place.

However, the copying becomes impractical from a performance point of view if the resources are big, so immutable resources offer an alternative that does not have the performance issues.

For example, if you have multiple threads computing sub-graphs of a graph and passing those sub-graphs around to other threads, copying the whole graph each time a thread needs to compute something that may potentially alter the graph is a killer for performance. You then have two choices:

Choice 1: make the graph thread-safe. Which is the usual route C++ takes.

Choice 2: make the graph out of immutable data structures.

Choice 1 is the practical choice when the scope of the work is limited, and therefore thread safety is easy to implement.

When the problem at hand becomes very complex though, and it's difficult to reason about the ordering of locks, immutable data structures is an easier choice.

Yes, there are many other benefits to immutability than parallelism applications related to correctness and ability to reason about programs. See referential transparency, etc.

The Clang Static Analyzer uses immutable data structures. Here, for instance, is its immutable list implementation: https://github.com/llvm/llvm-project/blob/master/llvm/includ...

The data structures are used during program state exploration because they are more memory efficient than storing many copies of the program state with small mutations.

There is something about this immutability thing I really don't like. In the authors example it looks like v1[0] is set to 42 (const auto v2 = v1.set(0, 42)), at least that's how you read it because it contains the word 'set', but you have to 'know' that v1 is immutable and is actually not setting the value, but returning it. So IMAO the naming should be better, I like to read code that is not confusing.

If this construct, that I actually never needed in my entire career, is handy for undo/redo, why not just have a dead simple undo stack? In what situation is an immutable structure your best choice?

what would be a good word for this ? recreate ? recompute ? with_new ?

I'd probably be happy with "update", which is similar to Clojure's API for its persistent vector and map.

https://clojuredocs.org/clojure.core/update

update is a different operation, it takes an update function for the value. The clojure equivalent to set is assoc.

Clojure as `(assoc col key val)` and `(update col key fn)` though I don't know that the naming scheme is significantly clearer.

In general, I think verbs should be avoided, when possible, as names of functional operations. For instance, in Java, 'BigInteger.add' should have been 'plus'. Compare:

  x.add(y);
  x.plus(y);

People have been known to write the first one expecting 'x' to be updated. With the second, I think it's clearer that it's a value that needs to be assigned to a variable.

For the operation in question here, I suggest 'with'. This is what I have used in my own functional collections libraries; I think it originated in SETL.

I am a fan of nouns(or gerunds) for pure functions, and verbs for mutating functions. I.e:

    x.add(y); // x now equals x + y 
    x.adding(y); // returns x + y without mutating x

Persistent data structures are thread-safe and are useful for concurrency. That's partly why they are a core part of functional programming languages like Clojure and Haskell. Persistent data structures are also useful for version control.

They are pretty useful for certain kinds of program analysis (like abstract interpretation and symbolic execution) where you need to create slightly modified copies of the program state (e.g. when you need to split the state on a conditional, or merge two states). Immutable data structures are (space) efficient for this use case. Moreover, you can combine them with hash consing for more space efficiency (only if you are creating lots of objects that share most of their data) and fast equality checking where there is only one copy a value in heap so equality checking is just object identity checking and addresses work as hash values now so hashing large objects is faster too.

The algorithms used in these analyses are usually described in terms of mathematical objects which are inherently immutable and using immutable objects makes correctness proofs easier.

When writing a piece of code, I start with immutable data structures because of the ease of mind they bring to the table (you can pass them around and you know they will not be modified so it makes reasoning and debugging easier, this is less of a problem in C++ because it has const references and const methods). Then, if an algorithm needs a mutable data structure or if the immutable data structures are too slow (e.g. the code is in the hot path) then I switch to mutable data structures. I think it is just a different mentality when approaching programming. It works for me because (a) it is the norm in my field (program analysis, or programming languages in general), and (b) I use a programming language with an ecosystem around immutable data structures (Scala).

Thank you all for taking the time to explain, very valuable for me at least.

The simplest answer is that immutability allows you to share data around without worrying about it being modified.

In the OOP world, you might have a "getter" for a property (e.g. a list of some kind) that you don't want readers to be able to modify.

Perhaps "set" was a poor name here, since it usually means something else in a C++ context. I quite like "with".

Should add that C++ has const, making some of this irrelevant. In the C++ case immutability is about making minor changes to a structure more efficient by reusing the previous version. This is only possible with immutability because you need to be sure that your "base" structure won't change underneath you!

Can't copy-on-write achieve the same thing? If you keep a reference count, you can know whether it's safe to mutate the underlying data, or whether you need to make a copy first.

Technically copy-on-write is an implementation detail.

It may or may not be implemented this way.

I mean that CoW classes like Qt's QStringList do the same data sharing without being immutable.

Admittedly, it's pretty easy to accidentally make unnecessary non-const accesses in modern C++. An immutable API would certainly avoid a lot of qAsConst casts.

In scheme, mutating functions end with "!". (append lst lst2) creates a new list without modifying lst, whereas (append! ...) is allowed, but not necessarily required, to mutate the list.

I see no problem with the set method name, this is what is used in other lib in other languages. When you use an immutable lib you understand the meaning and that every operation create a new base object.

This is extremely useful for undo/redo, it basically comes for free with it. You no longer have to deal with invisible mutation, listener, event, you just generate the ui on each change from the base to the leaf, and everything is always correct for free. The advantage over an undo stack is that there is a re-utilization of unchanged intermediate data structure (what is change is only the path from the base to the changed element), so you can add a simple ref check in the ui to not redraw of the underlying data has not changed. So the perf come for free.

Related: it’d be great if C++ had const constructors, so that we could have true const objects.

There are constexpr constructors

I'm looking for constructors that return immutable objects. Is there something in C++ that can help me?

Constructors do not return, and return type and lhs are decoupled, so you are looking for

    auto const &lol = make_wtf();

Well, more like I’m looking for something that gives you a const that you can’t get rid of. You could use a factory method but it’d be nicer if I could have a constructor that did it.

That's just not how C++ is designed. If you want const, you stick const on the member variables or declare member getter functions const. Then the language checks your work when you initialize an object into a constant variable.

This allows you to force an object to be immutable at a compiler enforced level regardless of how the calling code tries to initialize it.

Unfortunately I am trying to wrap const to something that wasn’t designed this way: https://news.ycombinator.com/item?id=20948523

Since soft const constraint is not part of the type, perhaps you could pass it to a lambda function that treats it as a const and another lambda function that treats it as mutable. A sort of const region and mutable region.

What would be the utility of such a constructor? You can just initialize const objects with regular constructors. How are these objects not "true" const?

The specific use case I had in mind was a implicit “conversion” constructor that took an immutable object and gave back something that you couldn’t strip the const off of (it’d also take a mutable object and give you a normal thing back). What I have specifically is a class that provides a base set of operations and a subclass that lets you do some modifications, and what I am trying to do is wrap it in C++ with an object that is const depending on which class I am converting (converting object to const wrapper_class and mutable_object, a subclass of object, to just wrapper_class).

I don't fully grasp what you are trying to do here. This looks familiar though:

> What I have specifically is a class that provides a base set of operations and a subclass that lets you do some modifications

If you actually do this with public inheritance then you possibly break const correctness.

Having to separate types for the immutable and mutable data structures with appropriate conversions is a sound idea though.

> What I have specifically is a class that provides a base set of operations and a subclass that lets you do some modifications

Your object isn't actually immutable, it just doesn't let you directly mutate it. That's a really important distinction.

That's a common pattern. In C++, rather than using a subclass for the mutator, use a different (friend) class. The semantics for implicit conversion between two different classes will allow you to accomplish what you are asking for with enforcing no changes from one interface but not the other.

> In C++, rather than using a subclass for the mutator, use a different (friend) class.

Unfortunately I don't control this class :(

Reply on news.ycombinator.com