[SERVER-82176] Implement effective dynamic bitset for the boolean simplifier Created: 13/Oct/23  Updated: 12/Dec/23  Resolved: 12/Dec/23

Status: Closed
Project: Core Server
Component/s: None
Affects Version/s: None
Fix Version/s: 7.3.0-rc0

Type: Task Priority: Major - P3
Reporter: Alexander Ignatyev Assignee: Alexander Ignatyev
Resolution: Fixed Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Issue split
split from SERVER-75079 Simplify boolean expressions before f... Closed
Backwards Compatibility: Fully Compatible
Sprint: QO 2023-10-30, QO 2023-11-13, QO 2023-11-27, QO 2023-12-11, QO 2023-12-25
Participants:

 Description   

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.


 Comments   
Comment by Githook User [ 12/Dec/23 ]

Author:

{'name': 'Alexander Ignatyev', 'email': 'alexander.ignatyev@mongodb.com', 'username': 'aligusnet'}

Message: SERVER-82176 Use inlined DynamicBitset in bitset algebra

GitOrigin-RevId: 136fbd7e898a8ddb7723011dab5b6185a54deea6
Branch: master
https://github.com/mongodb/mongo/commit/5930bc45a7be3cc1df50ad5ddfbf3c2468b2f63f

Comment by Githook User [ 11/Dec/23 ]

Author:

{'name': 'Alexander Ignatyev', 'email': 'alexander.ignatyev@mongodb.com', 'username': 'aligusnet'}

Message: SERVER-82176 Replace Minterm class by BitsetTerm

There is no need in a separate implementation of Minterm class, BitsetTerm can do everything required from Minterm.

GitOrigin-RevId: b82b37ad919245cf3cfb49d62d3003ab766ed4f6
Branch: master
https://github.com/mongodb/mongo/commit/820cada9968336a280eda2e299d8022c79fd0bf0

Comment by Githook User [ 07/Dec/23 ]

Author:

{'name': 'Alexander Ignatyev', 'email': 'alexander.ignatyev@mongodb.com', 'username': 'aligusnet'}

Message: SERVER-82176 Replace boost dynamic_bitset by inlined one in Petrick

GitOrigin-RevId: 386bd87c47c11be16e0caaa47b579fd3835aa0e4
Branch: master
https://github.com/mongodb/mongo/commit/96d51f5345796f070b734bec58e0a66e89d2f8b5

Comment by Githook User [ 06/Dec/23 ]

Author:

{'name': 'Alexander Ignatyev', 'email': 'alexander.ignatyev@mongodb.com', 'username': 'aligusnet'}

Message: SERVER-82176 Implement dynamic bitset

GitOrigin-RevId: 64ba074c84125e844924db74ed46bf6d932bcb0c
Branch: master
https://github.com/mongodb/mongo/commit/27aff485a8398ea168c9399a3567fced16221376

Comment by Githook User [ 01/Dec/23 ]

Author:

{'name': 'Alexander Ignatyev', 'email': 'alexander.ignatyev@mongodb.com', 'username': 'aligusnet'}

Message: SERVER-82176 Implement storage for inlined dynamic bitset
Branch: master
https://github.com/mongodb/mongo/commit/4ce72db6b548dad5a00a778b6970ff3247b6f9e7

Generated at Thu Feb 08 06:48:27 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.