A Hash Map for Graph Processing Workloads & a Methodology for Transactional Data Structures
summary
PMap is a lock‑free, open‑addressing persistent hash map that uses C++11 compare_exchange_strong, in‑place key/value storage, per‑cacheline alignment via alignas, and a modified link‑and‑persist to avoid pointer dereferences; benchmarks on Intel Optane DC show PMap averages 3122x faster than state‑of‑the‑art alternatives (clevel, OneFile, STL, PMDK) on R‑MAT workloads. PETRA provides durable transactions via persisted descriptors and semantic conflict detection, trading expensive recovery for high throughput and scalability and imposing a practical 62-bit values limitation for compactness.
AI-written summary · about
chapters (35)
- 0:00Intro
- 0:34Title
- 0:50Overview
- 1:20Persistent Memory
- 1:43Traditional Memory
- 2:32DRAM vs Persistent Memory
- 4:33Use Cases for Persistent Memory
- 5:20Characteristics of Persistent Memory
- 6:26Architecture Limitations
- 7:05Code Example
- 10:31Design Goals
- 12:18Design Overview
- 13:27Resizing Approach
- 16:24Persistence
- 16:52Flush on Read
- 19:03link and persist
- 21:59flushing
- 22:56recovery
- 24:04related works
- 25:12testing environment
- 26:00performance testing
- 29:38taxonomy of transactional data structures
- 30:45petra
- 32:56nonblocking
- 33:58type definitions
- 35:27methodology overview
- 36:12petra transaction management
- 38:20petra in action
- 39:40petra recovery
- 41:03cascade lake
- 41:43micro benchmarks
- 42:40results
- 44:25performance trends
- 45:44live demonstration
- 50:40Key takeaways
related talks
14mSEPH: Scalable, Efficient, and Predictable Hashing on Persistent Memory
01h 08mC++ and Persistent Memory Technologies, Like Intel's 3D-XPoint
01h 05mImplementing Understandable World Class Hash Tables in C++
29mMapDB - taking Java collections to the next level
27mEfficient shared memory data structures
34mLightweight Relations
24mWrite-Optimized Dynamic Hashing for Persistent Memory
17mPIMLex: A High-Performance Learned Index with Processing-in-Memory