Fast Immutable Interval Sets
summary
Two immutable interval-set implementations: a binary prefix tree for values packable to 64-bit longs and a sorted-array merger for any ordered type, both exposed in Spire/extras. They implement Boolean algebra (union, intersection, complement, XOR, contains, intersects, subset) with structural sharing for cheap backtracking. Performance: negation flips a bit in ~8 ns, union of 100k support points (50k intervals) completes in ~3 ms (tree) and ~5 ms (array), intersection ~2 ms (array). The tree is far more compact and faster when chunks let it reuse subtrees.
AI-written summary · about
chapters (25)
- 0:00Intro
- 1:53So what's this talk about?
- 2:37Spire Intervals
- 4:32Finding a date for a meeting
- 10:08Why functional data structures
- 13:28What's different to a collection?
- 14:13What operations would be useful?
- 17:06Bool typeclass
- 18:50Flat sorted array
- 24:02Leaf node
- 24:51Branch node
- 29:36Equality and hash code
- 31:01Binary operations (and, or, xor)
- 32:28Recursion step, same level
- 37:11Benchmark - summary
- 39:12Minimum comparison merge
- 40:49Get the maximum value out of each comparison
- 41:18Algorithm sketch
- 41:35And operation in IntervalSeq
- 42:40Benchmark - interleaved
- 43:51Benchmark - cutoff
- 44:29Array vs. Tree - who wins?
- 44:48Array vs. Tree - Interleaved
- 45:45Array vs. Tree - cutoff
- 47:23Questions
related talks
41mLeveraging Spire for complex time allocation logic
25mLEVERAGING SPIRE FOR COMPLEX TIME ALLOCATION LOGIC
39mExtreme Cleverness: Functional Data Structures in Scala
31mRadix Trees: How IntMap Works
46mImmutable Sequential Maps – Keeping order while hashed
49mNumeric Programming With Spire
50mPick your number type with Spire
25mImmutable APIs and mutable internals: a Scala design case study