Why DifferenceKit is so much faster than Apple's Foundation diffing?

[Moriquendi]

Checklist

• Reviewed the README and documents.
• Searched existing issues for ensure not duplicated.

I'm quite amazed by how fast DifferenceKit is compared to Apple's Foundation diffing.
Can someone please explain what's the catch here?

Is there any reason why Apple chooses to use slower algorithm for their collection diffing?

Here's a sample test I run to compare results:

for _ in 0..<5 {
   var source: [Item] = []
   for i in 0..<10_000 {
      source.append( Item(value: i) )
   }
            
   let target: [Item] = source.shuffled()
            
   measure(name: "DifferenceKit") {
      let _ = StagedChangeset(source: source, target: target)
   }
            
   measure(name: "Foundation") {
      let _ = target.difference(from: source)
   }
}

Output:

Time: DifferenceKit - 29.129458333500224 msec
Time: Foundation - 1961.1885833332963 msec
Time: DifferenceKit - 17.962249999982305 msec
Time: Foundation - 1882.0110833335093 msec
Time: DifferenceKit - 17.888999999740918 msec
Time: Foundation - 1904.927041666724 msec
Time: DifferenceKit - 17.906958333242073 msec
Time: Foundation - 1907.209416666774 msec
Time: DifferenceKit - 18.071041666644305 msec
Time: Foundation - 1919.3862499996612 msec

[ra1028]

Thanks. I'd say the performance tuning of CollectionDifference is quite amazing as same as DifferenceKit, but fundamentally they are based on different algorythms. CollectionDifference is based on Myers's algorythm which is used for general purposes such as text diffing, and DifferenceKit is based on Paul Heckel's which is more suited for UI.
In evidence, CollectionDifference is remarkably fast compared to other libraries which is based on Mayer, but it's not even close to DifferenceKit.
For more information: https://github.com/ra1028/DifferenceKit#comparison-with-other-frameworks

[Moriquendi]

Interesting, thanks @ra1028
Could you elaborate more on the differences between those algorithms and why Myer's is better for "text diffing"?