1

使用 struct shim 替换锯齿状数组是否有任何开销？

举一个具体的例子

vertices = new KeyValuePair<uint, EdgeData>[][];

对比

private struct Vertex
{
    public KeyValuePair<uint, EdgeData>[] Arcs { get; set; }
}

vertices = new KeyValuePair<uint, Vertex>[];

EdgeData 是一个类，如果它有任何区别
显然结​​构示例中的意图更清晰，但它需要能够保存大量图表，因此任何内存开销都很重要

4

3 回答 3

4

Astruct可能会或可能不会在堆栈上分配。引用类型永远不能在堆栈上分配；它们总是在堆上分配。

来自标准 (ISO 23270)，第 8.8 节：

8.8 结构 类和结构之间的相似之处很长——结构可以实现接口，并且可以具有与类相同类型的成员。然而，结构与类在几个重要方面有所不同：结构是值类型而不是引用类型，结构不支持继承。结构值存储在“堆栈上”或“内联”。细心的程序员有时可以通过明智地使用结构来提高性能。

例如，对 Point 使用结构而不是类可以在运行时执行的内存分配数量上产生很大差异。下面的程序创建并初始化一个包含 100 个点的数组。

作为Point一个类实现，101 个单独的对象被实例化——一个用于数组，一个用于 100 个元素。

class Point
{
  public int x, y;
  public Point(int x, int y)
  {
    this.x = x;
    this.y = y;
  }

}
class Test
{
  static void Main()
  {
    Point[] points = new Point[100];
    for (int i = 0; i < 100; i++)
    {
      points[i] = new Point(i, i*i);
    }
}

IfPoint被实现为结构，如

struct Point
{
  public int x, y;
  public Point(int x, int y)
  {
    this.x = x;
    this.y = y;
  }
}

只有一个对象被实例化——用于数组的那个。Point 实例在数组中内联分配。这种优化可能会被滥用。使用结构而不是类也会使应用程序运行速度变慢或占用更多内存，因为按值传递结构实例会导致创建该结构的副本。

所以答案是“也许”。

对于您的示例，将数组（引用类型）包装在struct（值类型）中并不意味着什么：该数组仍分配在堆上。

但是，如果您将类更改EdgeData为结构，则可以（但可能不会）在数组中内联分配它。EdgeData因此，例如，如果您的类的大小为 16 个字节，并且您创建并填充了EdgeData[]100 个条目，那么您实际上分配了 1 个数组实例（其后备存储大小可容纳 100 个对象引用和您的EdgeData类的 100 个单独实例.

如果EdgeData是一个结构，则分配 1 个数组，其后备存储大小可容纳 100 个EdgeData实例（在本例中为 1600 个字节，因为我们假设的EdgeData结构大小为 16 个字节。）

遍历数组的类版本，特别是如果数组非常大，可能会导致分页，因为当您跳过整个堆以访问各个EdgeData实例时，您可能会丢失引用的局部性。

对数组版本的迭代struct保留了引用的局部性，因为EdgeData实例是内联的。

于 2013-04-24T19:00:27.953 回答
2

结构数组往往相当有效，尽管在您的特定示例中，每行都有一个额外的 uint。此外，避免暴露结构类型的属性，并且如果结构表示与胶带绑定在一起的独立值的集合（例如点的坐标），则只需将这些项目作为字段公开。虽然在很多情况下 JIT 会将属性访问转换为字段访问，但也有很多情况下它不能。

如果要比较以下效率：

struct FloatPoint2D {public float X,Y;}
FloatPoint3D[] MyArray;

相对

float[] MyXCoords, MyYCoords;

使用上面定义的结构，以随机顺序访问项目的 X 和 Y 将比使用一对单独的数组（通常是一个缓存未命中而不是两个）更快，但只访问顺序中许多项目的 X 或 Y 坐标如果使用单独的数组会更快（每个缓存行将获取两倍的有用坐标）。

在您的特定示例中，尚不清楚您的类型需要封装哪些数据；您的结构和非结构示例包含不同的数据，因此很难说一个“更有效”。

于 2013-04-24T20:40:18.480 回答
2

将 2D 数组替换为 1D 结构数组不会导致任何问题。这实际上是您如何查看数据的问题。如果将其建模为结构数组更有意义，每个结构都包含一个弧数组，那么这就是您应该在代码中表达它的方式。

它们的存储方式存在一些细微差别。特别是，您的一维数组方法将比二维数组方法占用更多的内存。uint基本上，每一行都有一个额外的。

紧随其后。它正在讨论 struct 方法和 2D 数组（即 ）之间的区别，而不是OP 正在使用[,]的锯齿状数组（ ）。[][]

实际上，使用的总内存会更多。在二维数组方法(row * col) KeyValuePair中，数组中有结构。该数组在 64 位运行时有大约 50 个字节的分配开销（如果我记得的话，在 32 位运行时大约有 40 个字节）。在一维数组方法中，您仍然有(row * col) KeyValuePair结构，但每个结构都包含一个具有相同 50 字节分配开销的数组。此外，您还有vertices包含(row) KeyvaluePair结构的数组。

但是，您的二维数组（只是数组）需要(rows * cols * (4 + sizeof(IntPtr)))字节。一维vertices数组只需要(rows * (4 + sizeof(IntPtr)))字节。如果单个数组的大小限制为 2 GB（就像您在 .NET 4.0 和更早版本中一样，或者在 .NET 4.5 中，除非您启用非常大的对象），那么您可能会使用一维数组拥有更多的项目结构比二维数组。当然，假设您有足够的内存来保存这么多KeyValuePair<uint, EdgeData>实例。

所以你的整体内存使用会增加，但你最大的单个分配会小得多。

于 2013-04-24T19:05:28.183 回答