boolean[]和BitSet：哪个更高效？

Question

在内存和CPU使用方面，哪种更有效率——布尔数组还是位集？仅使用get/set/clear方法（对于数组分别为==、=、Arrays.fill）并不使用特定的位集方法。

- Maxim

Answer 1

• Boolean[]每个布尔值使用约4-20字节。
• boolean[]每个布尔值使用约1字节。
• BitSet每个布尔值使用约1位。

如果内存大小不是问题，那么使用boolean[]可能更简单。

- Peter Lawrey

---

请注意，BitSet中每个布尔值的位数为渐近值。在底层使用long[]数组，因此它被细分为64位块。 - mR_fr0g

提一下通常情况下每个值只需要4字节的指针就足够了，因为它会被缓存。除非你明确使用new Boolean()。但当然，这远不止于boolean[]。 - keiki

Boolean[]每个值使用4或8个字节，但绝对不会超过20个字节。如果假设应用程序为每个元素创建一个新的Boolean对象（尽管没有理由这样假设），那么大多数实现将需要24个字节用于对象，加上4或8个字节的引用，总共最多32个字节。但在实际应用中，谁会这样做呢... - undefined

@Holger 任何理智的人都会使用自动装箱，但在OpenJDK上，默认的对象头大小是12字节，而在Zing上是8字节。以8字节对齐，布尔值应该是16字节。 - undefined

是的，如今常见的实现方式是使用压缩类指针，我的错误。但是最大的头部仍然是16字节，这使得一个对象占用24字节，因此，对象加上一个未压缩的64位引用共占用32字节。我不确定在只需要boolean[]的情况下，是否有意义假设一个理智的人会使用Boolean[]数组。无论如何，短语“每个布尔值使用约4-20字节”是误导性的。 - undefined

Answer 2

通过在Sun JDK 1.6上使用筛法计算素数的一些基准测试（进行10次迭代来热身，给JIT编译器一个机会并排除随机调度延迟，Core 2 Duo T5600 1.83GHz）：

对于非常小的大小，BitSet比boolean[]更节省内存。数组中的每个布尔值占用一个字节。对于BitSet，从runtime.freeMemory()得到的数字有点混乱，但比boolean[]要少。

对于非常大的大小，boolean[]比较CPU高效，但它们在很大程度上是相当的。例如，对于100万个元素，boolean[]比BitSet快四倍左右（例如6毫秒比27毫秒），而对于一千万和一亿，它们则基本相同。

- starblue

---

我怀疑一些 BitSet 风格的操作（and、or、not）作为 BitSet 而不是数组会更快。值得注意哪些操作更好。标题会误导每个人永远不再使用 BitSet。 - basszero

这是一个没有测试代码和特定背景的误导性答案。我鼓励任何读到这篇文章的人仔细阅读其他答案，并对他们自己的具体情况进行思考。 - Jason C

这些只是来自特定基准测试的事实，我不认为它们有什么误导性。当然，如果这对你很重要，可以针对你的特定情况进行自己的基准测试。就个人而言，我更喜欢 BitSet，因为它表达了意图，除非我有许多相对较小的位集运行并需要优化运行时间。 - starblue

@starblue，您能解释一下为什么对于非常大的数据，boolean[] 和 BitSet 在 CPU 效率上大致相同吗？感觉 boolean[] 应该更高效。 - Utku

@Utku 可能是缓存的影响，因此对于访问主内存的访问，在写入字节时需要执行读取-更新-写入操作。请注意，100万字节是 boolean [] 更快的最大大小，这个大小可以合理地适应缓存。 - starblue

Answer 3

这里您可以看到一个内存/时间基准测试，比较了一个boolean[][]三角形矩阵和BitSet[]三角形矩阵。

我创建、设置和读取(size * (size-1) / 2)个值，并比较内存使用和时间...

希望这有所帮助...

这里是代码...（只是快速脏代码测试，抱歉 ;)

import java.util.BitSet;
import java.util.Date;

public class BooleanBitSetProfiler {

    Runtime runtime;
    int sum = 0;
    public void doIt() {

        runtime = Runtime.getRuntime();
        long[][] bitsetMatrix = new long[30][2];
        long[][] booleanMatrix = new long[30][2];
        int size = 1000;
        for (int i = 0; i < booleanMatrix.length; i++) {
            booleanMatrix[i] = testBooleanMatrix(size);
            bitsetMatrix[i] = testBitSet(size);
            size += 2000;
        }
        int debug = 1;
        for (int j = 0; j < booleanMatrix.length; j++){
            System.out.print(booleanMatrix[j][0] + ";");
        }
        System.out.println();
        for (int j = 0; j < booleanMatrix.length; j++){
            System.out.print(booleanMatrix[j][1] + ";");
        }
        System.out.println();
        for (int j = 0; j < bitsetMatrix.length; j++){
            System.out.print(bitsetMatrix[j][0] + ";");
        }
        System.out.println();
        for (int j = 0; j < bitsetMatrix.length; j++){
            System.out.print(bitsetMatrix[j][1] + ";");
        }
        System.out.println();
    }

    private long memory () {
        return runtime.totalMemory() - runtime.freeMemory();
    }
    private long[] testBooleanMatrix(int size) {
        runtime.gc();
        long startTime = new Date().getTime();
        long startMemory = memory();
        boolean[][] matrix = new boolean[size][];
        for (int i = 0; i < size; i++) {
            matrix[i] = new boolean[size - i - 1];
        }
        long creationMemory = memory();
        long creationTime = new Date().getTime();
        for (int i = 0; i < size; i++)  {
            for (int j = 0; j < matrix[i].length; j++) {
                matrix[i][j] = i % 2 == 0;
            }
        }
        long setMemory = memory();
        long setTime = new Date().getTime();
        for (int i = 0; i < size; i++)  {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j]) sum++;
            }
        }
        long readTime = new Date().getTime();
        System.out.println("Boolean[][] (size " + size + ")");
        System.out.println("Creation memory " + printMem(creationMemory-startMemory) + ", set memory " + printMem(setMemory-startMemory));
        System.out.println("Creation time " + printTime(creationTime-startTime) + ", set time " + printTime(setTime - creationTime) + " read time " + printTime(readTime - setTime) + "\n");
        runtime.gc();
        return new long[]{(setMemory-startMemory)/(1024*1024), (readTime-startTime)};
    }
    private long[] testBitSet(int size) {
        runtime.gc();
        long startTime = new Date().getTime();
        long startMemory = memory();
        BitSet[] matrix = new BitSet[size];
        for (int i = 0; i < size; i++) {
            matrix[i] = new BitSet(size - i - 1);
        }
        long creationMemory = memory();
        long creationTime = new Date().getTime();
        for (int i = 0; i < size; i++)  {
            for (int j = 0; j < matrix[i].size(); j++) {
                matrix[i].set(j, (i % 2 == 0));
            }
        }
        long setMemory = memory();
        long setTime = new Date().getTime();
        for (int i = 0; i < size; i++)  {
            for (int j = 0; j < matrix[i].size(); j++) {
                if (matrix[i].get(j)) sum++;
            }
        }
        long readTime = new Date().getTime();
        System.out.println("BitSet[] (size " + size + ")");
        System.out.println("Creation memory " + printMem(creationMemory-startMemory) + ", set memory " + printMem(setMemory-startMemory));
        System.out.println("Creation time " + printTime(creationTime-startTime) + ", set time " + printTime(setTime - creationTime) + " read time " + printTime(readTime - setTime) + "\n");
        runtime.gc();
        return new long[]{(setMemory-startMemory)/(1024*1024), (readTime-startTime)};
    }

    private String printMem(long mem) {
        mem = mem / (1024*1024);
        return mem + "MB";
    }
    private String printTime(long milis) {
        int seconds = (int) (milis / 1000);
        milis = milis % 1000;
        return seconds > 0 ? seconds + "s " + milis + "ms" : milis + "ms";
    }
}

- tagore84

Answer 4

关于内存，BitSet 的文档已经非常明确了。具体来说：

• 每个位集都有一个当前大小，即位集当前使用的位数。请注意，大小与位集的实现相关，因此它可能随着实现而改变。位集的长度与位集的逻辑长度相关，并独立于实现定义。

Java库类的源代码是公开可用的，人们可以轻松地自行检查。特别是：

The internal field corresponding to the serialField "bits".
89 
90     private long[] words;

关于速度，它取决于使用者的具体操作。一般来说，在编写代码时不要过早考虑速度问题，应该使用语义最为清晰而且代码最易懂的工具。只有在发现性能需求未能达到并确定瓶颈之后才进行优化。

在stackoverflow上询问A是否比B更快等类似问题通常是愚蠢的，原因如下（但不仅限于以下）：

1. 它取决于应用程序，而没有人可以对它进行全面地回答。所以应在使用环境中对其进行分析和性能测试，确保优化值得投入。 2. 此类关于速度的问题通常表明提问者认为他们关心效率，但却不愿意进行性能测试和定义性能需求。实际上，这通常是提问者走了错误方向的信号。

我知道这是一个老问题，但它最近又被提及，我相信这值得添加。

- Jason C

Answer 5

虽然有些超出你的问题范围，但如果存储是一个问题，你可能需要了解Huffman compression。例如，00000001可以通过频率压缩成等价于{(7)0, (1)1}。一个更“随机”的字符串00111010将需要更复杂的表示方式，例如{(2)0, (3)1, (1)0, (1)1, (1)0}，并且占用更多空间。根据您的位数据结构，您可能会从使用它获得一些存储优势，超出BitSet。

- Rothko

Answer 6

这取决于具体情况。BitSet更节省内存，但如果需要多线程访问，boolean[]可能是更好的选择。例如，对于计算质数，您只需将布尔值设置为true，因此不需要同步。 Hans Boehm 写了一些关于此的论文，相同的技术也可以用于标记图中的节点。

- kohlerm

---

只要您的布尔数组不增长，那对于并发使用肯定更好。 - Randolpho

你仍然需要同步来确保所有线程都看到其他线程已经写入的内容。这里是一篇相当不错的介绍文章：http://jeremymanson.blogspot.de/2007/08/atomicity-visibility-and-ordering.html。我很想阅读Hans Boehm的论文，可惜链接失效了。 - jcsahnwaldt Reinstate Monica

我想我找到了Hans Boehm的论文：http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf 。结果是：您不需要同步，您只需希望线程能够看到其他线程所做的事情。如果它们没有看到，也没有关系，它们只是在做重复的工作。但实际上，更改通常是可见的，算法将呈线性加速状态。 - jcsahnwaldt Reinstate Monica

Answer 7

从Java到CPU是完全基于虚拟机的。例如，布尔值过去实际上是作为32位值实现的(很可能到今天仍然如此)。

除非你知道它很重要，否则最好编写清晰的代码、分析性能，然后修复那些运行缓慢或消耗大量内存的部分。

你可以边做边改进。例如，我曾经决定不在字符串上调用.intern()，因为当我在分析器中运行代码时，它会使其变慢(尽管使用的内存更少)。

- TofuBeer

Answer 8

我相信BitSet更加节省内存和CPU，因为它可以将位数据内部打包成int、long或本地数据类型，而boolean[]则需要一个字节来存储每个位数据。此外，如果您使用其他方法（如and、or等），您会发现BitSet更加高效，因为不需要迭代数组的每个元素；而是使用位运算。

- lacqui

---

内存效率 - 可能是真的。CPU 效率 - 绝对不是。在 x86 上执行两个位操作（shift/and 或 shift/or）和最多两个内存访问（尽管很可能被缓存），几乎总是比单个内存访问低效。 - EFraim

通过减少内存使用量，您增加了在缓存中拥有所有内容的机会。缓存未命中非常昂贵。我不会感到惊讶，如果看到这个因素使 BitArray 更快。 - Jon Skeet

例如：如果整个 bitset 可以放入缓存中，但 boolean[] 不能，并且需要随机访问，则 bitset 的性能优于 boolean[]。 - Ron