Concurrent Size
summary
Presents a methodology that adds a linearizable size operation to sets and dictionaries by publishing small metadata per thread and using a snapshot of metadata rather than the whole structure; each update increments an insertion counter or deletion counter and operations help complete metadata updates for others. Claims a wait-free size with time complexity linear in thread count, implements it in Java (skip list, hash table, tree), shows orders-of-magnitude faster than full-snapshot approaches and 1%–20% throughput overhead; code is on GitHub.
AI-written summary · about
chapters (13)
- 0:00Start
- 1:33Attempt: Naïve Traversal
- 6:01Our Methodology
- 8:24Example: Transformed ins(k)
- 10:37Update Metadata
- 13:11Concurrent Inserts, Deletes
- 15:33Construction Summary
- 16:12Details in the Paper
- 16:55Evaluation
- 18:42Size Scalability
- 19:30Effect on Original Set Operations
- 21:25Compute Size from Metadata
- 23:29Throughput Insensitive to Set Size
related talks
19mEfficient Linearizability Monitoring
49mStriving to Make Things Simple and Fast
36mImplementing wait-free space bounded shared memory primitives on concurrent systems
14mVerifying Concurrent Multicopy Search Structures
55m “High Performance C++ Concurrent Transactional Data Structures"
25mMaking Hash Parallel, Thread-Safe and Fast!
10mEfficient Decrease-And-Conquer Linearizability Monitoring
39mLet's talk concurrency