My favorite data structures
summary
Clank’s constant-evaluation engine is a 17,000 line interpreter that implements values as APValue nodes with array/union/struct variants, a pointer model based on APValue pointer model paths not addresses, and allocation keys for lifetime tracking. Work includes a compile-time hashing library CT, hacking Clank to accept exceptions in constexpr (paper P3068 moved library wording as of this morning), and designing persistent, offset-based maps like HMT hash array mapped trie for snapshotting and zero-runtime overlay. Concrete prototypes exist and most features run in the interpreter.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 2:09Compiler internals and C++
- 4:40Symbolic execution in Clang
- 15:35Lvalues vs Rvalues in constexpr
- 24:14Constexpr limitations
- 29:47Standard containers deep dive
- 36:55In-place vector and deque
- 40:33Containers not constexpr yet
- 45:17Constexpr evolution
- 50:26HAMT explained
- 57:15Proposals for constexpr
- 1:00:22Summary
- 1:00:51Q&A
related talks
17mBring Your Own Data Structures to Datalog
48mC++ Data Structures That Make Video Games Go Round
01h 05mImplementing Understandable World Class Hash Tables in C++
48mA Helicopter Tour of Purely Functional Data Structures
35mChanging the Unchangeable: The Hows and Whys of Immutable Data Structures
01h 13mC++ Memory Model Meets High-Update-Rate Data Structures
58mHow Can Package Managers Handle ABI (In)compatibility in C++?
40m"Gaining Constant time Lookup over Unorganized Data"