bsdiff runs very long

[ctc]

I have 2 10MB big files where the bsdiff runs 82 minutes
bsdiff file_a file_b delta.diff

files.zip

[phmccarty]

Thanks for the report. I will investigate the problem.

[ctc]

Did some research and tests.

It's a well known old problem.
Switching to divsufsort does not help (from Freebsd)

Slowdown happens in line 757 / search

Sources:
https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664;msg=14
freebsd/freebsd-src@9c63dcd

[phmccarty]

@ctc search() is called after suffix sorting has finished, so I doubt that the suffix sort routines are to blame.

[tpepper]

IIRC in the past we saw a 24 or 48hour diff'ing of a pair large kernel binaries. There's something that can go pathologically wrong on large binary inputs. Colin's paper talk about complexities with a log in them, but it feels like a bug somewhere turns things exponential sometimes.

[ctc]

@phmccarty no, I did some debugging with gdb - it loops in search and not in suffix sort, "scan" variable is slowly increasing.

have switched now from rpm packages (files are rpm db's) to dpkg - now much better

[phmccarty]

I made some progress on this issue, with help from @tmarcu. See PR #3.