Я много работаю с массивами, поэтому хотел бы освежить тему того, как наиболее быстро по нему перемещаться в C#. Речь пойдёт об экономии наносекунд и оптимизации на уровне IL-кода. Кажется, что в 99% случаев вам это знать не нужно и задумываться об этом не стоит. Тем не менее, для горячих сценариев или если вы из high-load или геймдева, вам это может пригодиться.
Проблема: проверка границ массива
Ранее все выбирали обычный for, чтобы просто пробежаться по массиву. Ну, во всяком случае те, кто топил за перформанс. Это ведь оптимально и естественно, очень похоже на C++. И должно быть максимально быстро, правда? Да, но есть нюанс.
Основная проблема в том, что dotnet это не C++. Код исполняется несколько иначе, чем так, как вы видите. Dotnet следит за тем, чтобы вы не выходили в область памяти, которая вам не принадлежит. Следовательно, чтобы выбросить правильный exception и перед доступом к элементу массива, нужно проверить границы массива (array bounds check).
Каждый раз, когда вы пишите array[i], должна происходить эта проверка. Естественно, есть нюансы. Например, когда вы работаете внутри цикла for. Если в for использовать (var i = 0; i < array.Length; i++), то проверка осуществляется всего однажды, как раз вот в этой вот строчке.
Есть ещё более интересный способ избежать проверки границ массива: сделать магические (uint)index >= (uint)_size. Это подсказка для компилятора, что программист сам проверил выход за границу массива и дополнительно вставлять проверку в IL-код не требуется. Этот хитрый ход может применятся в изощрённых случаях и, например, при написании собственных коллекций.
При этом, есть ещё один, максимально простой и всем известный способ избежать проверок выхода за границы массива.
Foreach - всё просто
Тест предельно простой. У нас есть массив int'ов определённого размера и мы хотим выяснить, как по нему бежать максимально быстро. Собственно, никаких новостей не будет в том, что бежать по нему быстрее всего с помощью foreach. Результаты benchmark'a подтверждают:
Обычный foreach (см. колонку Ratio) самый первый во всех без исключения популярных и используемых версия фреймворка. Второе место закономерно занимает foreach по array.AsSpan(). Ну, кроме версии старого .NET Framework'а, конечно. В старом framework'e мы можем быть более хитрыми и воспользоваться собственным перечислителем, который очень похож на enumerator у Span'a.
Почему же foreach такой быстрый? Ответ очевиден - enumerator проверяет границы массива только один раз, а далее прозрачно для dotnet'a бежит по нему. Почему unsafe оказался медленнее? Для меня в этом загадка. При этом, я уверен, что большинство программистов не захотят тащить в свой код unsafe без видимой на то причины. Увы, в этом месте я написал максимально тупой unsafe и разместил его тут скорее для формальности - проверить и этот вариант.
Если возвращаться к 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.6.1, победа уходит unsafe коду. Это весьма очевидно, так как под капотом Span'a достаточно много похожего на unsafe кода. А старый framework может работать со Span только в качестве адаптера, чтобы обеспечить совместимость кода. Однако, если вам не хочется уходить в дебри unsafe, рекомендую опять таки воспользоваться получением элемента массива по ссылке. Ну или из собственного перечислителя.
Второй интересный момент заключается в том, что кастомный enumerator сильно отстаёт от Span в версии .NET Core 3.1. Это странно, учитывая то, что код очень похож на код из Span'a. Честно говоря, я так и не понял почему так. Однако, это и не важно, так как лучше выбирать array.AsSpan(), чем долго и упорно оптимизировать и писать свои велосипеды.
В-третьих, Unsafe benchmark закономерно показал хороший результат, поскольку, думаю, именно так и выглядит Span под глубоким капотом. Я попытался подыскать подтверждение моей мысли, но, увы, есть только результаты замеров.
Случайный доступ к элементам массива
Для полноты теста, прогоним benchmark на случайный доступ к элементам массива по индексу. Как всегда, несколькими способами.
Магии не случилось, старый-добрый доступ по индексу один из самых быстрых. Вы можете заметить, что доступ через unsafe-магию чуть быстрее, но так делать не надо. Это копейки по сравнению с тем, какое возрастание сложности кода мы получаем.
При этом, для меня стало неожиданным то, что доступ через Memory почти в три раза медленнее. Очень странно, учитывая то, что кода там не так чтобы много. Лишнего - тем более.
Выводы
1. Используйте foreach там, где вам необходимо быстро прочитать элементы из массива.
2. Если вам нужно изменять значения в массиве, используйте array.AsSpan и бегите по элементам, получаемым из его enumerator'a. В этом случае необходимо получать ссылку на элемент массива - foreach (ref var element in array.AsSpan()).
3. Если вы не используете современный dotnet, рекомендую присмотреться к собственной имплементации Enumerator'a по array.
4. Доступ по индексу, конечно, самый эффективный.
5. Не надо использовать unsafe. Во-первых, этого не одобрят коллеги, а во-вторых, это не всегда так быстро, как рассказывают.
#csharp #dotnet #for #foreach #array #span #программирование
