Back to Search
Start Over
BQ: A Lock-Free Queue with Batching
- Source :
- SPAA
- Publication Year :
- 2022
- Publisher :
- Association for Computing Machinery (ACM), 2022.
-
Abstract
- Concurrent data structures provide fundamental building blocks for concurrent programming. Standard concurrent data structures may be extended by allowing a sequence of operations to be submitted as a batch for later execution. A sequence of such operations can then be executed more efficiently than the standard execution of one operation at a time. In this article, we develop a novel algorithmic extension to the prevalent FIFO queue data structure that exploits such batching scenarios. An implementation in C++ on a multicore demonstrates significant performance improvement of more than an order of magnitude (depending on the batch lengths and the number of threads) compared to previous queue implementations.
- Subjects :
- Multi-core processor
Linearizability
Computer science
Concurrent data structure
020207 software engineering
0102 computer and information sciences
02 engineering and technology
Parallel computing
Data structure
01 natural sciences
Computer Science Applications
Computational Theory and Mathematics
010201 computation theory & mathematics
Hardware and Architecture
Modeling and Simulation
0202 electrical engineering, electronic engineering, information engineering
Non-blocking algorithm
Concurrent computing
Performance improvement
Queue
Software
Subjects
Details
- ISSN :
- 23294957 and 23294949
- Volume :
- 9
- Database :
- OpenAIRE
- Journal :
- ACM Transactions on Parallel Computing
- Accession number :
- edsair.doi.dedup.....09985bfef90e95e5f6bce53cd41b24ce