Big allocation for a small diff

[aminya]

It seems diff-rs allocates a big vector for diffing a small object resulting in out-of-memory

This was discussed in this issue as well
rust-pretty-assertions/rust-pretty-assertions#124

https://github.com/utkarshkukreti/diff.rs/blob/0.1.13/src/lib.rs?rgh-link-date=2024-01-31T21%3A37%3A48Z#L150

[utkarshkukreti]

This is because the current algorithm uses O(NM) memory. I've been working on adding a Myers diff implementation (#1) for the last 2 days which would use linear memory and in many cases much less time. I hope to push an implementation on a branch very soon. I will comment when it's up.

[utkarshkukreti]

I pushed an implementation in the myers branch. Can you test it (point the dependency to this git repo branch = "myers" and change diff::chars to diff::myers::chars) and see if it's fast enough now? The memory usage should be linear now, not quadratic.