Implement copy on write roaring bitmaps #780
Merged
+701
−1
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
|
||
| // Test iteration | ||
| int count = 0; | ||
| for (int value : cow) { |
Check notice
Code scanning / CodeQL
Unread local variable Note test
|
|
||
| // Original should still have 100 elements | ||
| int originalCount = 0; | ||
| for (int value : immutable) { |
Check notice
Code scanning / CodeQL
Unread local variable Note test
Contributor
Author
|
@lemire Can you help me review this ? |
Member
|
This looks very reasonable. Would you add a short section to the README file? |
Contributor
Author
Done. Thanks ! Let me know if anything else required. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Copy-on-Write Implementation for Roaring Bitmap
Overview
This document provides a comprehensive explanation of the copy-on-write (CoW) implementation for Roaring Bitmap, specifically addressing GitHub issue #193. The implementation enables efficient conversion of memory-mapped Roaring Bitmaps to mutable bitmaps by sharing containers until modification is required.
What is Copy-on-Write?
Copy-on-Write is a resource management technique where multiple copies of data can share the same underlying storage until one of them needs to modify the data. At that point, a private copy is created for the modifier, while other references continue to share the original data.
Benefits
Memory Efficiency: Shared containers reduce memory usage
Lazy Evaluation: Containers are only copied when modified.
**High-Level Design
ImmutableRoaringBitmap
↓
toMutableRoaringBitmapCopyOnWrite()
↓
CopyOnWriteRoaringBitmap
↓
[Shared Containers] → [Private Copy on Modify]**
Key Components
CopyOnWriteRoaringBitmap: Main class extending MutableRoaringBitmap
needsCopy Array: Tracks which containers require copying
appendCopyOnWrite Methods: Enable container sharing in MutableRoaringArray
Lazy Copying Logic: Defers container duplication until modification