For most reasonable quantities of data, diff speed is Good Enough as it is, and it's certainly not worth trading off accuracy for speed. In fact if anything we should be going the other direction - Patience Diff is not quite as fast as regular diff, but the output is much higher-quality in my experience, particularly with non-trivial amounts of diverge between codebases.
http://git.661346.n2.nabble.com/Bram-Cohen-speaks-up-about-p...