I don't know if it would help any, but if you have to diff a million strings, why not split um up into subgroups and fork a process to diff each subgroup (if you aren't doing that already)...
I mean if you're forced to brute force something, why not do it the right way, fork fork fork! :)
my humble opinion :)
- Magius_AR