6 ms·

The fastest object diff library in JavaScript

100 points by AsyncBanana 5y ago

wruza 5y 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 https://github.com/AsyncBanana/microdiff/issues/2
- nathcd 5y 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?
  - eyelidlessness 5y 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.
  - wruza 5y 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.
    - nathcd 5y ago
      Ah that's my mistake, I read more into your comment than you wrote. Sorry! It's a good point about edge cases in diffing. Dynamic value diffing in dynamically-typed languages is an interesting problem to think about.
- bikeshaving 5y 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.
spankalee 5y 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 :)
throwaway413 5y 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 5y ago
  Yeah, it's just a single function that recurses. So the limit will be your VM's call stack limit.
tekkk 5y ago
Hey this is really cool! Not sure how this compares to https://github.com/benjamine/jsondiffpatch 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 5y 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.
parhamn 5y 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 5y ago
  For a bit of info on why it is often faster, you can look at https://github.com/AsyncBanana/microdiff/issues/2 https://github.com/AsyncBanana/microdiff/issues/2. I will probably add something to the README about that soon too.
- megous 5y ago
  It doesn't handle arrays, for one example.
- sbr464 5y 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.
drodil 5y ago
Nice one. Have you tried replacing the for loops with forEach? It might be even more performant.
- Etheryte 5y 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 https://stackoverflow.com/q/22155280/1470607
  - deleted 5y ago
    [deleted]
- sbr464 5y 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.
megous 5y 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 5y ago
  > loops Don't
  - akie 5y ago
    Ok, let's pretend they don't exist and potentially hang the app.
megous 5y 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.
- StevenWaterman 5y ago
  You only see the finished product, not the 100 failures and incremental improvements over time. You could certainly write something yourself from scratch, but I doubt it would be competitive against this.
  - engmgrmgr 5y ago
    Mmm, agree with parent; can get faster. Unfortunately lots of perf critical code is created out of necessity and defaults to proprietary. You could profile this lib and figure out where it’s spending most of its time and figure out if there any ways to improve (starts getting into implications of JS <-> system), but as you get more idiosyncratic you lose flexibility and ease of use. Eg type checks, heap additions, recursion, etc can get “slow”
  - megous 5y ago
    > not the 100 failures and incremental improvements over time This code has 3 actual code commits over 6 days, none of which changed anything fundamental. What are you talking about? It's quite possible to compete against this on multiple levels. One would be correctness. The other a bit less wasteful interface. Another would be handling arrays in a more useful way (or at all). And yet another would be safety. Another would be speed and memory use. Yet another would be non-recursive implementation. Another would be documentation (what's this diffing? enumerable/non-enumerable properties? how it deals with getters? how about inherited properties? - I can't know any of this without looking long and hard at the code)... etc. etc.
    - can16358p 5y ago
      Note on only the first part: the author might have tested bunch of stuff on their local without commiting until they've found something worth, perhaps? That would result in very few commits.
ianberdin 5y ago
Please compare with a modern competitor: json-patch-plus https://github.com/n1ru4l/graphql-live-query/blob/main/packages/json-patch-plus/README.md https://github.com/n1ru4l/graphql-live-query/blob/main/packa... It’s a bit different, but I think it covers more cases.
wereHamster 5y ago
> const t = true; That should be the job of a minifier, makes the code less readable.
laurent123456 5y 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 5y 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-javascript-implementations-use-string-interning https://stackoverflow.com/questions/5276915/do-common-javasc... https://en.wikipedia.org/wiki/String_interning https://en.wikipedia.org/wiki/String_interning
kosinus 5y 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/ https://github.com/Two-Screen/symmetry/
- kosinus 5y ago
  Here is the microdiff benchmark wrapped in benchmark.js: https://github.com/stephank/js-diff-benchmarks 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)
can16358p 5y 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?)

100 points by AsyncBanana 5y 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 https://github.com/AsyncBanana/microdiff/issues/2

nathcd 5y 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?
- eyelidlessness 5y 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.
- wruza 5y 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.
  - nathcd 5y ago
    Ah that's my mistake, I read more into your comment than you wrote. Sorry! It's a good point about edge cases in diffing. Dynamic value diffing in dynamically-typed languages is an interesting problem to think about.
bikeshaving 5y 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.

spankalee 5y 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 :)

throwaway413 5y 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 5y ago
Yeah, it's just a single function that recurses. So the limit will be your VM's call stack limit.

tekkk 5y ago

Hey this is really cool! Not sure how this compares to https://github.com/benjamine/jsondiffpatch 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 5y 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.

parhamn 5y 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 5y ago
For a bit of info on why it is often faster, you can look at https://github.com/AsyncBanana/microdiff/issues/2 https://github.com/AsyncBanana/microdiff/issues/2. I will probably add something to the README about that soon too.
megous 5y ago
It doesn't handle arrays, for one example.
sbr464 5y 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.

drodil 5y ago

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

Etheryte 5y 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 https://stackoverflow.com/q/22155280/1470607
- deleted 5y ago
  [deleted]
sbr464 5y 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.

megous 5y 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 5y ago
> loops Don't
- akie 5y ago
  Ok, let's pretend they don't exist and potentially hang the app.

megous 5y 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.

StevenWaterman 5y ago
You only see the finished product, not the 100 failures and incremental improvements over time. You could certainly write something yourself from scratch, but I doubt it would be competitive against this.
- engmgrmgr 5y ago
  Mmm, agree with parent; can get faster. Unfortunately lots of perf critical code is created out of necessity and defaults to proprietary. You could profile this lib and figure out where it’s spending most of its time and figure out if there any ways to improve (starts getting into implications of JS <-> system), but as you get more idiosyncratic you lose flexibility and ease of use. Eg type checks, heap additions, recursion, etc can get “slow”
- megous 5y ago
  > not the 100 failures and incremental improvements over time This code has 3 actual code commits over 6 days, none of which changed anything fundamental. What are you talking about? It's quite possible to compete against this on multiple levels. One would be correctness. The other a bit less wasteful interface. Another would be handling arrays in a more useful way (or at all). And yet another would be safety. Another would be speed and memory use. Yet another would be non-recursive implementation. Another would be documentation (what's this diffing? enumerable/non-enumerable properties? how it deals with getters? how about inherited properties? - I can't know any of this without looking long and hard at the code)... etc. etc.
  - can16358p 5y ago
    Note on only the first part: the author might have tested bunch of stuff on their local without commiting until they've found something worth, perhaps? That would result in very few commits.

ianberdin 5y ago

Please compare with a modern competitor: json-patch-plus https://github.com/n1ru4l/graphql-live-query/blob/main/packages/json-patch-plus/README.md https://github.com/n1ru4l/graphql-live-query/blob/main/packa... It’s a bit different, but I think it covers more cases.

wereHamster 5y ago

> const t = true; That should be the job of a minifier, makes the code less readable.

laurent123456 5y 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 5y 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-javascript-implementations-use-string-interning https://stackoverflow.com/questions/5276915/do-common-javasc... https://en.wikipedia.org/wiki/String_interning https://en.wikipedia.org/wiki/String_interning

kosinus 5y 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/ https://github.com/Two-Screen/symmetry/

kosinus 5y ago
Here is the microdiff benchmark wrapped in benchmark.js: https://github.com/stephank/js-diff-benchmarks 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)

can16358p 5y 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?)