logo标签列表

结构体数组还是数组结构体？

javadata-structures
6

嗯，我有一个由结构体组成的数组表格需要存储在Java中。不加考虑内存的朴素方法是这样的:

public class Record {
  final private int field1;
  final private int field2;
  final private long field3;
  /* constructor & accessors here */
}

List<Record> records = new ArrayList<Record>();

如果我最终使用大量（> 106）的记录，其中单个记录偶尔一次访问一个，那么我该如何确定前面提到的方法（ArrayList）与优化存储成本的方法相比如何？
public class OptimizedRecordStore {
  final private int[] field1;
  final private int[] field2;
  final private long[] field3;

  Record getRecord(int i) { return new Record(field1[i],field2[i],field3[i]); }
  /* constructor and other accessors & methods */
}

编辑：

  • 假设记录数量很少更改或从未更改
  • 我可能不会使用OptimizedRecordStore方法，但我想了解存储成本问题，以便我可以有信心做出决定。
  • 显然，如果我在上述OptimizedRecordStore方法中添加/更改记录的数量，我要么必须用新对象替换整个对象，要么删除“final”关键字。
  • kd304提出了一个我心中有的好观点。在类似于此的其他情况下，我需要对记录进行列访问，例如，如果field1和field2是“时间”和“位置”，并且重要的是将这些值作为数组获取以便与MATLAB一起使用，以便可以高效地进行图形化/分析。
这个优化是怎么实现的？你是指成员对齐吗？ - EFraim
每个记录对象都会产生存储成本（4字节？8字节？我不知道），并且创建每个对象都会产生性能成本。如果我只有1000个，我不在乎。但是如果我有100,000或1,000,000个，我就开始关心了。 - Jason S
11个回答
7

在这种情况下，一般的“必要时优化”答案并没有起到太大帮助，因为程序员应该始终注意设计选择上的性能差异，特别是API编写者，尤其当这个选择导致了数量级的性能惩罚。

原始问题非常合理，考虑到他的特定情况，我倾向于认为第二种方法更好。我曾经写过图像处理代码，每个像素需要一个数据结构，这种情况与这种情况相似，只是我需要频繁随机访问每个像素。为每个像素创建一个对象的开销是巨大的。

6
如果你有数百万条记录，第二种方法有几个优点：
1. 内存使用：第一种方法会占用更多的内存，因为a)堆中的每个Java对象都有一个头（包含类ID、锁状态等）；b)对象在内存中对齐；c)每个对象引用占4字节（在64位JVM上使用压缩OOPs或32位JVM上），或8字节（在没有压缩OOPs的64位JVM上）。有关详细信息，请参见CompressedOops。因此，第一种方法需要大约两倍的内存（更确切地说，根据我的基准测试，在32位Java 7上具有16字节有效负载+对其进行引用的对象占用28字节，在具有压缩OOPs的64位Java 7上占用36字节，在没有压缩OOPs的64位Java 7上占用40字节）。
2. 垃圾收集：虽然第二种方法似乎会创建许多对象（每次调用getRecord时都会创建一个对象），但在某些情况下现代服务器JVM（例如Oracle的Java 7）可以应用逃逸分析和栈分配以避免堆分配临时对象；无论如何，垃圾收集短寿命的对象很便宜。另一方面，如果没有数百万个长期存在的对象（例如第一种方法中存在的对象）需要检查其可达性，则可能更容易进行垃圾回收（或者至少这些对象可能需要使应用程序需要更加小心调整GC生成大小）。因此，第二种方法对于GC性能可能更好。然而，为了看到在实际情况下是否有差异，一个人应该自己制作基准测试。
3. 序列化速度：在磁盘上序列化/反序列化大量原始数组的速度仅受HDD速度限制；序列化许多小对象不可避免地较慢（特别是如果您使用Java的默认序列化方式）。
因此，我经常使用第二种方法来处理非常大的集合。但是，当然，如果你有足够的内存并且不关心序列化，第一种方法更简单。
5
第二个版本要糟糕得多。在插入或删除时，您不仅要调整一个数组的大小，还要调整三个数组的大小。更重要的是，第二个版本将导致创建更多的临时对象，并且在访问时会这样做。从垃圾回收的角度来看，这可能会导致大量的垃圾。不好。
一般来说，在考虑性能之前，您应该担心如何长时间使用对象。所以您有一个具有三个字段或三个数组的记录。哪一个更准确地描述了您正在建模的内容？我的意思是，当您插入或删除项目时，您是在做三个数组中的一个还是全部三个？
我怀疑是后者，在这种情况下，前者更有意义。
如果您真的关心插入/删除性能，那么可能需要使用不同的数据结构，例如SortedSet或Map或SortedMap。
4
Cletus，我非常尊重你的想法和意见，但你给了我高级编程和软件设计的观点，这不是我想要的。在我能够对不同的实现方式的成本有直觉感觉和/或能够估算这些成本之前，我无法学会忽略优化。 - Jason S
1
@Jason：我已经告诉你这种情况下所有关于优化的知识了。第一个版本将调整一个数组（这就是最终的ArrayList）。第二个版本会调整三个数组并创建大量临时对象。而且它这样做似乎没有任何好处（至少我看不出来）。你不需要再去寻找其他原因了。 - cletus
1
@Jason S - 在你实际分析应用程序并发现真正的问题之前，你应该忽略优化。否则，你可能会浪费时间，降低代码的适应性和简洁性。 - whaley
1
@whaley：如果你把“你应该忽略优化”改为“在大多数情况下，你应该忽略优化”，我同意你的观点。就像我之前所说的，我需要对事物的成本有一些直观的感觉。 - Jason S
2
“过早的优化是万恶之源” (c) Donald Knuth - SomeWittyUsername
3
你将如何访问数据？如果字段的访问总是耦合的，那么请使用第一个选项；如果您将单独处理字段，则第二个选项更好。请参阅维基百科中的文章：Parallel Array。一个很好的例子是模拟，其中数字数据打包在同一个数组中，而其他属性（如名称、颜色等）则在另一个数组中进行访问，以便在其他数组中呈现数据时方便访问。
3

我很好奇，所以我实际上进行了基准测试。如果您不像[1]那样重新创建对象，则SoA在工作负载[2]的情况下比AoS快5-100％。在这里查看我的代码：

https://gist.github.com/twolfe18/8168262c5420c7a62d39

[1] 我没有加上这个，因为如果你足够关注速度以考虑这个重构，那么这样做就很愚蠢。

[2] 这也没有考虑重新分配，但是再次说明，这通常是可以摊销或静态知道的。对于纯速度基准测试来说，这是一个合理的假设。

2
我会选择第一种方法（结构体数组），除非您相对较少地访问存储并且遇到严重的内存压力问题。
第一个版本基本上以它们的“自然”形式存储对象（顺便说一句，使用不可变记录+1）。由于每个对象的开销（可能在您的JVM上大约为8-16字节）这使得它使用了更多的内存，但是通过一步简单的操作方便地访问和返回对象，并以人类可理解的形式呈现。
第二个版本总体上使用的内存较少，但是在每次“获取”时分配一个新对象是一个相当丑陋的解决方案，如果访问频繁，则性能将不佳。
考虑一些其他可能性：
一个有趣的“极端”变体是采用第二个版本，但编写您的算法/访问方法直接与底层数组交互。这显然会导致复杂的相互依赖和一些丑陋的代码，但如果您确实需要最佳性能，则可能会给您提供绝对最佳的性能。在处理大量3D坐标的密集图形应用程序中经常使用此方法。
“混合”选项是将基础数据存储在数组结构中，如第二个版本，但在HashMap中缓存访问的对象，以便仅在第一次访问特定索引时生成对象。如果只有很小的一部分对象可能被访问，但是所有数据都需要“以防万一”，那么这可能是有意义的。
2

(不是直接的答案，但我认为应该给出)

从你的评论中，

"cletus - 我非常尊重你的想法和意见，但你给了我高级编程和软件设计的观点，这不是我要找的。在我能够直观地感受到不同实现风格的代价和/或估算这些代价之前，我无法学会忽略优化。- Jason S 2009年7月14日下午2:27"

你应该总是忽略优化，直到它成为问题。最重要的是让系统可供开发人员使用（以便他们可以使其对用户可用）。实际上，在20年的专业编码中，你只关心过优化两次：

  1. 编写一个其主要目的是比另一个产品更快的程序
  2. 编写一个智能手机应用程序，旨在减少客户端和服务器之间发送的数据量

在第一种情况下，我编写了一些代码，然后通过分析器运行它，当我想做某事并且不确定哪种方法最好（用于速度/内存）时，我会以一种方式编码并在分析器中查看结果，然后以另一种方式编码并查看结果。然后我会选择两者中更快的那个。这很有效，你可以学到很多关于低级决策的知识。但是，我没有允许它影响更高级别的类。

在第二种情况下，没有涉及编程，但我做了同样基本的事情，即查看被发送的数据并找出如何减少发送的消息数量以及字节数。

如果你的代码清晰明了，那么一旦发现它变慢，就会更容易加速。正如Cletus在他的回答中所说，你正在调整一次 -vs- 三次...一次比三次更快。从更高的角度来看，一次比三次更简单易懂，因此更有可能是正确的。

就我个人而言，我宁愿慢慢地得到正确的答案，也不要快速得到错误的答案。一旦我知道如何得到正确的答案，我就可以找出系统缓慢的地方，并用更快的实现替换掉它们。

3
+1 - 但是我不同意"始终忽略优化"，尤其是"始终"这个词。我同意剩下的部分，但请理解有经验的程序员会基于他们的经验做出很多无意识的决策，相比之下我们这些经验较少的程序员必须要通过咕哝着学习。在过去的12个月里，我有几个应用程序因为不能正常工作而不得不进行优化 -- 我处理的是每秒需要处理数百千字节的系统，每当我采用"等到以后再优化"的方式时，最终都得重新设计我的代码。 - Jason S
我同意潜意识部分...但我不认为在代码“完成”之前应该有一个有意识的努力（大多数情况下）去找出最快的方法。 最近我做了一个需要在5分钟内完成的新系统，我从大约12分钟开始，现在已经缩短到约3.5分钟。 在这个过程中，我逐步重写了100％的代码，直到速度变快。每次迭代也都使事情变得更好。 最后，我得到了一些与我预期非常不同，但非常好的东西。 - TofuBeer
1
另一个想法是，你不会刻意让事情变慢，例如在不需要重复项时选择List而不是Set（因此必须在插入之前迭代List），但这与担心数据表示等不同...如果你总是选择更简单的代码，然后找出它为什么变慢，你将更容易地加速它需要加速的地方。 - TofuBeer
2
请注意，第二种方法可能会对缓存行为产生负面影响。如果您想一次访问一条记录，最好将该记录不分散在各个地方。
另外，在第二种方法中，您唯一节省的内存可能是由于成员对齐而导致的（并且需要分配一个单独的对象）。 否则，它们在渐近意义下具有完全相同的内存使用。在我看来，由于局部性，第一种选项要好得多。
如果只是对一个字段进行操作，那么不用判断。 - fortran
为什么相同的内存使用渐近？对于第一种方法，一个记录= 16字节+每个记录的一些对象开销+ ArrayList的一些开销。对于第二种方法，它是16字节*记录数+ OptimizedRecordStore的一些开销。如果对象开销为8字节，则第一种方法的内存使用大约多50％...也许这没关系，但我想弄清楚它是什么。 - Jason S
2

每当我尝试在Java中进行数字计算时，我总是不得不回归到C风格的编码（即接近您的选项2）。这最小化了系统中漂浮的对象数量，因为您只有3个对象，而不是1,000,000个对象。使用C风格，我能够对实时音频数据进行一些FFT分析，但使用对象会慢得多。

1
我也会选择 ArrayList 版本，这样我就不需要担心它的增长。你需要像访问列一样访问值吗？你提出问题背后的场景是什么？
编辑：你也可以使用一个常见的 long[][] 矩阵。我不知道你如何将列传递给 Matlab，但我猜你不会因为基于列的存储而获得更快的速度，更可能是在 Java 计算中失去速度。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接