Speed up dirty_log() (a lot) #36
Merged
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
blitz
force-pushed
the
fast-dirty-log
branch
2 times, most recently
from
b315ec0 to
2d294ef
Compare
Instead of using ad-hoc code, just write an extension to the Iterator trait that we can easily unit test. On-behalf-of: SAP [email protected] Signed-off-by: Julian Stecklina <[email protected]>
It improves iteration code a lot! I'll use it in the upcoming commit to speed up dirty bitmap scanning. On-behalf-of: SAP [email protected] Signed-off-by: Julian Stecklina <[email protected]>
With this change, we don't need a copy of the vector. Just something that can be coerced into an iterator. We also use the bit position iterator to make the code somewhat clearer. The new code is much faster, because it will not iterate over every bit, just each 1 bit in the input. The next commit will complete this optimization and have some concrete numbers. On-behalf-of: SAP [email protected] Signed-off-by: Julian Stecklina <[email protected]>
This would be a good opportunity to optimize another pointless vector away, but I don't have a good way to test this at the moment. But maybe someone else gives it a shot. On-behalf-of: SAP [email protected] Signed-off-by: Julian Stecklina <[email protected]>
... by passing the slice along instead. On-behalf-of: SAP [email protected] Signed-off-by: Julian Stecklina <[email protected]>
... by just passing the iterator along. For large VMs this bitmap is gigantic. A 12TB VM has 384MB of dirty bitmap. With all these optimizations from the previous commits in place, we see quite the improvement when it comes to scanning the dirty bitmap. For a bitmap with 1% bits (randomly) set, dirty_log() takes: Original code: 2166ms (100.0%) New code: 382ms ( 17.6%) on my system. The sparser the dirty bitmap the faster. Scanning an empty bitmap is 100x faster. For a 5% populated bitmap we are still 3x faster. If someone wants to play with this, there is a benchmark harness here: https://github.com/blitz/chv-bitmap-bench On-behalf-of: SAP [email protected] Signed-off-by: Julian Stecklina <[email protected]>
olivereanderson
approved these changes
Nov 7, 2025
olivereanderson
left a comment
olivereanderson
left a comment
There was a problem hiding this comment.
Love these changes!
The new code definitely avoids large copies and is at least as readable as the old.
It would be interesting to see some benchmarks with real world data, but I doubt this will ever be slower than what we currently have (except perhaps for extremely dense bitmaps which should not be a common occurrence).
Member
|
We now have a ticket to track this: https://github.com/cobaltcore-dev/cobaltcore/issues/316 |
phip1611
approved these changes
Nov 10, 2025
13 tasks
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.
This is fallout from #30. I've noticed that the function that turns dirty bitmaps during migration into
MemoryRangeTableis very inefficient. It creates useless temporary vectors. It has a very basic method of finding the 1 bits in the bitmap.I've transformed the dirty bitmap scanning using iterators (without temporaries). To do that I introduced
BitposIteratorwhich takes an iterator over a bitmap and emits the positions of all 1 bits. With some Itertools magic (coalesce) we can then easily merge the resulting bit ranges.The code now:
Improvements
I've benchmarked this for a 384 MB dirty bitmap (equivalent to 12TB VM). I got the following results:
The 0% means that we are scanning the empty bitmap at 24 GB/s (on my system). I should have 56GB/s memory bandwidth, so this is pretty good without any SIMD magic.
For even dirtier bitmaps, the performance will be more equal, because it's dominated by constructing the huge vector inside of
MemoryRangeTable. This can also be optimized away (https://github.com/cobaltcore-dev/cobaltcore/issues/280) and the optimization in this PR is a first step.These numbers were generated using criterion using this harness.
Testing