Use boost::dynamic_bitset instead of ConcurrentBitsetPtr · Issue #4277 · milvus-io/milvus

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement . We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Currently, the calculation of DSL is based on ConcurrentBitsetPtr , which is slow due to unnecessary atomic memory access (access every bit will always flush the cache line).

Change it with boost::dynamic_bitset<> will have the following pros:

native support for bit manipulating operations: (and, or, negate, ...), and much faster

cheap memory access comparing to


    ConcurrentBitset

can use


    boost::to_block_range

to export the internal storage (which


    vector<bool>

can't)

~~Use boost::dynamic_bitset instead of ConcurrentBitmapPtr~~ Use boost::dynamic_bitset instead of ConcurrentBitsetPtr

Nov 24, 2020

Our previous tests have shown that atomic itself is not a performance bottleneck.
But that the bitset has no access locality in IVF will result in severe performance degradation.
However, ff you find it convenient to use, you can also try to modify it.

After investigation, maybe it's better to decouple the storage and search:

For storage and DSL calculation, don't modify the code, just use the


    ConcurrentBitmapPtr

anyway;

For searching, use the following


    BitmapView

, and create a


    BitmapView

from


    ConcurrentBitmapPtr

,


    boost::dynamic_bitmap

,


    std::bitset

etc., just like


    const char*

,


    std::string

to


    std::string_view

struct BitmapView {
  const uint8_t* ptr_to_bitmap;
  int64_t size; // optional
 public:
  bool test(int64_t index) const { /* easy implementation */} 
  BitmapView(const ConcurrentBitmapPtr& con_bitmap) { /*implicit conversion*/ }
  BitmapView(const std::bitmap& bitmap) { /*implicit conversion*/ }
Pros:
Least code to modify
Adaptive to all possible bitmap
Performance is as good as vanilla bitmap