I tried to use Algorithm::Diff on split("",$str)'ed contents of 2 revisions, and for bigger (like 30kB) pages it takes a few minutes. This is weird.
How is MediaWiki doing it ? Does it try to find longest common subsequence of lines or characters ?
Well, MediaWiki surely doesn't consider each character singly, but rather whole words. I don't know if that's it, but seeing as the algorithm is O(n*m), it seems to make some sense.