Performance Improvements of diff

[Miserlou]

Hi, Corka! Excellent project!

I've been developing on top of this library and it performs very nicely, but I think it might end up being a bottleneck for some applications. I have compared it to other JSON diffing libraries and it seems to be an order of magnitude slower, however, it is the only good one I've found which is RFC 6902 compatible, which is a more important requirement.

So, I was wondering if there were any areas of the diffing algorithm which you think could do with speed improvement that you'd like me to take a look at to try to help speed up.

Cheers!

[corka149]

Hi Miserlou,

thank you so much for your feedback. Honestly, I have a weak background on algorithms.

But maybe this could be a possible starting point:
I checked diff with :eprof by adding it to the test test/jsonpatch_test.exs:66.

      :eprof.start_profiling([self()])

      patch = Jsonpatch.diff(source, destination)

      :eprof.stop_profiling()
      :eprof.analyze()

This was the result:

****** Process <0.269.0>    -- 100.00 % of profiled time *** 
FUNCTION                                                      CALLS        %  TIME  [uS / CALLS]
--------                                                      -----  -------  ----  [----------]

<...snip...>

'Elixir.Jsonpatch':flat/1                                        21     0.65     6  [      0.29]
'Elixir.Stream':map/2                                            22     0.65     6  [      0.27]
'Elixir.Enumerable':impl_for/1                                   38     0.76     7  [      0.18]
'Elixir.Enumerable.Stream':do_each/4                             19     0.76     7  [      0.37]
'Elixir.Jsonpatch':get/2                                         38     0.87     8  [      0.21]
'Elixir.Enumerable.Stream':'-do_reduce/3-fun-0-'/2               41     0.87     8  [      0.20]
'Elixir.Map':get/3                                               34     1.09    10  [      0.29]
'Elixir.Enumerable.Stream':do_reduce/3                           19     1.20    11  [      0.58]
'Elixir.Enumerable':'impl_for!'/1                                38     1.31    12  [      0.32]
'Elixir.Stream':'-filter/2-fun-0-'/4                             38     1.31    12  [      0.32]
'Elixir.Enum':'member?'/2                                        38     1.31    12  [      0.32]
'Elixir.Jsonpatch':'-do_diff/5-fun-2-'/2                         38     1.42    13  [      0.34]
'Elixir.Stream':'-map/2-fun-0-'/4                                39     1.42    13  [      0.33]
'Elixir.Enumerable':reduce/3                                     38     1.74    16  [      0.42]
'Elixir.Enumerable.Stream':'-do_reduce/3-lists^foldl/2-0-'/3     60     1.85    17  [      0.28]
lists:member/2                                                   38     1.96    18  [      0.47]
'Elixir.Enumerable.List':reduce/3                                65     1.96    18  [      0.28]
'Elixir.Keyword':get/2                                          136     2.18    20  [      0.15]
'Elixir.String':replace/3                                       136     2.18    20  [      0.15]
'Elixir.String':replace/4                                       136     2.40    22  [      0.16]
'Elixir.Jsonpatch':escape/1                                      76     2.51    23  [      0.30]
erlang:iolist_to_binary/1                                       136     3.05    28  [      0.21]
'Elixir.String':do_replace/4                                    136     3.93    36  [      0.26]
lists:keyfind/3                                                 272     8.40    77  [      0.28]
'Elixir.Jsonpatch':do_diff/5                                     49     8.62    79  [      1.61]
binary:matches/2                                                136     9.49    87  [      0.64]
'Elixir.Keyword':get/3                                          272    10.69    98  [      0.36]
'Elixir.String':replace_guarded/4                               136    15.27   140  [      1.03]
------------------------------------------------------------  -----  -------  ----  [----------]
Total:                                                         2634  100.00%   917  [      0.35]

I highly suspect that the String handling is not the best.

[Miserlou]

Nice! Great starting point.

[Miserlou]

btw, if you're interested, this is how I'm using your library! https://github.com/Miserlou/live_json

[corka149]

Nice, now I understand your demand for more performance. When I have some free time, I will spend it on performance improvements.

[corka149]

💡 I think I discovered the origin of the performance issue.

The path was always escaped for ~ and /. This is not always necessary. Therefore, I made it conditional.

On my machine the time changed from ~900 to ~580. For comparison JsonDiffEx needed ~670.

@Miserlou would you like to test the feature branch and check if the performance changed?

Dependency should be

{:jsonpatch, git: "https://github.com/corka149/jsonpatch.git", branch: "11-performance-improvements-of-diff"}

[Miserlou]

Yoooooo! This is awesome! Looks really good!

It's interesting that it doesn't actually happen at the language level, seems like that'd be an easy performance improvement for anybody using replace.

If you publish a version bump I'll include it downstream!

[corka149]

🙌 The version 0.13.1 is released. 🥳