Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-82176

Implement effective dynamic bitset for the boolean simplifier

    • Type: Icon: Task Task
    • Resolution: Fixed
    • Priority: Icon: Major - P3 Major - P3
    • 7.3.0-rc0
    • Affects Version/s: None
    • Component/s: None
    • None
    • Fully Compatible
    • QO 2023-10-30, QO 2023-11-13, QO 2023-11-27, QO 2023-12-11, QO 2023-12-25

      boost::dynamic_bitset<> demonstrate poor performance on bit operation since it uses internally an std::vector and allocates on any operation that produces a new bitset, such as bitwise and.

      std::vector<> does not allocate on bit operations and, according to our benchmarks, is about 100 times faster that boost::dynamic_bitset<>. Unfortunately, its size must be specified in compile time and, therefore, is not suitable for our purposes.

      We need to implement a new dynamic bitset which is:

      • uses inlined storage for small bitsets (e.g. <= 64 bits) and, therefore, never allocates on operations with small bitsets
      • provides comparable performance to std::bitset<> on small bitsets.
      • faster than boost::dynamic_bitset<> on bitsets of any sizes.

            Assignee:
            alexander.ignatyev@mongodb.com Alexander Ignatyev
            Reporter:
            alexander.ignatyev@mongodb.com Alexander Ignatyev
            Votes:
            0 Vote for this issue
            Watchers:
            5 Start watching this issue

              Created:
              Updated:
              Resolved: