search

bhousel / node-diff3

A node.js library for text diffing and three-way-merge
Other
92 stars 13 forks source link

Poor performance #84

Open denis-sokolov opened 2 months ago

denis-sokolov commented 2 months ago

Diff3.diffComm(a, b) where a and b are lists of words totalling about 20,000 characters each takes about 10 seconds on my laptop. This seems to be an uncharacteristically poor performance. With some simple testing, it seems to be O(n³).

In contrast, in the same time diffWords from diff performs a diff on strings of 20,000,000 characters each. I have not compared what algorithm it uses.

Diff3.diff3Merge(a, b, original) with a and original being identical 100,000 character strings, and b an empty string takes about 20 seconds on my laptop.

EmmanuelJego commented 2 months ago

Hey @denis-sokolov,

I was looking for a 3-way-diff library, and thanks to your comment I looked for other libraries that would have better performances. I ended up finding this lib, which is actually just a script, but that's enough for me (also no dependencies). It is ~1000x faster than this lib for long strings (~100k characters), same as you measured for diffWords.

So if you ever need a 3-way-diff lib, you might be interested in this one 👍