THREAD-SAFE BITSET WITH FAST EXTRACT MIN OPERATION

UDC 004.272.2

Karasik Oleg Nikolayevich − PhD (Engineering), Lead Engineer, ISsoft Solutions (5 Chapaeva str., 220034, Minsk, Republic of Belarus). E-mail: karasik.oleg.nikolaevich@gmail.com

Prihozhy Anatoly Alexievich − DSc (Engineering), Professor, Professor, the Department of Computer and System Software. Belarusian National Technical University (65 Nezavisimosti Ave., 220013, Minsk, Republic of Belarus). E-mail: prihozhy@bntu.by

DOI: https://doi.org/ 10.52065/2520-6141-2025-290-10.

Key words: bitset, concurrent data structure, find first set bit, extract min.

For citation: Karasik O. N., Prihozhy А. А. Thread-safe bitset with fast extract min operation. Proceedings of BSTU, issue 3, Physics and Mathematics. Informatics, 2025, no. 1 (290), pp. 62–69. DOI: 10.52065/2520-6141-2025-290-10.

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.

Download

References

  1. Chambi S., Lemire D., Kaser O., Godin R. Better bitmap performance with Roaring bitmaps. Software: Practice and Experience, 2015, vol. 46, no. 5, pp. 709–719. DOI: 10.1002/spe.2325.
  2. Corrales F., Chiu D., Sawin J. Variable length compression for bitmap indices: Database and Expert Systems Applications: 22nd International Conference, 2011, vol. 2, pp. 381–395.
  3. Goodwin B., Hopcroft M., Luu D., Clemmer A., Curmei M., Elnikety S., He Y. BitFunnel: Revisiting Signatures for Search. SIGIR'17: Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2017, pp. 605–614. DOI: 10.1145/3077136.3080789.
  4. Liang W., Shi W., Liao Z., Qian S., Zheng Z., Cao J., Xue G. BOP: A Bitset-based Optimization Paradigm for Content-based Event Matching Algorithms (S). SEKE 2023: The 35th International Conference on Software Engineering and Knowledge Engineering, 2023, pp. 487–492. DOI: 10.18293/SEKE2023-142.
  5. VanCompernolle M., Barford L., Harris F. Maximum Clique Solver Using Bitsets on GPUs. Information Technology: New Generations, 2016, pp. 327–337.
  6. Gueniche T., Fournier-Viger P., Tseng V. S. Compact Prediction Tree: A Lossless Model for Accurate Sequence Prediction. Advanced Data Mining and Applications, 2013, pp. 177–188.
  7. McIlroy R., Dickman P., Sventek J. Efficient dynamic heap allocation of scratch-pad memory: ISMM'08: Proceedings of the 7th international symposium on Memory management, 2008, pp. 31–40.
  8. Terci G. S., Abdulhalik E., Bayrakci A. A., Boz B. BitEA: BitVertex Evolutionary Algorithm to Enhance Performance for Register Allocation, IEEE Access, 2024. vol. 12, pp. 115497–115514. DOI: 10.1109/ACCESS.2024.34465.96.
  9. Karasik O. N., Prihozhy A. A. Cooperative multi-thread scheduler for solving large-size tasks on multi-core systems. Big Data and Advanced Analytics VI. Minsk, 2020, pp. 202–212.
  10. Karasik O. N., Prihozhy A. A. Blocked algorithm of finding all-pairs shortest paths in graphs divided into weakly connected clusters. System analysis and applied information science, 2024, no. 2, pp. 4–10. DOI: 10.21122/2309-4923-2024-2-4-10.
  11. Prihozhy A. A., Karasik O. N. New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes. System analysis and applied information science, 2023, no. 4, pp. 4–13.
  12. Prihozhy А. А., Karasik O. N. Advanced heterogeneous block-parallel all-pairs shortest path algorithm. Trudy BSTU [Proceedings of BSTU], issue 3, Physics and Mathematics. Informatics, 2023, no. 1 (266), pp. 77–83 (In Russian).
  13. Prihozhy А. A. Generation of shortest path search dataflow networks of actors for parallel multicore implementation. Informatics, 2023, vol. 20, no. 2, pp. 65–84.
  14. Prihozhy A. A. Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms. System analysis and applied information science, 2021, no. 3, pp. 40–50.
  15. Karasik O. N., Prihozhy A. A. Tuning block-parallel all-pairs shortest path algorithm for efficient multi-core implementation. System analysis and applied information science, 2022, no. 3, pp. 57–65.
  16. Prihozhy A. A., Karasik O. N. Influence of shortest path algorithms on energy consumption of multicore processors. System analysis and applied information science, 2023, no. 2, pp. 4–12.

15.11.2024