数组数组与多维数组的性能比较

Question

当我在大学使用C++时，我被告知尽可能使用多维数组（以下简称MDA），因为它表现出更好的内存局部性，因为它是在一个大块中分配的。而另一方面，数组的数组（AoA）则是在多个较小的块中分配的，可能散布在物理内存中的任何空缺处。

所以我想第一个问题是：这是一个谬论，还是值得遵循的建议？

假设这是后者，那么接下来的问题就是，在像Java这样没有真正MDA的语言中该怎么办。当然，用1DA模拟MDA并不难。本质上，对于具有MDA的语言的语法糖可以作为对没有MDA的语言的库支持实现。

这是否值得付出努力？对于像Java这样的语言来说，这是否过于低级的优化问题？我们应该放弃数组，甚至对于基元类型也使用List吗？

另一个问题：在Java中，将AoA一次性分配（new int[M][N]）可能会产生与逐层分配（new int[M][]; for (... new int[N]）不同的内存分配吗？

- polygenelubricants

---

请参见 https://dev59.com/kXE85IYBdhLWcg3w_I38，其中包含实际的基准测试结果。 - rwong

Answer 1

Java和C#的内存分配方式与C++大不相同。事实上，在.NET中，如果数组是一个接一个地分配的话，所有AoA的数组都会紧密地排列在一起，因为那里的内存只是一个连续的块，没有任何碎片。

但是对于C++来说这仍然是正确的，如果你想要最大的速度的话就有意义。虽然你不应该每次都遵循这个建议来创建多维数组，你应该首先编写可维护的代码，然后在它变慢时进行优化，过早的优化是万恶之源。

- vava

---

例如，一个 int[128][2] 实例占用 3,600 字节。与使用相同容量的 int[256] 实例的 1,040 字节相比，3,600 字节表示了 246% 的额外开销。 - Ghandhikus

Answer 2

这值得付出努力吗？对于像Java这样的语言来说，这是否太低级的优化问题？

一般而言，不值得这么做。最好的策略是在应用程序的第一个版本中忘记这个问题，并以直截了当（即易于维护）的方式进行实现。如果第一个版本运行速度过慢，无法满足您的要求，请使用性能分析工具找出应用程序的瓶颈。如果分析表明数组的数组可能是问题所在，请进行一些实验，更改数据结构以模拟多维数组，并进行性能分析以查看它是否有显着的区别。（我认为这样做不会有太大的区别，但最重要的是不要浪费时间去不必要地进行优化。）

我们应该放弃数组并即使使用列表来处理基元类型吗？

我认为没有必要这么做。假设您正在处理预定义大小的数组：

- 对象数组将比对象列表稍微快一些。 - 基元类型数组将比基元类型包装器的等效列表更快，占用的空间也会少得多。

另一方面，如果您的应用程序需要“增长”数组，则使用列表将简化您的代码。

- Stephen C

Answer 3

从我在Java方面的个人经验来看，如果要加载大量数据或访问位于不同位置的数据元素，则多维数组比一维数组慢得多。我编写了一个程序，它以BMP格式获取屏幕截图图像，然后搜索较小的图像。将屏幕截图图像（约3 MB）加载到多维数组（三维，[xPos] [yPos] [color]（其中color = 0表示红色值等））中需要14秒钟。将其加载到单个维度数组中只需1秒钟。

在查找较大图像中的较小图像时，使用多维数组和一维数组存储两个图像时，获得的收益是相似的。当两个图像都存储为多维数组时，在较大图像中查找较小图像需要约28秒钟。当两个图像都存储为一维数组时，在较大图像中查找较小图像只需要约1秒钟。话虽如此，出于可读性的考虑，我首先使用了多维数组编写我的程序。

- William Royle

---

你确定问题是数组吗？在不了解JVM如何工作的情况下，轻易地说Java中的某些东西很慢是很容易的...你必须考虑预热时间和你正在使用的JVM类型（客户端或服务器）。在程序刚开始运行的早期阶段，你会发现速度较慢。 - ceklock

Answer 4

我不会浪费精力在Java中使用1D数组作为多维数组，因为没有语法来帮助。当然，你可以定义函数（方法）来隐藏工作，但是当使用数组的数组时，你最终只会得到一个函数调用而不是跟随指针。即使编译器/解释器为您加速了这个过程，我仍然认为这不值得一试。此外，当尝试使用期望作为数组的数组的2D（或N-Dim）数组时，您可能会遇到复杂的情况。我相信大多数通用代码都会像Java中的这些数组一样编写。此外，你可以便宜地重新分配行（或列，如果你决定这样想）。

如果你知道这个多维数组是瓶颈，你可以忽略我说的话，看看手动优化是否有所帮助。

- Thomas Eding