Immer: Value Based Equality Checking

[jclangst]

• [x] Feature request: ______
  
  
  
  • [x] I am willing to implement this myself
  
  

Really loving this library and the use of native javascript instead of having to fall back on ImmutableJS for structural sharing! One of the projects, I was originally using ImmutableJS for was for a compiler that runs isomorphically in the browser and in server environments. For performance reasons, there are a couple of key features that are necessary:

• structural sharing
• optimized value equality checks

Immer of course takes care of structural sharing (and is much better on the js engine due to not having to serialize and deserialize from native js like ImmutableJS requires). But the one thing that I am struggling with is value equality checks. This might not necessarily be an ideal feature to add to the core library, but I think it would be something that would benefit the immer ecosystem even if only as system on top of immer. I am willing to build such a system and make it available, but I was hoping for some initial feedback.

Essentially, I'd like to take care of the following scenarios with relatively similar efficiency as ImmutableJS's Collection.equals (https://immutable-js.github.io/immutable-js/docs/#/Collection/equals):

Scenario 1: Same updates produce objects that appear equal

const orig = { a: 1}
const new1 = produce(orig, draft => draft.a = 2);
const new2 = produce(orig, draft => draft.a = 2);
console.log(new1 === new2) //true

Scenario 2: Same compressed updates produce objects that appear equal

const orig = { a: 1, b: "jane" }
const new1 = produce(orig, draft => {
  draft.a = 2;
  draft.a = 3;
  draft.b = "joe";
});
const new2 = produce(orig, draft => {
  draft.b = "joe";
  draft.a = 3;
});
console.log(new1 === new2) //true

Scenario 3: As a result of the above two, we are able to use the results of immutable operations as keys to one of the javascript Map implementations

const orig = { a: 1}
const map = new WeakMap();

const new1 = produce(orig, draft => draft.a = 2);
const new2 = produce(orig, draft => draft.a = 2);

map.set(new1, "hi");
console.log(map.get(new2)) //"hi"

Note that for all of the above operations, I assume reference equality for value equality. This is only one possible route and I am open to other approaches. Another route (the one that ImmutableJS falls back on) is a combination of reference equality, hash equality (as a fail early mechanism), and structural recursion. I'd like to do no worse than what ImmutableJS provides in terms of efficiency, however.

I have spent a couple hours solutioning the problem, but haven't yet ended up at anything that provides an elegant solution. I wanted to put it out there to see if I am missing something obvious or if anyone else had any thoughts.

[jclangst]

Here is an architectural question that might yield a path to a good solution:

Is the compress patches method mentioned here deterministic (https://medium.com/@david.b.edelstein/using-immer-to-compress-immer-patches-f382835b6c69)?

To rephrase, if I am moving from states A -> B via some arbitrary mutations (i.e., multiple ways to move between those states), is there a way to compress those mutations into the same list of patches deterministically?

[mweststrate]

no, patches track mutations, they don't diff outcome. E.g. given base state
"x = { a: { b : 2 } }", the mutation "x.a = { c: 3 }", generates different
patches compared to "delete x.a.b; x.a.c = 3", although the end result is
structurally the same.

On Thu, Mar 7, 2019 at 4:28 PM Jack Langston [e-mail]
wrote:

Here is an architectural question that might yield a path a good solution:

Is the compress patches method mentioned here deterministic (
https://medium.com/@david.b.edelstein/using-immer-to-compress-immer-patches-f382835b6c69
)?

To rephrase, if I am moving from states A -> B via some arbitrary
mutations (i.e., multiple ways to move between those states), is there a
way to compress those mutations into the same list of patches
deterministically?

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/mweststrate/immer/issues/324#issuecomment-470570621,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ABvGhM0JwTV3y8NrPypvmKpyrOuRc1eHks5vUTAYgaJpZM4bhSgG
.

[jclangst]

Thanks for the clarification. Diffing wouldn't be the ideal of course because that would essentially be the same as a deep equality check which is what we'd like avoid. I am wondering if it would be possible to do some sort of just in time compression of the patches. For that, I think something might be reasonable performance wise IFF it didn't try to decompose something like the x.a = { c: 3} into the base primitive mutations. The architecture might be a JIT patch compressor module that could be used internally to generate deterministic patches per produce as well perhaps be used externally to compress patches from multiple produce calls (similar to the link above). Thoughts?

[mweststrate]

I think you've found yourself a very challenging problem, and my gut
feeling says that the costs in time / space might be higher than the
optimizations it enables in the end. That being said, you probably can get
quite far with a good hashing algorithm and some weakmaps, and if it
succeeds that would be really cool :)

On Thu, Mar 7, 2019 at 5:47 PM Jack Langston [e-mail]
wrote:

Thanks for the clarification. Diffing wouldn't be the ideal of course
because that would essentially be the same as a deep equality check which
is what we'd like avoid. I am wondering if it would be possible to do some
sort of just in time compression of the patches. For that, I think
something might be reasonable performance wise IFF it didn't try to
decompose something like the x.a = { c: 3} into the base primitive
mutations. The architecture might be a JIT patch compressor module that
could be used internally to generate deterministic patches per produce as
well perhaps be used externally to compress patches from multiple produce
calls (similar to the link above). Thoughts?

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/mweststrate/immer/issues/324#issuecomment-470602597,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ABvGhBRyydw1K1WLmlkEdWO6BIORQT6Wks5vUUKSgaJpZM4bhSgG
.

[jclangst]

I would agree that that path seems dubious. If I were to develop a solution similar to the ImmutableJS one of assigning hash values to each subtree, do you think that would be better developed as something in the core library or something on top of the core library that interprets the patches and recomputes the hashes after produce?

[mweststrate]

I think that could be done on top, there are extension hooks to manipulate
the process of constructing the new tree

Op vr 8 mrt. 2019 16:02 schreef Jack Langston [e-mail]:

I would agree that that path seems dubious. If I were to develop a
solution similar to the ImmutableJS one of assigning hash values to each
subtree, do you think that would be better developed as something in the
core library or something on top of the core library that interprets the
patches and recomputes the hashes after produce?

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/mweststrate/immer/issues/324#issuecomment-470958209,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ABvGhNy6kjubhxIBi9jkj7Z-Cwtm23eyks5vUnuHgaJpZM4bhSgG
.

[jclangst]

Thank you. I will look into it.

[luisherranz]

Hey guys, I'm looking into this as well.

I've found this library that seems to work well:
https://github.com/Starcounter-Jack/JSON-Patch

The actual algorithm that creates the patches don't seem too complex either:
https://github.com/Starcounter-Jack/JSON-Patch/blob/master/src/duplex.ts#L164-L216

I guess this can create some performance issues when dealing with large objects but the purpose of immer is to work near the leafs. I wonder how _bad_ this is in terms of performance.

Implementing something like this won't only make patches deterministic, but it will minimize re-renders in React when users do things like:

const state = { user: { name: "Jon", surmane: "Snow" } };

const Name = ({ name }) => <div>Name: {name}</div>;
const Surname = ({ surname }) => <div>Surname: {surname}</div>;

// Right now in immer these are different:
state.user.surname = "Targaryen";
// patch -> { op: 'replace', path: '/user/surname', value: 'Targaryen' }
// rerenders -> Only "Surname"
state.user = { name: "Jon", surname: "Targaryen" };
// patch -> { op: 'replace', path: '/user', value: { name: "Jon", surname: "Targaryen" } }
// rerenders -> Both "Name" and "Surname"

Using JSON-Patch to minimize the patches, they are equivalent:

state.user.surname = "Targaryen";
// patch -> { op: 'replace', path: '/user/surname', value: 'Targaryen' }
// rerenders -> Only "Surname"
state.user = { name: "Jon", surname: "Targaryen" };
// patch -> { op: 'replace', path: '/user/surname', value: 'Targaryen' }
// rerenders -> Only "Surname"

Actually, MobxStateTree works that way:

const store = types
  .model({
    user: types.model({
      name: types.string,
      surname: types.string
    })
  })
  .actions(self => ({
    changeSurname(surname) {
      self.user.surname = surname;
    },
    changeUser(user) {
      self.user = user;
    }
  }))
  .create({ user: { name: "Jon", surname: "Snow" } });

store.changeSurname("Targaryen");
// patch -> { op: 'replace', path: '/user/surname', value: 'Targaryen' }
store.changeUser({ name: "Jon", surname: "Targaryen" });
// patch -> { op: 'replace', path: '/user/surname', value: 'Targaryen' }

I know developers can be educated to modify leafs instead of nodes, but immer is about improving the developer experience, isn't it?

What do you think @mweststrate?

[luisherranz]

Another idea: what if, instead of comparing the values to get the patches, it iterates over the received object and adds the leaves one by one:

state.user = { name: "Jon", surname: "Targaryen" };
// This triggers a "set" with:
target = state
prop = "user"
value = { name: "Jon", surname: "Targaryen" };

// And runs something like:
for (let key in value) {
  target[prop][key] = value[key]
}

This can happen only if there is an existing object in state.user. If it's not, it just adds it. And of course it should be recursive as well.

[mweststrate]

Please open a new issue @luisherranz, that way others can see it :)

Short answer: for what you want Immer would need to do start diffing, which is precisely what it tries to avoid. The patches now reflect the mutation that were made. There are many different ways on what 'the most optimal' patch is. Many small ones? Or better one big one? The "best" largely depends on your use case. So immer opts for "the most efficient" to generate. From there you can post-process the patches in your own code to get your preferred kind of patch. Generating splice patches instead of length change patches, etc etc. In your case, you could take an object assignment patch, and it's inverse patch, the combination of those two will enable you to do diffing and achieve the leaf-patches you are looking for.

[luisherranz]

You're right, it's not clear which one is the best and also the dev can post-process the patch so no need for a new issue :)