在多维数组和单个数组之间存储数据的最有效方法是什么? [英] What is the most efficient way of storing data between a multi-dimension array, and a single array?

问题描述

基本上，我不确定如何存储3D数据结构以实现最快的访问，因为我不确定多维数组的内幕是什么.

Essentially I'm not sure how to store a 3D data structure for the fastest access possible as I'm not sure what is going on under the hood for multi-dimensional arrays.

注意:数组每次都将是一个常数且已知大小，并且每个元素都将恰好是16位.

NOTE: The arrays will be a constant and known size each and every time, and each element will be exactly 16 bits.

选项1是具有多维数组 data [16，16，16] ，只需通过 data [x，y，z] 进行访问，选项2是具有一个单一维度数组 data [16 * 16 * 16] 并通过 data [x +(y * 16)+(z * 16 * 16)] 访问.

Option one is to have a multi-dimension array data[16, 16, 16] and simply access via data[x, y, z] option two is to have a single dimension array data[16 * 16 * 16] and access via data[x + (y * 16) + (z * 16 * 16)].

由于每个元素只能有16位长，而且我怀疑多维数组会在内部以其他方式至少以32位存储很多对其他数组的引用，这会浪费大量内存.但是，我担心它可能比每次运行选项2中指定的方程更快，并且速度是此项目的关键.

As each element should only be 16 bits long, and I have a suspicion that a multi-dimension array would store a lot of references to other arrays internally at a minimum of 32 bits per one, that is a lot of wasted memory. However, I fear it may be faster than running the equation specified in option two each time, and speed is key to this project.

那么，有人能启发我将速度差异与内存消耗差异相提并论吗?

So, can anyone enlighten me as to how much difference in speed there would likely to be compared to how much difference in memory consumption?

推荐答案

C#将多维数组存储为单个内存块，因此它们可以编译成几乎相同的东西.(一个区别是要检查三组边界.)

C# stores multidimensional arrays as a single block of memory, so they compile to almost the same thing. (One difference is that there are three sets of bounds to check).

即 arr [x，y，z] 几乎等同于 arr [x + y * ny + z * nz * ny] ，并且通常具有相似的性能特征.

I.e. arr[x,y,z] is just about equivalent to arr[x + y*ny +z*nz*ny] and will generally have similar performance characteristics.

但是，确切的性能将由内存访问模式以及这如何影响缓存一致性(至少对于大量数据)决定.您可能会发现，依次遍历 x ， y 和 z 的嵌套循环可能比以不同顺序进行循环更快或更慢(如果有的话)可以更好地将当前使用的数据保留在处理器缓存中.

The exact performance however will be dominated by the pattern of memory access, and how this affects cache coherence (at least for large amounts of data). You may find that nested loops over x, then y then z may be faster or slower than doing the loops in a different order, if one does a better job of keeping currently used data in the processor cache.

这在很大程度上取决于确切的算法，因此不可能给出对所有算法都正确的答案.

This is highly dependent on the exact algorithm, so it isn't possible to give an answer which is correct for all algorithms.

与C或C ++相比，任何速度降低的另一个原因是边界检查，在一维数组的情况下仍然需要进行边界检查.但是，这些通常(但并非总是)会自动删除.

The other cause of any speed reduction versus C or C++ is the bounds-checking, which will still be needed in the one-dimensional array case. However these will often, but not always, be removed automatically.

• https://blogs.msdn.microsoft.com/clrcodegeneration/2009/08/13/array-bounds-check-elimination-in-the-clr/

同样，确切的算法将影响优化器是否能够删除边界检查.

Again, the exact algorithm will affect whether the optimiser is able to remove the bounds checks.

您的行动方针应如下:

• 使用 arr [x，y，z] 编写朴素的算法版本.
• 如果足够快，您可以停下来.
• 否则，对算法进行概要分析，以检查是否确实存在数组访问问题，分析内存访问模式等.

• Write a naïve version of the algorithm with arr[x,y,z].
• If it's fast enough you can stop.
• Otherwise profile the algorithm to check it is actually array accesses which are the issue, analyse the memory access patterns and so on.

这篇关于在多维数组和单个数组之间存储数据的最有效方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！