Bring Your Own Data Structures to Datalog
summary
Claims a compiler and runtime that let analyses plug Bring Your Own Data Structures into a Datalog engine via a Rust embedded DSL and procedural macros, with a trait-based runtime protocol for reads, writes and semi-naïve evaluation. Prototype compiles to efficient kernels and runs comparable to Soufflé while enabling special structures like Union-find transitive relations. Reproductions show Polonius runs ~2× faster and uses 1.5–2× less memory, transitive tests hit up to 10× time and 30× memory wins, PageRank scales ~40× at 64 threads, and an LLVM analysis enumerates 5.3B points in 7.3h (8 threads) and 2.7h (32 threads).
AI-written summary · about
chapters (13)
- 0:00Datalog and applications
- 3:34Why Datalog is useful
- 5:40Data structure mismatches
- 6:44Bring Your Own Data Structures
- 8:08Integrating user-defined structures
- 9:30BODess performance with Ascent
- 10:14Polonius case study
- 10:56Transitive closure with Union-Find
- 11:59Parallelism in PageRank
- 12:23LLVM analysis with BODess
- 13:24Index sharing in pointer analysis
- 14:28Conclusion and future
- 15:19Q&A: Negation and limits
related talks
13mAccelerating Program Analyses in Datalog by Merging Library Facts
26mDebugging Large-Scale Datalog: A Scalable Provenance Evaluation Strategy
52mData Over Code: A Short Hyperbole
01h 01mLogic and Algebras for Distributed Computing: Applications and Open Questions
19mMaking Formulog Fast: An Argument for Unconventional Datalog Evaluation
17mFixpoints for the Masses: Programming with First-Class Datalog Constraints
17mBetter Together: Unifying Datalog and Equality Saturation
52mI See What You Mean