BitSet 值得使用吗？

Question

我做了一个 Java 对象，它有很多布尔字段。当我开始质疑它的用处时，我正在考虑使用 BitSet。

当然，人们会出于内存原因使用它，因为 boolean 单独是 8 位，数组中有 4 位。使用 BitSet，每个值都存储为一个位。 但是，节省下来的内存不会被下面的开销打飞吗？

BitSet class 和方法定义元数据（每个运行时）
对象需要作为语义检索值的键（根据 class 使用 BitSet）
BitSet 中 bits 数组的元数据（每个实例）

与使用 booleans:

布尔值（每个实例）

下面再看一下class:

private boolean isVisible; // 8 bits per boolean * 82 booleans = ~0.6Kb
// 81 lines later...
private boolean isTasty;

// ...

public boolean isVisible() { return isVisible; }
// ...
public boolean isTasty() { return isTasty; }

public void setVisible(boolean newVisibility) { isVisible = newVisibility; }
// ...
public void setTasty(boolean newTastiness) { isTasty = newTastiness; }

现在，如果我要将我所有的 boolean 合并为一个 BitSet 并且仍然保持我的代码语义，我可能会这样做：

private static final int _K_IS_VISIBLE = 1; // 32 bits per key * 82 keys = ~2.5Kb
// ...
private static final int _K_IS_TASTY = 82;
private BitSet bools = new BitSet(82); // 2 longs = 64b

// ...

public boolean isVisible() { return bools.get(_K_IS_VISIBLE); }
// ...
public boolean isTasty() { return bools.get(_K_IS_TASTY); }

public void setVisible(boolean newVisibility) { bools.set(_K_IS_VISIBLE, newVisibility); }
// ...
public void setTasty(boolean newTastiness) { bools.set(_K_IS_TASTY, newTastiness); }

tl;博士

costOfUsingBitSet =
    bitSetMethodsAndClassMetaData + // BitSet class overhead
    (numberOfKeysToRetrieveBits * Integer.SIZE) + // Semantics overhead
    (numberOfBitSetsUsed * floor((bitsPerBitSet / Long.SIZE) + 1)); // BitSet internal array overhead

可能还有更多。而使用 booleans 将是：

costOfBooleans = 
    (numberOfBooleansOutsideArrays * 8) + 
    (numberOfBooleansInsideArrays * 4);

感觉BitSet的开销要高很多。我说的对吗？

Answer 1

BitSet 会占用更少的内存，只使用一位效率更高。无论您有多少 class 实例，您正在查看的方法开销都是一次，因此其成本基本上摊销为 0

boolean 相对于 boolean 数组或 BitSet 的优势在于它不是 Object，因此您的间接

缓存命中是性能的主要驱动因素，因此您必须权衡更少的缓存命中与更高的内存消耗导致从缓存中逐出数据的可能性

粗略地说，几个 booleans 会更快但更多的内存，因为你有更多的字段或接近巨大的数字，规模将达到 BitSet

Answer 2

space boolean[] 和 BitSet 之间的比较不错：

https://www.baeldung.com/java-boolean-array-bitset-performance

认为他们在这里交换了标签。 BitSet.

中每个内存（蓝色）应该有更多位

这里的关键是，BitSet 在内存占用方面优于 boolean[]，除了最少的位数。

您的示例中的另一种方法是使用 2 long 作为位标志。

class A {
// 1st set
private static final long IS_VISIBLE_MASK = 1; 
...
private static final long IS_DARK_MASK = 1 << 63 ; 

// 2nd set...
private static final long IS_TASTY_MASK = 1;
...

// IS_VISIBLE_MASK .. IS_DARK_MASK
long data1;

// IS_TASTY_MASK ...
long data2;

boolean isDark = (data1 & IS_DARK_MASK) != 0; 

}

限制

BitSet 带有愚蠢的限制，因为您最多可以达到 Integer.MAX_VALUE 位。我需要尽可能多的位，我可以存储在 RAM 中。 So modified the original implementation 两种方式：

对于固定大小的 LongBitSets（即用户在构建时指定长度）浪费更少的计算。
它可以到达最大可能单词数组中的最后一位。

在 this thread

中添加了有关限制的详细信息

BitSet 值得使用吗？

Is BitSet worth using?

java

memory-management

bitset

tl;博士

这里的关键是，BitSet 在内存占用方面优于 boolean[]，除了最少的位数。

限制