search

chbrown / rfc6902

Complete implementation of RFC6902 in TypeScript
https://chbrown.github.io/rfc6902/
316 stars 39 forks source link

Improve performances #39

Open Toub opened 6 years ago

Toub commented 6 years ago

Is there a way to make rfc6902 faster?

See benchmark: https://github.com/Starcounter-Jack/JSON-Patch

amiller-gh commented 4 years ago

ref: https://github.com/chbrown/rfc6902/issues/73

williamstein commented 3 years ago

(Caveat: I'm just a random user.)

I just took some real-world data from an application I'm working on (a nested JSON structure coming from a slatejs document tree, which JSON.stringify's to something with about 30K characters). I'm interested in computing diffs, so I took one edit operation (which slightly changes the tree), and compared performance of making a diff using rfc6902 versus https://github.com/Starcounter-Jack/JSON-Patch. The difference in performance is striking:

JSON-Patch was 30x-200x times faster than rfc6902 at this benchmark.

I hope this comment isn't too annoying since I'm not providing the exact JSON object. It's really just a random "in nature" JSON object that pops up when parsing some markdown. The benchmark code I ran is:

t = new Date(); for(i=0;i<100;i++){w=rfc.createPatch(cur, next);}; new Date() - t

where rfc = require("rfc6902") and cur and next are my two objects. With JSON-Patch, I ran the same loop:

t = new Date(); for(i=0;i<100;i++){w=jsonpatch.compare(cur, next);}; new Date() - t

Both libraries output equivalent rfc-6902 looking results in my tests, though of course things can be random in general. I tried other objects and got similar timings (where JSON-Patch is orders of magnitude faster).

I'm not asking for anything, and I realize that rfc6902 might be significantly better than JSON-Patch in terms of semantics, correctness, optimal patches (?), or some other metrics. I realize computing diffs is fraught with complexity. I just didn't expect such a huge difference in performance, and wanted to record that somewhere, in case it is helpful to somebody.

Looking more deeply: The source code of JSON-patch's function to compute a diffs looks like a straightforward recursive algorithm (it's short, but has basically no useful comments). The code in rfc6902 for computing diffs is here, and it's much prettier, vastly better commented, and appears to produces significantly more efficient patches in general. But these cost a lot more to produce in some cases.

williamstein commented 3 years ago

Just to add to the previous comment, I tried some more "real world examples", and indeed this rfc6902 produces dramatically better patches in practice on some examples. For one I just tried, rfc6902 produces a nice clean single add op, compared to JSON-patch producing a sequence of 37 operations to do the same thing. So indeed, you get what you pay for.

image