Feature Request: timeout for calcPatch
Closed this issue · 5 comments
Most of the time fast-myers-diff works fast, great job!
Sometimes, calculating patch for unoptimal input takes forever. I'm wondering if we can put a timeout, e.g. maximum 300ms, if calcPatch takes more than that it will throw an exception
I tried naive implementation, but it does not work:
let time_out = false
setTimeout(() => {
time_out = true;
}, 300);
const result_diff = [...calcPatch(old_data, new_data, (a,b) => {
if (time_out) return false;
return old_data[a] === old_data[b]
)]result_diff still run even time_out === true.
What do you think ?
Interesting attempt. Maybe try with return true and validate the output instead. return false makes the algorithm degenerate to quadratic. return true should be linear but gives an incorrect output with a smaller difference.
Another option that should be possible with Myers' algorithm is to set a maximum length for the diff (i.e. minimum length for the LCS) beyond which the algorithm would not try to find a match. Not sure if this is part of the public API of fast-myers-diff yet, but you can already try it with @edit-distance/myers-1986 which I wrote and tell us if it would help you if fast-myers-diff implemented the same as part of the public API.
A last option is to run such long computations in a worker thread.
After tinkering with fast-myers-diff internal, i found that h_loop: method is called to generate the generators. I just put my own should_break() function there:
if should_break() then it just return 0.
I don't know if this is the correct approach, but my timeout returns exactly 300ms.
Hence, the job is done... I think.
Of course the resulting diff is unusable. So the correct action is to throw an Error when timeout is reached.
@rizrmd Wait, how can any of the suggested solutions possibly work given the computation is synchronous?
@rizrmd Does state.should_break() in your example do something akin to return Date.now() - state.start >= timeout perhaps?
yes. But I use performance.now() instead of Date.now()