Comparison with Swift's CollectionDifference (SE-0240)

[lstomberg]

How does this compare with the Swift development proposal that plans to add Ordered Collection Diffing? Are you involved with that project in any way?

https://github.com/apple/swift-evolution/blob/master/proposals/0240-ordered-collection-diffing.md

[tonyarnold]

At this stage, it's a little hard to tell. Differ's more geared toward providing UI conveniences such as moves alongside a specific difference algorithm, whereas CollectionDifference provides only insertions and removals, and will potentially provide more than one underlying method of calculating differences. See @numist's comments below.

In short, I'd expect once it's released that with a couple of extension methods, CollectionDifference should become the go-to. I'll keep maintaining Differ for the foreseeable future, but I expect that the Swift-provided method will be what I personally use once it's available.

[numist]

The associatedWith: portion of the CollectionDifference.Change type exists to support the encoding of move operations and is set by inferringMoves() :)

[tonyarnold]

That's super exciting, and I'm looking forward to using it in production - thanks for your work on the proposal and implementation, Scott!

[numist]

It has been my pleasure; thanks to you for being the tip of the spear!

[DivineDominion]

I was interested in this as well and ran a couple of benchmarks from https://github.com/tonyarnold/DiffPerformanceSuite -- Differ is too slow for String comparisons, so I left these out here (1x diff would take 45s on my computer).

	Dwifft<Array<Character>>	Differ<String>	Differ<Array<Character>>	Swift<String>	Swift<Array<Character>>
same	0.4334	N/A	0.0094	0.0035	0.0001
created	0.0014	N/A	0.0086	0.0823	0.0808
deleted	0.0014	N/A	0.0092	0.0807	0.0793
diff	0.4843	N/A	0.0528	0.0083	0.0048

IMHO this package is a good choice when you don't compare strings and want to support older OS's 👍

[tonyarnold]

Thanks for the thorough pass at the benchmarks, and for updating them, Christian!

I wonder what it is about Differ's handling of String that is tanking performance? I have less and less need for this library, but it wouldn't hurt to fix the issues.

[tonyarnold]

Oooo, interesting - it looks like accessing a character within a String is triggering some really heavy calls into CFStringCheckAndGetCharacterAtIndex - it looks like maybe the index type is under scrutiny:

[tonyarnold]

Oh, right - Differ is assuming that String.Index == Int in a bunch of places.

[DivineDominion]

Might be because the lib predates String.Index being a proper type? 🤔

It also doesn't help that the algorithm uses Shlemiel the painter's algorithm: Glancing over the implementation, it should be possible to cache previous array indexes and advance from there, instead of computing the index from startIndex every time.

I was also considering to add a NSString variant because of it's NSRange and UTF-16 based rather stable and useful index.

[tonyarnold]

Christian, if you have the time and inclination to improve the performance of string diffing I would be mighty appreciative. I'm not actively using Differ in many places right now, so I can't justify fixing it until I find some mythical "free time" ❤️