This is an automated email from the ASF dual-hosted git repository. jt2594838 pushed a commit to branch add_bitmap_long_imple in repository https://gitbox.apache.org/repos/asf/tsfile.git
commit 1f89e60ce0ffd7894feb92505a8d73878803dfa9 Author: Tian Jiang <[email protected]> AuthorDate: Tue Jul 21 09:41:01 2026 +0800 Refine BitMapLongImpl --- .../main/java/org/apache/tsfile/utils/BitMap.java | 43 ++++++--------------- .../org/apache/tsfile/utils/BitMapArrayImpl.java | 42 ++++++++++++++++++++ .../java/org/apache/tsfile/utils/BitMapImpl.java | 40 +++++++++++++++++++ .../org/apache/tsfile/utils/BitMapLongImpl.java | 45 ++++++++++++++++++++++ .../apache/tsfile/utils/BitMapPerformanceTest.java | 45 +++++++++++++++++----- .../java/org/apache/tsfile/utils/BitMapTest.java | 43 +++++++++++++++++---- 6 files changed, 210 insertions(+), 48 deletions(-) diff --git a/java/common/src/main/java/org/apache/tsfile/utils/BitMap.java b/java/common/src/main/java/org/apache/tsfile/utils/BitMap.java index 8886eed72..54bfb168c 100644 --- a/java/common/src/main/java/org/apache/tsfile/utils/BitMap.java +++ b/java/common/src/main/java/org/apache/tsfile/utils/BitMap.java @@ -22,20 +22,19 @@ package org.apache.tsfile.utils; import org.apache.tsfile.i18n.Messages; import java.util.Arrays; -import java.util.Objects; public class BitMap { private BitMapImpl implementation; - /** Initialize a BitMap with given size. */ + /** Initialize an array-backed BitMap with the given size. */ public BitMap(int size) { - implementation = createImplementation(size); + implementation = new BitMapArrayImpl(size); } - /** Initialize a BitMap with given size and bytes. */ + /** Initialize an array-backed BitMap with the given size and bytes. */ public BitMap(int size, byte[] bits) { - implementation = createImplementation(size, bits); + implementation = new BitMapArrayImpl(size, bits); } BitMap(BitMapImpl implementation) { @@ -112,8 +111,8 @@ public class BitMap { @Override public int hashCode() { - int result = Objects.hash(getSize()); - result = 31 * result + Arrays.hashCode(getByteArray()); + int result = 31 + getSize(); + result = 31 * result + implementation.contentHashCode(); return result; } @@ -126,7 +125,7 @@ public class BitMap { return false; } BitMap other = (BitMap) obj; - return getSize() == other.getSize() && Arrays.equals(getByteArray(), other.getByteArray()); + return getSize() == other.getSize() && implementation.contentEquals(other.implementation); } public boolean equalsInRange(Object obj, int rangeSize) { @@ -145,22 +144,7 @@ public class BitMap { Math.min(getSize(), other.getSize()))); } - int byteSize = rangeSize / Byte.SIZE; - byte[] thisBits = getByteArray(); - byte[] otherBits = other.getByteArray(); - for (int i = 0; i < byteSize; i++) { - if (thisBits[i] != otherBits[i]) { - return false; - } - } - int remainingBits = rangeSize % Byte.SIZE; - if (remainingBits > 0) { - byte mask = (byte) (0xFF >> (Byte.SIZE - remainingBits)); - if ((thisBits[byteSize] & mask) != (otherBits[byteSize] & mask)) { - return false; - } - } - return true; + return implementation.contentEqualsInRange(other.implementation, rangeSize); } @Override @@ -248,13 +232,8 @@ public class BitMap { return size >= 0 && size <= Long.SIZE ? new BitMapLongImpl(size) : new BitMapArrayImpl(size); } - private static BitMapImpl createImplementation(int size, byte[] bits) { - return size >= 0 && size <= Long.SIZE - ? new BitMapLongImpl(size, bits) - : new BitMapArrayImpl(size, bits); - } - - public static BitMap createArrayBackedBitMap(int size) { - return new BitMap(new BitMapArrayImpl(size)); + /** Initialize a BitMap whose implementation is selected according to the given size. */ + public static BitMap createBitMapDynamically(int size) { + return new BitMap(createImplementation(size)); } } diff --git a/java/common/src/main/java/org/apache/tsfile/utils/BitMapArrayImpl.java b/java/common/src/main/java/org/apache/tsfile/utils/BitMapArrayImpl.java index f1eda3389..b55306178 100644 --- a/java/common/src/main/java/org/apache/tsfile/utils/BitMapArrayImpl.java +++ b/java/common/src/main/java/org/apache/tsfile/utils/BitMapArrayImpl.java @@ -55,6 +55,16 @@ class BitMapArrayImpl extends BitMapImpl { return bits; } + @Override + int getByteArrayLength() { + return bits.length; + } + + @Override + byte getByte(int index) { + return bits[index]; + } + @Override boolean isMarked(int position) { return (bits[position / Byte.SIZE] & BIT_UTIL[position % Byte.SIZE]) != 0; @@ -220,6 +230,38 @@ class BitMapArrayImpl extends BitMapImpl { return true; } + @Override + boolean contentEquals(BitMapImpl other) { + return other instanceof BitMapArrayImpl + ? Arrays.equals(bits, ((BitMapArrayImpl) other).bits) + : super.contentEquals(other); + } + + @Override + boolean contentEqualsInRange(BitMapImpl other, int rangeSize) { + if (!(other instanceof BitMapArrayImpl)) { + return super.contentEqualsInRange(other, rangeSize); + } + byte[] otherBits = ((BitMapArrayImpl) other).bits; + int byteSize = rangeSize / Byte.SIZE; + for (int i = 0; i < byteSize; i++) { + if (bits[i] != otherBits[i]) { + return false; + } + } + int remainingBits = rangeSize % Byte.SIZE; + if (remainingBits > 0) { + byte mask = (byte) (0xFF >> (Byte.SIZE - remainingBits)); + return (bits[byteSize] & mask) == (otherBits[byteSize] & mask); + } + return true; + } + + @Override + int contentHashCode() { + return Arrays.hashCode(bits); + } + @Override BitMapImpl copy() { return new BitMapArrayImpl(size, Arrays.copyOf(bits, bits.length)); diff --git a/java/common/src/main/java/org/apache/tsfile/utils/BitMapImpl.java b/java/common/src/main/java/org/apache/tsfile/utils/BitMapImpl.java index b95ee7253..d9f296fe2 100644 --- a/java/common/src/main/java/org/apache/tsfile/utils/BitMapImpl.java +++ b/java/common/src/main/java/org/apache/tsfile/utils/BitMapImpl.java @@ -33,6 +33,10 @@ abstract class BitMapImpl { abstract byte[] getByteArray(); + abstract int getByteArrayLength(); + + abstract byte getByte(int index); + abstract boolean isMarked(int position); abstract void markAll(); @@ -57,6 +61,42 @@ abstract class BitMapImpl { abstract boolean isAllMarked(); + boolean contentEquals(BitMapImpl other) { + int byteArrayLength = getByteArrayLength(); + if (byteArrayLength != other.getByteArrayLength()) { + return false; + } + for (int i = 0; i < byteArrayLength; i++) { + if (getByte(i) != other.getByte(i)) { + return false; + } + } + return true; + } + + boolean contentEqualsInRange(BitMapImpl other, int rangeSize) { + int byteSize = rangeSize / Byte.SIZE; + for (int i = 0; i < byteSize; i++) { + if (getByte(i) != other.getByte(i)) { + return false; + } + } + int remainingBits = rangeSize % Byte.SIZE; + if (remainingBits > 0) { + byte mask = (byte) (0xFF >> (Byte.SIZE - remainingBits)); + return (getByte(byteSize) & mask) == (other.getByte(byteSize) & mask); + } + return true; + } + + int contentHashCode() { + int result = 1; + for (int i = 0; i < getByteArrayLength(); i++) { + result = 31 * result + getByte(i); + } + return result; + } + abstract BitMapImpl copy(); abstract BitMapImpl extend(int newSize); diff --git a/java/common/src/main/java/org/apache/tsfile/utils/BitMapLongImpl.java b/java/common/src/main/java/org/apache/tsfile/utils/BitMapLongImpl.java index f3c8d64f1..2d12acba9 100644 --- a/java/common/src/main/java/org/apache/tsfile/utils/BitMapLongImpl.java +++ b/java/common/src/main/java/org/apache/tsfile/utils/BitMapLongImpl.java @@ -49,6 +49,16 @@ class BitMapLongImpl extends BitMapImpl { return bytes; } + @Override + int getByteArrayLength() { + return BitMap.getSizeOfBytes(size); + } + + @Override + byte getByte(int index) { + return index < Long.BYTES ? (byte) (bits >>> (index * Byte.SIZE)) : 0; + } + @Override boolean isMarked(int position) { return (bits & (1L << position)) != 0; @@ -124,6 +134,41 @@ class BitMapLongImpl extends BitMapImpl { return (bits & mask) == mask; } + @Override + boolean contentEquals(BitMapImpl other) { + if (!(other instanceof BitMapLongImpl)) { + return super.contentEquals(other); + } + int serializedBitSize = Math.min(getByteArrayLength() * Byte.SIZE, Long.SIZE); + long mask = lowerBitsMask(serializedBitSize); + return (bits & mask) == (((BitMapLongImpl) other).bits & mask); + } + + @Override + boolean contentEqualsInRange(BitMapImpl other, int rangeSize) { + if (!(other instanceof BitMapLongImpl)) { + return super.contentEqualsInRange(other, rangeSize); + } + long mask = lowerBitsMask(rangeSize); + return (bits & mask) == (((BitMapLongImpl) other).bits & mask); + } + + @Override + int contentHashCode() { + int result = 1; + long value = bits; + int byteArrayLength = getByteArrayLength(); + int longByteCount = Math.min(byteArrayLength, Long.BYTES); + for (int i = 0; i < longByteCount; i++) { + result = 31 * result + (byte) value; + value >>>= Byte.SIZE; + } + for (int i = Long.BYTES; i < byteArrayLength; i++) { + result *= 31; + } + return result; + } + @Override BitMapImpl copy() { BitMapLongImpl copy = new BitMapLongImpl(size); diff --git a/java/tsfile/src/test/java/org/apache/tsfile/utils/BitMapPerformanceTest.java b/java/tsfile/src/test/java/org/apache/tsfile/utils/BitMapPerformanceTest.java index cf5234ac3..5f943e3ba 100644 --- a/java/tsfile/src/test/java/org/apache/tsfile/utils/BitMapPerformanceTest.java +++ b/java/tsfile/src/test/java/org/apache/tsfile/utils/BitMapPerformanceTest.java @@ -124,10 +124,16 @@ public class BitMapPerformanceTest { regionWorkload(longBitMap()))); results.add( benchmark( - "equals/equalsInRange/hashCode", + "equals/equalsInRange", ALLOCATION_OPERATION_COUNT, - equalityWorkload(arrayBitMap(), arrayBitMap()), - equalityWorkload(longBitMap(), longBitMap()))); + equalityWorkload(BitMapPerformanceTest::arrayBitMap), + equalityWorkload(BitMapPerformanceTest::longBitMap))); + results.add( + benchmark( + "hashCode", + CHEAP_OPERATION_COUNT, + hashCodeWorkload(BitMapPerformanceTest::arrayBitMap), + hashCodeWorkload(BitMapPerformanceTest::longBitMap))); results.add( benchmark( "toString", @@ -380,15 +386,36 @@ public class BitMapPerformanceTest { }; } - private static Workload equalityWorkload(BitMap left, BitMap right) { - markAlternatingBits(left); - markAlternatingBits(right); + private static Workload equalityWorkload(BitMapFactory factory) { + BitMap[] left = new BitMap[BIT_MAP_SIZE]; + BitMap[] right = new BitMap[BIT_MAP_SIZE]; + for (int i = 0; i < BIT_MAP_SIZE; i++) { + left[i] = factory.create(); + right[i] = factory.create(); + left[i].mark(i); + right[i].mark(i); + } + return operationCount -> { + long checksum = 0; + for (int i = 0; i < operationCount; i++) { + int index = i & 63; + checksum += left[index].equals(right[index]) ? 1 : 0; + checksum += left[index].equalsInRange(right[index], BIT_MAP_SIZE) ? 2 : 0; + } + return checksum; + }; + } + + private static Workload hashCodeWorkload(BitMapFactory factory) { + BitMap[] bitMaps = new BitMap[BIT_MAP_SIZE]; + for (int i = 0; i < bitMaps.length; i++) { + bitMaps[i] = factory.create(); + bitMaps[i].mark(i); + } return operationCount -> { long checksum = 0; for (int i = 0; i < operationCount; i++) { - checksum += left.equals(right) ? 1 : 0; - checksum += left.equalsInRange(right, BIT_MAP_SIZE) ? 2 : 0; - checksum += left.hashCode(); + checksum += bitMaps[i & 63].hashCode(); } return checksum; }; diff --git a/java/tsfile/src/test/java/org/apache/tsfile/utils/BitMapTest.java b/java/tsfile/src/test/java/org/apache/tsfile/utils/BitMapTest.java index 2199f60fe..256a8cd41 100644 --- a/java/tsfile/src/test/java/org/apache/tsfile/utils/BitMapTest.java +++ b/java/tsfile/src/test/java/org/apache/tsfile/utils/BitMapTest.java @@ -26,6 +26,7 @@ import java.util.Random; import static org.junit.Assert.assertArrayEquals; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertNotEquals; import static org.junit.Assert.assertTrue; public class BitMapTest { @@ -71,11 +72,17 @@ public class BitMapTest { @Test public void testImplementationSelectionAndExtension() { - assertTrue(new BitMap(0).getImplementation() instanceof BitMapLongImpl); - assertTrue(new BitMap(64).getImplementation() instanceof BitMapLongImpl); + assertTrue(new BitMap(0).getImplementation() instanceof BitMapArrayImpl); + assertTrue(new BitMap(64).getImplementation() instanceof BitMapArrayImpl); + assertTrue( + new BitMap(64, new byte[BitMap.getSizeOfBytes(64)]).getImplementation() + instanceof BitMapArrayImpl); assertTrue(new BitMap(65).getImplementation() instanceof BitMapArrayImpl); + assertTrue(BitMap.createBitMapDynamically(0).getImplementation() instanceof BitMapLongImpl); + assertTrue(BitMap.createBitMapDynamically(64).getImplementation() instanceof BitMapLongImpl); + assertTrue(BitMap.createBitMapDynamically(65).getImplementation() instanceof BitMapArrayImpl); - BitMap bitMap = new BitMap(64); + BitMap bitMap = BitMap.createBitMapDynamically(64); bitMap.mark(0); bitMap.mark(63); bitMap.extend(65); @@ -100,17 +107,39 @@ public class BitMapTest { (byte) 0b01111110, 0 }; - BitMap bitMap = new BitMap(64, bytes); + BitMap bitMap = new BitMap(new BitMapLongImpl(64, bytes)); assertArrayEquals(bytes, bitMap.getByteArray()); assertEquals(bitMap, bitMap.clone()); assertEquals(bitMap.hashCode(), bitMap.clone().hashCode()); } + @Test + public void testEqualsAcrossImplementations() { + BitMap arrayBitMap = new BitMap(64); + BitMap longBitMap = BitMap.createBitMapDynamically(64); + for (int i = 0; i < 64; i += 2) { + arrayBitMap.mark(i); + longBitMap.mark(i); + } + + assertEquals(arrayBitMap, longBitMap); + assertEquals(longBitMap, arrayBitMap); + assertEquals(arrayBitMap.hashCode(), longBitMap.hashCode()); + + longBitMap.mark(63); + assertNotEquals(arrayBitMap, longBitMap); + assertTrue(arrayBitMap.equalsInRange(longBitMap, 63)); + + arrayBitMap.mark(63); + assertEquals(arrayBitMap, longBitMap); + assertEquals(arrayBitMap.hashCode(), longBitMap.hashCode()); + } + @Test public void testLongImplementationFullRange() { - BitMap rangeBitMap = new BitMap(64); - BitMap singleBitMap = new BitMap(64); + BitMap rangeBitMap = BitMap.createBitMapDynamically(64); + BitMap singleBitMap = BitMap.createBitMapDynamically(64); rangeBitMap.markRange(0, 64); for (int i = 0; i < 64; i++) { @@ -125,7 +154,7 @@ public class BitMapTest { @Test public void testLongImplementationMarkAllByteCompatibility() { - BitMap bitMap = new BitMap(32); + BitMap bitMap = BitMap.createBitMapDynamically(32); bitMap.markAll(); assertArrayEquals(
