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

Question

У меня есть следующий код в пуле объектов, который реализует интерфейс IEnumerable.

public IEnumerable<T> ActiveNodes
{
    get
    {
        for (int i = 0; i < _pool.Count; i++)
        {
            if (_pool[i].AvailableInPool)
            {
                yield return _pool[i];
            }
        }
    }
}

Насколько я знаю (в соответствии с этим вопросом), это приведет к генерации мусора, так как объект IEnumerable необходимо будет собрать. Ни один из элементов в _pool никогда не будет собран, так как целью пула является сохранение ссылок на все из них для предотвращения создания мусора.

Кто-нибудь может предложить способ итерации по _pool, чтобы не создавался мусор?

При переборе по пулу, все элементы в пуле, которые имеют AvailableInPool == true, должны быть перебраны. Заказ не имеет значения.

Answer 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 2

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

Проект без мусора возможен, возвращая структуры, которые не реализуют IEnumerable. Компилятор C # все еще может выполнять итерации таких объектов, потому что в операторе foreach используется типизированная утка. Но, опять же, вряд ли это вам поможет.

UPDATE

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

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 поверх элемента. Для этого вам нужен интерфейс IEnumerable, который включает в себя сборку и сборку мусора.

Удачи.

UPDATE:

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

Answer 3

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

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

При выполнении foreach над Collection<T> перечислитель будетalloc.

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

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

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

В качестве дополнительного чтения Shawn Hargreaves может найти применениеПолная дополнительная информация.

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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

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

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

Answer 7

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

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

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