Document Open Access Logo

Reuse, Don't Recycle: Transforming Lock-Free Algorithms That Throw Away Descriptors

Authors Maya Arbel-Raviv, Trevor Brown

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.4.pdf
  • Filesize: 1.76 MB
  • 16 pages

Document Identifiers

Author Details

Maya Arbel-Raviv
Trevor Brown

Cite As Get BibTex

Maya Arbel-Raviv and Trevor Brown. Reuse, Don't Recycle: Transforming Lock-Free Algorithms That Throw Away Descriptors. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.4

Abstract

In many lock-free algorithms, threads help one another, and each operation creates a descriptor that describes how other threads should help it. Allocating and reclaiming descriptors introduces significant space and time overhead. We introduce the first descriptor abstract data type (ADT), which captures the usage of descriptors by lock-free algorithms. We then develop a weak descriptor ADT which has weaker semantics, but can be implemented significantly more efficiently. We show how a large class of lock-free algorithms can be transformed to use weak descriptors, and demonstrate our technique by transforming several algorithms, including the leading k-compare-and-swap (k-CAS) algorithm. The original k-CAS algorithm allocates at least k+1 new descriptors per k-CAS. In contrast, our implementation allocates two descriptors per process, and each process simply reuses its two descriptors. Experiments on a variety of workloads show significant performance improvements over implementations that reclaim descriptors, and reductions of up to three orders of magnitude in peak memory usage.

Subject Classification

Keywords
  • Concurrency
  • data structures
  • lock-free
  • synchronization
  • descriptors

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Yehuda Afek, Dalia Dauber, and Dan Touitou. Wait-free made fast. In Proceedings of STOC'95, pages 538-547, 1995. Google Scholar
  2. James H. Anderson and Mark Moir. Universal constructions for multi-object operations. In Proceedings of PODC'95, pages 184-193, 1995. Google Scholar
  3. Hagit Attiya and Eshcar Hillel. Highly concurrent multi-word synchronization. Theoretical Computer Science, 412(12):1243-1262, 2011. Google Scholar
  4. Greg Barnes. A method for implementing lock-free shared-data structures. In Proceedings of SPAA'93, pages 261-270, 1993. Google Scholar
  5. Alex Brodsky, Faith Ellen, and Philipp Woelfel. Fully-adaptive algorithms for long-lived renaming. Distributed Computing, 24(2):119, 2011. Google Scholar
  6. Trevor Brown. Reclaiming memory for lock-free data structures. In Proceedings of PODC'15, pages 261-270, 2015. Google Scholar
  7. Trevor Brown. Techniques for Constructing Efficient Data Structures. PhD thesis, University of Toronto, 2017. Google Scholar
  8. Trevor Brown. A template for implementing fast lock-free trees using HTM. In Proceedings of PODC'17, pages 293-302, 2017. Google Scholar
  9. Trevor Brown, Faith Ellen, and Eric Ruppert. Pragmatic primitives for non-blocking data structures. In Proceedings of PODC'13, pages 13-22, 2013. Google Scholar
  10. Trevor Brown, Faith Ellen, and Eric Ruppert. A general technique for non-blocking trees. In Proceedings of PPoPP'14, pages 329-342, 2014. Google Scholar
  11. Mathieu Desnoyers, Paul E. McKenney, Alan S. Stern, Michel R. Dagenais, and Jonathan Walpole. User-level implementations of Read-Copy Update. IEEE Transactions on Parallel and Distributed Systems, 23(2):375-382, 2012. Google Scholar
  12. Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. Non-blocking binary search trees. In Proceedings of PODC'10, pages 131-140, 2010. Google Scholar
  13. Timothy L. Harris. A pragmatic implementation of non-blocking linked-lists. In Proceedings of DISC'01, pages 300-314, 2001. Google Scholar
  14. Timothy L. Harris, Keir Fraser, and Ian A. Pratt. A practical multi-word compare-and-swap operation. In Proceedings of DISC'02, pages 265-279, 2002. Google Scholar
  15. Meng He and Mengdu Li. Deletion without rebalancing in non-blocking binary search trees. In Proceedings of OPODIS'16, pages 34:1-34:17, 2017. Google Scholar
  16. Shane V. Howley and Jeremy Jones. A non-blocking internal binary search tree. In Proceedings of SPAA '12, pages 161-171, 2012. Google Scholar
  17. Amos Israeli and Lihu Rappoport. Disjoint-access-parallel implementations of strong shared memory primitives. In Proceedings of PODC'94, pages 151-160, 1994. Google Scholar
  18. Prasad Jayanti and Srdjan Petrovic. Efficiently implementing a large number of LL/SC objects. In Proceedings of OPODIS'05, pages 17-31, 2005. Google Scholar
  19. Yujie Liu, Tingzhe Zhou, and Michael Spear. Transactional acceleration of concurrent data structures. In Proceedings of SPAA'15, pages 244-253, 2015. Google Scholar
  20. Victor Luchangco, Mark Moir, and Nir Shavit. Nonblocking k-compare-single-swap. Theory of Computing Systems, 44(1):39-66, January 2009. Google Scholar
  21. Virendra Jayant Marathe and Mark Moir. Toward high performance nonblocking software transactional memory. In Proceedings of PPoPP'08, pages 227-236, 2008. Google Scholar
  22. Maged M. Michael. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of SPAA'02, pages 73-82, 2002. Google Scholar
  23. Maged M. Michael. Hazard pointers: Safe memory reclamation for lock-free objects. IEEE Trans. Parallel Distrib. Syst., 15(6):491-504, June 2004. Google Scholar
  24. Mark Moir. Practical implementations of non-blocking synchronization primitives. In Proceedings of PODC '97, pages 219-228, 1997. Google Scholar
  25. Aravind Natarajan and Neeraj Mittal. Fast concurrent lock-free binary search trees. In Proceedings of PPoPP '14, pages 317-328, 2014. Google Scholar
  26. Niloufar Shafiei. Non-blocking patricia tries with replace operations. In Proceedings of ICDCS'13, pages 216-225, 2013. Google Scholar
  27. John D. Valois. Lock-free linked lists using compare-and-swap. In Proceedings of PODC'95, pages 214-222, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact