ArrayDeques and How to Contribute to Scala 2.13 Collections

on YouTube ↗28m

" summary

Scala 2.13 adds a mutable ArrayDeque implemented as a circular array with start/end pointers that gives constant-time prepend/append/get and O(min(i, n-i)) insert/delete at index, using at most two memcpy copies on resize and a bit trick when capacity is power-of-two. Benchmarks (ref-tree visuals and GitHub code) show prepends that take milliseconds versus seconds for ArrayBuffer when growing to 10 million items. API includes both clear and clearAndShrink. Source, diagrams and benchmarks are on the linked repo.

AI-written summary · about

" chapters (7)

1. 0:00Start
2. 4:06New Collections
3. 7:14Insert and Deletes
4. 18:16Source Code
5. 19:21Pre-Emptive Allocations of the Correct Size
6. 20:42Benchmarks
7. 22:54Takeaways

" related talks

• 23mArrayDeques and How to Contribute to Scala 2.13Pathikrit Bhowmick · Scale By The Bay 2018
• 39mExtreme Cleverness: Functional Data Structures in ScalaDaniel Spiewak · Clojure/conj 2011
• 51mImplementing the Scala 2.13 collectionsStefan Zeiger · Scala Days Lausanne 2019
• 37mWhat’s in the next iteration of the standard collections?Julien Richard-Foy · Scala.IO 2017
• 54mHow Not to Write Slow ScalaColin Woodbury · LambdaConf 2018
• 35mMigrating to Scala 2.13Julien Richard-Foy, Stefan Zeiger · Scala Days Berlin 2018
• 42mWhat Scala can learn from Rust, Swift, and C++D. Racordon, E. Flesselle · Scala Days 2025
• 28mRust and Scala, Sitting in a Tree….Evan Chan · Scale By The Bay 2019