Array: for/foreach или unsafe

Я много работаю с массивами, поэтому хотел бы освежить тему того, как наиболее быстро по нему перемещаться в C#. Речь пойдёт об экономии наносекунд и оптимизации на уровне IL-кода. Кажется, что в 99% случаев вам это знать не нужно и задумываться об этом не стоит. Тем не менее, для горячих сценариев или если мы из high-load или геймдева, нам это может пригодиться.

Проблема: проверка границ массива

Ранее все выбирали обычный for, чтобы просто пробежаться по массиву. Ну, во всяком случае те, кто топил за перформанс. Это ведь оптимально и естественно, очень похоже на C++. И должно быть максимально быстро, правда? Да, но есть нюанс.

Основная проблема в том, что dotnet это не C++. Код исполняется несколько иначе, чем так, как мы видим. Dotnet следит за тем, чтобы мы не выходили в область памяти, которая нам не принадлежит. Следовательно, чтобы выбросить правильный exception и перед доступом к элементу массива, нужно проверить границы массива (array bounds check).

Каждый раз, когда мы пишем array[i], внутри .NET должна происходить эта проверка. Естественно, есть нюансы. Например, когда мы работаем внутри цикла for. Если в for использовать var i = 0; i < array.Length; i++, то проверка осуществляется всего однажды, как раз вот в этой вот строчке.

Есть ещё более интересный способ избежать проверки границ массива: сделать магические (uint)index <= (uint)size. Это подсказка для компилятора, что программист сам проверил выход за границу массива и дополнительно вставлять проверку в IL-код не требуется. Этот хитрый ход может применятся в изощрённых случаях и, например, при написании собственных коллекций.

При этом, есть ещё один, максимально простой и всем известный способ избежать проверок выхода за границы массива.

Foreach — всё просто

Тест предельно простой. У нас есть массив int’ов определённого размера и мы хотим выяснить, как по нему бежать максимально быстро. Собственно, никаких новостей не будет в том, что бежать по нему быстрее всего (обычными способами) с помощью foreach. Результаты benchmark’a подтверждают:

Обычный foreach (см. колонку Ratio) хороший вариант в популярных и используемых версиях .NET. Однако, в .NET Core 3.1 следует присмотреться к foreach по array.AsSpan() или воспользоваться собственным перечислителем, который очень похож на enumerator у Span’a, если нам, почему-то, не нравятся Span’ы. Ещё в .NET Core 3.1 стоит присмотреться к unsafe, если наши коллеги не против. Спасибо @onyxmaster за дополнение.

Почему же foreach такой быстрый? Ответ очевиден — enumerator проверяет границы массива только один раз, а далее прозрачно для dotnet’a бежит по нему.

Почему unsafe оказался примерно на том же уровне, что и foreach в .NET 6 и в старом фреймворке? Для меня загадка. При этом, я уверен, что большинство программистов не захотят тащить в свой код unsafe без видимой на то причины. Увы, в этом месте я написал максимально тупой unsafe и разместил его тут скорее для формальности — проверить и этот вариант. Хороший код размещён в методе UnsafeFixed, который я взял из комментариев.

Однако, если возвращаться к foreach, то у него есть проблема, которая возникает при одновременном чтении и записи элементов в массив.

Проблема: чтение и запись одновременно

В чём проблема? Мы должны взять элемент массива, а затем заменить его на новый. Таким образом мы пытаемся имитировать случаи работы с массивами, как с основными коллекциями данных, когда нам нужно их не только читать, но и изменять содержимое.

Мы знаем, что лучше бы ходить в массив (использовать индексатор — array[i]) минимальное количество раз за итерацию. Как это сделать, если после чтения вам нужно присвоить array[i] = newValue? Всё опять-таки, всё просто. Но только начиная с C# 7.3. Именно тогда мы научились получать элемент массива по ref: ref var element = ref array[i]. Напомню, что это ссылка на элемент массива, присвоив которой новое значение, мы получим новое значение в самом массиве.

Кстати, почему нельзя использовать тот же самый foreach? Увы, дело в том, что foreach возвращает ref readonly, то есть ссылку на элемент массива, но только на чтение. Если нам всё-таки очень хочется работать с элементами массива в foreach like стиле, то можно снова воспользоваться собственным enumerator или просто сделать array.AsSpan(). Обе эти структуры возвращают изменяемую ссылку на элемент массива, что позволит нам выполнить чтение, а затем и присваивание.

Тестируем? Кажется, результаты benchmark’а будут интересные!

Да, действительно, интересные. Во-первых, в случае .NET Framework 4.8, победа уходит unsafe-коду. Это весьма очевидно, так как под капотом Span’a достаточно много похожего на unsafe-код. А старый framework может работать со Span только в качестве адаптера, чтобы обеспечить совместимость кода. Однако, если нам не хочется уходить в дебри unsafe, рекомендую опять таки воспользоваться возможностями собственного перечислителя.

Второй интересный момент заключается в том, что кастомный enumerator сильно опережает Span в версии .NET Framework 4.8 и .NET Core 3.1. Это странно, учитывая то, что код очень похож на код из Span’a. Честно говоря, я так и не понял почему так. Однако, это и не важно, так как лучше выбирать array.AsSpan(), чем долго и упорно оптимизировать и писать свои велосипеды.

В-третьих, unsafe закономерно показал хороший результат (кроме .NET 6). Мне кажется, это стоит запомнить и использовать. Если только ваши коллеги не против.

Случайный доступ к элементам массива

Для полноты теста, прогоним benchmark на случайный доступ к элементам массива по индексу. Как всегда, несколькими способами.

Магии не случилось, старый-добрый доступ по индексу один из самых быстрых, без ухода в unsafe. При этом, мы можем заметить, что доступ через unsafe затрачивает примерно то же самое время. Но так делать не надо, вас заклюют коллеги. Если даже вам что-то получится «выкружить» из unsafe, то это копейки по сравнению с тем, какое возрастание сложности кода мы получаем.

При этом, для меня стало неожиданным то, что доступ через Memory почти в три раза медленнее. Очень странно, учитывая то, что кода там не так чтобы много. Лишнего — тем более.

Выводы

1. Используем foreach там, где нам необходимо быстро прочитать элементы из массива.

2. Если нам нужно изменять значения в массиве, используем array.AsSpan и бужим по элементам, получаемым из его enumerator’a. В этом случае необходимо получать ссылку на элемент массива — foreach (ref var element in array.AsSpan()).

3. Если мы не используем современный .NET, то… снова используемforeach, так как собственные имплементации Enumerator’a по array не всегда эффективны.

4. Доступ по индексу, конечно, самый эффективный при случайном доступе. Мы можем «уйти в unsafe», но, чаще всего, результат не стоит усложнения кода.

5. Не надо использовать unsafe. Во-первых, это надо уметь. А во-вторых, этого не одобрят коллеги. Ну и в-третьих, это не всегда так быстро, как рассказывают.

Где это тестировалось

Статья была опубликована в моём канале почти год назад. За это время многое изменилось. Изменился код .NET, люди удалили статьи с Хабра, изменили адреса в Youtube. Я тоже поменял машину. Извините, если в статье что-то не работает. Я очень старался сделать так, чтобы чтение было приятным. Наконец, я заново прогнал все бенчмарки. Машина для тестирования за год тоже изменилась, теперь она вот такая:

BenchmarkDotNet=v0.13.5, OS=Windows 11 (10.0.22621.1265/22H2/2022Update/SunValley2) AMD Ryzen 7 5800H with Radeon Graphics, 1 CPU, 16 logical and 8 physical cores .NET SDK=7.0.102   [Host]             : .NET 6.0.13 (6.0.1322.58009), X64 RyuJIT AVX2   .NET 6.0           : .NET 6.0.13 (6.0.1322.58009), X64 RyuJIT AVX2   .NET Core 3.1      : .NET Core 3.1.22 (CoreCLR 4.700.21.56803, CoreFX 4.700.21.57101), X64 RyuJIT AVX2   .NET Framework 4.8 : .NET Framework 4.8.1 (4.8.9139.0), X64 RyuJIT VectorSize=256