为什么Java中BitSet的内部数据存储为long[]而不是Java中的int[]? [英] Why is the internal data of BitSet in java stored as long[] instead of int[] in Java?

问题描述

在java中，BitSet 存储为 long[] 而不是 int[]，我想知道为什么?这是jdk中的代码:

In java, the internal data of BitSet is stored as long[] instead of int[], I want to know why? Here is the code in jdk:

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

如果一切都与性能有关，我想知道为什么 long[] 存储会获得更好的性能.

If it's all about performance, I wonder why long[] storage will get better performance.

推荐答案

查询或操作单个位时，没有显着差异.您必须计算单词索引并读取该单词，并且在更新的情况下，操作该单词的一位并将其写回.int[] 和 long[] 都是一样的.

When querying or manipulating a single bit, there is no significant difference. You have to calculate the word index and read that word and, in case of an update, manipulate one bit of that word and write it back. That’s all the same for int[] and long[].

有人可能会争辩说，使用 long 而不是 int 可能会增加单个位操作必须传输的内存量，如果你有一个真正的32 位内存总线，但由于 Java 是在上个世纪 90 年代设计的，因此设计者认为这不再是问题.

One could argue that doing it using a long instead of int could raise the amount of memory that has to be transferred for a single bit operation if you have a real 32 bit memory bus, but since Java was designed in the nineties of the last century, the designers decided that this is not an issue anymore.

另一方面，当一次处理多个位时，您会大获全胜.当您执行诸如 和、 或 或 xor 对整个BitSet，你可以对整个字执行操作，读取64位，使用时一次长数组.

On the other hand, you get a big win when processing multiple bits at once. When you perform operations like and, or or xor on an entire BitSet, you can perform the operation on an entire word, read 64 bits, at once when using a long array.

同样，当搜索下一个设置位，如果该位不在起始位置的字内，则后续字首先针对零进行测试，这是一种内在操作，即使对于大多数 32 位 CPU 也是如此，因此您可以在第一个时一次性跳过 64 个零位非零字肯定会包含下一个设置位，因此整个迭代只需要一位提取操作.

Similarly, when searching for the next set bit, if the bit is not within the word of the start position, subsequent words are first tested against zero, which is an intrinsic operation, even for most 32 bit CPUs, so you can skip 64 zero bits at once while the first non-zero word will definitely contain the next set bit, so only one bit extraction operation is needed for the entire iteration.

批量操作的这些好处将超过任何与单位相关的缺点，如果有的话.如上所述，当今的大多数 CPU 都能够直接对 64 位字进行所有操作.

These benefits for bulk operations will outweigh any single-bit related drawbacks, if there ever are one. As said, most today’s CPU are capable of doing all operations on 64 bit words directly.

这篇关于为什么Java中BitSet的内部数据存储为long[]而不是Java中的int[]?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！