Diffing challenge: Swift vs Objective-C++

[rnystrom]

I'm proposing this mostly for fun/learning. We spent a lot of time optimizing our diffing algorithm in Objective-C++ (e.g. custom unordered_map, tables, structs). It's blazing fast, but I'm really curious how it would perform in Swift.

Parameters:

• Test with and without @objc protocol IGListDiffable { ... }
  • A big bottleneck in the diffing algorithm is objc_msgSend(...) for diffIdentifier and isEqual:
  • Should test a Swift implementation with and without the Objective-C messages
• The same input and output
  • Can omit experiments
• Compile for production
  • -Os for Objective-C
  • ??? for Swift

My hunch is that the current implementation will be faster, but I'd love to be proven wrong!

[AndrewSB]

@rnystrom is there a write-up for what the algorithm is? I can look through the .mm source if not, but this does look fun and it would be cool if you guys wrote about it 😄

EDIT: oops, found it! https://engineering.instagram.com/open-sourcing-iglistkit-3d66f1e4e9aa#.i4tl6xe0w

[AndrewSB]

@rnystrom IMHO it would also be really cool to have the diffing engine as a dependency to IGListKit, that way it can be used for other applications - diffing is useful in a number of other places, and especially when it's computable in O(n)

Also, switching b/w the two implementations for you guys at Instagram to test performance would then just be changing one line in your (Pod/Cart)file 😄

[rnystrom]

@AndrewSB all the diffing is actually independent of the rest of the framework, just bundled w/ it so we aren't managing 2 projects where one (IGListKit) depends on the other (diffing). In fact, they used to be separate projects internally!

We're tracking making a sub-podspec in #53 as well. Should be pretty easy.

I like the idea about switching the algos on the fly though! Would be pretty cool.

Oh you can find the original algorithm paper here.

[AndrewSB]

@rnystrom that makes sense for including just the diff engine in other projects, or IGListKit on macOS

I'm going to take a shot at the implementation in Swift over the next couple days - will be at https://github.com/AndrewSB/Diff.
I would love to have you guys measure and test it for efficiency, and I'm completely willing to work with you guys to either improve what I end up writing or helping out with an IGListKit-internal implementation in Swift 👍

[rnystrom]

@AndrewSB amazing. I'll keep an eye on it, and if you run into issues or have questions, ping me on an issue there (or here). Happy to help out!

[jessesquires]

Should test a Swift implementation with and without the Objective-C messages

Not sure what you mean by this.

1. Using objc_msgsend / inheriting from NSObject means using the ObjC runtime. In this case, Swift is just "Objective-C with a new syntax". I wouldn't expect to see many differences. If you use the Swift stdlib, then you're kind of just measuring that against C++ STL, right?
2. Do you mean static vs dynamic dispatch? In this case, if everything is protocol P, you'll still end up with dynamic dispatch. However, using constrained generics (<T: MyProtocol>) should give you static dispatch.

[jessesquires]

Also: optimization levels should be the same:

• none: -O0
• fast: -O
• fastest, smallest: -Os
• fastest, most agressive: -Ofast

Note that -Ofast will remove all safety (overflow-checking, etc.) from Swift. This is only recommended for hot, well-tested code paths. I would bet that this has a chance of out-perfoming the ObjC++ version.

[rnystrom]

Not sure what you mean by this.

I think #2?

I was more talking about using a protocol that called Objective-C methods on NSObject subclasses (resulting in objc_msgSend(...)) vs just calling Swift functions on a Swift-only protocol. So ya I think static dispatch is what I was after.

[AndrewSB]

@rnystrom I mentioned you on an issue I was having AndrewSB/Diff#1

I've implemented a pretty naive version of Paul Heckel's algorithm in Diff.playground. There are a number of speed ups I know of already, but I wanted to get the algorithm outputting Edits before I started making it more complex.

[lxcid]

I went for the talk of Ryan in Singapore (great talk btw) and tried porting it to Swift.
It was quite fun and I think I got an identical implementation. I passed most of the relevant unit tests which are also ported.

https://github.com/lxcid/ListDiff

This is done is Swift 3 and depends only on Foundation. Its in a single file so you guys can just copy into your project. Let me know if you find any bug.

Thanks for the reference implementation. It very interesting and I learnt quite a bit.

Equality check is not implemented yet because I haven't figure out the API interface.

[rnystrom]

@lxcid can you do === for pointer comparison then == for equality? Just means diffed items have to conform to Equatable.

Algorithm looks good tho! Funny how it looks basically the same considering its C++ and Swift.

[lxcid]

Thanks! Yeah, it was a direct port from IGListKit, much of the structural part of the code was kept similar. 😅

Was surprise to see that the === operator only work with class though, which make it tricky now.

A workaround is to drop support for pointerPersonality check but introduce a custom enum that has the type pass through using generics, than one of the case take a closure which the user can implement pointerPersonality check. Something like this.

lxcid/ListDiff@cc0794a

I haven't test out yet though…

[rnystrom]

@lxcid re: pointer personality, that makes sense! I guess we could just stick to == and expect classes to check their pointers first, then values. Something like:

func ==(lhs: MyClass, rhs: MyClass) -> Bool {
  return lhs === rhs || lhs.value == rhs.value
}

Then structs are always just value comparisons.

[lxcid]

Ahhh didn't thought about that. I agree!
I have made the suggested changes and port the associated tests at lxcid/ListDiff#1

[AndrewSB]

@rnystrom did you end up testing the swift version? Was it any faster?