Patch Set 3:

I'm fairly happy with this implementation now.  Performance beats MyersDiff, and is close enough to the heavily optimized PatienceDiff that I'm starting to think Christian is right and we should drop PatienceDiff:

  testDefault     Myers                 560000 ns    8 edits
  testDefault     Patience              220000 ns    6 edits
  testDefault     Histogram             420000 ns    8 edits
  
  testIgnoreAll   Myers                1460000 ns    8 edits
  testIgnoreAll   Patience              360000 ns    6 edits
  testIgnoreAll   Histogram             420000 ns    8 edits

These numbers were taken using the heavily optimized PatienceDiff, not the one that is currently in tree.  Unfortunately PatienceDiff and HistogramDiff run so fast that I'm having trouble getting a stable set of results from them, values vary from 360000 ns to the 420000 ns you see above.  I'm suspecting its noise from the GC, because both algorithms discard and allocate new memory during each recursive step.