Menu
Menu
In this talk, Karoly describes several ways to implement the same simple ordered set protocol in Swift, demonstrating how the language supports a number of surprisingly different approaches to programming. At every step, we trade extra complexity for improved runtime performance, ending on an implementation that is ludicrously fast but also quite difficult to handle.
The full source code behind the talk is available as a GitHub repository:
https://github.com/lorentey/OptimizingCollections
The repository includes an Xcode playground with all the data structures presented in the talk. The playground also explains how we can conform all implementations to the Collection protocol—which is something Károly conveniently skipped.
As an extra bonus, Károly included the fun Mac app that he wrote to run benchmarks and to generate the colorful performance plots used in their slides. The app also contains super-secret experimental enhancements to the BTree struct.
For a production-quality implementation of ordered sets (and other ordered collection types), check out my BTree package:
https://github.com/lorentey/BTree
Some of the optimizations benchmarked are not yet implemented in this package. If you have time to spare, help him implement them!