Immutable Sequential Maps – Keeping order while hashed

on YouTube ↗46m

" summary

Scala 2.13 adds a SeekMap trait with mutable and immutable variants; several implementations are benchmarked using sbt-jmh and JMH plus the JMH visualizer. The default vector map stores a hashmap plus an index vector and performs well generally but inserts tombstones on removals, causing very slow consecutive deletes; a tree-based SeekMap trades about 50% more memory for much faster removals and in one concat benchmark shows ~370k vs ~900k ns/op for vector map. ListMap is cheapest for prepend-heavy patterns but degrades badly for indexed access.

AI-written summary · about

" chapters (11)

1. 0:00Start
2. 1:55What is a sequential map?
3. 4:22Challenges
4. 5:27Essential Operations
5. 7:13LinkedHashMap
6. 8:35Immutable
7. 9:04Combination Strategy
8. 10:18Definitions
9. 16:03VectorMap - Removal
10. 37:25Conclusions
11. 39:54Becoming a contributor

" related talks

• 54mHow Not to Write Slow ScalaColin Woodbury · LambdaConf 2018
• 39mExtreme Cleverness: Functional Data Structures in ScalaDaniel Spiewak · Clojure/conj 2011
• 31mRadix Trees: How IntMap WorksTikhon Jelvis · Scale By The Bay 2018
• 23mThe Future of Scala Performance on Big DataCarlos Abad · Scala Days Berlin 2016
• 48mHigh performance Scala systems without tearsZahari Dichev · Scala Days Berlin 2018
• 32mLIFTING DATA STRUCTURES TO THE TYPE-LEVELJon Pretty · Scalar 2018
• 25mImmutable APIs and mutable internals: a Scala design case studyOscar Boykin · Scale By The Bay 2018
• 42mWhat Scala can learn from Rust, Swift, and C++D. Racordon, E. Flesselle · Scala Days 2025