RoaringBitmap / RoaringBitmap/CRoaring

fastunion vs |= in a loop

Open
#417 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
C
Stars
1.9k
Forks
334
Avg merge
2d 5h
Merged PRs (30d)
17

Description

I have a std::vector of Roaring64Maps

std::vector<roaring::Roaring64Map> results = // some process

When I use fastunion (probably incorrectly):

    auto sharded_results = new const roaring::Roaring64Map*[results.size()];
    for (size_t i = 0; i < results.size(); ++i) {
        sharded_results[i] = &results.data()[i];
    }

    roaring::Roaring64Map combined = roaring::Roaring64Map::fastunion(results.size(), sharded_results);

It takes almost 5 seconds to combine them. However when I just do:

    roaring::Roaring64Map combined;
      for(const auto& sharded : results) {
        combined |= sharded;
    } 

It takes 2.8 seconds. In this case I only have 4 maps, and the combined carnality ends up just above 3 million.
Am I doing something wrong or is this expected?

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Reproduce the comparison using four roaring::Roaring64Map values, the fastunion call, and the loop using operator|=. Start by tracing or benchmarking both entry points in the C++ API; done means explaining whether the timing difference is expected or identifying a reproducible performance problem.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.