(Эта статья была первоначально размещена в моем блоге)

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

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

Сопутствующее видео!

Настройка эталона

Мы, конечно, будем использовать BenchmarkDotNet для наших тестов, и вы можете найти весь код для них на GitHub. Для начала нам нужен хук точки входа для нашего единственного класса Benchmark, который будет определять перестановки сценариев, которые мы хотели бы запустить. Это будет относительно основным следующим образом:

var config = ManualConfig
    .Create(DefaultConfig.Instance)
    .WithOptions(ConfigOptions.DisableOptimizationsValidator);

var summary = BenchmarkRunner.Run(
    typeof(Benchmarks),
    config);

if (!summary.BenchmarksCases.Any())
{
    throw new InvalidOperationException("Benchmarks did not have results.");
}

Далее будет часть класса Benchmarks, которая фактически определяет перестановки, с которыми мы хотели бы, чтобы наши сценарии работали:

[Orderer(BenchmarkDotNet.Order.SummaryOrderPolicy.Method)]
[ShortRunJob(RuntimeMoniker.Net70)]
[MemoryDiagnoser]
public class Benchmarks
{
    public enum ImplementationScenario
    {
        Iterator,
        PopulateAsList,
        PopulateAsROCollection
    }

    private int[] _dataset;

    [Params(
        1_000,
        100_000,
        10_000_000)]
    public int NumberOfEntriesInDataset;

    [Params(
        ImplementationScenario.Iterator,
        ImplementationScenario.PopulateAsList, 
        ImplementationScenario.PopulateAsROCollection)]
    public ImplementationScenario Implementation;

    [GlobalSetup]
    public void Setup()
    {
        // seed this for consistency
        var random = new Random(1337);
        _dataset = new int[NumberOfEntriesInDataset];
        for (int i = 0; i < _dataset.Length; i++)
        {
            _dataset[i] = random.Next();
        }
    }

  // TODO: all the benchmark methods go here
}

Приведенный выше код создаст исходный массив для работы с 1000, 100 000 или 10 000 000 случайных целых чисел в зависимости от запуска теста. Мы используем начальное значение Random для наших тестов, но сценарии, которые мы собираемся рассматривать, не должны касаться значений целых чисел. Далее у нас есть один из трех сценариев, которые будут выбраны для тренировки, и мы можем увидеть этот код следующим образом:

    private IEnumerable<int> GetResultsUsingIterator()
    {
        foreach (var item in _dataset)
        {
            yield return item;
        }
    }

    private List<int> GetResultsUsingListAsList()
    {
        var results = new List<int>();
        foreach (var item in _dataset)
        {
            results.Add(item);
        }

        return results;
    }

    private IReadOnlyCollection<int> GetResultsUsingListAsReadOnlyCollection()
    {
        var results = new List<int>();
        foreach (var item in _dataset)
        {
            results.Add(item);
        }

        return results;
    }

Первые два метода показывают итератор и вариант материализованной коллекции. Третий метод также является материализованной коллекцией, но мы использовали IReadOnlyCollection<T> и вернемся к этому, когда будем углубляться в примеры. Намек в том, что я хотел помочь разобраться в том, что я наблюдал в результатах тестов итераторов!

Результаты LINQ Any() соответствуют ожиданиям!

Я начну с одного из ожидаемых тестов итераторов, и это будет вызов Any() для результата наших тестируемых функций. Этот Benchmark код выглядит следующим образом (его можно найти здесь, на GitHub):

[Benchmark]
    public void LinqAny()
    {
        _ = Implementation switch
        {
            ImplementationScenario.Iterator => GetResultsUsingIterator().Any(),
            ImplementationScenario.PopulateAsList => GetResultsUsingListAsList().Any(),
            ImplementationScenario.PopulateAsROCollection => GetResultsUsingListAsReadOnlyCollection().Any(),
            _ => throw new NotImplementedException(Implementation.ToString()),
        };
    }

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

Приведенные ниже результаты демонстрируют это, когда мы смотрим на столбцы Mean и Allocated.

Результаты LINQ Count() начинают выглядеть интересно…

Метод LINQ Count() — вот где я начал заставать себя врасплох. Метод Benchmark для этого очень похож на тот, который мы рассматривали ранее, но мы используем Count() вместо Any():

    [Benchmark]
    public void LinqCount()
    {
        _ = Implementation switch
        {
            ImplementationScenario.Iterator => GetResultsUsingIterator().Count(),
            ImplementationScenario.PopulateAsList => GetResultsUsingListAsList().Count(),
            ImplementationScenario.PopulateAsROCollection => GetResultsUsingListAsReadOnlyCollection().Count(),
            _ => throw new NotImplementedException(Implementation.ToString()),
        };
    }

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

Но что я нашел очень странным, так это то, что производительность итератора во время выполнения была ненамного выше, чем у материализованных коллекций. На самом деле, иногда это было медленнее, если не примерно так же. По глупости я забыл, что метод Count() из LINQ имеет оптимизацию: если у вас есть коллекция, он может проверять ее количество/длину как ярлык, а не принудительно перечислять. Таким образом, несмотря на то, что это сократит время выполнения материализованных коллекций, не должны ли накладные расходы на выделение всей этой дополнительной коллекции по-прежнему влечь за собой какие-то дополнительные затраты?

Результаты здесь не совсем очевидны, но они становятся более интересными, когда мы продолжаем смотреть на оставшиеся тесты итераторов!

Сравнение контрольных показателей Collection и Iterator для Foreach

Код для этого Benchmark таков:

[Benchmark]
    public void Foreach()
    {
        switch (Implementation)
        {
            case ImplementationScenario.Iterator:
                foreach (var x in GetResultsUsingIterator())
                {
                }
                break;
            case ImplementationScenario.PopulateAsList:
                foreach (var x in GetResultsUsingListAsList())
                {
                }
                break;
            case ImplementationScenario.PopulateAsROCollection:
                foreach (var x in GetResultsUsingListAsReadOnlyCollection())
                {
                }
                break;
            default:
                throw new NotImplementedException(Implementation.ToString());
        }
    }

И если вам интересно, почему я использовал только foreach вместо традиционного цикла for со счетчиком, то это потому, что IEnumerable и, следовательно, итераторы не имеют такой возможности. Я хотел сохранить эквивалентность сравнений.

Перейдем к результатам бенчмарков:

Когда мы смотрим на результаты нашего вывода Benchmark для foreach, распределение памяти в столбце Allocated соответствует тому, что я ожидал увидеть. Когда мы рассматриваем итератор по сравнению с материализацией всей коллекции, итератору не нужно выделять всю дополнительную коллекцию при потоковой передаче данных.

Тем не менее, производительность во время выполнения в столбце Mean — это то место, где я начал сильно запутываться. И я должен добавить, что изначально у меня не было третьего варианта с возвращаемым типом IReadOnlyCollection<T>, поэтому он был добавлен позже, чтобы помочь в моем анализе.

Учитывая, что итераторы могут передавать результаты в потоковом режиме, цикл foreach приведет к одному полному перечислению набора данных. Однако для материализованных коллекций в этом случае (в отличие от LINQ Count(), который мы видели ранее) абсолютно необходимо выполнить второе полное перечисление. Первый предназначен для создания материализованной коллекции, а второй — для ее перечисления. Как получается, что возвращаемый тип List<T> может быть быстрее, чем итератор в каждом из этих сценариев? И еще одна головоломка (которая может дать вам ответ, если вы освежили свои версии dotnet): почему тип возврата IReadOnlyCollection<T> намного медленнее, когда тип возврата является единственной разницей?

Момент «Ага!»

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

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