This is an automated email from the ASF dual-hosted git repository.
jt2594838 pushed a commit to branch develop
in repository https://gitbox.apache.org/repos/asf/tsfile.git
The following commit(s) were added to refs/heads/develop by this push:
new 928ca9412 Optimize small BitMap with long-backed implementation (#871)
928ca9412 is described below
commit 928ca94122060dabc7cc76c38f3d9c240b0722da
Author: Jiang Tian <[email protected]>
AuthorDate: Tue Jul 21 11:24:41 2026 +0800
Optimize small BitMap with long-backed implementation (#871)
* Add BitMapLongImpl
* Refine BitMapLongImpl
* Add BitMap performance test report
* Remove BitMap performance report file
* fix review comment
* refine memory calculation
---
.../main/java/org/apache/tsfile/utils/BitMap.java | 257 +++-------
.../org/apache/tsfile/utils/BitMapArrayImpl.java | 298 ++++++++++++
.../java/org/apache/tsfile/utils/BitMapImpl.java | 105 ++++
.../org/apache/tsfile/utils/BitMapLongImpl.java | 238 +++++++++
.../org/apache/tsfile/utils/RamUsageEstimator.java | 9 +-
.../apache/tsfile/utils/BitMapPerformanceTest.java | 537 +++++++++++++++++++++
.../java/org/apache/tsfile/utils/BitMapTest.java | 130 ++++-
7 files changed, 1372 insertions(+), 202 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 fd82bc015..629cda9c0 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,224 +22,97 @@ package org.apache.tsfile.utils;
import org.apache.tsfile.i18n.Messages;
import java.util.Arrays;
-import java.util.Objects;
-
-public class BitMap {
- private static final byte[] BIT_UTIL = new byte[] {1, 2, 4, 8, 16, 32, 64,
-128};
- private static final byte[] UNMARK_BIT_UTIL =
- new byte[] {
- (byte) 0XFE, // 11111110
- (byte) 0XFD, // 11111101
- (byte) 0XFB, // 11111011
- (byte) 0XF7, // 11110111
- (byte) 0XEF, // 11101111
- (byte) 0XDF, // 11011111
- (byte) 0XBF, // 10111111
- (byte) 0X7F // 01111111
- };
-
- private byte[] bits;
- private int size;
-
- /** Initialize a BitMap with given size. */
+
+public class BitMap implements Accountable {
+
+ private BitMapImpl implementation;
+
+ /** Initialize an array-backed BitMap with the given size. */
public BitMap(int size) {
- this.size = size;
- bits = new byte[getSizeOfBytes(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) {
- this.size = size;
- this.bits = bits;
+ implementation = new BitMapArrayImpl(size, bits);
+ }
+
+ BitMap(BitMapImpl implementation) {
+ this.implementation = implementation;
}
public byte[] getByteArray() {
- return this.bits;
+ return implementation.getByteArray();
}
public int getSize() {
- return this.size;
+ return implementation.getSize();
}
/** returns the value of the bit with the specified index. */
public boolean isMarked(int position) {
- return (bits[position / Byte.SIZE] & BIT_UTIL[position % Byte.SIZE]) != 0;
+ return implementation.isMarked(position);
}
/** mark as 1 at all positions. */
public void markAll() {
- Arrays.fill(bits, (byte) 0XFF);
+ implementation.markAll();
}
/** mark as 1 at the given bit position. */
public void mark(int position) {
- bits[position / Byte.SIZE] |= BIT_UTIL[position % Byte.SIZE];
+ implementation.mark(position);
}
public void markRange(int startPosition, int length) {
- if (length <= 0) {
- return;
- }
-
- if (startPosition < 0 || startPosition + length > size) {
- throw new IndexOutOfBoundsException(
- Messages.format(
- "error.common.bitmap_start_length_out_of_range", startPosition,
length, size));
- }
-
- int bitEnd = startPosition + length - 1;
- int byte0 = startPosition >>> 3;
- int byte1 = bitEnd >>> 3;
-
- if (byte0 == byte1) {
- bits[byte0] |= (byte) (((1 << length) - 1) << (startPosition & 7));
- return;
- }
-
- bits[byte0++] |= (byte) (0xFF << (startPosition & 7));
-
- while (byte0 < byte1) {
- bits[byte0++] = (byte) 0xFF;
- }
-
- bits[byte1] |= (byte) (0xFF >>> (7 - (bitEnd & 7)));
+ implementation.markRange(startPosition, length);
}
/** mark as 0 at all positions. */
public void reset() {
- Arrays.fill(bits, (byte) 0);
+ implementation.reset();
}
public void unmark(int position) {
- bits[position / Byte.SIZE] &= UNMARK_BIT_UTIL[position % Byte.SIZE];
+ implementation.unmark(position);
}
public void unmarkRange(int startPosition, int length) {
- if (length <= 0) {
- return;
- }
-
- if (startPosition < 0 || startPosition + length > size) {
- throw new IndexOutOfBoundsException(
- Messages.format(
- "error.common.bitmap_start_length_out_of_range", startPosition,
length, size));
- }
-
- int bitEnd = startPosition + length - 1;
- int byte0 = startPosition >>> 3;
- int byte1 = bitEnd >>> 3;
-
- if (byte0 == byte1) {
- bits[byte0] &= (byte) ~(((1 << length) - 1) << (startPosition & 7));
- return;
- }
-
- bits[byte0++] &= (byte) ~(0xFF << (startPosition & 7));
-
- while (byte0 < byte1) {
- bits[byte0++] = 0;
- }
-
- bits[byte1] &= (byte) (0xFF << ((bitEnd & 7) + 1));
+ implementation.unmarkRange(startPosition, length);
}
public void merge(BitMap src, int srcStart, int destStart, int len) {
- if (len <= 0) return;
- if (srcStart < 0 || destStart < 0 || srcStart + len > src.size ||
destStart + len > this.size) {
- throw new IndexOutOfBoundsException();
- }
-
- int done = 0;
- int dstBit = destStart & 7;
- while (done < len) {
- int size = Math.min(len - done, 64);
- long bits = extractBits(src.bits, srcStart + done, size);
- int destStartByte = (destStart + done) >>> 3;
- this.bits[destStartByte++] |= (byte) ((bits << dstBit) & 255L);
- bits = bits >>> (8 - dstBit);
- while (bits > 0L) {
- this.bits[destStartByte++] |= (byte) (bits & 255L);
- bits = bits >>> 8;
- }
- done += size;
- }
- }
-
- private long extractBits(byte[] buf, int off, int len) {
- int start = off >>> 3;
- int size = 8 - (off & 7);
- long val = (buf[start++] & 0xFFL) >>> (off & 7);
- while (size < len) {
- val |= ((buf[start++] & 0xFFL) << size);
- size += 8;
- }
-
- return val & (0xffff_ffff_ffff_ffffL >>> (64 - len));
+ implementation.merge(src.implementation, srcStart, destStart, len);
}
/** whether all bits are zero, i.e., no Null value */
public boolean isAllUnmarked() {
- int j;
- for (j = 0; j < size / Byte.SIZE; j++) {
- if (bits[j] != (byte) 0) {
- return false;
- }
- }
- for (j = 0; j < size % Byte.SIZE; j++) {
- if ((bits[size / Byte.SIZE] & BIT_UTIL[j]) != 0) {
- return false;
- }
- }
- return true;
+ return implementation.isAllUnmarked();
}
// whether all bits in the range are unmarked
public boolean isAllUnmarked(int rangeSize) {
- int j;
- for (j = 0; j < rangeSize / Byte.SIZE; j++) {
- if (bits[j] != (byte) 0) {
- return false;
- }
- }
- int remainingBits = rangeSize % Byte.SIZE;
- if (remainingBits > 0) {
- byte mask = (byte) (0xFF >> (Byte.SIZE - remainingBits));
- if ((bits[rangeSize / Byte.SIZE] & mask) != 0) {
- return false;
- }
- }
- return true;
+ return implementation.isAllUnmarked(rangeSize);
}
/** whether all bits are one, i.e., all are Null */
public boolean isAllMarked() {
- int j;
- for (j = 0; j < size / Byte.SIZE; j++) {
- if (bits[j] != (byte) 0XFF) {
- return false;
- }
- }
- for (j = 0; j < size % Byte.SIZE; j++) {
- if ((bits[size / Byte.SIZE] & BIT_UTIL[j]) == 0) {
- return false;
- }
- }
- return true;
+ return implementation.isAllMarked();
}
@Override
public String toString() {
- StringBuilder res = new StringBuilder();
- for (int i = 0; i < size; i++) {
- res.append(isMarked(i) ? 1 : 0);
+ StringBuilder result = new StringBuilder();
+ for (int i = 0; i < getSize(); i++) {
+ result.append(isMarked(i) ? 1 : 0);
}
- return res.toString();
+ return result.toString();
}
@Override
public int hashCode() {
- int result = Objects.hash(size);
- result = 31 * result + Arrays.hashCode(bits);
+ int result = 31 + getSize();
+ result = 31 * result + implementation.contentHashCode();
return result;
}
@@ -248,56 +121,35 @@ public class BitMap {
if (obj == this) {
return true;
}
- if (obj == null) {
- return false;
- }
if (!(obj instanceof BitMap)) {
return false;
}
BitMap other = (BitMap) obj;
- return this.size == other.size && Arrays.equals(this.bits, other.bits);
+ return getSize() == other.getSize() &&
implementation.contentEquals(other.implementation);
}
public boolean equalsInRange(Object obj, int rangeSize) {
if (obj == this) {
return true;
}
- if (obj == null) {
- return false;
- }
if (!(obj instanceof BitMap)) {
return false;
}
BitMap other = (BitMap) obj;
- if (rangeSize > size || rangeSize > other.size) {
+ if (rangeSize > getSize() || rangeSize > other.getSize()) {
throw new IllegalArgumentException(
Messages.format(
"error.common.bitmap_range_size_exceeds",
rangeSize,
- Math.min(this.size, other.size)));
+ Math.min(getSize(), other.getSize())));
}
- int byteSize = rangeSize / Byte.SIZE;
- for (int i = 0; i < byteSize; i++) {
- if (this.bits[i] != other.bits[i]) {
- return false;
- }
- }
- int remainingBits = rangeSize % Byte.SIZE;
- if (remainingBits > 0) {
- byte mask = (byte) (0xFF >> (Byte.SIZE - remainingBits));
- if ((this.bits[byteSize] & mask) != (other.bits[byteSize] & mask)) {
- return false;
- }
- }
- return true;
+ return implementation.contentEqualsInRange(other.implementation,
rangeSize);
}
@Override
public BitMap clone() {
- byte[] cloneBytes = new byte[this.bits.length];
- System.arraycopy(this.bits, 0, cloneBytes, 0, this.bits.length);
- return new BitMap(this.size, cloneBytes);
+ return new BitMap(implementation.copy());
}
/**
@@ -316,13 +168,14 @@ public class BitMap {
* @throws IndexOutOfBoundsException if copying would cause access of data
outside bitmap bounds.
*/
public static void copyOfRange(BitMap src, int srcPos, BitMap dest, int
destPos, int length) {
- if (srcPos + length > src.size) {
+ if (srcPos + length > src.getSize()) {
throw new IndexOutOfBoundsException(
- Messages.format("error.common.bitmap_out_of_src_range", (srcPos +
length - 1), src.size));
- } else if (destPos + length > dest.size) {
+ Messages.format(
+ "error.common.bitmap_out_of_src_range", (srcPos + length - 1),
src.getSize()));
+ } else if (destPos + length > dest.getSize()) {
throw new IndexOutOfBoundsException(
Messages.format(
- "error.common.bitmap_out_of_dest_range", (destPos + length - 1),
dest.size));
+ "error.common.bitmap_out_of_dest_range", (destPos + length - 1),
dest.getSize()));
}
for (int i = 0; i < length; ++i) {
if (src.isMarked(srcPos + i)) {
@@ -350,7 +203,7 @@ public class BitMap {
}
public byte[] getTruncatedByteArray(int size) {
- return Arrays.copyOf(this.bits, getSizeOfBytes(size));
+ return Arrays.copyOf(getByteArray(), getSizeOfBytes(size));
}
public void append(BitMap another, int position, int length) {
@@ -364,10 +217,24 @@ public class BitMap {
}
public void extend(int newSize) {
- if (size >= newSize) {
- return;
- }
- bits = Arrays.copyOf(bits, getSizeOfBytes(newSize));
- size = newSize;
+ implementation = implementation.extend(newSize);
+ }
+
+ @Override
+ public long ramBytesUsed() {
+ return RamUsageEstimator.BIT_MAP_SIZE +
implementation.getRetainedSizeInBytes();
+ }
+
+ BitMapImpl getImplementation() {
+ return implementation;
+ }
+
+ private static BitMapImpl createImplementation(int size) {
+ return size >= 0 && size <= Long.SIZE ? new BitMapLongImpl(size) : 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
new file mode 100644
index 000000000..9e8a40910
--- /dev/null
+++ b/java/common/src/main/java/org/apache/tsfile/utils/BitMapArrayImpl.java
@@ -0,0 +1,298 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.tsfile.utils;
+
+import org.apache.tsfile.i18n.Messages;
+
+import java.util.Arrays;
+
+class BitMapArrayImpl extends BitMapImpl {
+
+ // Object header + BitMapImpl.size (int) + BitMapArrayImpl.bits (reference).
+ private static final long INSTANCE_SIZE =
+ RamUsageEstimator.alignObjectSize(
+ (long) RamUsageEstimator.NUM_BYTES_OBJECT_HEADER
+ + Integer.BYTES
+ + RamUsageEstimator.NUM_BYTES_OBJECT_REF);
+ private static final byte[] BIT_UTIL = new byte[] {1, 2, 4, 8, 16, 32, 64,
-128};
+ private static final byte[] UNMARK_BIT_UTIL =
+ new byte[] {
+ (byte) 0XFE, // 11111110
+ (byte) 0XFD, // 11111101
+ (byte) 0XFB, // 11111011
+ (byte) 0XF7, // 11110111
+ (byte) 0XEF, // 11101111
+ (byte) 0XDF, // 11011111
+ (byte) 0XBF, // 10111111
+ (byte) 0X7F // 01111111
+ };
+
+ private byte[] bits;
+
+ BitMapArrayImpl(int size) {
+ super(size);
+ bits = new byte[BitMap.getSizeOfBytes(size)];
+ }
+
+ BitMapArrayImpl(int size, byte[] bits) {
+ super(size);
+ this.bits = bits;
+ }
+
+ @Override
+ byte[] getByteArray() {
+ 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;
+ }
+
+ @Override
+ void markAll() {
+ Arrays.fill(bits, (byte) 0XFF);
+ }
+
+ @Override
+ void mark(int position) {
+ bits[position / Byte.SIZE] |= BIT_UTIL[position % Byte.SIZE];
+ }
+
+ @Override
+ void markRange(int startPosition, int length) {
+ if (length <= 0) {
+ return;
+ }
+
+ checkRange(startPosition, length);
+
+ int bitEnd = startPosition + length - 1;
+ int byte0 = startPosition >>> 3;
+ int byte1 = bitEnd >>> 3;
+
+ if (byte0 == byte1) {
+ bits[byte0] |= (byte) (((1 << length) - 1) << (startPosition & 7));
+ return;
+ }
+
+ bits[byte0++] |= (byte) (0xFF << (startPosition & 7));
+
+ while (byte0 < byte1) {
+ bits[byte0++] = (byte) 0xFF;
+ }
+
+ bits[byte1] |= (byte) (0xFF >>> (7 - (bitEnd & 7)));
+ }
+
+ @Override
+ void reset() {
+ Arrays.fill(bits, (byte) 0);
+ }
+
+ @Override
+ void unmark(int position) {
+ bits[position / Byte.SIZE] &= UNMARK_BIT_UTIL[position % Byte.SIZE];
+ }
+
+ @Override
+ void unmarkRange(int startPosition, int length) {
+ if (length <= 0) {
+ return;
+ }
+
+ checkRange(startPosition, length);
+
+ int bitEnd = startPosition + length - 1;
+ int byte0 = startPosition >>> 3;
+ int byte1 = bitEnd >>> 3;
+
+ if (byte0 == byte1) {
+ bits[byte0] &= (byte) ~(((1 << length) - 1) << (startPosition & 7));
+ return;
+ }
+
+ bits[byte0++] &= (byte) ~(0xFF << (startPosition & 7));
+
+ while (byte0 < byte1) {
+ bits[byte0++] = 0;
+ }
+
+ bits[byte1] &= (byte) (0xFF << ((bitEnd & 7) + 1));
+ }
+
+ @Override
+ void merge(BitMapImpl src, int srcStart, int destStart, int len) {
+ if (len <= 0) {
+ return;
+ }
+ if (srcStart < 0 || destStart < 0 || srcStart + len > src.size ||
destStart + len > size) {
+ throw new IndexOutOfBoundsException();
+ }
+
+ int done = 0;
+ int dstBit = destStart & 7;
+ while (done < len) {
+ int batchSize = Math.min(len - done, Long.SIZE);
+ long extractedBits = src.extractBits(srcStart + done, batchSize);
+ int destStartByte = (destStart + done) >>> 3;
+ bits[destStartByte++] |= (byte) ((extractedBits << dstBit) & 255L);
+ extractedBits >>>= Byte.SIZE - dstBit;
+ while (extractedBits > 0L) {
+ bits[destStartByte++] |= (byte) (extractedBits & 255L);
+ extractedBits >>>= Byte.SIZE;
+ }
+ done += batchSize;
+ }
+ }
+
+ @Override
+ long extractBits(int offset, int length) {
+ int start = offset >>> 3;
+ int extractedSize = Byte.SIZE - (offset & 7);
+ long value = (bits[start++] & 0xFFL) >>> (offset & 7);
+ while (extractedSize < length) {
+ value |= (bits[start++] & 0xFFL) << extractedSize;
+ extractedSize += Byte.SIZE;
+ }
+
+ return value & BitMapLongImpl.lowerBitsMask(length);
+ }
+
+ @Override
+ boolean isAllUnmarked() {
+ int index;
+ for (index = 0; index < size / Byte.SIZE; index++) {
+ if (bits[index] != (byte) 0) {
+ return false;
+ }
+ }
+ for (index = 0; index < size % Byte.SIZE; index++) {
+ if ((bits[size / Byte.SIZE] & BIT_UTIL[index]) != 0) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ @Override
+ boolean isAllUnmarked(int rangeSize) {
+ int index;
+ for (index = 0; index < rangeSize / Byte.SIZE; index++) {
+ if (bits[index] != (byte) 0) {
+ return false;
+ }
+ }
+ int remainingBits = rangeSize % Byte.SIZE;
+ if (remainingBits > 0) {
+ byte mask = (byte) (0xFF >> (Byte.SIZE - remainingBits));
+ if ((bits[rangeSize / Byte.SIZE] & mask) != 0) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ @Override
+ boolean isAllMarked() {
+ int index;
+ for (index = 0; index < size / Byte.SIZE; index++) {
+ if (bits[index] != (byte) 0XFF) {
+ return false;
+ }
+ }
+ for (index = 0; index < size % Byte.SIZE; index++) {
+ if ((bits[size / Byte.SIZE] & BIT_UTIL[index]) == 0) {
+ return false;
+ }
+ }
+ 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));
+ }
+
+ @Override
+ BitMapImpl extend(int newSize) {
+ if (size < newSize) {
+ bits = Arrays.copyOf(bits, BitMap.getSizeOfBytes(newSize));
+ size = newSize;
+ }
+ return this;
+ }
+
+ @Override
+ long getRetainedSizeInBytes() {
+ // The byte array size includes its header, content, and object alignment.
+ return INSTANCE_SIZE + RamUsageEstimator.sizeOfByteArray(bits.length);
+ }
+
+ private void checkRange(int startPosition, int length) {
+ if (startPosition < 0 || startPosition + length > size) {
+ throw new IndexOutOfBoundsException(
+ Messages.format(
+ "error.common.bitmap_start_length_out_of_range", startPosition,
length, size));
+ }
+ }
+}
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
new file mode 100644
index 000000000..d9f296fe2
--- /dev/null
+++ b/java/common/src/main/java/org/apache/tsfile/utils/BitMapImpl.java
@@ -0,0 +1,105 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.tsfile.utils;
+
+abstract class BitMapImpl {
+
+ protected int size;
+
+ protected BitMapImpl(int size) {
+ this.size = size;
+ }
+
+ int getSize() {
+ return size;
+ }
+
+ abstract byte[] getByteArray();
+
+ abstract int getByteArrayLength();
+
+ abstract byte getByte(int index);
+
+ abstract boolean isMarked(int position);
+
+ abstract void markAll();
+
+ abstract void mark(int position);
+
+ abstract void markRange(int startPosition, int length);
+
+ abstract void reset();
+
+ abstract void unmark(int position);
+
+ abstract void unmarkRange(int startPosition, int length);
+
+ abstract void merge(BitMapImpl src, int srcStart, int destStart, int len);
+
+ abstract long extractBits(int offset, int length);
+
+ abstract boolean isAllUnmarked();
+
+ abstract boolean isAllUnmarked(int rangeSize);
+
+ 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);
+
+ abstract long getRetainedSizeInBytes();
+}
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
new file mode 100644
index 000000000..452c7f096
--- /dev/null
+++ b/java/common/src/main/java/org/apache/tsfile/utils/BitMapLongImpl.java
@@ -0,0 +1,238 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.tsfile.utils;
+
+import org.apache.tsfile.i18n.Messages;
+
+class BitMapLongImpl extends BitMapImpl {
+
+ private static final long ALL_BITS_MARKED = -1L;
+ // Object header + BitMapImpl.size (int) + bits (long) + paddingByte (byte).
+ private static final long INSTANCE_SIZE =
+ RamUsageEstimator.alignObjectSize(
+ (long) RamUsageEstimator.NUM_BYTES_OBJECT_HEADER
+ + Integer.BYTES
+ + Long.BYTES
+ + Byte.BYTES);
+
+ private long bits;
+ // BitMap serialization always has one extra byte, which does not fit in
bits at size 64.
+ private byte paddingByte;
+
+ BitMapLongImpl(int size) {
+ super(size);
+ }
+
+ BitMapLongImpl(int size, byte[] bytes) {
+ super(size);
+ int byteCount = Math.min(bytes.length, Long.BYTES);
+ for (int i = 0; i < byteCount; i++) {
+ bits |= (bytes[i] & 0xFFL) << (i * Byte.SIZE);
+ }
+ if (getByteArrayLength() > Long.BYTES && bytes.length > Long.BYTES) {
+ paddingByte = bytes[Long.BYTES];
+ }
+ }
+
+ @Override
+ byte[] getByteArray() {
+ byte[] bytes = new byte[BitMap.getSizeOfBytes(size)];
+ int byteCount = Math.min(bytes.length, Long.BYTES);
+ for (int i = 0; i < byteCount; i++) {
+ bytes[i] = (byte) (bits >>> (i * Byte.SIZE));
+ }
+ if (bytes.length > Long.BYTES) {
+ bytes[Long.BYTES] = paddingByte;
+ }
+ return bytes;
+ }
+
+ @Override
+ int getByteArrayLength() {
+ return BitMap.getSizeOfBytes(size);
+ }
+
+ @Override
+ byte getByte(int index) {
+ return index < Long.BYTES ? (byte) (bits >>> (index * Byte.SIZE)) :
paddingByte;
+ }
+
+ @Override
+ boolean isMarked(int position) {
+ return (bits & (1L << position)) != 0;
+ }
+
+ @Override
+ void markAll() {
+ bits = ALL_BITS_MARKED;
+ if (getByteArrayLength() > Long.BYTES) {
+ paddingByte = (byte) 0xFF;
+ }
+ }
+
+ @Override
+ void mark(int position) {
+ bits |= 1L << position;
+ }
+
+ @Override
+ void markRange(int startPosition, int length) {
+ if (length <= 0) {
+ return;
+ }
+ checkRange(startPosition, length);
+ bits |= lowerBitsMask(length) << startPosition;
+ }
+
+ @Override
+ void reset() {
+ bits = 0L;
+ paddingByte = 0;
+ }
+
+ @Override
+ void unmark(int position) {
+ bits &= ~(1L << position);
+ }
+
+ @Override
+ void unmarkRange(int startPosition, int length) {
+ if (length <= 0) {
+ return;
+ }
+ checkRange(startPosition, length);
+ bits &= ~(lowerBitsMask(length) << startPosition);
+ }
+
+ @Override
+ void merge(BitMapImpl src, int srcStart, int destStart, int len) {
+ if (len <= 0) {
+ return;
+ }
+ if (srcStart < 0 || destStart < 0 || srcStart + len > src.size ||
destStart + len > size) {
+ throw new IndexOutOfBoundsException();
+ }
+ bits |= src.extractBits(srcStart, len) << destStart;
+ }
+
+ @Override
+ long extractBits(int offset, int length) {
+ return (bits >>> offset) & lowerBitsMask(length);
+ }
+
+ @Override
+ boolean isAllUnmarked() {
+ return (bits & lowerBitsMask(size)) == 0L;
+ }
+
+ @Override
+ boolean isAllUnmarked(int rangeSize) {
+ return (bits & lowerBitsMask(rangeSize)) == 0L;
+ }
+
+ @Override
+ boolean isAllMarked() {
+ long mask = lowerBitsMask(size);
+ 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);
+ BitMapLongImpl otherLongImpl = (BitMapLongImpl) other;
+ return (bits & mask) == (otherLongImpl.bits & mask)
+ && (getByteArrayLength() <= Long.BYTES || paddingByte ==
otherLongImpl.paddingByte);
+ }
+
+ @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 * result + paddingByte;
+ }
+ return result;
+ }
+
+ @Override
+ BitMapImpl copy() {
+ BitMapLongImpl copy = new BitMapLongImpl(size);
+ copy.bits = bits;
+ copy.paddingByte = paddingByte;
+ return copy;
+ }
+
+ @Override
+ BitMapImpl extend(int newSize) {
+ if (size >= newSize) {
+ return this;
+ }
+ if (newSize <= Long.SIZE) {
+ size = newSize;
+ return this;
+ }
+ return new BitMapArrayImpl(newSize, getExtendedByteArray(newSize));
+ }
+
+ @Override
+ long getRetainedSizeInBytes() {
+ return INSTANCE_SIZE;
+ }
+
+ static long lowerBitsMask(int length) {
+ return length == Long.SIZE ? -1L : (1L << length) - 1;
+ }
+
+ private byte[] getExtendedByteArray(int newSize) {
+ byte[] bytes = new byte[BitMap.getSizeOfBytes(newSize)];
+ for (int i = 0; i < Long.BYTES; i++) {
+ bytes[i] = (byte) (bits >>> (i * Byte.SIZE));
+ }
+ bytes[Long.BYTES] = paddingByte;
+ return bytes;
+ }
+
+ private void checkRange(int startPosition, int length) {
+ if (startPosition < 0 || startPosition + length > size) {
+ throw new IndexOutOfBoundsException(
+ Messages.format(
+ "error.common.bitmap_start_length_out_of_range", startPosition,
length, size));
+ }
+ }
+}
diff --git
a/java/common/src/main/java/org/apache/tsfile/utils/RamUsageEstimator.java
b/java/common/src/main/java/org/apache/tsfile/utils/RamUsageEstimator.java
index 841fc5fe0..e70a00f40 100644
--- a/java/common/src/main/java/org/apache/tsfile/utils/RamUsageEstimator.java
+++ b/java/common/src/main/java/org/apache/tsfile/utils/RamUsageEstimator.java
@@ -123,7 +123,6 @@ public final class RamUsageEstimator {
LOCAL_DATE_ARRAY_SIZE = RamUsageEstimator.shallowSizeOf(LocalDate[].class);
LOCAL_DATE_SIZE = RamUsageEstimator.shallowSizeOf(LocalDate.class);
- BIT_MAP_SIZE = RamUsageEstimator.shallowSizeOfInstance(BitMap.class);
SIZE_OF_ARRAYLIST =
RamUsageEstimator.shallowSizeOfInstance(ArrayList.class);
}
@@ -197,6 +196,8 @@ public final class RamUsageEstimator {
}
ALIGN_MASK = NUM_BYTES_OBJECT_ALIGNMENT - 1;
+ // Object header + BitMap.implementation (reference).
+ BIT_MAP_SIZE = alignObjectSize((long) NUM_BYTES_OBJECT_HEADER +
NUM_BYTES_OBJECT_REF);
// get min/max value of cached Long class instances:
long longCacheMinValue = 0;
@@ -707,11 +708,7 @@ public final class RamUsageEstimator {
if (bitMap == null) {
return 0L;
}
- long size = BIT_MAP_SIZE;
-
- size +=
- RamUsageEstimator.alignObjectSize(NUM_BYTES_ARRAY_HEADER +
bitMap.getByteArray().length);
- return size;
+ return bitMap.ramBytesUsed();
}
public static long sizeOf(final LocalDate[] input) {
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
new file mode 100644
index 000000000..7f3d239c0
--- /dev/null
+++
b/java/tsfile/src/test/java/org/apache/tsfile/utils/BitMapPerformanceTest.java
@@ -0,0 +1,537 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.tsfile.utils;
+
+import org.junit.Assume;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+public class BitMapPerformanceTest {
+
+ private static final int BIT_MAP_SIZE = Long.SIZE;
+ private static final int WARMUP_ROUNDS = 3;
+ private static final int MEASUREMENT_ROUNDS = 7;
+ private static final int CHEAP_OPERATION_COUNT = 2_000_000;
+ private static final int ALLOCATION_OPERATION_COUNT = 200_000;
+ private static final int COMPOSITE_OPERATION_COUNT = 50_000;
+ private static final int BULK_INSTANCE_COUNT = 1_000_000;
+ private static final String RUN_PERFORMANCE_TEST_PROPERTY =
"tsfile.runPerformanceTests";
+
+ private static volatile long blackHole;
+ private static volatile Object referenceBlackHole;
+
+ @Test
+ public void testLength64Implementations() {
+ Assume.assumeTrue(
+ "Set -Dtsfile.runPerformanceTests=true to run the performance test",
+ Boolean.getBoolean(RUN_PERFORMANCE_TEST_PROPERTY));
+
+ List<BenchmarkResult> results = new ArrayList<>();
+ results.add(
+ benchmark(
+ "isMarked",
+ CHEAP_OPERATION_COUNT,
+ readMarkedWorkload(arrayBitMap()),
+ readMarkedWorkload(longBitMap())));
+ results.add(
+ benchmark(
+ "isAllMarked/isAllUnmarked",
+ CHEAP_OPERATION_COUNT,
+ readStateWorkload(BitMapPerformanceTest::arrayBitMap),
+ readStateWorkload(BitMapPerformanceTest::longBitMap)));
+ results.add(
+ benchmark(
+ "mark/unmark (one write)",
+ CHEAP_OPERATION_COUNT,
+ pointWriteWorkload(BitMapPerformanceTest::arrayBitMap),
+ pointWriteWorkload(BitMapPerformanceTest::longBitMap)));
+ results.add(
+ benchmark(
+ "markRange/unmarkRange (one write)",
+ CHEAP_OPERATION_COUNT,
+ rangeWriteWorkload(BitMapPerformanceTest::arrayBitMap),
+ rangeWriteWorkload(BitMapPerformanceTest::longBitMap)));
+ results.add(
+ benchmark(
+ "markAll/reset (one write)",
+ CHEAP_OPERATION_COUNT,
+ bulkWriteWorkload(BitMapPerformanceTest::arrayBitMap),
+ bulkWriteWorkload(BitMapPerformanceTest::longBitMap)));
+ results.add(
+ benchmark(
+ "getByteArray",
+ ALLOCATION_OPERATION_COUNT,
+ getByteArrayWorkload(arrayBitMap()),
+ getByteArrayWorkload(longBitMap())));
+ results.add(
+ benchmark(
+ "getTruncatedByteArray",
+ ALLOCATION_OPERATION_COUNT,
+ getTruncatedByteArrayWorkload(arrayBitMap()),
+ getTruncatedByteArrayWorkload(longBitMap())));
+ results.add(
+ benchmark(
+ "constructFromBytes",
+ ALLOCATION_OPERATION_COUNT,
+ constructFromBytesWorkload(BitMapArrayImpl::new),
+ constructFromBytesWorkload(BitMapLongImpl::new)));
+ results.add(
+ benchmark(
+ "clone",
+ ALLOCATION_OPERATION_COUNT,
+ cloneWorkload(arrayBitMap()),
+ cloneWorkload(longBitMap())));
+ results.add(
+ benchmark(
+ "merge",
+ CHEAP_OPERATION_COUNT,
+ mergeWorkload(BitMapPerformanceTest::arrayBitMap),
+ mergeWorkload(BitMapPerformanceTest::longBitMap)));
+ results.add(
+ benchmark(
+ "append",
+ COMPOSITE_OPERATION_COUNT,
+ appendWorkload(BitMapPerformanceTest::arrayBitMap),
+ appendWorkload(BitMapPerformanceTest::longBitMap)));
+ results.add(
+ benchmark(
+ "getRegion",
+ COMPOSITE_OPERATION_COUNT,
+ regionWorkload(arrayBitMap()),
+ regionWorkload(longBitMap())));
+ results.add(
+ benchmark(
+ "equals/equalsInRange",
+ ALLOCATION_OPERATION_COUNT,
+ equalityWorkload(BitMapPerformanceTest::arrayBitMap),
+ equalityWorkload(BitMapPerformanceTest::longBitMap)));
+ results.add(
+ benchmark(
+ "hashCode",
+ CHEAP_OPERATION_COUNT,
+ hashCodeWorkload(BitMapPerformanceTest::arrayBitMap),
+ hashCodeWorkload(BitMapPerformanceTest::longBitMap)));
+ results.add(
+ benchmark(
+ "toString",
+ COMPOSITE_OPERATION_COUNT,
+ toStringWorkload(arrayBitMap()),
+ toStringWorkload(longBitMap())));
+
+ printResults(results);
+ printMemoryUsage();
+ }
+
+ private static BenchmarkResult benchmark(
+ String name, int operationCount, Workload arrayWorkload, Workload
longWorkload) {
+ for (int round = 0; round < WARMUP_ROUNDS; round++) {
+ run(arrayWorkload, operationCount);
+ run(longWorkload, operationCount);
+ }
+
+ long[] arrayNanos = new long[MEASUREMENT_ROUNDS];
+ long[] longNanos = new long[MEASUREMENT_ROUNDS];
+ for (int round = 0; round < MEASUREMENT_ROUNDS; round++) {
+ TimedRun arrayRun;
+ TimedRun longRun;
+ if ((round & 1) == 0) {
+ arrayRun = run(arrayWorkload, operationCount);
+ longRun = run(longWorkload, operationCount);
+ } else {
+ longRun = run(longWorkload, operationCount);
+ arrayRun = run(arrayWorkload, operationCount);
+ }
+ assertEquals(arrayRun.checksum, longRun.checksum);
+ arrayNanos[round] = arrayRun.elapsedNanos;
+ longNanos[round] = longRun.elapsedNanos;
+ }
+ return new BenchmarkResult(
+ name,
+ median(arrayNanos) / (double) operationCount,
+ median(longNanos) / (double) operationCount);
+ }
+
+ private static TimedRun run(Workload workload, int operationCount) {
+ long startTime = System.nanoTime();
+ long checksum = workload.run(operationCount);
+ long elapsedNanos = System.nanoTime() - startTime;
+ blackHole = checksum;
+ return new TimedRun(elapsedNanos, checksum);
+ }
+
+ private static long median(long[] values) {
+ long[] sortedValues = Arrays.copyOf(values, values.length);
+ Arrays.sort(sortedValues);
+ return sortedValues[sortedValues.length / 2];
+ }
+
+ private static Workload readMarkedWorkload(BitMap bitMap) {
+ markAlternatingBits(bitMap);
+ return operationCount -> {
+ long checksum = 0;
+ for (int i = 0; i < operationCount; i++) {
+ checksum += bitMap.isMarked(i & 63) ? 1 : 0;
+ }
+ return checksum;
+ };
+ }
+
+ private static Workload readStateWorkload(BitMapFactory factory) {
+ BitMap[] bitMaps = new BitMap[BIT_MAP_SIZE];
+ for (int i = 0; i < bitMaps.length; i++) {
+ bitMaps[i] = factory.create();
+ if (i % 3 == 0) {
+ bitMaps[i].markAll();
+ } else if (i % 3 == 1) {
+ markAlternatingBits(bitMaps[i]);
+ }
+ }
+ return operationCount -> {
+ long checksum = 0;
+ for (int i = 0; i < operationCount; i++) {
+ BitMap bitMap = bitMaps[i & 63];
+ checksum += bitMap.isAllMarked() ? 1 : 0;
+ checksum += bitMap.isAllUnmarked() ? 2 : 0;
+ checksum += bitMap.isAllUnmarked(BIT_MAP_SIZE) ? 4 : 0;
+ }
+ return checksum + BIT_MAP_SIZE;
+ };
+ }
+
+ private static Workload pointWriteWorkload(BitMapFactory factory) {
+ return operationCount -> {
+ BitMap bitMap = factory.create();
+ long checksum = 0;
+ for (int i = 0; i < operationCount; i++) {
+ int position = i & 63;
+ if ((i & 64) == 0) {
+ bitMap.mark(position);
+ } else {
+ bitMap.unmark(position);
+ }
+ if ((i & 255) == 0) {
+ checksum += bitMap.isMarked(position) ? 1 : 0;
+ }
+ }
+ referenceBlackHole = bitMap;
+ return checksum;
+ };
+ }
+
+ private static Workload rangeWriteWorkload(BitMapFactory factory) {
+ return operationCount -> {
+ BitMap bitMap = factory.create();
+ long checksum = 0;
+ for (int i = 0; i < operationCount; i++) {
+ int start = (i * 7) & 63;
+ int length = Math.min(8, BIT_MAP_SIZE - start);
+ if ((i & 64) == 0) {
+ bitMap.markRange(start, length);
+ } else {
+ bitMap.unmarkRange(start, length);
+ }
+ if ((i & 255) == 0) {
+ checksum += bitMap.isMarked(start) ? 1 : 0;
+ }
+ }
+ referenceBlackHole = bitMap;
+ return checksum;
+ };
+ }
+
+ private static Workload bulkWriteWorkload(BitMapFactory factory) {
+ return operationCount -> {
+ BitMap bitMap = factory.create();
+ long checksum = 0;
+ for (int i = 0; i < operationCount; i++) {
+ if ((i & 1) == 0) {
+ bitMap.markAll();
+ } else {
+ bitMap.reset();
+ }
+ if ((i & 255) == 0) {
+ checksum += bitMap.isAllMarked() ? 1 : 0;
+ }
+ }
+ referenceBlackHole = bitMap;
+ return checksum;
+ };
+ }
+
+ private static Workload getByteArrayWorkload(BitMap bitMap) {
+ markAlternatingBits(bitMap);
+ return operationCount -> {
+ byte[][] sink = new byte[1024][];
+ long checksum = 0;
+ for (int i = 0; i < operationCount; i++) {
+ byte[] bytes = bitMap.getByteArray();
+ sink[i & 1023] = bytes;
+ checksum += bytes[i & 7] & 0xFFL;
+ checksum += bytes.length;
+ }
+ referenceBlackHole = sink[operationCount & 1023];
+ return checksum;
+ };
+ }
+
+ private static Workload getTruncatedByteArrayWorkload(BitMap bitMap) {
+ markAlternatingBits(bitMap);
+ return operationCount -> {
+ byte[][] sink = new byte[1024][];
+ long checksum = 0;
+ for (int i = 0; i < operationCount; i++) {
+ byte[] bytes = bitMap.getTruncatedByteArray(BIT_MAP_SIZE);
+ sink[i & 1023] = bytes;
+ checksum += bytes[i & 7] & 0xFFL;
+ checksum += bytes.length;
+ }
+ referenceBlackHole = sink[operationCount & 1023];
+ return checksum;
+ };
+ }
+
+ private static Workload constructFromBytesWorkload(BitMapImplFactory
factory) {
+ byte[] bytes = serializedAlternatingBits();
+ return operationCount -> {
+ BitMap[] sink = new BitMap[1024];
+ long checksum = 0;
+ for (int i = 0; i < operationCount; i++) {
+ BitMap bitMap = new BitMap(factory.create(BIT_MAP_SIZE, bytes));
+ sink[i & 1023] = bitMap;
+ checksum += bitMap.isMarked(i & 63) ? 1 : 0;
+ }
+ referenceBlackHole = sink[operationCount & 1023];
+ return checksum;
+ };
+ }
+
+ private static Workload cloneWorkload(BitMap bitMap) {
+ markAlternatingBits(bitMap);
+ return operationCount -> {
+ BitMap[] sink = new BitMap[1024];
+ long checksum = 0;
+ for (int i = 0; i < operationCount; i++) {
+ BitMap clone = bitMap.clone();
+ sink[i & 1023] = clone;
+ checksum += clone.isMarked(i & 63) ? 1 : 0;
+ }
+ referenceBlackHole = sink[operationCount & 1023];
+ return checksum;
+ };
+ }
+
+ private static Workload mergeWorkload(BitMapFactory factory) {
+ BitMap source = factory.create();
+ markAlternatingBits(source);
+ return operationCount -> {
+ BitMap destination = factory.create();
+ long checksum = 0;
+ for (int i = 0; i < operationCount; i++) {
+ destination.merge(source, 0, 0, BIT_MAP_SIZE);
+ checksum += destination.isMarked(i & 63) ? 1 : 0;
+ }
+ return checksum;
+ };
+ }
+
+ private static Workload appendWorkload(BitMapFactory factory) {
+ BitMap source = factory.create();
+ markAlternatingBits(source);
+ return operationCount -> {
+ BitMap destination = factory.create();
+ long checksum = 0;
+ for (int i = 0; i < operationCount; i++) {
+ destination.append(source, 0, BIT_MAP_SIZE);
+ checksum += destination.isMarked(i & 63) ? 1 : 0;
+ }
+ return checksum;
+ };
+ }
+
+ private static Workload regionWorkload(BitMap bitMap) {
+ markAlternatingBits(bitMap);
+ return operationCount -> {
+ BitMap[] sink = new BitMap[1024];
+ long checksum = 0;
+ for (int i = 0; i < operationCount; i++) {
+ BitMap region = bitMap.getRegion(0, BIT_MAP_SIZE);
+ sink[i & 1023] = region;
+ checksum += region.isMarked(i & 63) ? 1 : 0;
+ }
+ referenceBlackHole = sink[operationCount & 1023];
+ return checksum;
+ };
+ }
+
+ 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 += bitMaps[i & 63].hashCode();
+ }
+ return checksum;
+ };
+ }
+
+ private static Workload toStringWorkload(BitMap bitMap) {
+ markAlternatingBits(bitMap);
+ return operationCount -> {
+ String[] sink = new String[1024];
+ long checksum = 0;
+ for (int i = 0; i < operationCount; i++) {
+ String value = bitMap.toString();
+ sink[i & 1023] = value;
+ checksum += value.charAt(i & 63);
+ checksum += value.length();
+ }
+ referenceBlackHole = sink[operationCount & 1023];
+ return checksum;
+ };
+ }
+
+ private static BitMap arrayBitMap() {
+ return new BitMap(new BitMapArrayImpl(BIT_MAP_SIZE));
+ }
+
+ private static BitMap longBitMap() {
+ return new BitMap(new BitMapLongImpl(BIT_MAP_SIZE));
+ }
+
+ private static void markAlternatingBits(BitMap bitMap) {
+ for (int i = 0; i < BIT_MAP_SIZE; i += 2) {
+ bitMap.mark(i);
+ }
+ }
+
+ private static byte[] serializedAlternatingBits() {
+ BitMap bitMap = arrayBitMap();
+ markAlternatingBits(bitMap);
+ return Arrays.copyOf(bitMap.getByteArray(), bitMap.getByteArray().length);
+ }
+
+ private static void printResults(List<BenchmarkResult> results) {
+ System.out.println("BitMap length=64 performance (median ns/op)");
+ System.out.printf("%-34s %14s %14s %14s%n", "operation", "ArrayImpl",
"LongImpl", "Long/Array");
+ for (BenchmarkResult result : results) {
+ System.out.printf(
+ "%-34s %14.3f %14.3f %13.3fx%n",
+ result.name,
+ result.arrayNanosPerOperation,
+ result.longNanosPerOperation,
+ result.longNanosPerOperation / result.arrayNanosPerOperation);
+ }
+ }
+
+ private static void printMemoryUsage() {
+ BitMap arrayBitMap = arrayBitMap();
+ BitMap longBitMap = longBitMap();
+ long arrayBytes = arrayBitMap.ramBytesUsed();
+ long longBytes = longBitMap.ramBytesUsed();
+ assertTrue(longBytes < arrayBytes);
+
+ long arrayContainerBytes =
+ RamUsageEstimator.alignObjectSize(
+ RamUsageEstimator.NUM_BYTES_ARRAY_HEADER
+ + (long) RamUsageEstimator.NUM_BYTES_OBJECT_REF *
BULK_INSTANCE_COUNT);
+ long arrayBulkBytes = arrayContainerBytes + arrayBytes *
BULK_INSTANCE_COUNT;
+ long longBulkBytes = arrayContainerBytes + longBytes * BULK_INSTANCE_COUNT;
+
+ System.out.println("BitMap length=64 retained memory estimate");
+ System.out.printf(
+ "ArrayImpl: %,d bytes/object, %,d bytes for %,d objects%n",
+ arrayBytes, arrayBulkBytes, BULK_INSTANCE_COUNT);
+ System.out.printf(
+ "LongImpl : %,d bytes/object, %,d bytes for %,d objects%n",
+ longBytes, longBulkBytes, BULK_INSTANCE_COUNT);
+ System.out.printf(
+ "Reduction: %.2f%% per object%n", (arrayBytes - longBytes) * 100.0 /
arrayBytes);
+ }
+
+ @FunctionalInterface
+ private interface Workload {
+ long run(int operationCount);
+ }
+
+ @FunctionalInterface
+ private interface BitMapFactory {
+ BitMap create();
+ }
+
+ @FunctionalInterface
+ private interface BitMapImplFactory {
+ BitMapImpl create(int size, byte[] bytes);
+ }
+
+ private static class TimedRun {
+
+ private final long elapsedNanos;
+ private final long checksum;
+
+ private TimedRun(long elapsedNanos, long checksum) {
+ this.elapsedNanos = elapsedNanos;
+ this.checksum = checksum;
+ }
+ }
+
+ private static class BenchmarkResult {
+
+ private final String name;
+ private final double arrayNanosPerOperation;
+ private final double longNanosPerOperation;
+
+ private BenchmarkResult(
+ String name, double arrayNanosPerOperation, double
longNanosPerOperation) {
+ this.name = name;
+ this.arrayNanosPerOperation = arrayNanosPerOperation;
+ this.longNanosPerOperation = longNanosPerOperation;
+ }
+ }
+}
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 2b6e10cef..e4b59e452 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 {
@@ -69,6 +70,133 @@ public class BitMapTest {
}
}
+ @Test
+ public void testImplementationSelectionAndExtension() {
+ 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 = BitMap.createBitMapDynamically(64);
+ bitMap.mark(0);
+ bitMap.mark(63);
+ bitMap.extend(65);
+
+ assertTrue(bitMap.getImplementation() instanceof BitMapArrayImpl);
+ assertEquals(65, bitMap.getSize());
+ assertTrue(bitMap.isMarked(0));
+ assertTrue(bitMap.isMarked(63));
+ assertFalse(bitMap.isMarked(64));
+ }
+
+ @Test
+ public void testLongImplementationByteArrayCompatibility() {
+ byte[] bytes = {
+ (byte) 0b10101010,
+ (byte) 0b01010101,
+ (byte) 0b11110000,
+ (byte) 0b00001111,
+ (byte) 0b11001100,
+ (byte) 0b00110011,
+ (byte) 0b10000001,
+ (byte) 0b01111110,
+ 0
+ };
+ 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 = BitMap.createBitMapDynamically(64);
+ BitMap singleBitMap = BitMap.createBitMapDynamically(64);
+
+ rangeBitMap.markRange(0, 64);
+ for (int i = 0; i < 64; i++) {
+ singleBitMap.mark(i);
+ }
+ assertTrue(rangeBitMap.isAllMarked());
+ assertArrayEquals(singleBitMap.getByteArray(), rangeBitMap.getByteArray());
+
+ rangeBitMap.unmarkRange(0, 64);
+ assertTrue(rangeBitMap.isAllUnmarked());
+ }
+
+ @Test
+ public void testLongImplementationMarkAllByteCompatibility() {
+ BitMap bitMap = BitMap.createBitMapDynamically(32);
+ bitMap.markAll();
+
+ assertArrayEquals(
+ new byte[] {(byte) 0xFF, (byte) 0xFF, (byte) 0xFF, (byte) 0xFF, (byte)
0xFF},
+ bitMap.getByteArray());
+
+ bitMap.extend(64);
+ for (int i = 0; i < 64; i++) {
+ assertTrue(bitMap.isMarked(i));
+ }
+ }
+
+ @Test
+ public void testLongImplementationMarkAllAt64Bits() {
+ BitMap arrayBitMap = new BitMap(64);
+ BitMap longBitMap = BitMap.createBitMapDynamically(64);
+
+ arrayBitMap.markAll();
+ longBitMap.markAll();
+
+ assertArrayEquals(arrayBitMap.getByteArray(), longBitMap.getByteArray());
+ assertEquals(arrayBitMap, longBitMap);
+ assertEquals(arrayBitMap.hashCode(), longBitMap.hashCode());
+ assertEquals(arrayBitMap, longBitMap.clone());
+ }
+
+ @Test
+ public void testRamBytesUsed() {
+ BitMap arrayBitMap = new BitMap(64);
+ BitMap longBitMap = BitMap.createBitMapDynamically(64);
+
+ assertEquals(
+ RamUsageEstimator.BIT_MAP_SIZE +
arrayBitMap.getImplementation().getRetainedSizeInBytes(),
+ arrayBitMap.ramBytesUsed());
+ assertEquals(
+ RamUsageEstimator.BIT_MAP_SIZE +
longBitMap.getImplementation().getRetainedSizeInBytes(),
+ longBitMap.ramBytesUsed());
+ assertEquals(arrayBitMap.ramBytesUsed(),
RamUsageEstimator.sizeOfObject(arrayBitMap));
+ assertEquals(longBitMap.ramBytesUsed(),
RamUsageEstimator.sizeOfObject(longBitMap));
+ assertTrue(longBitMap.ramBytesUsed() < arrayBitMap.ramBytesUsed());
+ }
+
@Test
public void testIsAllUnmarkedInRange() {
BitMap bitMap = new BitMap(16);
@@ -141,7 +269,7 @@ public class BitMapTest {
}
BitMap copy =
- new BitMap(src.getSize(), Arrays.copyOf(dst.getByteArray(),
dst.getByteArray().length));
+ new BitMap(destSize, Arrays.copyOf(dst.getByteArray(),
dst.getByteArray().length));
for (int i = 0; i < len; i++) {
if (src.isMarked(srcStart + i)) {
