The fastest object diff library in JavaScript

The fastest object diff library in JavaScript(github.com)

100 points by AsyncBanana 4 years ago | 44 comments

wruza 4 years ago |

Fast diffing of objects may be seen as rarely needed to a regular user, but it’s very important part of handling vdom/vnode diffs. Recently I researched few lesser web ui libraries for my own use and found out that many of them do not diff vnodes correctly, e.g. in case of RegExp or Date arguments. I don’t remember exact library names vs flaws, but my conclusion was that almost all of non-actively supported libs had it in one way or another. If you want to explore, check that first, because it’s a surprising pain point.

Seems that this particular library is aware of these potential issues (which motivated me to write this comment): https://github.com/AsyncBanana/microdiff/issues/2

nathcd 4 years ago | |

But vnodes have a predefined shape, whereas this library is for diffing (relatively) arbitrary objects, right? If your data isn't arbitrarily shaped, I would assume you'd get much better performance by just implementing a simple direct diff, no?

wruza 4 years ago | | |

Yes. I should have noted for clarity that vdom diff is a special case, not a general one like that of subj. But their similarity reminded me of the experience.

eyelidlessness 4 years ago | | |

And, often but probably not always, using a class instance rather than a POJO. Seems unintuitive (function call overhead), but it can signal to the JIT that the object’s type is relatively stable.

bikeshaving 4 years ago | |

Are these RegExps/Date objects passed as props? I’m not sure why a VDOM algorithm would have to handle these types of objects.

kosinus 4 years ago |

I maintain symmetry[1] and wanted to try the benchmark against it, but the results are very inconsistent. Symmetry is anywhere between 50% slower to 20% _faster_ than microdiff on the small object benchmark.

Symmetry doesn't get a lot of activity, but I've been using it in production for many years. It does some more work on array diffing, which this benchmark doesn't cover, by implementing part of Myers' algorithm.

[1]: https://github.com/Two-Screen/symmetry/

kosinus 4 years ago | |

Here is the microdiff benchmark wrapped in benchmark.js: https://github.com/stephank/js-diff-benchmarks

I added three more libraries, and also the size in bytes of `JSON.stringify(result)` for each. (That was also important for me in making symmetry.)

The results from benchmark.js are a lot more consistent on my laptop:

Benchmark: Small object (baseline)

- @n1ru4l/json-patch-plus x 1,426,241 ops/sec ±0.29% (94 runs sampled) (94 bytes)

- deep-diff x 337,122 ops/sec ±0.45% (95 runs sampled) (193 bytes)

- deep-object-diff x 2,138,118 ops/sec ±0.25% (96 runs sampled) (60 bytes)

- diff x 59,277 ops/sec ±0.60% (97 runs sampled) (268 bytes)

- jsondiffpatch x 841,880 ops/sec ±0.38% (96 runs sampled) (113 bytes)

- microdiff x 6,979,471 ops/sec ±0.77% (95 runs sampled) (171 bytes)

- symmetry x 8,666,619 ops/sec ±0.21% (97 runs sampled) (7 bytes)

Benchmark: Large Object (300 properties)

- @n1ru4l/json-patch-plus x 16,902 ops/sec ±0.66% (92 runs sampled) (515 bytes)

- deep-diff x 8,378 ops/sec ±0.68% (96 runs sampled) (1194 bytes)

- deep-object-diff x 19,647 ops/sec ±0.40% (94 runs sampled) (410 bytes)

- diff x 737 ops/sec ±0.45% (94 runs sampled) (12051 bytes)

- jsondiffpatch x 14,306 ops/sec ±0.76% (95 runs sampled) (714 bytes)

- microdiff x 22,131 ops/sec ±0.25% (95 runs sampled) (935 bytes)

- symmetry x 21,432 ops/sec ±0.92% (98 runs sampled) (424 bytes)

megous 4 years ago |

In all seriousness, what's so noteworthy about this? It's one trivial 50 line recursive function. This is kind of stuff devs just type out instead of searching for a npm package, because it's faster that way.

spankalee 4 years ago |

I know some diffing libraries are reluctant to do this for perf reasons, but many of them do not handle cycles correctly leading to potential infinite loops based on the shape of the objects and order of arguments.

Fast is great, but unless you know that your data doesn't have cycles, infinite loops take a long time :)

ianberdin 4 years ago |

Please compare with a modern competitor: json-patch-plus https://github.com/n1ru4l/graphql-live-query/blob/main/packa...

It’s a bit different, but I think it covers more cases.

megous 4 years ago |

What if object references have loops? That doesn't seem to be handled. Also it looks like it will diff not just own properties but properties from prototype objects, too.

tantalor 4 years ago | |

> loops

Don't

akie 4 years ago | | |

Ok, let's pretend they don't exist and potentially hang the app.

wereHamster 4 years ago |

> const t = true;

That should be the job of a minifier, makes the code less readable.

tekkk 4 years ago |

Hey this is really cool! Not sure how this compares to https://github.com/benjamine/jsondiffpatch which has been unmaintained for some time. But if this could replace it I'd happy to start using it.

AsyncBanana 4 years ago | |

Thanks for your interest! Currently, Microdiff does not have a patching functionality by default, and the API is different. If there is enough interest, though, I might make a compatibility layer to ease the differences, and it probably would not be hard to do yourself too.

can16358p 4 years ago |

I wonder how it plays with React(Native)/Redux. I'm having a bottleneck issue with state changes with many state comparisons and wondering if I can swap the builtin diff with this to speed up the diffs.

(I admit there are many other parts to optimize too, but if I can just plug this for some extra juice, why not?)

laurent123456 4 years ago |

> type: "CREATE" | "REMOVE" | "CHANGE";

Since performance is a goal, why not define an enum and use integer values? I don't know about speed, but the resulting diff would be smaller.

Also I wonder what "const t = true" is for.

wruza 4 years ago | |

Usually it doesn’t make a difference neither in speed, nor in size, because of “interning” of literals. Unless you jsonify it, of course. It could show up, if you’d later compare .type with some “CRE”+”ATE” values made funny way, but not for literals, e.g.:

  // x.js
  export const foo = "foo"

  // y.js
  if (x.foo === "foo") {
    // ^ as cheap as int
  }

  const foo2 = "FOO".toLowerCase()
  if (x.foo === foo2) {
    // ^ questionable
    // depends on jit/optimization
  }

https://stackoverflow.com/questions/5276915/do-common-javasc...

https://en.wikipedia.org/wiki/String_interning

parhamn 4 years ago |

Interesting it’s so much faster, the code looks very natural and trickless besides the richobject check (at least at first glance).

Wonder what everyone else is doing to make it slow.

Also curious what mobx and reacts object diffing looks like now.

AsyncBanana 4 years ago | |

For a bit of info on why it is often faster, you can look at https://github.com/AsyncBanana/microdiff/issues/2. I will probably add something to the README about that soon too.

sbr464 4 years ago | |

Not checking for arrays (and nested array recursion) is most likely the biggest performance/feature difference.

Some diff libraries have React specific optimizations, if values might be React elements/components.

megous 4 years ago | |

It doesn't handle arrays, for one example.

throwaway413 4 years ago |

Is this a true deep diff utility? Didn’t check the code, but the readme makes no mention of depth capability beyond comparing to some other deep diffing libs.

nathcd 4 years ago | |

Yeah, it's just a single function that recurses. So the limit will be your VM's call stack limit.

drodil 4 years ago |

Nice one. Have you tried replacing the for loops with forEach? It might be even more performant.

Etheryte 4 years ago | |

In Javascript, forEach, map, reduce and other similar array methods are considerably slower than a regular for loop. You can see [0] and the linked questions for more technical details.

[0] https://stackoverflow.com/q/22155280/1470607

sbr464 4 years ago | |

Function callbacks are definitely slower. You could probably shave another 10% by changing the array.push() calls to direct assignments: array[array.length] = value. Same with the nested array.map, changing to a for loop.

// x.js export const foo = "foo" // y.js if (x.foo === "foo") { // ^ as cheap as int } const foo2 = "FOO".toLowerCase() if (x.foo === foo2) { // ^ questionable // depends on jit/optimization }