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 061e749bde6b53947fd5ee87a695c0c7cf87db86 Author: Tian Jiang <[email protected]> AuthorDate: Mon Jul 20 19:16:10 2026 +0800 Add BitMapLongImpl --- .../main/java/org/apache/tsfile/utils/BitMap.java | 241 +++------- .../org/apache/tsfile/utils/BitMapArrayImpl.java | 250 ++++++++++ .../java/org/apache/tsfile/utils/BitMapImpl.java | 65 +++ .../org/apache/tsfile/utils/BitMapLongImpl.java | 170 +++++++ .../org/apache/tsfile/utils/RamUsageEstimator.java | 6 +- .../apache/tsfile/utils/BitMapPerformanceTest.java | 511 +++++++++++++++++++++ .../java/org/apache/tsfile/utils/BitMapTest.java | 71 ++- 7 files changed, 1131 insertions(+), 183 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..8886eed72 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 @@ -25,221 +25,95 @@ 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; + + private BitMapImpl implementation; /** Initialize a BitMap with given size. */ public BitMap(int size) { - this.size = size; - bits = new byte[getSizeOfBytes(size)]; + implementation = createImplementation(size); } /** Initialize a BitMap with given size and bytes. */ public BitMap(int size, byte[] bits) { - this.size = size; - this.bits = bits; + implementation = createImplementation(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 = Objects.hash(getSize()); + result = 31 * result + Arrays.hashCode(getByteArray()); return result; } @@ -248,45 +122,41 @@ 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() && Arrays.equals(getByteArray(), other.getByteArray()); } 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; + byte[] thisBits = getByteArray(); + byte[] otherBits = other.getByteArray(); for (int i = 0; i < byteSize; i++) { - if (this.bits[i] != other.bits[i]) { + if (thisBits[i] != otherBits[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)) { + if ((thisBits[byteSize] & mask) != (otherBits[byteSize] & mask)) { return false; } } @@ -295,9 +165,7 @@ public class BitMap { @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 +184,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 +219,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 +233,28 @@ public class BitMap { } public void extend(int newSize) { - if (size >= newSize) { - return; - } - bits = Arrays.copyOf(bits, getSizeOfBytes(newSize)); - size = newSize; + implementation = implementation.extend(newSize); + } + + long getRetainedSizeInBytes() { + return implementation.getRetainedSizeInBytes(); + } + + BitMapImpl getImplementation() { + return implementation; + } + + private static BitMapImpl createImplementation(int size) { + 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)); } } 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..f1eda3389 --- /dev/null +++ b/java/common/src/main/java/org/apache/tsfile/utils/BitMapArrayImpl.java @@ -0,0 +1,250 @@ +/* + * 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 { + + 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 + 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 + 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() { + return RamUsageEstimator.shallowSizeOfInstance(BitMapArrayImpl.class) + + RamUsageEstimator.alignObjectSize(RamUsageEstimator.NUM_BYTES_ARRAY_HEADER + 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..b95ee7253 --- /dev/null +++ b/java/common/src/main/java/org/apache/tsfile/utils/BitMapImpl.java @@ -0,0 +1,65 @@ +/* + * 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 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(); + + 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..f3c8d64f1 --- /dev/null +++ b/java/common/src/main/java/org/apache/tsfile/utils/BitMapLongImpl.java @@ -0,0 +1,170 @@ +/* + * 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; + + private long bits; + + 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); + } + } + + @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)); + } + return bytes; + } + + @Override + boolean isMarked(int position) { + return (bits & (1L << position)) != 0; + } + + @Override + void markAll() { + bits = ALL_BITS_MARKED; + } + + @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; + } + + @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 + BitMapImpl copy() { + BitMapLongImpl copy = new BitMapLongImpl(size); + copy.bits = bits; + 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 RamUsageEstimator.shallowSizeOfInstance(BitMapLongImpl.class); + } + + 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)); + } + 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..50945e7de 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 @@ -707,11 +707,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 shallowSizeOfInstance(BitMap.class) + bitMap.getRetainedSizeInBytes(); } 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..cf5234ac3 --- /dev/null +++ b/java/tsfile/src/test/java/org/apache/tsfile/utils/BitMapPerformanceTest.java @@ -0,0 +1,511 @@ +/* + * 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/hashCode", + ALLOCATION_OPERATION_COUNT, + equalityWorkload(arrayBitMap(), arrayBitMap()), + equalityWorkload(longBitMap(), 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(BitMap left, BitMap right) { + markAlternatingBits(left); + markAlternatingBits(right); + 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(); + } + 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 wrapperBytes = RamUsageEstimator.shallowSizeOfInstance(BitMap.class); + long arrayBytes = wrapperBytes + arrayBitMap.getRetainedSizeInBytes(); + long longBytes = wrapperBytes + longBitMap.getRetainedSizeInBytes(); + 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..2199f60fe 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 @@ -69,6 +69,75 @@ public class BitMapTest { } } + @Test + public void testImplementationSelectionAndExtension() { + assertTrue(new BitMap(0).getImplementation() instanceof BitMapLongImpl); + assertTrue(new BitMap(64).getImplementation() instanceof BitMapLongImpl); + assertTrue(new BitMap(65).getImplementation() instanceof BitMapArrayImpl); + + BitMap bitMap = new BitMap(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(64, bytes); + + assertArrayEquals(bytes, bitMap.getByteArray()); + assertEquals(bitMap, bitMap.clone()); + assertEquals(bitMap.hashCode(), bitMap.clone().hashCode()); + } + + @Test + public void testLongImplementationFullRange() { + BitMap rangeBitMap = new BitMap(64); + BitMap singleBitMap = new BitMap(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 = new BitMap(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 testIsAllUnmarkedInRange() { BitMap bitMap = new BitMap(16); @@ -141,7 +210,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)) {
