slow diff_chars

[chenyan2002]

Diffing a large text, e.g., 27k of text, diff_chars seems to take a very long time, whereas diff_lines finishes instantly. Is there a way to speed up the diff_chars?

[oli-obk]

Just to be sure: were you running in release mode?

Did you compare processing the resulting iterator, or did you just time the initial function call?

[romankoblov]

LCS has O(N^2) complexity, so for chars it would be O(27k^2), but there is significantly less lines.

[chenyan2002]

Running in release mode, and time the initial function call with the same content: let diff = prettydiff::diff_chars(&content, &content); println!("{diff}");. diff_chars takes 5s, while diff_lines takes 0.2s.

Yeah, if diff_chars is using LCS, that's expected. If we assume the diff is small, not sure if there is a more efficient algorithm.

[oli-obk]

So... is there anything actionable here? Would you have benefited from some documentation somewhere about the algorithms being used?

[chenyan2002]

The only action item I can think of is to document diff_chars that it's a O(n^2) algorithm. People may blindly use that function to process large text without realizing its time complexity.