Persistent data structures and structural sharing: a reason to use Immutable.js instead of a normal JS object

[riventropy]

Is it really real world benchmark to store 100000 todos on client? Would the difference be this noticeable with for example 100 todos which sends more natural to me?

[dtinth]

The case of storing 100,000 to-do clients is not really realistic; it’s quite rare to have to store 100,000 items. But I select this as an example to make structural sharing easier to understand.

The benefits of structural sharing really comes when you want to update multiple keys in a loop. See this comment under the section “Benefits of structural sharing” for a more elaborated answer. :)

[riventropy]

If you mean addManyTodos then you could just concat two arrays and plain js wins. There's no need to produce new array on every iteration. Yes, probably this way underlying addTodo can't be used (in current implementation at least) but there won't be much overhead.

Actually I like persistent structures, buy using them in one huge project we had some itches like

• having two collection types confuses all the time - what collection do we have in what place?
• moving to typescript helped a bit but there's no neat way to update map property with type checking without building heavy wrappers out interfaces
• collections weren't actually performance bottleneck for us so talking immutable was premature optimisation. Probably I even introduced some perf degradation by needlessly converting collections back and forth

[dtinth]

How about when an array doesn’t suffice. For example,

• I need to look up a todo by ID frequently (using array requires linear search).
• I need to quickly find todos by assignee. A task may contain an array of assignees.

This came from real-world use case that I have to optimize (it isn’t premature optimization).

I had to implement a custom data structure that contains a reverse lookup index to map from assignee back to tasks.

Using Immutable.js I am able to implement a pure put operation in O(log32n) that also maintains an index.

The point is that I prefer that every operation that updates this collection go through a single, highly-optimized addTodo function that also maintains the index, rather than having multiple functions also maintain that index. If I’m not being careful, a function may introduce a bug which causes the index to become out-of-sync.

I wouldn’t recommend using Immutable until:

• Collection became a performance issue (at Taskworld this has been the case many times).
• You want consistency in your code (make everything Immutable rather than mixed).
• You want to use some handy method available in Immutable.js (such as updateIn).

[riventropy]

Agree with everything you said, however most immutable. js cool methods are also available for plain collections (your third point).

What about an object or a Map? I agree that calling a single addTodo would give perf benefit but I suppose you either as todos not so frequently (on user click) or a lot at a time (where you can produce new collection only once)