Бенчмаркая Enumerable.Chunk: почему батчей меньше, а проход до ×2,7 дольше / Хабр

Уважаемые читатели, в этой статье я хочу разобраться, что происходит с Enumerable.Chunk на крупных батчах, — и представить свои выводы.

Chunk создаёт под каждый чанк отдельный массив. На мелких чанках это ни на что не влияет. Но массив на 25 000 int занимает 100 024 байта, а объекты от 85 000 байт рантайм размещает в куче больших объектов. Её очищает сборка второго поколения.

Поэтому увеличение батча с 20 000 до 25 000 записей даёт обратный результат: вызовов меньше, а времени тратится в 1,52–2,74 раза больше. Разница в выделенной памяти — 0,66 КБ на миллион элементов. Ни компилятор, ни анализаторы про это не сообщают.

Будет 6 историй:

чанк на 25 000 int вместо 20 000 замедляет обработку в 1,52–2,74 раза при том же объёме выделенной памяти;
где проходит граница: один лишний элемент к чанку — и на всех четырёх машинах появляются сборки второго поколения;
причина: те же замеры с порогом кучи больших объектов в 196 608 байт вместо 85 000;
считаю, во сколько массивов обходится первый чанк и почему он отличается от остальных;
почему с .NET 9 массив и List<int> попадают в разные реализации Chunk;
чем Chunk заменяется на массиве и на методе с yield return.

Шесть способов, которые сравниваются:

Enumerable.Chunk на массиве — у массива в LINQ своя реализация;
Enumerable.Chunk на List<int> — тот же вызов, но параметр объявлен интерфейсом;
Enumerable.Chunk на методе с yield return — длина набора заранее неизвестна;
ReadOnlySpan<int>.Slice — часть исходного массива, без копирования;
CollectionsMarshal.AsSpan — то же самое для List<int>;
свой цикл с одним буфером — массив создаётся один раз и перезаполняется.

Весь код проверки — в репо ChunkProof. Машины те же, что в статье про StringBuilder:

Ryzen 9 5950X;
Core i9-10900KF;
2 × Xeon Silver 4314;
Xeon W-2255.

Все на .NET 8, 9 и 10, BenchmarkDotNet 0.15.8.

История 1. Чанк на 25 000 против чанка на 20 000

Миллион int разбивается на чанки, чанки складываются в List<int[]> и остаются в памяти, пока обработка не закончится — так работает батчинг, когда чанк передают дальше отдельным массивом. Для сравнения те же данные через ReadOnlySpan<int>.Slice (.NET 10).

Чанк с 20 000 до 25 000, вызовов стало меньше — а времени тратится вдвое больше. Байт выделено почти столько же — разница 0,66 КБ

Чанк на 25 000 обрабатывается в 1,52–2,74 раза дольше, чем на 20 000. Памяти при этом запрошено на 0,66 КБ больше — 3909,26 против 3908,60. У ReadOnlySpan<int>.Slice время не меняется.

Различается одно — сборки второго поколения. На чанке 20 000 их нет, на 25 000 — 406,25–697,27 на тысячу вызовов.

Сборка второго поколения обходит всю управляемую кучу и останавливает потоки на всё время работы. Сборка нулевого поколения разбирает только недавно созданные объекты и заканчивается быстрее. Поэтому одинаковый объём выделенной памяти даёт разное время.

25 000 × 4 + 24 = 100 024 байта. Двадцать четыре байта — заголовок массива на x64: указатель на таблицу методов, поле синхронизации и длина. Порог кучи больших объектов — 85 000 байт, поэтому такой чанк попадает туда, а чанк на 20 000 с его 80 024 байтами остаётся в обычной куче.

Сорок чанков по 100 024 байта — это 4 000 960 байт в куче, которую очищает сборка второго поколения. Отчёт memory из репо:

// ChunkProof, вывод dotnet run -c Release -f net10.0 -- memory chunkHeld 25000
 
Способ                                          Выделено      Живого в LOH
Chunk, чанки остаются в памяти               4 009 160 Б       4 000 960 Б

4 000 960 — это ровно 40 × 100 024, одинаково на всех четырёх машинах.

История 2. Где проходит граница

Раз дело в размере чанка, границу можно найти перебором. 21 243 × 4 + 24 = 84 996 байт, а 21 244 × 4 + 24 = 85 000. Два соседних размера, .NET 10, чанки в памяти не остаются.

*Один элемент разницы: на 21 243 сборок второго поколения нет, на 21 244 — больше одной на вызов*

На 21 243 сборок второго поколения нет ни на одной машине, на 21 244 — 1103,52–1110,35 на тысячу вызовов. Байт выделено одинаково, 3,82 МБ, время выросло в 1,07–1,28 раза.

Дальше ничего не добавляется: на 25 000 сборок 1092,77–1104,49, столько же.

Число 21 244 взято не из документации, а найдено перебором. Отчёт threshold создаёт массивы по возрастающей длине и находит первую, с которой рантайм сразу относит массив ко второму поколению:

// ChunkProof, вывод dotnet run -c Release -f net10.0 -- threshold
 
    Тип элемента   Байт на элемент    Первая длина в LOH   Размер с заголовком
          ссылка                 8                10 622                85 000
            long                 8                10 622                85 000
             int                 4                21 244                85 000
            byte                 1                84 976                85 000

Заголовок в 24 байта в коде не задан константой, а измеряется: разница между запрошенными байтами и длиной массива. На int и на long результат один.

У массива ссылок граница — 10 622 элемента, потому что ссылка занимает 8 байт. Между 10 000 и 20 000 записей на батч она и проходит: 10 000 остаётся в обычной куче, 20 000 попадает в кучу больших объектов.

Про Xeon Silver 4314 отдельно. Чанк 20 000 показывает 833,30 мкс на .NET 9 и 1043,30 на .NET 10 при погрешности 16,10 и 18,90. Оба размера ниже границы, байт выделено одинаково, значит куча больших объектов тут ни при чём. Причину этой разницы между рантаймами мои замеры не находят, поэтому таблица построена на размерах вплотную к границе, где все четыре машины показывают одно и то же.

История 3. Проверяю причину: те же чанки вне кучи больших объектов

Пока это только совпадение: размер перешёл за 85 000 — время выросло. Порог кучи задаётся настройкой рантайма, поэтому его можно поднять и повторить замеры на тех же данных.

rem ChunkProof, all.bat, шаг 8
 
set DOTNET_GCLOHThreshold=0x30000
dotnet run -c Release -f net10.0 --no-build -- threshold
dotnet run -c Release -f net10.0 --no-build -- collect chunkArray 21244
dotnet run -c Release -f net10.0 --no-build -- --filter *ChunkValueBench* *ChunkHeldBench*

0x30000 — это 196 608 байт. Настройка сработала, и это видно по отчёту threshold: граница для ссылок стала 24 573 вместо 10 622, для int — 49 146 вместо 21 244. Ни один чанк из замера в кучу больших объектов больше не попадает.

*С поднятым порогом чанки 20 000 и 25 000 обрабатываются за одно время на трёх машинах из четырёх*

На Ryzen 9 5950X, Core i9-10900KF и Xeon W-2255 отношение стало 0,98–1,01 — размер чанка на время не влияет. На Xeon Silver 4314 остаётся 1,18.

Со сборками эти 1,18 не связаны: счётчик сборок на всех четырёх машинах показывает одно и то же.

Падает не только число полных сборок. С поднятым порогом всего сборок на проход становится 9–15 вместо 41–48, то есть нагрузка не переходит в другое поколение, а снимается.

Сборки второго поколения появляются на 21 244 и прекращаются с поднятым порогом. Байт выделено одинаково во всех трёх строках

Xeon Silver 4314 — единственная двухсокетная машина в прогоне, и остаток в 1,18 может идти оттуда. Число сборок на ней меняется так же, как на остальных трёх, поэтому к куче больших объектов этот остаток отношения не имеет.

История 4. Под первый чанк создаётся 14 массивов

Первый чанк создаётся не так, как остальные. Под него берётся массив на 4 элемента, дальше его длина удваивается до нужного размера. На каждом шаге создаётся новый массив, а данные из старого переносятся через Array.Resize.

// dotnet/runtime, System/Linq/Chunk.cs, сокращённый листинг
 
int arraySize = Math.Min(size, 4);
...
arraySize = (int)Math.Min((uint)size, 2 * (uint)array.Length);
Array.Resize(ref array, arraySize);

Отчёт blocks считает, сколько байт запрошено на один чанк и сколько на два. Разница даёт второй. На .NET 8, 9 и 10 числа одинаковые:

*Первый чанк на 20 000 int занимает 211 504 байта против 80 024 у второго — в 2,64 раза больше*

На чанк в 20 000 создаётся 14 массивов: первый на 4 элемента, двенадцать удвоений до 16 384 и последний на 20 000. Все вместе — 52 764 элемента, это 211 056 байт, плюс 14 заголовков по 24 байта и 112 байт на объекты итератора. Итого 211 504.

BenchmarkDotNet на том же коде показал 206,55 КБ на первый чанк и 284,70 КБ на первые два, разница 78,15 КБ. Два независимых счётчика сошлись.

Это важно там, где из набора нужен не весь результат, а первый чанк или пара первых: из 14 массивов в работе остаётся один, остальные 13 будут собраны сборщиком мусора.

История 5. У массива своя реализация Chunk, у List — нет

Миллион int, чанк 1 000, три источника: массив, List<int> и метод с yield return.

Между .NET 8 и .NET 9 массив стал в 5,5 раза быстрее, а List<int> и метод с yield return — на том же уровне — *Между .NET 8 и .NET 9 массив стал в 5,5 раза быстрее, а* `List<int>` *и метод с* `yield return` *— на том же уровне*

Числа сняты на Ryzen 9 5950X. На .NET 8 массив — 2483,90 мкс, список — 2583,40, метод с yield return — 2483,50. На .NET 9 массив ускоряется с 2483,90 до 447,60 мкс, два других не меняются. На .NET 10 массив — 443,80 мкс, List<int> — 3164,30.

Разница между List<int> и массивом на .NET 10 по четырём машинам:

Массив принят за единицу: List<int> обрабатывается в 5,58–7,14 раза дольше — *Массив принят за единицу:* `List<int>` *обрабатывается в 5,58–7,14 раза дольше*

Причину искать не пришлось: проект выводит имя типа, который вернул Chunk. На .NET 8 он один на все источники:

// ChunkProof, вывод dotnet run -c Release -f net8.0 -- blocks
 
Источник                      Тип итератора
массив int                    <ChunkIterator>d__70`1
список int, через интерфейс   <ChunkIterator>d__70`1
метод с yield return          <ChunkIterator>d__70`1

На .NET 9 и .NET 10 их два:

// ChunkProof, вывод dotnet run -c Release -f net10.0 -- blocks
 
Источник                      Тип итератора
массив int                    <ArrayChunkIterator>d__39`1
список int, через интерфейс   <EnumerableChunkIterator>d__40`1
метод с yield return          <EnumerableChunkIterator>d__40`1

Разделение — в Chunk.cs:

// dotnet/runtime, System/Linq/Chunk.cs, сокращённый листинг
 
if (source is TSource[] array)
{
    return array.Length != 0 ?
        ArrayChunkIterator(array, size) :
        [];
}
 
return EnumerableChunkIterator(source, size);

Проверка source is TSource[] работает по реальному типу объекта, а не по типу параметра. List<int> её не проходит и попадает в общую реализацию, где первый чанк собирается через Array.Resize.

Параметр у Chunk объявлен как IEnumerable<TSource>, поэтому в коде оба вызова написаны одинаково. Разницу задаёт реальный тип аргумента.

В этой же ветке видно ещё одно отличие: на пустом массиве .NET 9 и .NET 10 итератор не создают — возвращается Int32[][], пустой массив массивов.

История 6. Чем заменить Chunk

Замена зависит от источника. Для массива и List<int> сравнение идёт с Chunk на массиве, для метода с yield return — с Chunk на такой же последовательности. Чанк 20 000, .NET 10.

ReadOnlySpan<int>.Slice обрабатывается за 0,35–0,57 времени Chunk и не выделяет ни байта — `ReadOnlySpan<int>.Slice` *обрабатывается за 0,35–0,57 времени* `Chunk` *и не выделяет ни байта*

Chunk на массиве запрашивает 4 001 264 байта, ReadOnlySpan<int>.Slice — ноль. Время одинаковое и для массива, и для List<int>: 240,80–470,00 против 241,10–469,70 мкс.

*На методе с yield return свой буфер быстрее в 1,47–1,95 раза, буфер из ArrayPool — в 1,52–1,85*

Свой буфер запрашивает 80 064 байта — один массив на 20 000 int. Буфер из ArrayPool<int>.Shared — 40 байт: массив берётся из пула и возвращается обратно.

Где замена не работает

ReadOnlySpan<int>.Slice — это часть исходного массива, а не отдельный объект. Он живёт столько же, сколько исходный массив, и в метод с параметром int[] не подходит.

У буфера, который переиспользуется, ограничение строже: следующий чанк перезаписывает предыдущий, поэтому обработка идёт во время перебора. Когда чанк нужен отдельным массивом и должен остаться в памяти после обработки, Chunk заменить нечем, и размер чанка считается в байтах с расчётом на предел в 85 000.

А если в наборе тысяча элементов?

Тысяча элементов, чанк 100, .NET 10:

*На тысяче элементов List<int> отстаёт от массива в 6,05–6,82 раза — как и на миллионе*

Разница между List<int> и массивом остаётся. Skip с Take — самая распространённая замена — это 2,77–5,04 мкс и 960 байт против 0,49–0,88 мкс и 4 304 байт у Chunk на массиве: медленнее, но памяти запрашивает меньше.

Выводы

По цифрам:

чанк на 25 000 int, который остаётся в памяти до конца обработки, замедляет проход в 1,52–2,74 раза против чанка на 20 000 — при разнице в выделенной памяти 0,66 КБ на миллион элементов;
граница кучи больших объектов для int — 21 244 элемента: 21 244 × 4 + 24 = 85 000; для массива ссылок — 10 622;
один лишний элемент сверх границы — 1103,52–1110,35 сборок второго поколения на тысячу вызовов вместо нуля;
при пороге 196 608 байт сборки второго поколения прекращаются на всех четырёх машинах, а время выравнивается на трёх из четырёх: на Xeon Silver 4314 остаётся 1,18;
первый чанк на 20 000 int создаётся через 14 массивов и занимает 211 504 байта против 80 024 у второго;
с .NET 9 у массива своя реализация ArrayChunkIterator: между .NET 8 и .NET 10 он ускорился в 4,33–5,60 раза, а List<int> замедлился в 1,13–1,22 на трёх машинах из четырёх; на Core i9-10900KF разница 112,7 мкс при погрешности 41,1 и 42,3 — чуть больше суммы погрешностей;
List<int> отстаёт от массива в 5,58–7,14 раза на миллионе элементов и в 6,05–6,82 на тысяче;
ReadOnlySpan<int>.Slice обрабатывается за 0,35–0,57 времени Chunk и не выделяет памяти; буфер, который переиспользуется, на методе с yield return быстрее в 1,47–1,95 раза;
на .NET 8, 9 и 10 граница одна и та же — в рантайме её не меняли.

Что стоит помнить:

размер чанка считается в байтах, а не в элементах: для int граница — 21 244 элемента, для массива ссылок — 10 622, и второе число попадает между 10 000 и 20 000 записей;
крупный батч не значит быстрый: если чанки живут до конца обработки, за границей 85 000 байт каждый вызов добавляет сборку второго поколения;
DOTNET_GCLOHThreshold сдвигает границу, но только вверх и на весь процесс: значение читается один раз при запуске и может быть ограничено рантаймом, поэтому применившийся порог стоит проверять через GC.GetConfigurationVariables. С поднятым порогом суммарных сборок на проход становится меньше, а не больше: 9–15 против 41–48;
быструю реализацию Chunk получает только массив, проверка идёт по реальному типу объекта — параметр объявлен интерфейсом, и по коду вызова этого не видно;
если чанк нужен только для чтения, ReadOnlySpan<int>.Slice решает ту же задачу без выделения памяти;
когда из набора берут первый чанк или пару первых, стоит помнить про 14 массивов на один чанк в 20 000 int.

Код из статьи

ChunkProof — замеры, отчёты, прогоны на четырёх машинах и трёх рантаймах

Ссылки

Всем удачи и до новых встреч!

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

66.67%Да2

0%Нет0

33.33%А чё, так можно было что ли!1

Проголосовали 3 пользователя. Воздержавшихся нет.