Optimizing Swift Collections
summary
Implements an ordered-set protocol in Swift and compares concrete implementations: wrapping NSOrderedSet, a sorted array, a red-black tree and finally an inlined, cache-aware B-tree. Claims include a sorted array being up to 40× faster than NSOrderedSet for small sizes, red‑black giving ~2.5× better worst‑case than NSOrderedSet, a 200k element sorted array taking ~4s, a 4,000‑element/L1‑cache threshold (~32KB), and a 3 million insert benchmark where the B‑tree is fastest.
AI-written summary · about
chapters (20)
- 0:00Intro
- 0:28Overview
- 1:50NS Ordered Set
- 3:31Array Representation
- 4:20Insert
- 5:23Search Tree
- 5:48Tree Structure
- 6:10Tree Representation
- 6:50RedBlack Trees
- 7:31Inorder Work
- 7:58Insertion
- 10:01Performance
- 12:29Copyonwrite
- 13:06Unique Reference
- 14:14Results
- 15:19Division Line
- 15:50Sorting Arrays
- 17:05Inline Implementation
- 18:05Summary
- 18:59Outro
related talks
20mExtending the Standard Library
18mHigh-performance systems in Swift
28mUsability Meets Performance in Swift
33mSwift at Scale: Where Performance Really Comes From
01h 00mThe Mysterious Swift Performance
57mSwift Tutorial - Exploring Swift Sequences in Depth
11mMaking our Swift better
04mStating the obvious