Разрешение итерации без создания мусора

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

Дизайн без мусора возможен за счет возврата структур, которые не реализуют IEnumerable. Компилятор C# по-прежнему может выполнять итерацию таких объектов, поскольку оператор foreach использует утиную типизацию. .NET List<T>, например, использует этот подход.

При использовании foreach как для массива, так и для List<T> мусор не будет генерироваться. При использовании foreach для массива C# преобразует операцию в оператор for, в то время как List<T> уже реализует перечислитель struct, в результате чего foreach не создает мусора.

Вот перечисляемая структура и перечислитель структур. Когда вы возвращаете перечислимое, компилятор C# может выполнить foreach по нему:

public struct StructEnumerable<T>
{
    private readonly List<T> pool;

    public StructEnumerable(List<T> pool)
    {
        this.pool = pool;
    }

    public StructEnumerator<T> GetEnumerator()
    {
        return new StructEnumerator<T>(this.pool);
    }
}

Вот StructEnumerator:

public struct StructEnumerator<T>
{
    private readonly List<T> pool;
    private int index;

    public StructEnumerator(List<T> pool)
    {
        this.pool = pool;
        this.index = 0;
    }

    public T Current
    {
        get
        {
            if (this.pool == null || this.index == 0)
                throw new InvalidOperationException();

            return this.pool[this.index - 1];
        }
    }

    public bool MoveNext()
    {
        this.index++;
        return this.pool != null && this.pool.Count >= this.index;
    }

    public void Reset()
    {
        this.index = 0;
    }
}

Вы можете просто вернуть StructEnumerable<T> следующим образом:

public StructEnumerable<T> Items
{
    get { return new StructEnumerable<T>(this.pool); }
}

И C# может повторить это с помощью обычного foreach:

foreach (var item in pool.Items)
{
    Console.WriteLine(item);
}

Обратите внимание, что вы не можете использовать LINQ для элемента с помощью System.Linq.Enumerable. Для этого вам нужен интерфейс IEnumerable<T>, а это включает в себя создание перечислителей и, следовательно, сборку мусора. Вы можете, конечно, создать свои собственные методы расширения LINQ, но это вряд ли поможет, потому что это все равно будет приводить к созданию новых объектов (когда замыкания создаются для используемых делегатов).

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

Компактный сборщик мусора имеет простую политику; он запускает сбор каждый раз, когда выделяется 1000 КБ памяти. Теперь предположим, что вы пишете игру, которая работает на компактной платформе, и физический движок каждый раз генерирует 1 КБ мусора. Физические движки обычно запускаются порядка 20 раз в секунду. Так что это 1200 КБ давления в минуту, и эй, это уже более одной коллекции в минуту только от физического движка. Если коллекция вызывает заметное зависание в игре, это может быть неприемлемо. В таком случае поможет все, что вы можете сделать, чтобы уменьшить давление на взыскание.

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

Итак, чтобы перейти к вашему вопросу, как вы можете перебирать коллекцию объединенных объектов, не создавая давления на сбор?

Во-первых, давайте подумаем, почему в типичном сценарии возникает давление сбора. Предположим, у вас есть

 foreach(var node in ActiveNodes) { ... }

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

На практике иногда вы можете немного схитрить и иметь один объект, представляющий и последовательность, и перечислитель, но при этом у вас все равно будет выделен один объект.

Как мы можем избежать этого давления сбора? На ум приходят три вещи.

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

2) Как предполагает Стивен, компилятор примет любые типы, которые имеют правильные общедоступные методы и свойства; они не должны быть IEnumerable и IEnumerator. Вы можете создать свою собственную последовательность изменяемых структур и объекты курсора, передать их по значению и избежать давления при сборе. Опасно иметь изменяемые структуры, но это возможно. Обратите внимание, что List<T> использует эту стратегию для своего перечислителя; изучить его реализацию для идей.

3) Выделите последовательность и счетчики в куче как обычно и объедините их! Вы уже используете стратегию объединения, поэтому нет никаких причин, по которым вы не можете объединить счетчик. У перечислителей даже есть удобный метод «Сброс», который обычно просто выдает исключение, но вы можете написать собственный объект перечислителя, который использовал бы его для сброса перечислителя обратно в начало последовательности, когда он возвращается в пул.

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

(Теперь, конечно, у вас может возникнуть проблема курицы и яйца; как вы собираетесь перечислять пул счетчиков?)

Поскольку XNA для XBox также работает с Compact Framework (и я подозреваю, что вы работаете именно над этим, учитывая данные вами подсказки(1)), мы можем доверьтесь разработчикам XNA, чтобы они научили нас, когда именно foreach создает мусор.

Процитирую наиболее важный момент (хотя стоит прочитать всю статью):

При выполнении foreach над Collection<T> перечислитель БУДЕТ выделен.

При выполнении foreach для большинства других коллекций, в том числе в виде массивов, списков, очередей, связанных списков и других:

• если коллекции используются явно, перечислитель НЕ будет выделен.
• если они приводятся к интерфейсам, перечислитель БУДЕТ выделен.

Таким образом, если _pool является List, массивом или подобным и может себе это позволить, вы можете либо вернуть этот тип напрямую, либо привести IEnumerable<T> к соответствующему типу, чтобы избежать мусора во время foreach.

В качестве дополнительного чтения, Шон Харгривз может предоставить полезную дополнительную информацию.

(1) 60 вызовов в секунду, Compact Framework, не может перейти к собственному коду, 1 МБ выделения до запуска GC.

Должен ли он быть IEnumerable? Поможет ли рефакторинг в массив со старым добрым индексированным acecss?

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

@Edit: если вы вынуждены использовать управляемую платформу и действительно хотите заархивировать состояние без мусора, откажитесь от использования пула в цикле foreach и повторите его другим способом, возможно, используя индексатор. Или рассмотрите возможность создания списка потенциальных узлов и возврата его вместо этого.

@Edit2: Конечно, реализация IEnumerator и использование Current(), Next() и т. д. также будут работать.

Вы можете реализовать свой собственный класс IEnumerator, который будет перечислять эти активные узлы.

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

Это опасное предположение, но если вы занимаетесь оптимизацией, вы можете его рассмотреть

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

Кроме того, у вас может быть пул предварительно выделенных счетчиков. Подумайте, сколько одновременных перечислений вы хотите поддерживать.

Накладные расходы на сборку мусора пойдут за счет дополнительного потребления памяти. Дилемма скорости и оптимизации памяти в чистом виде.