6 ms·

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

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?)

acemarke 7y ago
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.
viraptor 7y ago
> 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.
fyp 7y ago
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 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-array.cc#L887 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.
- repsilat 7y ago
  > 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.
  - fyp 7y ago
    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/978-3-642-39038-8_29 https://sci-hub.tw/https://link.springer.com/chapter/10.1007...
    - repsilat 7y ago
      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.
- hatch_q 7y ago
  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.
  - jkoudys 7y ago
    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.
hatch_q 7y ago
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).
jkoudys 7y ago
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.

acemarke 7y ago

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.

viraptor 7y ago

> 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.

fyp 7y ago

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 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-array.cc#L887 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.

repsilat 7y ago
> 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.
- fyp 7y ago
  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/978-3-642-39038-8_29 https://sci-hub.tw/https://link.springer.com/chapter/10.1007...
  - repsilat 7y ago
    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.
hatch_q 7y ago
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.
- jkoudys 7y ago
  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.

hatch_q 7y ago

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).

jkoudys 7y ago

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.