RFR: 8327093: Add slice function to BitMap API [v3]
Axel Boldt-Christmas
aboldtch at openjdk.org
Thu Mar 7 07:46:55 UTC 2024
On Wed, 6 Mar 2024 21:34:06 GMT, Matias Saavedra Silva <matsaave at openjdk.org> wrote:
>> The BitMap does not currently have a "slice" method which can return a subset of the bitmap defined by a start and end bit. This utility can be used to analyze portions of a bitmap or to overwrite the existing map with a shorter, modified map.
>>
>> This implementation has two core methods:
>> `copy_of_range` allocates and returns a new word array as used internally by BitMap
>> `truncate` overwrites the internal array with the one generated by `copy_of_range` so none of the internal workings are exposed to callers outside of BitMap.
>>
>> This change is verified with an included test.
>
> Matias Saavedra Silva has updated the pull request incrementally with one additional commit since the last revision:
>
> Ioi comments and moved tests
The implementation looks correct now. But there is a mix of styles with regards to const that I think should be consistent at least inside the PR. It is not really possible to unify completely with the rest of the file as there is a mix of `const` usage.
The actual style is not that important to me, but mixing styles with `const` makes me question the intent of code.
I would also have much more confidence in the implementation (and for capturing regressions) if this test could be added.
diff --git a/test/hotspot/gtest/utilities/test_bitMap.cpp b/test/hotspot/gtest/utilities/test_bitMap.cpp
index e1fc744f07a..2dcb5cfef26 100644
--- a/test/hotspot/gtest/utilities/test_bitMap.cpp
+++ b/test/hotspot/gtest/utilities/test_bitMap.cpp
@@ -148,6 +148,38 @@ class BitMapTruncateTest {
EXPECT_TRUE(map.is_same(result));
}
+ template <class ResizableBitMapClass>
+ static void testRandom() {
+ for (int i = 0; i < 100; i++) {
+ ResourceMark rm;
+
+ const size_t max_size = 1024;
+ const size_t size = os::random() % max_size + 1;
+ const size_t truncate_size = os::random() % size + 1;
+ const size_t truncate_start = size == truncate_size ? 0 : os::random() % (size - truncate_size);
+
+ ResizableBitMapClass map(size);
+ ResizableBitMapClass result(truncate_size);
+
+ for (BitMap::idx_t idx = 0; idx < truncate_start; idx++) {
+ if (os::random() % 2 == 0) {
+ map.set_bit(idx);
+ }
+ }
+
+ for (BitMap::idx_t idx = 0; idx < truncate_size; idx++) {
+ if (os::random() % 2 == 0) {
+ map.set_bit(truncate_start + idx);
+ result.set_bit(idx);
+ }
+ }
+
+ map.truncate(truncate_start, truncate_start + truncate_size);
+
+ EXPECT_TRUE(map.is_same(result));
+ }
+ }
+
template <class ResizableBitMapClass>
static void testTruncateSame() {
// Resulting map should be the same as the original
@@ -394,3 +426,12 @@ TEST_VM(BitMap, truncate_one_word) {
BitMapTruncateTest::testTruncateOneWord<TestArenaBitMap>();
EXPECT_FALSE(HasFailure()) << "Failed on type ArenaBitMap";
}
+
+TEST_VM(BitMap, truncate_random) {
+ BitMapTruncateTest::testRandom<ResourceBitMap>();
+ EXPECT_FALSE(HasFailure()) << "Failed on type ResourceBitMap";
+ BitMapTruncateTest::testRandom<TestCHeapBitMap>();
+ EXPECT_FALSE(HasFailure()) << "Failed on type CHeapBitMap";
+ BitMapTruncateTest::testRandom<TestArenaBitMap>();
+ EXPECT_FALSE(HasFailure()) << "Failed on type ArenaBitMap";
+}
Also agree with @iklam that the PR title should not mention `slice` but `truncate`
src/hotspot/share/utilities/bitMap.cpp line 110:
> 108: idx_t const cutoff = bit_in_word(end_bit);
> 109: idx_t const start_word = to_words_align_down(start_bit);
> 110: idx_t const end_word = to_words_align_up(end_bit);
Using right CV-qualifiers is very rare in HotSpot. I think there are around 600 uses and 1/3 is in the G1 code.
I do not mind either style, but this PR mixes them, and this file already uses left CV-qualifiers. It would probably be best to keep this consistent.
src/hotspot/share/utilities/bitMap.cpp line 111:
> 109: idx_t const start_word = to_words_align_down(start_bit);
> 110: idx_t const end_word = to_words_align_up(end_bit);
> 111: bm_word_t* const old_map = map();
The pointed to type should probably also be `const`. This code should not touch the old memory.
src/hotspot/share/utilities/bitMap.cpp line 113:
> 111: bm_word_t* const old_map = map();
> 112:
> 113: BitMapWithAllocator* derived = static_cast<BitMapWithAllocator*>(this);
Variable could be `const` (just like `old_map` above)
src/hotspot/share/utilities/bitMap.cpp line 115:
> 113: BitMapWithAllocator* derived = static_cast<BitMapWithAllocator*>(this);
> 114:
> 115: bm_word_t* new_map = derived->allocate(end_word - start_word);
Variable could be `const`
src/hotspot/share/utilities/bitMap.cpp line 120:
> 118: idx_t const shift = bit_in_word(start_bit);
> 119: // Bits shifted out by a word need to be passed into the next
> 120: idx_t carry = 0;
`carry` should be of type `bm_word_t` it contains bits of the payload, not an index.
src/hotspot/share/utilities/bitMap.cpp line 141:
> 139: bm_word_t* const old_map = map();
> 140:
> 141: bm_word_t* new_map = copy_of_range(start_bit, end_bit);
Variable could be `const`
src/hotspot/share/utilities/bitMap.cpp line 143:
> 141: bm_word_t* new_map = copy_of_range(start_bit, end_bit);
> 142:
> 143: BitMapWithAllocator* derived = static_cast<BitMapWithAllocator*>(this);
Variable could be `const`
-------------
Changes requested by aboldtch (Reviewer).
PR Review: https://git.openjdk.org/jdk/pull/18092#pullrequestreview-1921642108
PR Review Comment: https://git.openjdk.org/jdk/pull/18092#discussion_r1515669936
PR Review Comment: https://git.openjdk.org/jdk/pull/18092#discussion_r1515670841
PR Review Comment: https://git.openjdk.org/jdk/pull/18092#discussion_r1515672496
PR Review Comment: https://git.openjdk.org/jdk/pull/18092#discussion_r1515672703
PR Review Comment: https://git.openjdk.org/jdk/pull/18092#discussion_r1515673268
PR Review Comment: https://git.openjdk.org/jdk/pull/18092#discussion_r1515674184
PR Review Comment: https://git.openjdk.org/jdk/pull/18092#discussion_r1515674256
More information about the hotspot-dev
mailing list