RoaringBitmap / RoaringBitmap/roaring
Use vector instructions for union2by2
Nobody has claimed this yet.
- Dominant language
- Go
- Stars
- 2.9k
- Forks
- 262
- Avg merge
- 2h 34m
- Merged PRs (30d)
- 8
Description
We have ARM assembly for union2by2 as per https://github.com/RoaringBitmap/roaring/pull/287
It should be said that there are vectorized algorithm (hint: ARM NEON) for union routines. It appears in the C code (for SSE only but it is portable).
https://github.com/RoaringBitmap/CRoaring/blob/master/src/array_util.c#L1569-L1647
It is described in section 4.3 of the following paper:
- Roaring Bitmaps: Implementation of an Optimized Software Library, Software: Practice and Experience 48 (4), 2018
It is actually not difficult to implement. For someone that is either fluent in ARM NEON or wants to learn... it is a great project.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the ARM assembly for union2by2 from pull request 287, then compare it with the vectorized union routines in CRoaring's src/array_util.c at lines 1569-1647 and section 4.3 of the referenced paper. The work is complete when union2by2 uses the corresponding ARM NEON approach while preserving the routine's union behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go
- Domain
- performance
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100