Lightweight Relations
summary
Presents a type-safe hybrid hash map/multi-map (a shallow prefix tree with per-slot two‑bit bitmaps and compacted type slices) that stores keys and either single value or compact value collections inline, removes per-nested-set size/hashcode overhead, and demonstrates up to 5x smaller memory footprint versus idiomatic nested maps/sets in Scala/Clojure while preserving O(1) local hash-table behavior and often improving lookup/iteration speed. Also prototypes intrinsics added to HotSpot for parallel bitmap extract/compact operations and shows faster parallel Stream API merges.
AI-written summary · about
chapters (13)
- 0:00Introduction to relations
- 0:36Properties of collections
- 1:16Implementing relations
- 3:08Explicit composition issues
- 5:06Immutable builder limits
- 6:18Designing a new data type
- 8:46The Axiom data structure
- 12:43Global property optimization
- 15:00Performance characteristics
- 17:05Platform support requirements
- 20:22Parallel stream processing
- 23:49Conclusion and outlook
- 26:12Q&A session
related talks
25mHigh on Cardinality, Low on Memory
40m"Gaining Constant time Lookup over Unorganized Data"
29mMapDB - taking Java collections to the next level
01h 09mOak: A scalable off-heap allocated key-value map
59mA Hash Map for Graph Processing Workloads & a Methodology for Transactional Data Structures
52mPolymorphic record types in a lifted enbedding
46mPolymorphic Record Types in a Limited Embedding
39mData-centric Metaprogramming