Open yoavaa opened 1 year ago
Update:
Reading the Immer source again, I can see that for objects there is the state.assigned_
member which marks which object properties have been updated or deleted.
I suggest to extend the idea for arrays to also include added and removed array items, those making the above algorithm redundant and making for a simpler solution.
What do you think?
I am thinking as offering it as a pull request - let me know what you think
🚀 Feature Proposal
Today when computing a patch on arrays, immer compares objects by index, which results in all array change in case of
unshift
orsplice
usage. An example is the following test taken from immer testing -https://github.com/immerjs/immer/blob/main/__tests__/patch.js#L543-L559
the expected result should be instead
Motivation
I am working on a new framework that also serializes patches, and the above is a performance issue.
Consider the above case - for an array of object, lets say an array of 100 objects with 10 attributes each, the current algorithm will generate 1000 patches, while my suggestion is to produce only 1 per added / removed object
Can this be solved in user-land code?
no
Example
See the example above.
Usage: immer -> serialize -> deserialize -> patched object
suggested algorithm
(pseudo code)
the problem with json diff is that given two
array
s, without any additional knowledge, to figure out if an item was pushed to the front, we have to do a===
comparison between the array items, which isO(n^2)
complexity.However, we can create an algorithm focused on small changes that has complexity
O(n)
with a cutoff. The algorithm makes the assumption that small changes can be found fast and require small number of mutations to describe. The cutoff is set atlet limit = log(min(A.length, B.length))
and the algorithm has complexityO(limit^2) ~ O(n)
The algorithm -