1. Introduction
  2. 1. This Book
    1. 1.1. A Message
  3. 2. Concurrency
    1. 2.1. Keywords
  4. 3. Atomics
    1. 3.1. What are Memory Orderings?
    2. 3.2. Compare-and-Swap
  5. 4. Introduction to the Paper
    1. 4.1. Structure: Memory
    2. 4.2. Structure: Synchronization
    3. 4.3. The Algorithm
  6. 5. Starting Code
  7. 6. Memory Allocation
    1. 6.1. get
    2. 6.2. allocate_bucket
    3. 6.3. reserve
  8. 7. Operations
    1. 7.1. new
    2. 7.2. complete_write
    3. 7.3. push
    4. 7.4. pop
    5. 7.5. size
    6. 7.6. tests
  9. 8. Memory Reclamation
    1. 8.1. Hazard Pointers
    2. 8.2. Fixing complete_write
    3. 8.3. Fixing push & pop
    4. 8.4. Dropping the vector
    5. 8.5. Final tests!
  10. 9. Reflections
    1. 9.1. A Potential Optimization
    2. 9.2. unsafe code
    3. 9.3. Atomic Intuition
    4. 9.4. Debugging
  11. 10. Acknowledgements
  12. 11. Helpful Resources

Building a Rusty, Lock-free Dynamically Resizable Array

Helpful Resources

  • Rust Standard Library Documentation
  • Jon Gjenset's Youtube Channel
  • The Book
  • The Rust Reference
  • The Rustonomicon
  • Preshing's Blog (especially his content on atomics and lock-free programming!)
  • Learn Rust With Entirely Too Many Linked Lists

Reading source code is a great way to learn!

  • crossbeam_queue
  • crossbeam_utils
  • atomic
  • haphazard
  • std::vec::Vec (also check out RawVec)