DROPS

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2021.60

Brief Announcement: Crystalline: Fast and Memory Efficient Wait-Free Reclamation

Authors: Ruslan Nikolaev and Binoy Ravindran

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract

We present a new wait-free memory reclamation scheme, Crystalline, that simultaneously addresses the challenges of high performance, high memory efficiency, and wait-freedom. Crystalline guarantees complete wait-freedom even when threads are dynamically recycled, asynchronously reclaims memory in the sense that any thread can reclaim memory retired by any other thread, and ensures (an almost) balanced reclamation workload across all threads. The latter two properties result in Crystalline’s high performance and high memory efficiency, a difficult trade-off for most existing schemes. Our evaluations show that Crystalline exhibits outstanding scalability and memory efficiency, and achieves superior throughput than state-of-the-art reclamation schemes as the number of threads grows.

Cite as

Ruslan Nikolaev and Binoy Ravindran. Brief Announcement: Crystalline: Fast and Memory Efficient Wait-Free Reclamation. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 60:1-60:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{nikolaev_et_al:LIPIcs.DISC.2021.60,
  author =	{Nikolaev, Ruslan and Ravindran, Binoy},
  title =	{{Brief Announcement: Crystalline: Fast and Memory Efficient Wait-Free Reclamation}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{60:1--60:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.60},
  URN =		{urn:nbn:de:0030-drops-148626},
  doi =		{10.4230/LIPIcs.DISC.2021.60},
  annote =	{Keywords: memory reclamation, wait-free, reference counting, hazard pointers}
}

Document

DOI: 10.4230/LIPIcs.DISC.2019.28

A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue

Authors: Ruslan Nikolaev

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract

We present a new lock-free multiple-producer and multiple-consumer (MPMC) FIFO queue design which is scalable and, unlike existing high-performant queues, very memory efficient. Moreover, the design is ABA safe and does not require any external memory allocators or safe memory reclamation techniques, typically needed by other scalable designs. In fact, this queue itself can be leveraged for object allocation and reclamation, as in data pools. We use FAA (fetch-and-add), a specialized and more scalable than CAS (compare-and-set) instruction, on the most contended hot spots of the algorithm. However, unlike prior attempts with FAA, our queue is both lock-free and linearizable. We propose a general approach, SCQ, for bounded queues. This approach can easily be extended to support unbounded FIFO queues which can store an arbitrary number of elements. SCQ is portable across virtually all existing architectures and flexible enough for a wide variety of uses. We measure the performance of our algorithm on the x86-64 and PowerPC architectures. Our evaluation validates that our queue has exceptional memory efficiency compared to other algorithms and its performance is often comparable to, or exceeding that of state-of-the-art scalable algorithms.

Cite as

Ruslan Nikolaev. A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{nikolaev:LIPIcs.DISC.2019.28,
  author =	{Nikolaev, Ruslan},
  title =	{{A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.28},
  URN =		{urn:nbn:de:0030-drops-113356},
  doi =		{10.4230/LIPIcs.DISC.2019.28},
  annote =	{Keywords: FIFO, queue, ring buffer, lock-free, non-blocking}
}

Search Results

Documents authored by Nikolaev, Ruslan

Brief Announcement: Crystalline: Fast and Memory Efficient Wait-Free Reclamation

Abstract

Cite as

A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue

Abstract

Cite as

Thanks for your feedback!

Could not send message