I'm finally reaching a point with difftastic where I'm pretty happy with performance. 0.22 has some effective heuristics for making the tree diff faster, and 0.23 will have Myers' diff algorithm for text.