Hacker News Reader

Comment by csande17 | Hacker News Reader

Something I've wondered about the "immutable updates" pattern discussed in the article: do JavaScript engines optimize it somehow? On its face, it seems like it would turn a constant-time "favorite post X" operation into a linear-time "create a copy of the array of all the posts, replacing post X with a copy of post X where 'favorited' is true" operation.

Or do developers just assume that their UI code won't ever need to scale to large numbers of items? (Is this why JIRA's web UI is so slow when you have a couple thousand open tickets?)

View on HN

Duplicating arrays of objects is well-trod territory as far as the engine goes. Your array isn't storing all the content, just a bunch of pointers to the old objects, so "a couple thousand" entries in the array is trivially small. Once you're dealing with millions you may consider using immutable.js, since that uses datastructures optimized on the assumption of immutability (eg less duplicating of whole arrays, more storing only the deltas).

If you're using jira's web UI as an example, you'll find the overhead of array and object duplicating to be a tiny fraction of the cost for actually rendering all those items in browser. Probably in the one-billionth or less range of the total cost.

We hit that limit. And yes developers think things will just work - until they don't. When item count and especially app complexity go up, redux becomes cumbersome and you then need to start using action batching, avoid immutability and so on...

Second issue is that developers think they know how Redux works, but there are a lot of gotchas. From example on OP - `return state.map(toggleTodo(action));` With large app, there are for sure cases where such arrays are empty - and this thing will get updated and re-rendered even if it's empty.

From my experience - in most cases MobX is much better than Redux and it's horizontally scalable - as you can just create new, unrelated stores (something that's total PITA with Redux).

Most functional languages have immutable persistent data structures that don't require a linear copy and are fairly efficient.

For example in clojure, sequences are implemented as 32-ary tries so insert/delete/update to any particular index will only cost around sizeOfNode * numParents=32 * log_32(n). This comes with a cost that indexing is now log_32(n) but it's usually a fair price to pay.

In javascript, immutable.js implement these same ideas (as least according to these talks where they talk about index tries and hash array mapped tries: https://youtu.be/I7IdS-PbEgI?t=456)

If you want native support, javascript engines are actually free to swap out their implementation of arrays! I know they already do depending on whether they think your array is sparse("holey") or not: https://github.com/v8/v8/blob/8.1.81/src/builtins/builtins-a.... I also vaguely recall someone saying that unshift (push to front) is automatically optimized by switching to a deque/circular buffer but I might be remembering wrong. Anyway, they can make these optimizations in a distant future but I don't think do today.

> Most functional languages have immutable persistent data structures that don't require a linear copy and are fairly efficient.

This is true, but unfortunately those libraries/languages don't make use of that tree structure for "partial memoization" of derived data. They very well could, but they don't -- even when you use Immutable.js in a Redux app, and you use Reselect, your selectors will take linear time when you mutate one element in an object/array instead of taking constant- or log-time.

Yea that's a good point. This matters when your derived data takes linear time to recompute. There are still techniques to make this work (but not automatically afaik). For example it's easy to make them efficient again if your computation is just an associative fold or reversible fold: https://sci-hub.tw/https://link.springer.com/chapter/10.1007...

That article talks about map and filter and fold, but I think there are also (trickier) ways to make joins and sorts work as well.

I think it could be a great technique for a lot of things -- compilers and database views, in addition to front-end state.

immutableJS gives you false sense of immutability - never forget that you have intrinsic reflection in Javascript and the only thing to force immutability is Object.freeze() which makes things unusably slow.

Or you can enforce it with readonlys in TypeScript. Not enforced by the engine of course, so there's always the danger some 3rd party component could get its fingers in your objects, but any of the devs on your project will be prevented from modifying their objects directly.

TS and immutablejs work together surprisingly well. One enforces immutability via static analysis, and the other creates (relatively) efficient datastructures predicated on the assumption of immutability.

TS works well. But ImmutableJS is slow, really slow. https://jsperf.com/immutable-js-iteration

I wouldn't go by benchmarks run against a 100-length array of numbers. That's so small it's practically a tuple. Where immutable.js improves your perf is if you need to have very large (1M+) datasets, and/or need to keep references to those data over time for thing like undo, diffing, saving those diffs, etc. If you used a pure array that's 1M, that'd be over 64MB per array, so at just 10 levels of undo you could already exhaust your heap. Immutable.js would be barely over 64MB for hundreds of levels of undo, since it can rely on the last state being immutable it can store only the diffs.

Immutable.js was a bad solution when it was used purely to enforce immutability. Unfortunately that's what its reputation became, but really it should be thought of as a lib that takes advantage of immutable data, not a lib that checks for immutability.

A great resource for understanding how persistent data structures are implemented is Okasaki’s Purely Functional Data Structures: https://www.amazon.com/Purely-Functional-Data-Structures-Oka...

Also available as a free PDF: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

> Or do developers just assume that their UI code won't ever need to scale to large numbers of items?

If you have enough items that a copy of all attributes is noticeable to the user, the user will never realistically see those items. (We'd be talking about thousands of them minimum) Or alternatively you're loading A LOT of data per item. Either way, the issue in almost every single case is not that the copy takes too long.

I mena, there are edge cases like an endless list of small items (twitter?) which someone scrolls for a long time and then makes a modification. But then you should know it's potentially a REALLY long list you need to handle.

There are definitely costs to doing immutable updates of objects and arrays. The engine has to allocate a new object in memory, copy over all the existing keys, and copy any new keys / values you're assigning. For very large objects, yes, this can become noticeable.

But, for most apps, this isn't a concern given the kinds of data and state updates that are common.

There's a specific library called Immutable.js, which implements some complex internal data structures to optimize copying objects. However, the library is relatively large, and complicated some common usage patterns. My opinion is that it's rarely worth using that lib.

Reply on news.ycombinator.com