Как бороться с неизменностью возвращаемых структур? - PullRequest
8 голосов
/ 01 сентября 2010

Я пишу игру, в которой есть огромный массив «ячеек». Ячейка занимает всего 3 байта. У меня также есть класс CellMap, который содержит 2D-массив в качестве частного поля и обеспечивает доступ к нему через открытый индексатор.

Профилирование показало, что проблема с производительностью вызвана сборкой мусора слишком большого числа объектов Cell. Поэтому я решил сделать Cell структурой (это был класс).

Но теперь такой код не работает:

cellMap[x, y].Population++;

Я могу придумать много вариантов, но мне не нравится ни один из них.

  1. Сделать массив общедоступным и написать cellMap.Data[x, y].Population = 5;
  2. Прекратите использовать класс CellMap и просто используйте 2D-массив напрямую. Но CellMap очень удобен, потому что он реализует свою собственную оптимизированную сериализацию и предоставляет свойства Width и Height, которые более удобны, чем запись cellMap.GetLength(0)
  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++

Как традиционно решается эта проблема?

Ответы [ 6 ]

18 голосов
/ 01 сентября 2010

Так что здесь на самом деле две проблемы.Есть вопрос, который вы на самом деле задали: какие методы должны учитывать тот факт, что структуры должны быть неизменными, потому что они копируются по значению, но вы хотите изменить его.И затем возникает вопрос, который мотивирует этот вопрос: «Как я могу сделать производительность моей программы приемлемой?»

Мой другой ответ касается первого вопроса, но также интересен и второй вопрос.

Во-первых, если профилировщик действительно определил, что проблема производительности связана с сборкой мусора из ячеек,тогда возможно , что поможет преобразование ячейки в структуру.Также возможно, что это не поможет вообще, и возможно, что это ухудшит ситуацию.

Ваши ячейки не содержат никаких ссылочных типов;мы знаем это, потому что вы сказали, что они только три байта.Если кто-то еще читает это, думает, что он может сделать оптимизацию производительности, превратив класс в структуру, тогда это может вообще не помочь, потому что класс может содержать поле ссылочного типа , в этом случае мусорколлектор все еще должен собирать каждый экземпляр, даже если он превращен в тип значения.Типы ссылок в нем тоже нужно собирать!Я бы рекомендовал делать это только из соображений производительности, если Cell содержит только типы значений, что, по-видимому, и делает.

Это может ухудшить ситуацию, поскольку типы значений не являются панацеей;у них тоже есть расходы.Типы значений часто более дороги для копирования, чем ссылочные типы (которые почти всегда имеют размер регистра, почти всегда выровнены по соответствующей границе памяти, и поэтому микросхема высоко оптимизирована для их копирования).И типы значений копируются постоянно.

Теперь, в вашем случае, у вас есть структура, которая на меньше , чем ссылка;ссылки обычно составляют четыре или восемь байтов.И вы помещаете их в массив, что означает, что вы упаковываете массив;если у вас их будет тысяча, потребуется три тысячи байт.Это означает, что три из каждых четырех структур имеют неправильно выровненный , что означает больше времени (на многих архитектурах чипов) для извлечения значения из массива.Возможно, вы захотите измерить влияние padding вашей структуры на четыре байта, чтобы увидеть, будет ли это иметь значение, при условии, что вы все еще будете хранить их в массиве, что подводит меня к следующему пункту..

Абстракция ячеек может быть просто плохой абстракцией с целью хранения данных о множестве ячеек .Если проблема в том, что ячейки являются классами, вы храните массив из тысяч ячеек, и собирать их стоит дорого, тогда существуют другие решения, кроме превращения ячейки в структуру.Предположим, например, что ячейка содержит два байта заполнителя и один байт цвета.Это механизм 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 полностью неизменен. (Черт, Ячейка могла бы быть здесь структурой, хотя, конечно, приведение ее к ICell в любом случае просто поместило бы ее в коробку.) Это карта , которая является изменяемой, и ячейка изменяет карту для пользователь.

9 голосов
/ 01 сентября 2010

Если вы хотите сделать ячейку неизменной - как следует, если она является структурой - тогда хорошим методом будет создать фабрику, которая будет экземпляр метода в ячейке:

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();

Однако я думаю, что это, возможно, тупик;лучше было бы просто не иметь так много Ячеек вокруг, чем пытаться оптимизировать мир, в котором их тысячи.Я напишу другой ответ на это.

4 голосов
/ 01 сентября 2010

6. Используйте параметр ref в методе, который изменяет значение, вызывайте его как IncrementCellPopulation(ref cellMap[x, y])

2 голосов
/ 01 сентября 2010

Если ваша карта ячеек на самом деле "разреженная", то есть если есть много смежных ячеек, которые не имеют ни значения, ни некоторого значения по умолчанию, я бы посоветовал вам не создавать для них объект ячейки. Создавайте объекты только для тех ячеек, которые на самом деле имеют состояние не по умолчанию. (Это может значительно уменьшить общее количество ячеек, что снижает нагрузку на сборщик мусора.)

Этот подход, конечно, потребует от вас поиска нового способа хранения карты вашей ячейки. Вам придется отказаться от хранения ваших ячеек в массиве (поскольку они не редки) и использовать структуру данных другого типа, вероятно, дерево.

Например, вы можете разделить вашу карту на несколько однородных регионов, чтобы вы могли перевести любые координаты ячейки в соответствующий регион. (Вы можете дополнительно подразделить каждый регион на субрегионы в соответствии с той же идеей.) Затем вы можете иметь дерево поиска для региона, где координаты ячейки выступают в качестве ключа в дереве.

Такая схема позволит вам хранить только те ячейки, которые вам нужны, при этом обеспечивая быстрый доступ к любой ячейке на вашей карте. Если в деревьях не найдено ни одной ячейки с указанными координатами, можно предположить, что это ячейка по умолчанию.

1 голос
/ 01 сентября 2010

Инкапсулируйте то, что вы хотите, чтобы CellMap делал, и разрешите доступ к фактическому массиву только через соответствующие методы, такие как IncrementPopupation(int x, int y). Создание массива (или любой другой переменной) в большинстве случаев является серьезным запахом кода, как и возвращение массива в .NET.

Из соображений производительности рассмотрите возможность использования одномерного массива; это намного быстрее в .NET.

0 голосов
/ 09 сентября 2010

Подход Эрика Липперта хорош, но я бы предложил использовать базовый класс, а не интерфейс для косвенного метода доступа.Следующая программа демонстрирует класс, который действует как разреженный массив точек.При условии, что ни один элемент типа PointRef (*) не сохраняется, все должно работать прекрасно.Говоря:

  MyPointHolder(123) = somePoint

или

  MyPointHolder(123).thePoint = somePoint

создаст временный объект pointRef (pointRef.onePoint в одном случае; pointHolder.IndexedPointRef в другом), но расширяющиеся типы работаютподдерживать семантику значения.Конечно, все было бы намного проще, если бы (1) методы для типов значений могли быть помечены как мутаторы, и (2) запись поля структуры, к которой осуществляется доступ через свойство, могла бы автоматически прочитать свойство, отредактировать временную структуру и записатьобратно.Используемый здесь подход работает, хотя, увы, я не знаю способа сделать его универсальным.

(*) Элементы типа PointRef должны возвращаться только свойствами и никогда не должны храниться в переменной или использоватьсяв качестве параметров к чему-либо, кроме свойства сеттера, которое преобразуется в Point.

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
...