Please use this identifier to cite or link to this item: https://elib.belstu.by/handle/123456789/69406
Title: Thread-safe bitset with fast extract min operation
Authors: Karasik, Oleg Nikolayevich
Prihozhy, Anatoly Alexievich
Keywords: bitset
concurrent data structure
find first set bit
extract min
Issue Date: 2025
Publisher: БГТУ
Citation: Karasik O. N., Prihozhy А. А. Thread-safe bitset with fast extract min operation // Труды БГТУ. Сер. 3, Физико-математические науки и информатика. 2025. № 1 (290). С. 62–69
Abstract: Even in today’s ever-changing world where every modern PC, game console, mobile device, or TV is equipped with GBs of RAM and CPUs have multiple cores, fast, thread-safe, space-efficient data structures remain an active field of research. Bitsets (binary array of individually accessible bits) have many applications in various industry domains like operating systems, database design, searching and allocating resources. The existing implementations of bitsets are mainly focused on compression and encoding of bits to reduce memory footprint, disk storage consumption and speed up bulk bitwise operations (primarily in cases of search and database design), or on low- and non-concurrent scenarios for tracking and allocating resources, or on the usage of bitset as a set of unique integers to insert, remove and test their presence. This paper proposes the implementation of fast, thread-safe bitset designed for high-concurrent scenarios like reservation and tracking of resources. High performance is achieved using an additional index array and a novel non-blocking synchronization mechanism. Experiments carried out on a server equipped with two Intel Xeon E5-2620 v4 processors have shown the speedup of 2 – 6 times compared to implementation which uses standard blocking synchronization mechanisms like mutexes and locks
URI: https://elib.belstu.by/handle/123456789/69406
Appears in Collections:выпуск журнала постатейно

Files in This Item:
File Description SizeFormat 
10.Karasik.pdf832.46 kBAdobe PDFView/Open



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.