Reimplementation and Performance Evaluation of a Lock-free Queue with Batching

This paper describes an implementation of a lock-free queue that utilizes batching to increase performance by up to 16x over standard lock-free queues. We attempted to implement the design and algorithms from the original research paper BQ: A Lock-Free Queue with Batching and tried to reproduce similar functionality and performance. The original implementation of this data structure was done in C++, but we wanted to try and build this in Java so we could compare the results of how the data structure performs in two different languages.

Content

Author and article information

Journal

Title: ScienceOpen Preprints

Publisher: ScienceOpen

Publication date (Electronic preprint): 31 May 2019

Affiliations

[1 ] UCF

Author information

Daniel Motta https://orcid.org/0000-0002-0849-3044

Article

DOI: 10.14293/S2199-1006.1.SOR-.PPHO1JO.v1

SO-VID: bcd2b838-91b5-43a4-aa5a-50dade0c92d5

License:

This work has been published open access under Creative Commons Attribution License CC BY 4.0 , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Conditions, terms of use and publishing policy can be found at www.scienceopen.com .

History

Data availability: The datasets generated during and/or analysed during the current study are available from the corresponding author on reasonable request.

ScienceOpen disciplines: Data structures & Algorithms

Keywords: lock-free queue,batching