lock-free-data-structure
Skill17 starsChanged 9 months agoApache-2.0View on GitHub
Implement lock-free and wait-free data structures for high-concurrency systems.
In this repository98 other files it gives its agents.
- abstract-interpretation-engineSkill
- abstract-machineSkill
- acsl-annotation-assistantSkill
- actor-model-implementerSkill
- algebraic-effectsSkill
- alias-and-points-to-analysisSkill
- axiomatic-semanticsSkill
- bidirectional-type-checkingSkill
- bisimulation-checkerSkill
- capability-systemSkill
- closure-converterSkill
- common-subexpression-eliminatorSkill
- concurrency-verifierSkill
- constant-propagation-passSkill
- contextual-equivalenceSkill
- control-flow-analysisSkill
- coq-proof-assistantSkill
- cps-transformerSkill
- dafny-verifierSkill
- dataflow-analysis-frameworkSkill
- dead-code-eliminatorSkill
- defunctionalizationSkill
- denotational-semantics-builderSkill
- dependent-type-implementerSkill
- dsl-embeddingSkill
- effect-handlers-implementerSkill
- effect-systemSkill
- effect-type-systemSkill
- escape-analysisSkill
- existential-typesSkill
- ffi-designerSkill
- fuzzer-generatorSkill
- gadt-implementerSkill
- garbage-collector-implementerSkill
- graalvm-truffle-implementerSkill
- gradual-typing-implementerSkill
- higher-order-abstract-syntaxSkill
- hoare-logic-verifierSkill
- incremental-computationSkill
- information-flow-analyzerSkill
- inline-expanderSkill
- interprocedural-analysisSkill
- invariant-generatorSkill
- jit-compiler-builderSkill
- lambda-calculus-interpreterSkill
- language-server-protocolSkill
- lean-proverSkill
- lexer-generatorSkill
- linear-type-implementerSkill
- liveness-analysisSkill
- llvm-backend-generatorSkill
- loop-optimizerSkill
- loop-termination-proverSkill
- macro-expanderSkill
- memory-allocatorSkill
- message-passing-systemSkill
- mlir-dialect-designerSkill
- model-checkerSkill
- module-systemSkill
- monad-transformerSkill
- The first 60 shown.
The file
We split this skill into the rules it gives an agent
8 rules. About 0 are common, 8 are distinctive, and 0 are very specific to this project.
≈0
Common · estimate
Many files like this have a rule of this kind.
≈8
Distinctive · estimate
This author's own choices. Worth a look.
0
Very specific
Tied to their project's names, files or tools. Probably skip.
- Common
- Distinctive
- Very specific
- Distinctive: line 25
CAS Operations: Use compare-and-swap for atomic updates
- Distinctive: line 28
Progress Guarantees: Ensure lock-free or wait-free progress
- Distinctive: line 44
Use atomic primitives (CAS, FAA) for lock-free code
- Distinctive: line 47
Test extensively with thread sanitizers
- Distinctive: line 48
Consider using existing libraries (crossbeam, kotlinx)
- Distinctive: line 86
When simplicity is more important than performance
- Distinctive: line 87
When memory ordering is platform-specific
- Distinctive: line 93
Not all algorithms have lock-free versions
≈ “Common” is an estimate: at least 1 in 5 of the 350,495 skill files we read have a rule of the same kind, not the same words. “Very specific” is our guess from the words: it names a file, a command, a setting or the project itself.
Files
Lock-Free Data Structure
Lock-free data structures allow multiple threads to access shared data without using locks, enabling better scalability and avoiding issues like deadlocks and priority inversion.
When to Use This Skill
- Building high-performance concurrent systems
- Avoiding lock-related issues (deadlocks, convoying)
- Real-time systems requiring wait-free guarantees
- High-contention scenarios
- Scalable server applications
What This Skill Does
- CAS Operations: Use compare-and-swap for atomic updates
- Memory Reclamation: Safe memory reclamation (hazard pointers, RCU)
- ABA Prevention: Handle ABA problem in lock-free algorithms
- Progress Guarantees: Ensure lock-free or wait-free progress
- Correctness Verification: Prove linearizability
Key Concepts
| Concept | Description |
| CAS | Compare-And-Swap atomic operation |
| Lock-Free | At least one thread makes progress |
| Wait-Free | Every thread completes in bounded steps |
| Linearizability | Operations appear atomic |
| ABA Problem | Value changes A→B→A, CAS succeeds incorrectly |
| Hazard Pointer | Safe memory reclamation scheme |
Tips
- Use atomic primitives (CAS, FAA) for lock-free code
- Implement safe memory reclamation (hazard pointers, EBR)
- Be aware of the ABA problem
- Test extensively with thread sanitizers
- Consider using existing libraries (crossbeam, kotlinx)
Common Use Cases
- High-throughput message queues
- Concurrent caches
- Real-time trading systems
- Game engines
- Database systems
Related Skills
concurrency-verifier- Verify correctnessmessage-passing-system- Alternative concurrency modelmemory-allocator- Lock-free allocatorstransactional-memory- Alternative to lock-free
Canonical References
| Reference | Why It Matters |
| Herlihy & Shavit "The Art of Multiprocessor Programming" | Comprehensive treatment |
| Maged M. Michael & Michael L. Scott "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms" (PODC 1996) | Classic queue algorithm |
| Michael "Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects" (TPDS 2004) | Memory reclamation |
Tradeoffs and Limitations
Approach Tradeoffs
| Approach | Pros | Cons |
| Lock-free | No deadlocks, scalable | Complex, ABA issues |
| Wait-free | Guaranteed progress | Very complex |
| Lock-based | Simple | Deadlocks, contention |
When NOT to Use This Skill
- Low-contention scenarios (locks are fine)
- When simplicity is more important than performance
- When memory ordering is platform-specific
Limitations
- Memory reclamation is tricky
- ABA problem requires careful handling
- Not all algorithms have lock-free versions
Assessment Criteria
A high-quality implementation should have:
| Criterion | What to Look For |
| Correctness | Linearizable operations |
| Progress | Lock-free or wait-free |
| Safety | No use-after-free |
| Performance | Scales with thread count |
Quality Indicators
✅ Good: Linearizable, proper memory reclamation, handles ABA ⚠️ Warning: Works but has memory safety issues ❌ Bad: Race conditions, memory leaks, not actually lock-free
Research Tools & Artifacts
Real-world lock-free data structures:
| Tool | Why It Matters |
| crossbeam (Rust) | Lock-free data structures |
| ConcurrentSkipList | Java concurrent skiplist |
| ConcurrentHashMap | Java CHM |
| boost.lockfree | C++ lock-free |
| disruptor | LMAX Disruptor |
Key Libraries
- crossbeam: Rust concurrency
- java.util.concurrent: Java concurrent
Research Frontiers
Current lock-free research:
| Direction | Key Papers | Challenge |
| Linearizability | "Linearizability" (1990) | Verification |
| Epoch-based | "Epoch Reclamation" | Memory reclamation |
| Hybrid | "Hybrid Reclamation" | Combining approaches |
Hot Topics
- Lock-free for Wasm: WebAssembly concurrency
- Quantum lock-free: Quantum data structures
Implementation Pitfalls
Common lock-free bugs:
| Pitfall | Real Example | Prevention |
| ABA | CAS succeeds on reused node | Tag pointers |
| Memory | Use-after-free | Hazard pointers |
| Ordering | Wrong memory order | Careful ordering |
Does it work?
Reviews from people and from AI agents that ran it: what they used it for, and whether it worked.
Reviews can't be read right now.
Your trail
Files you open will collect here, so you can find them again.
Open two or more, and you can remix the rules you like from each into one list. Kept in this browser only.
Now do this for your own.
Bring your CLAUDE.md, AGENTS.md or skills. agentleFS shows which of your rules are common, which are yours and which only fit one project, and keeps one version your agents read everywhere.