如何处理返回结构的不可变性？

Question

我正在编写一个具有巨大二维“单元”数组的游戏。一个单元仅占用 3 个字节。我还有一个名为 CellMap 的类，其中包含作为私有字段的 2D 数组，并提供通过公共索引器对其进行访问。

分析表明，性能问题是由过多 Cell 对象的垃圾回收引起的。所以我决定让 Cell 成为一个结构（它是一个类）。

但现在这样的代码不起作用：

cellMap[x, y].Population++;

我可以想到很多选择，但我并不真正喜欢其中任何一个。

1. 将数组公开，并写入 cellMap.Data[x, y].Population = 5;
2. 停止使用 CellMap 类，只需使用直接二维数组。但 CellMap 非常方便，因为它实现了自己优化的序列化，并且公开了比编写 cellMap.GetLength(0)< 更方便的 Width 和 Height 属性。 /code>
3. 使单元格不可变。但是代码会是什么样子呢？ cellMap[x, y] = IncrementCellPopulation(cellMap[x, y])？非常详细。
4. 几个实用函数，例如 cellMap.SetPopulationAt(x, y, 5)
5. 在拥有 CellMap 的每个类中，添加一个实用属性，例如private Cell[,] CellData { get { return this.CellMap.GetInternalArray(); } }，那么我的代码可能看起来像 CellData[x, y].Population++

这个问题传统上是如何解决的？

Answer 1

Eric Lippert 的方法很好，但我建议间接访问器使用基类而不是接口。以下程序演示了一个类，其行为类似于稀疏点数组。如果人们从不保留任何 PointRef(*) 类型的项目，那么事情应该会顺利进行。说：

  MyPointHolder(123) = somePoint

或者

  MyPointHolder(123).thePoint = somePoint

都会创建一个临时 pointRef 对象（一种情况下是 pointRef.onePoint；另一种情况下是 pointHolder.IndexedPointRef），但扩大类型转换可以维护值语义。当然，如果（1）值类型上的方法可以标记为修改器，并且（2）编写通过属性访问的结构的字段可以自动读取属性，编辑临时结构，并写入，那么事情会容易得多它回来了。这里使用的方法是有效的，尽管我不知道有什么方法可以使其通用。

(*) PointRef 类型的项只能由属性返回，并且绝不应存储在变量中或用作除将转换为 Point 的 setter 属性之外的任何内容的参数。

MustInherit Class PointRef
    Public MustOverride Property thePoint() As Point
    Public Property X() As Integer
        Get
            Return thePoint.X
        End Get
        Set(ByVal value As Integer)
            Dim mypoint As Point = thePoint
            mypoint.X = value
            thePoint = mypoint
        End Set
    End Property
    Public Property Y() As Integer
        Get
            Return thePoint.X
        End Get
        Set(ByVal value As Integer)
            Dim mypoint As Point = thePoint
            mypoint.Y = value
            thePoint = mypoint
        End Set
    End Property
    Public Shared Widening Operator CType(ByVal val As Point) As PointRef
        Return New onePoint(val)
    End Operator
    Public Shared Widening Operator CType(ByVal val As PointRef) As Point
        Return val.thePoint
    End Operator
    Private Class onePoint
        Inherits PointRef

        Dim myPoint As Point

        Sub New(ByVal pt As Point)
            myPoint = pt
        End Sub

        Public Overrides Property thePoint() As System.Drawing.Point
            Get
                Return myPoint
            End Get
            Set(ByVal value As System.Drawing.Point)
                myPoint = value
            End Set
        End Property
    End Class
End Class


Class pointHolder
    Dim myPoints As New Dictionary(Of Integer, Point)
    Private Class IndexedPointRef
        Inherits PointRef

        Dim ref As pointHolder
        Dim index As Integer
        Sub New(ByVal ref As pointHolder, ByVal index As Integer)
            Me.ref = ref
            Me.index = index
        End Sub
        Public Overrides Property thePoint() As System.Drawing.Point
            Get
                Dim mypoint As New Point(0, 0)
                ref.myPoints.TryGetValue(index, mypoint)
                Return mypoint
            End Get
            Set(ByVal value As System.Drawing.Point)
                ref.myPoints(index) = value
            End Set
        End Property
    End Class

    Default Public Property item(ByVal index As Integer) As PointRef
        Get
            Return New IndexedPointRef(Me, index)
        End Get
        Set(ByVal value As PointRef)
            myPoints(index) = value.thePoint
        End Set
    End Property

    Shared Sub test()
        Dim theH1, theH2 As New pointHolder
        theH1(5).X = 9
        theH1(9).Y = 20
        theH2(12).X = theH1(9).Y
        theH1(20) = theH2(12)
        theH2(12).Y = 6
        Dim h5, h9, h12, h20 As Point
        h5 = theH1(5)
        h9 = theH1(9)
        h12 = theH2(12)
        h20 = theH1(20)
    End Sub
End Class

Answer 2

封装您希望 CellMap 执行的操作，并仅允许通过 IncrementPopupation(int x, int y) 等适当的方法访问实际数组。在大多数情况下，将数组（或任何变量）公开是一种严重的代码味道，就像在 .NET 中返回数组一样。

出于性能考虑，考虑使用一维数组；这些在 .NET 中要快得多。

Answer 3

如果您的单元格地图实际上是“稀疏”的，也就是说，如果有很多相邻单元格没有值或有默认值，我建议您不要为这些创建单元格对象。只为实际上具有某些非默认状态的单元格创建对象。 （这可能会大量减少单元格总数，从而减轻垃圾收集器的压力。）

这种方法当然需要您找到一种新的方法来存储单元格图。您必须摆脱将单元格存储在数组中（因为它们并不稀疏），并采用不同类型的数据结构，可能是树。

例如，您可以将地图细分为多个统一区域，以便可以将任何单元格坐标转换为相应的区域。 （您可以根据相同的想法将每个区域进一步细分为子区域。）然后，您可以为每个区域创建一个搜索树，其中单元格坐标充当树中的键。

这样的方案将允许您仅存储所需的单元格，同时仍然提供对地图中任何单元格的快速访问。如果在树中没有找到某个指定坐标处的单元格，则可以假定它是默认单元格。

Answer 4

6.在改变值的方法中使用 ref 参数，将其称为 IncrementCellPopulation(ref cellMap[x, y])

Answer 5

如果您想让 Cell 不可变 - 就像您应该在它是一个结构时一样 - 那么一个好的技术是创建一个工厂，它是 Cell 上的实例方法：

struct C
{
    public int Foo { get; private set; }
    public int Bar { get; private set; }
    private C (int foo, int bar) : this()
    {
        this.Foo = foo;
        this.Bar = bar;
    }
    public static C Empty = default(C);
    public C WithFoo(int foo)
    {
        return new C(foo, this.Bar);
    }
    public C WithBar(int bar)
    {
        return new C(this.Foo, bar);
    }
    public C IncrementFoo()
    {
        return new C(this.Foo + 1, bar);
    }
    // etc
}
...
C c = C.Empty;
c = c.WithFoo(10);
c = c.WithBar(20);
c = c.IncrementFoo();
// c is now 11, 20

所以您的代码将类似于

map[x,y] = map[x,y].IncrementPopulation();

但是，我想这可能是一条死胡同；最好从一开始就不要有那么多细胞，而不是试图优化一个有数千个细胞的世界。我会写另一个答案 关于这一点。

Answer 6

所以这里实际上有两个问题。您实际上问了一个问题：有哪些技术可以处理结构应该是不可变的这一事实，因为它们是按值复制的，但您想要改变一个。然后还有一个问题激发了这个问题，即“我怎样才能使我的程序的性能可以接受？”

我的另一个答案解决了第一个问题，但第二个问题也很有趣。

首先，如果探查器实际上已确定性能问题是由于单元格的垃圾收集造成的，那么将单元格转换为结构体可能会有所帮助。也有可能它根本没有帮助，而且有可能这样做会让情况变得更糟。

您的单元格不包含任何引用类型；我们知道这一点是因为你说过它们只有三个字节。如果阅读本文的其他人认为他们可以通过将类转换为结构来进行性能优化，那么它可能根本没有帮助，因为该类可能包含引用类型的字段，在这种情况下垃圾收集器仍然必须收集每个实例，即使它变成了值类型。里面的引用类型也需要收集！如果 Cell 仅包含值类型（显然确实如此），出于性能原因，我建议尝试此操作。

这可能会让情况变得更糟，因为值类型并不是万能的。他们也有成本。值类型的复制通常比引用类型更昂贵（引用类型几乎总是寄存器的大小，几乎总是在适当的内存边界上对齐，因此芯片针对复制它们进行了高度优化）。并且值类型始终被复制。

现在，在您的情况下，您有一个比引用更小的结构；引用通常是四个或八个字节。你将它们放入一个数组中，这意味着你正在将数组打包；如果有一千个，则需要三千字节。这意味着每四个结构中就有三个未对齐，这意味着需要更多时间（在许多芯片架构上）从数组中获取值。您可能会考虑测量将结构填充到四个字节的影响，看看这是否会产生影响，前提是您仍将它们保留在数组中，这引出了我的下一点。 ..

Cell 抽象可能只是一个糟糕的抽象用于存储有关大量细胞的数据。如果问题是 Cell 是类，您要保留数千个 Cell 的数组，并且收集它们的成本很高，那么除了将 Cell 制作为结构体之外，还有其他解决方案。例如，假设一个 Cell 包含两个字节的 Population 和一个字节的 Color。这就是 Cell 的机制，但肯定不是您想要向用户公开的界面。 您的机制没有理由必须使用与接口相同的类型。因此，您可以按需制造 Cell 类的实例：

interface ICell
{
   public int Population { get; set; }
   public Color Color { get; set; }
}
private class CellMap
{
    private ushort[,] populationData; // Profile the memory burden vs speed cost of ushort vs int
    private byte[,] colorData; // Same here. 
    public ICell this[int x, int y] 
    {
        get { return new Cell(this, x, y); }
    }

    private sealed class Cell : ICell
    {
        private CellMap map;
        private int x;
        private int y;
        public Cell(CellMap map, int x, int y)
        {
            this.map = map; // etc
        }
        public int Population  
        {
            get { return this.map.populationData[this.x, this.y]; } 
            set { this.map.populationData[this.x, this.y] = (ushort) value; } 
        }

等等。 按需制造电池。如果它们的寿命很短，它们几乎会立即被收集。 CellMap 是一个抽象，因此使用抽象来隐藏混乱的实现细节。

使用这种架构，您不会遇到任何垃圾收集问题，因为您几乎没有活动的 Cell 实例，但您仍然可以说

map[x,y].Population++;

没问题，因为第一个索引器创建了一个不可变的对象，它知道如何更新地图的状态。 Cell 不需要是可变的；请注意，Cell 类是完全不可变的。 （哎呀，这里的 Cell 可能是一个结构体，当然，将其转换为 ICell 无论如何都会将其装箱。）映射是可变的，并且单元格会改变映射用户。