weichch / system-text-json-jsondiffpatch

High-performance, low-allocating JSON object diff and patch extension for System.Text.Json. Support generating patch document in RFC 6902 JSON Patch format.
MIT License
104 stars 13 forks source link

Improve performance of comparison in LCS #11

Closed weichch closed 2 years ago

weichch commented 2 years ago

As part of benchmark improvement(#7), I found the performance of Diff and DeepEquals is not ideal for array comparisons in some scenarios. Further investigation suggests the issue might be related to Lcs where materializing is done N x M times where N and M are the length of the arrays being compared.

Conversely, JToken.DeepEquals performs a lot faster, even faster than comparing JsonNode by RawText, as the tokens are only materialized N+M times and cached in the JToken instances.

I've already benchmarked enabling a global value cache for the entire diff operation, but there is performance setback instead of improvement. I've also benchmarked a custom parser for parsing JSON strings into JsonNode instances in not readonly mode, but the performance gain is once again not worth it, and no improvement in array comparisons.

So, for now, I'm looking at a solution that is just enough for LCS, and hopefully release an enhancement as part of the next version going out.

weichch commented 2 years ago

Fixed in #12