logo标签列表

为什么Java中BitSet的内部数据存储为long[]而不是int[]？

javaperformancebitset
14

在Java中，BitSet的内部数据存储为long[]而不是int[]，我想知道原因？以下是JDK中的代码：

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

如果说性能是最重要的，那我想知道为什么使用 long[] 存储会得到更好的性能。

2
我想知道为什么不行？将其存储为int[]会有什么更好的效果？ - user207421
1
如果我必须猜测的话，我会说这可能与现在大多数人使用64位机器/操作系统有关，因此对长整型的操作往往得到更好的支持/更快的速度。我并不真正相信Santi的论点。 - devoured elysium
@devouredelysium，我认为“大多数人都使用64位系统”这样的说法确实非常大胆。 除了个人经验之外，您是否有其他证据来支持这个说法呢？考虑到Java被设计为在无数平台上运行（包括许多嵌入式系统），我真的不认为这是设计决策背后的原因。 - daiscog
@daiscog：然而他们选择了longs而不是ints。如果你查看BitSet的源代码，可以清楚地看到：“BitSets被打包成“words”的数组。”。 - devoured elysium
@devouredelysium 对不起，我觉得你可能误解了我的意思。我知道他们选择了long而不是int，但我想说的是，我不相信你给出的原因是他们这样做的原因。 - daiscog
5个回答
12

在64位机器上，对单个long值进行按位操作比对两个int值进行相同操作要更具有性能优势，因为硬件直接支持64位值。在32位机器上，差异可能不是非常显著。

在32位机器上，使用int[]还是long[]会有更好的性能？ - displayName
@displayName，你可以编写自己的基于int[]的“BitSet”，然后自行测试 :-) 也可以参考@Holger的答案。 - Tagir Valeev
@displayName 我会说 int[] 因为它是本地的 :D 但 Tagir 是正确的... 我们应该实现并查看。 - Willi Mentzel
@TagirValeev：你对我的评论的回应是最好的。 :) 我之所以还问是因为我觉得你可能已经知道了。我过去大约两年一直在使用C#。在我的笔记本电脑上启动eclipse需要很多“热身”。:D - displayName
@displayName：请记住，即使是32位CPU也可能具有64位内存总线以及一些适当的64位操作。这不是关于一般算术，而只是某些位操作。此外，JVM可能对标准的BitSet类有所了解，并在操作不够“本地化”时替换某些操作。更大的障碍是找到一个适当的测试机器，具有真正的 32位架构... - Holger
12

当查询或操作单个位时，没有太大的区别。您必须计算字索引并读取该字，在更新的情况下，操作该字的一个位并将其写回。这对于int []和long []都是一样的。

有人可能会认为，使用long而不是int进行操作，如果您有一个真正的32位内存总线，可能会增加必须传输的内存量，但是由于Java是设计于上世纪九十年代，设计者认为这不再是一个问题。

另一方面，当同时处理多个位时，你会获得巨大的优势。当执行像and、or或xor这样的操作时，你可以在使用long数组时一次性地对整个字进行操作，读取64位。

同样，当查找下一个设置的位时，如果该位不在起始位置的字中，则首先将后续字与零进行比较，这是一个内在操作，即使对于大多数32位CPU也是如此，因此您可以一次跳过64个零位，而第一个非零字一定会包含下一个设置的位，因此整个迭代只需要一个位提取操作。

如果有单位相关的缺点，这些针对批量操作的优势将超过它们。正如所说，今天的大多数CPU都能够直接在64位字上执行所有操作。

由于BitSet是一种数据结构，因此在考虑性能时，我们应该考虑它所支持的操作。你是第一个以这种方式分析性能的人。干得好！ - jerry_sjtu
6
根据对这里源码的粗略阅读，似乎主要原因纯粹出于性能考虑。这是从源代码中检索到的注释。

BitSet被打包成“words”数组。目前，一个word是long类型，由64位组成，需要6个地址位。word大小的选择完全基于性能考虑。

如果所有问题都与性能有关，那么我想知道为什么 long[] storage 会获得更好的性能。 - jerry_sjtu
这个类调整容量时，增加64比增加32更快。 - kucing_terbang
1
这肯定是一个优化问题：一个 long 值最多可以存储 64 位，而 int 只有 32 位。因此，任何长度小于 64 的用户只需要在数组中有 一个条目。如果它是一个int 数组，就需要 两个条目，这样会更慢，也更难以维护。
1
为什么它的速度较慢，而且维护起来更加困难呢？ - devoured elysium
1
显然，将两个项目存储在数组中所需的时间是存储一个项目的两倍。 - Little Santi
不一定。这在很大程度上取决于您的硬件。 - devoured elysium
1
我不是指将值存储在一行内，而是在循环内部，这是像BitSet这样的通用解决方案中的情况：当n==2时，for (int i=0;i<n;i++) {array[i]=0;} 比n==1时需要更多的时间。 - Little Santi
这对我来说就是这样。如果我设计这个类，我会选择一个长整型数组，正是出于这个原因（除了“更难维护”这一点，我不同意）。 - daiscog
显示剩余2条评论
1
使用 long[] 时，BitSet 的基数比使用 int[] 大得多。因为数组的最大大小对于它们两者都相当（但受堆大小限制）。
这表面上是有道理的；数组的最大元素意味着长整型数组给你更多可能的位数。然而，我认为想要拥有那么多标志的使用情况并不足以成为这个原因的真正原因。 - daiscog
BitSet 的方法使用 int 索引参数和返回值，因此由于 API 的限制，它们仅限于 2³¹ 位。因此，其内部数组所施加的理论限制比实际限制高32倍或64倍并不重要。即使是 byte 数组也能存储比 API 支持的更多位。 - Holger
是的，bitSet内部数组使用整数索引，但值为长整型，因此我们可以容纳更多的位数，而不是使用int。 - Lemonov
我说的不是数组索引，而是 BitSet 的 API。试着用一个大于 2³¹ 的数字来 设置 一个位——这是不可能的，因为没有提供该操作的方法。同样，size() 返回一个 int。所以，使用 long[] 而不是 int[] 内部仍然最多只有 2³¹ 个位数，这是当前 API 的限制。 - Holger
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接