提问人：Simon 提问时间：12/17/2009 更新时间：12/18/2009 访问量：4699
我应该如何处理 Java 中非常大的数组？
How should I deal with a very large array in Java?
问：
我有一个算法，它目前分配了一个非常大的双精度数组，它经常更新和搜索。数组的大小为 N^2/2，其中 N 是算法运行的行数。我还必须保留整个事情的副本，用于与算法周围的应用程序相关的目的。
当然，这对我的算法可以处理的行数施加了限制，因为我有堆限制要应对。到目前为止，我已经要求使用该算法的人更新 -Xmx 设置以分配更多空间，并且效果很好。但是，我现在遇到了一个真正的问题，我需要这个数组大于内存的容量。
我已经计划改变我的算法，以减轻这个大数组的必要性，并在该领域取得一些有希望的结果。然而，这是对流程的根本性改变，需要更多的工作才能达到我当前代码的高度完善状态，该代码在生产中非常成功地运行并且已经运行了好几年。
因此，在我完善新算法的同时，我想延长现有算法的寿命，这意味着要解决与分配大量双精度数组相关的堆限制。
我的问题是处理它的最佳方法是什么？我应该使用 nio FileChannel 和 MappedByteBuffer，还是有更好的方法。如果我确实使用 nio 方法，与相同大小的内存中阵列相比，我应该期望获得什么样的性能影响？
谢谢
答：
6赞
Paul Wagland
12/17/2009
#1
如果您开始用完可用内存，那么您可能很快就会开始用完可用的数组索引，数组的大小限制为 ，并且当使用双倍作为数组元素时，大小“仅”为 32GB。Integer.MAX_VALUE
获得一台具有 32GB 内存的机器很昂贵，但可能不如修改算法的时间和所有相关的测试那么昂贵。
但是，如果客户端运行到内存的边缘，并且它们的数据集仍在增长，那么您现在咬紧牙关进行更改以能够在任何给定时间使用更少的内存是有意义的，因为它们可能很快就会超过数组。
假设数组填充有些稀疏，您拥有的另一个选项是使用各种稀疏数组数据结构之一，尽管这些结构往往仅在数组填充率低于 20% 时才有用。
编辑：由于您似乎已经研究了替代方案，因此MappedByteBuffer很可能是要走的路。显然，这将对性能产生影响，但是，如果您主要从阵列中执行顺序读取和写入操作，那么这应该不会太糟糕。如果你正在做随机的读取和写入，那么这将变得非常慢，非常快。或者很慢，很慢......取决于你如何看待这些事情;-）
评论
0赞
Simon
12/17/2009
买一个更大的盒子可能确实会更便宜，但这对客户来说并不是一个非常可口的答案。到目前为止，对话已经结束了 客户：“它又崩溃了”我：“增加分配给 JVM 的内存”。如果我的下一个答案是“买一台具有 32GB RAM 的新电脑”，他们会反击。事实上，代码已经足够抽象了，我想我可以在运行时注入一个不同的数组类。因此，我的风险仅限于我实现基于 nio 的阵列的质量。
3赞
basszero
12/17/2009
似乎更多内存推回的答案是“等到新算法完成”。你的时间是花在新算法上还是照顾旧算法更好？对于新算法，您是否有任何性能指标可以展示来说服客户？
0赞
Simon
12/17/2009
@basszero商业情况是这样的，答案是我必须两者兼而有之。我的时间最好花在让他们与客户成功上，这在扩展现有算法方面投入相对较少。我认为，如果我能得到大约两倍于现在的容量，我就可以为自己争取一年的时间来真正确定“合适的”解决方案，并对其进行充分测试，以便我可以将其插入到他们现有的框架中。他们非常善解人意，我们同意长期解决方案是正确的，这只是一个在此时此地帮助他们的问题。
0赞
martinr
12/17/2009
我们一次又一次地回到如何对数据集进行分区......我猜这对这个应用程序来说很棘手。任意分区似乎是有序的。在最坏的情况下，如果无法删除随机访问性，则系统速度很慢。我猜，但也许该算法可以分几个阶段运行，在某些阶段的数据上小于双精度（使用例如 8 位代码对某些双精度值进行分类），并在需要时引用完整的 64 位。
0赞
Simon
12/17/2009
@martinr当然，你是对的。即使在我现在拥有的范围内（25k 行），我也有一个 Paul 所暗示的寻址问题，所以我无论如何都必须对数组进行分区。然而，对于完全重写算法的解决方案来说，这是一个不那么突兀的解决方案，正如我所说，它正在进行中。
0赞
Thorbjørn Ravn Andersen
12/17/2009
#2
您正在研究如何编写最能利用缓存（如 CPU 中的内存缓存）的软件。这很难做对，而“正确”的方法取决于你的算法是如何设计的。
那么，你的程序在算法上实际上是做什么的呢？
评论
1赞
Simon
12/17/2009
如果我回答这个问题，你保证不会告诉我以不同的方式实现我的算法吗？我认为通过回答你的问题，我会遇到的问题是，我有一个低效的算法。我知道这一点，并且我正在修复它。我正在寻找一种延长其寿命的方法，以便我有时间完成重新实现。对不起，有点短，但我现在需要的是我关于 nio 对我眼前问题的利弊的问题的答案。
3赞
tster
12/17/2009
@Simon，除非我们知道算法的特征，否则我们无法告诉您。例如，如果它在数组中对不同的元素进行大量二进制搜索，那么您可能会遇到麻烦。但是，如果在较小的区域中花费大量时间，然后移动到另一个区域，则缓存和磁盘 IO 可能会成功。
0赞
Thorbjørn Ravn Andersen
12/17/2009
@Simon，我对你选择的算法不感兴趣，但我对你选择的算法的行为感兴趣。通常，选择哪个顺序来迭代多维数组的维度很重要，例如
2赞
martinr
12/17/2009
#3
如果在电脑上运行，则映射文件的页面大小可能为 4 KB。
因此，问题实际上始于我是否开始将数据交换到磁盘，“我对RAM的随机访问有多随机”？
而且（...我可以吗，如果是这样......如何对双精度进行排序，以最大限度地利用在下一个 4K 磁盘获取之前同时访问 4K 页面中的双精度，而不是在每个页面中一次访问几个双精度？
如果您使用标准 IO，您可能仍然希望在块中读取和写入，但其他块可能会更小。扇区至少为 512 字节，磁盘集群更大，但考虑到每个 IO 都有内核往返开销，读取大小最好？
对不起，恐怕你最好的下一步在很大程度上取决于你使用的算法和数据。
评论
0赞
Simon
12/17/2009
+1 这是一个非常好的转向，谢谢。我意识到我的问题还有很多，这取决于我的算法如何工作，但这给了我一些参数来做出判断，这就是我所希望的。
0赞
martinr
12/17/2009
我承认，在设计中考虑 L2 缓存大小问题也很重要。
0赞
martinr
12/21/2009
引用 ChrisW 的话：“我很惊讶：queue.acm.org/detail.cfm?id=1563874 中间的图 3 表明，当您进行顺序访问时，内存的速度仅快了大约 6 倍（内存为 350 Mvalues/秒，而磁盘为 58 Mvalues/秒）;但是当你进行随机访问时，它的速度要快 100,000 倍左右。stackoverflow.com/questions/1371400/......
0赞
tster
12/17/2009
#4
您可以尝试将数组存储为数据库表中的行，并使用存储的过程对其进行更新和搜索。
另一个想法：
使用 B 树作为阵列，并在磁盘上保留一些叶子。确保 B 树的节点大小为页面大小或多个页面大小。
评论
0赞
Simon
12/17/2009
我已经考虑过这一点，并且在数据库方面有很多经验。在这种情况下，阻止我的是它极大地增加了我摆在客户面前的解决方案的复杂性。在某些时候，我可能会转向使用数据库进行一些持久性，但现在我判断对于我当前的问题来说，这有点开销太大了，这只是为了延长现有算法的寿命。
0赞
Stephen C
12/17/2009
#5
如果问题是内存不足，简单的解决方案是用更多内存升级硬件，增加 Java 堆大小和/或切换到 64-bi5t JVM。
另一方面，如果你正在反对 Java 对数组大小的限制，你可以沿着 ByteBuffer 路由，或者你可以切换到使用数组数组。后者是 Sun 建议的解决方法。
使用数组数组方法，您可以（理论上）处理接近 的值。在实践中，您的限制将取决于您拥有的物理内存量，以及使用操作系统/JVM 组合可以解决的内存量。N2**31
1赞
Stu Thompson
12/17/2009
#6
我对 Java 的 MappedByteBuffers 总体上有很好的体验，并鼓励您更深入地了解它。它很可能允许您不再处理更改。请注意，如果您需要超过 2-4GB 的可寻址空间，则需要 64 位 CPU、操作系统和 JVM。-Xmx
为了解决索引问题，您可以编写一个分页算法，就像我在 Java 中对排序（内存映射？）文件中的二进制搜索的相关答案所做的那样。Integer.MAX_VALUE
评论
0赞
Simon
12/18/2009
医 管 局！我刚刚写完MappedByteBuffers的分页列表，很高兴看到别人的解决方案。就我而言，我没有要映射到的预先存在的文件，因此我将为每个 Integer.MAX_INT doubles 块提供一个单独的页面文件。这对我来说还有一个优势，因为我可以生成一个线程来执行相当多的搜索，从而利用我知道正在敲门和未使用的其他处理器。我偷偷地怀疑我可能能够扩展我的算法的大小，同时使其更快。我们拭目以待。谢谢你的帖子+1
0赞
Stu Thompson
12/18/2009
很高兴听到听到:)我一直对这个答案感到非常满意。至于您的性能想法，请务必检查 CPU 是否是瓶颈而不是磁盘。如果稍后，多个进程/线程同时访问磁盘的不同部分可能会妨碍您的整体性能。即使是前者，有节制的添加线程的方法也是一个好主意。（对我来说，这是艰难的教训;)
0赞
Dave Griffiths
12/17/2009
#7
请注意，某些操作系统比其他操作系统对内存映射的支持更好。
我很想这样做：
- 将所有数组 get/put 放在对象接口后面（如果它们还没有），从而让您腾出时间轻松更改实现。
- 使用 SoftReferences 数组，其中每个 SoftReference 都指向该行的双精度数组。使用 ReferenceQueue 在 GC 将数组踢出时将数组保存到磁盘。当 get（） 返回 null 时，从磁盘中检索。
您可能会发现这样可以更好地控制性能 - 可以根据需要调整 -Xmx。
评论