Как синхронно обойти две коллекции без выделений памяти в куче в C#

Коротко: если оба источника являются массивами, списками или чем-то, из чего можно получить ReadOnlySpan<T>, возьмите меньшую из длин, обрежьте до неё оба span и пройдите их одним циклом for с единственным индексом. Это ничего не выделяет и является самой быстрой формой, которую знает JIT. Если нужен синтаксис foreach (var (x, y) in ...) без накладных расходов, напишите zip-перечислитель на ref struct из 20 строк, который проверяет обе длины в MoveNext. Если источники не поддерживают индексацию (HashSet<T>, Dictionary<TKey, TValue>), управляйте их структурными перечислителями вручную, вызвав GetEnumerator() дважды на конкретных типах. Избегайте Enumerable.Zip на горячих путях: на .NET 10.0.10 и .NET 11 RC 3 он выделяет от 144 до 208 байт на вызов и в бенчмарке ниже работал примерно в 10 раз медленнее обычного цикла.

Все замеры в этой статье сделаны с C# 14 на .NET 10.0.10 (SDK 10.0.302) и .NET 11.0.0-rc.3.26522.148 на Apple M4. Объём выделений на обеих средах выполнения совпал.

Откуда берутся байты в Enumerable.Zip

Enumerable.Zip напрашивается сам собой, когда нужно “пройти две последовательности вместе”, а начиная с .NET Core 3.0 у него есть перегрузка, возвращающая кортежи, так что код читается хорошо:

// .NET 10, C# 14
long sum = 0;
foreach (var (x, y) in first.Zip(second))
    sum += (long)x * y;

Проблема в том, что каждый элемент этого конвейера является ссылочным типом за интерфейсом. Zip принимает два параметра IEnumerable<T>, поэтому вызывает GetEnumerator() у каждого источника через интерфейс. Для List<T> это упаковывает его структурный List<T>.Enumerator; для массива выделяется объект перечислителя массива. Затем сам Zip возвращает объект-итератор, который хранит оба перечислителя. Ваш foreach общается с этим итератором через IEnumerator<(T1, T2)>, так что каждый MoveNext и Current становится интерфейсным вызовом, который JIT обычно не может встроить.

Я измерил выделения в установившемся режиме с помощью GC.GetAllocatedBytesForCurrentThread(), предварительно дав каждому методу перейти на Tier 1 с динамическим PGO, на двух источниках int по 1,000 элементов:

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

Обратите внимание, что статическая лямбда в перегрузке с селектором не помогла: делегат кешируется, но итератор и два перечислителя всё равно выделяются.

Самый быстрый вариант: один индекс, два обрезанных span

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

// .NET 10, C# 14
static long DotProduct(ReadOnlySpan<int> a, ReadOnlySpan<int> b)
{
    int n = Math.Min(a.Length, b.Length);
    a = a[..n];
    b = b[..n];

    long sum = 0;
    for (int i = 0; i < a.Length; i++)
        sum += (long)a[i] * b[i];
    return sum;
}

int[] prices = [10, 20, 30];
int[] quantities = [3, 2, 1];
long total = DotProduct(prices, quantities); // 100

Обрезка здесь не для красоты. Условие цикла i < a.Length позволяет JIT убрать проверку границ для a[i]. После b = b[..n] с тем же n JIT также знает, что b.Length == a.Length, и может убрать проверку и для b[i]. Без обрезки b[i] сохраняет проверку границ на каждой итерации, потому что ничто в цикле не доказывает, что b не короче a. Это то же правило “делайте длину границей цикла”, которое я разбирал в статье что такое Span и когда он действительно ускоряет код.

Массивы неявно преобразуются в ReadOnlySpan<T>, так что места вызова остаются чистыми. Для List<T> получите span поверх его внутреннего массива через CollectionsMarshal.AsSpan:

// .NET 10, C# 14
using System.Runtime.InteropServices;

List<int> prices = [10, 20, 30];
List<int> quantities = [3, 2, 1];

long total = DotProduct(
    CollectionsMarshal.AsSpan(prices),
    CollectionsMarshal.AsSpan(quantities));

CollectionsMarshal.AsSpan ничего не стоит: он возвращает span поверх внутреннего массива списка, ограниченный Count. Подвох в том, что span больше ничего не знает о списке. Если вы вызовете Add у списка, пока держите span, и список вырастет, span продолжит указывать на старый массив, и вы будете читать устаревшие данные без всякого исключения. Не меняйте размер списка, пока span жив. Остальные стороны этого компромисса разобраны в сравнении List vs Span vs ReadOnlySpan.

Чтобы писать в одну из последовательностей, читая другую, сделайте целевую последовательность Span<T> вместо ReadOnlySpan<T>. Шаблон не меняется.

Сохраняем синтаксис foreach с zip-перечислителем на ref struct

Индексный цикл быстрый, но не красивый, и когда тело занимает больше одной строки, a[i] и b[i] начинают мешать чтению. foreach в C# основан на шаблоне: ему не нужен IEnumerable<T>, достаточно метода GetEnumerator(), возвращающего что-то с MoveNext() и Current. Этим чем-то может быть ref struct, а значит, оно может хранить span и никогда не будет упаковано:

// .NET 10, C# 14
public ref struct SpanZip<T1, T2>
{
    private readonly ReadOnlySpan<T1> _first;
    private readonly ReadOnlySpan<T2> _second;
    private int _index;

    public SpanZip(ReadOnlySpan<T1> first, ReadOnlySpan<T2> second)
    {
        _first = first;
        _second = second;
        _index = -1;
    }

    public SpanZip<T1, T2> GetEnumerator() => this;

    public bool MoveNext()
    {
        int i = _index + 1;
        if ((uint)i < (uint)_first.Length && (uint)i < (uint)_second.Length)
        {
            _index = i;
            return true;
        }
        return false;
    }

    public (T1 First, T2 Second) Current => (_first[_index], _second[_index]);
}

public static class SpanZipExtensions
{
    public static SpanZip<T1, T2> ZipSpan<T1, T2>(
        this ReadOnlySpan<T1> first, ReadOnlySpan<T2> second) => new(first, second);
}

Использование читается как LINQ:

// .NET 10, C# 14
int[] prices = [10, 20, 30];
int[] quantities = [3, 2, 1];

long total = 0;
foreach (var (price, quantity) in prices.ZipSpan(quantities))
    total += (long)price * quantity;

Возвращаемый кортеж является ValueTuple, то есть структурой, поэтому его деконструкция ничего не стоит в куче. Вызов метода расширения для ReadOnlySpan<T> прямо на int[] с выводом аргументов типа опирается на первоклассные преобразования span из C# 14; на C# 13 сначала пришлось бы написать prices.AsSpan(). Для List<T> вызывайте его на CollectionsMarshal.AsSpan(list).

Форма MoveNext важнее, чем кажется. Моя первая версия обрезала оба span до общей длины в конструкторе и в MoveNext сравнивала _index только с _first.Length. Это было корректно, но работало почти ровно в 2 раза дольше обычного цикла. Проверка обеих длин в MoveNext снизила это до 1.23x. Я объясняю результат так: после встраивания MoveNext и Current JIT видит оба сравнения прямо перед двумя вызовами индексатора и может использовать их, чтобы убрать проверки границ; обрезка, сделанная в другом методе, не даёт ему этого факта. Так или иначе, измеренная разница велика, поэтому оставляйте обе проверки.

С ref struct идут два ограничения: SpanZip нельзя использовать через await или yield return, и его нельзя хранить в поле обычного класса. Если компилятор жалуется на время жизни, действуют правила, описанные в статье как C# определяет ref-safe-context.

Когда источники не поддерживают индексацию

HashSet<T>, Dictionary<TKey, TValue>, Queue<T>, LinkedList<T> и подобные им не могут дать span, но каждая из этих коллекций предоставляет публичный структурный перечислитель, если вызвать GetEnumerator() на конкретном типе. Управляйте двумя такими перечислителями сами:

// .NET 10, C# 14
static long SumProducts(List<int> a, List<int> b)
{
    long sum = 0;
    using var ea = a.GetEnumerator();   // List<int>.Enumerator, a struct
    using var eb = b.GetEnumerator();
    while (ea.MoveNext() && eb.MoveNext())
        sum += (long)ea.Current * eb.Current;
    return sum;
}

Замер показал 0 B на вызов. Важная деталь здесь в статическом типе параметров. Замените List<int> на IEnumerable<int>, и точно такое же тело будет выделять 80 B на вызов (два упакованных экземпляра List<int>.Enumerator) или 64 B, если объекты во время выполнения являются массивами. var это скрывает: ea имеет тип List<int>.Enumerator в одной версии и IEnumerator<int> в другой.

Структурные перечислители также сохраняют собственные проверки безопасности коллекции. List<T>.Enumerator выбрасывает InvalidOperationException, если список изменён во время перечисления, а версии на основе span так не умеют.

Вторая ловушка здесь в порядке. Синхронный обход двух экземпляров HashSet<T> или Dictionary<TKey, TValue> сопоставляет элементы по внутреннему порядку бакетов, который не совпадает с порядком вставки и не стабилен между разными экземплярами с одинаковым содержимым. Применяйте zip только к упорядоченным коллекциям. Если на самом деле нужно сопоставить элементы по ключу, это join или поиск по словарю, а не zip.

Что исправляет и чего не исправляет выделение на стеке в .NET 10

В .NET 10 JIT научился девиртуализировать интерфейсные методы массивов и, благодаря условному escape-анализу, выделять перечислители на стеке “в определённых сценариях”, как сказано на странице What’s new in .NET 10 runtime. Разумно надеяться, что это сделает интерфейсные версии бесплатными. В моих прогонах этого не произошло:

• Варианты с Enumerable.Zip выделяли одинаковое количество байт на .NET 10.0.10 и .NET 11 RC 3. Перечислители создаются внутри итератора Zip, который уходит к вызывающему коду, так что escape-анализу не с чем работать.
• Два IEnumerator<int> поверх массивов выделяли 64 B в моём замере установившегося режима и 32 B под BenchmarkDotNet. Это говорит о том, что в одних компиляциях JIT разместил на стеке один из двух перечислителей, а в других ни одного. На такую оптимизацию нельзя полагаться, и до нуля она никогда не доходит.

Работа по де-абстракции реальна и действительно помогает при foreach по одной последовательности, когда массив типизирован как IEnumerable<T>. Если нужен контекст, статья о выделении небольших массивов на стеке в .NET 10 описывает связанную работу с массивами. Случай с двумя источниками она пока просто не покрывает.

Цифры

BenchmarkDotNet 0.15.8, [MemoryDiagnoser], in-process toolchain, .NET 10.0.10 Arm64 RyuJIT, Apple M4, два массива (или списка) по 1,000 значений int, вычисление суммы произведений:

Строка SpanZip с обеими проверками взята из второго прогона того же класса бенчмарков, где базовый цикл for показал 251.4 ns, поэтому коэффициент считается относительно базовой линии этого прогона. In-process toolchain понадобился потому, что BenchmarkDotNet не может сгенерировать свой обычный отдельный проект для файлового приложения dotnet run bench.cs.

Из таблицы следуют два вывода. Во-первых, всё, что построено на span, укладывается в погрешность рукописного цикла; CollectionsMarshal.AsSpan не добавляет ничего измеримого. Во-вторых, “без выделений” и “быстро” являются разными свойствами: ручные структурные перечислители ничего не выделяют, но всё равно обходятся в 2.6x, потому что List<T>.Enumerator.MoveNext выполняет проверку версии и проверку границ на каждом элементе. Если вас беспокоит нагрузка на GC, её решает любая строка с нулевыми выделениями. Если важна пропускная способность, используйте span.

Как выбрать

• Оба источника являются массивами, списками, ImmutableArray<T>, Memory<T> или буферами на стеке: используйте цикл for по обрезанным span или SpanZip, если предпочитаете foreach и можете позволить себе около 20% на плотном числовом цикле. Если тело цикла выполняет реальную работу, эти 60 ns на тысячу элементов растворяются.
• Источники являются другими коллекциями BCL: храните их под конкретным типом и управляйте структурными перечислителями. Никогда не пропускайте их сначала через параметр IEnumerable<T>.
• Длины могут различаться, и это ошибка: проверьте a.Length != b.Length и выбросьте исключение до цикла. Enumerable.Zip, цикл по span выше и SpanZip молча останавливаются на более короткой последовательности, а строгого zip в BCL нет; я проверил ссылочные сборки .NET 11 RC 3, и Enumerable.Zip по-прежнему единственный zip из коробки.
• Три источника и больше: цикл по span расширяется тривиально (обрежьте все три до минимальной длины). Перегрузка Enumerable.Zip для трёх источников, добавленная в .NET 6, стоит 208 B на вызов.
• Холодный код, небольшие входные данные или конвейер LINQ, который и так выделяет память: оставьте Enumerable.Zip. Это самый понятный вариант, и байты там не важны.

Если вы переводите много LINQ-кода на span, помните, что C# 14 изменил привязку аргументов-массивов к перегрузкам со span; неявные преобразования span в C# 14 объясняют, почему вызов, который раньше выбирал перегрузку с IEnumerable<T>, теперь может выбрать перегрузку со span.

Что почитать дальше

• Что такое Span в C# и когда он действительно ускоряет код?
• List vs Span vs ReadOnlySpan в C#
• Что такое ref-safe-context в C# и как компилятор определяет его для ref-локальных переменных?
• .NET 10: выделение массивов значимых типов на стеке

Источники

• Метод Enumerable.Zip (Microsoft Learn)
• Метод CollectionsMarshal.AsSpan (Microsoft Learn)
• Оператор foreach и перечисление на основе шаблона (справочник по языку C#)
• Типы ref struct (справочник по языку C#)
• Что нового в среде выполнения .NET 10: де-абстракция перечисления массивов и выделение на стеке
• Планы по де-абстракции в .NET 10, dotnet/runtime#108913