You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tsfile.apache.org by ji...@apache.org on 2026/07/21 01:48:50 UTC
(tsfile) 02/03: Refine BitMapLongImpl
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 <jt...@163.com>
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(