На собеседованиях мы слышим или говорим сами, что поиск в массиве медленнее, чем в хеш-таблице. Кто-то даже вспоминает, что поиск в массиве имеет линейную сложность или O(n), а в хеш-таблице — константную O(1). Но работает ли это на практике? Что, если есть ситуации, когда поиск в массиве оказывается быстрее? Давайте не будем торопиться с выводами.
Итак, сравним поиск в массиве и HashSet на малых коллекциях, возьмём разные типы — примитивный int и ссылочный string.
Полный код бенчмарка. Нажмите, чтобы развернуть.
using System.Collections.Generic; using System.Linq; using BenchmarkDotNet.Attributes; using BenchmarkDotNet.Jobs; namespace Benchmarks { [ShortRunJob(RuntimeMoniker.Net60)] [ShortRunJob(RuntimeMoniker.Net80)] [ShortRunJob(RuntimeMoniker.Net10_0)] [HideColumns("Job", "Error", "StdDev", "Gen0", "Median")] [DisassemblyDiagnoser(printSource: true, maxDepth: 2)] public class HashSetContainsBenchmark { [Params(1, 10, 100, 1000)] public int Size { get; set; } private int[] _arrayInt; private HashSet<int> _hashSetInt; private int _missingInt; private string[] _arrayString; private HashSet<string> _hashSetString; private string _missingString; [GlobalSetup] public void Setup() { // --- Int Setup --- var intData = Enumerable.Range(0, Size).ToArray(); _arrayInt = intData; _hashSetInt = new HashSet<int>(intData); _missingInt = Size + 1; // --- String Setup --- var stringData = Enumerable.Range(0, Size).Select(i => $"value-{i}").ToArray(); _arrayString = stringData; _hashSetString = new HashSet<string>(stringData); _missingString = "value-a"; } // --- Int Benchmarks --- [Benchmark(Description = "Array.Contains (Int)")] public bool Int_Array() => _arrayInt.Contains(_missingInt); [Benchmark(Description = "HashSet.Contains (Int)")] public bool Int_HashSet() => _hashSetInt.Contains(_missingInt); // --- String Benchmarks --- [Benchmark(Description = "Array.Contains (String)")] public bool String_Array() => _arrayString.Contains(_missingString); [Benchmark(Description = "HashSet.Contains (String)")] public bool String_HashSet() => _hashSetString.Contains(_missingString); } }
| Method | Runtime | Size | Mean | Code Size | |------------------------------ |---------- |----- |------------:|----------:| | 'Array.Contains (Int)' | .NET 6.0 | 1 | 3.443 ns | 50 B | | 'HashSet.Contains (Int)' | .NET 6.0 | 1 | 2.052 ns | 447 B | | 'Array.Contains (String)' | .NET 6.0 | 1 | 8.621 ns | 57 B | | 'HashSet.Contains (String)' | .NET 6.0 | 1 | 4.741 ns | 737 B | | 'Array.Contains (Int)' | .NET 8.0 | 1 | 2.676 ns | 40 B | | 'HashSet.Contains (Int)' | .NET 8.0 | 1 | 1.954 ns | 385 B | | 'Array.Contains (String)' | .NET 8.0 | 1 | 9.639 ns | 51 B | | 'HashSet.Contains (String)' | .NET 8.0 | 1 | 4.599 ns | 351 B | | 'Array.Contains (Int)' | .NET 10.0 | 1 | 1.193 ns | 669 B | | 'HashSet.Contains (Int)' | .NET 10.0 | 1 | 1.666 ns | 377 B | | 'Array.Contains (String)' | .NET 10.0 | 1 | 2.285 ns | 548 B | | 'HashSet.Contains (String)' | .NET 10.0 | 1 | 3.698 ns | 233 B |
Интуитивно кажется, что перебрать 1 элемент из массива должно быть быстрее, чем более сложный механизм с поиском по хэшу. Как видим, даже при поиске в коллекции из одного int массив проигрывает HashSet'у до .NET 10:
И то, преимущество совсем небольшое.
Для строк наблюдается такая же картина:
Давайте запомним это на будущее.
Ну ладно, коллекции из 1 элемента — это странные коллекции. Давайте всё-таки возьмём побольше — 10 элементов. Там-то преимущество HashSet должно стать более очевидным:
| Method | Runtime | Size | Mean | Code Size | |------------------------------ |---------- |----- |------------:|----------:| | 'Array.Contains (Int)' | .NET 6.0 | 10 | 4.059 ns | 50 B | | 'HashSet.Contains (Int)' | .NET 6.0 | 10 | 2.901 ns | 447 B | | 'Array.Contains (String)' | .NET 6.0 | 10 | 33.465 ns | 57 B | | 'HashSet.Contains (String)' | .NET 6.0 | 10 | 5.807 ns | 737 B | | 'Array.Contains (Int)' | .NET 8.0 | 10 | 3.137 ns | 40 B | | 'HashSet.Contains (Int)' | .NET 8.0 | 10 | 2.497 ns | 397 B | | 'Array.Contains (String)' | .NET 8.0 | 10 | 31.164 ns | 51 B | | 'HashSet.Contains (String)' | .NET 8.0 | 10 | 5.937 ns | 377 B | | 'Array.Contains (Int)' | .NET 10.0 | 10 | 1.639 ns | 729 B | | 'HashSet.Contains (Int)' | .NET 10.0 | 10 | 2.230 ns | 377 B | | 'Array.Contains (String)' | .NET 10.0 | 10 | 18.063 ns | 548 B | | 'HashSet.Contains (String)' | .NET 10.0 | 10 | 4.583 ns | 233 B |
Уже видите странности? Вот они:
Время поиска в HashSet остаётся примерно одинаковым независимо от фреймворка, а вот поиск в массиве всё улучшается и улучшается. Более того, в .NET 10 массив обгоняет HashSet! Как так? Неужели поиск в массиве тоже теперь работает за константное время? Кажется, мы на пороге грандиозного открытия. Давайте проверим нашу гипотезу на коллекциях из 100 элементов:
| Method | Runtime | Size | Mean | Code Size | |------------------------------ |---------- |----- |------------:|----------:| | 'Array.Contains (Int)' | .NET 6.0 | 100 | 13.073 ns | 50 B | | 'HashSet.Contains (Int)' | .NET 6.0 | 100 | 2.116 ns | 447 B | | 'Array.Contains (String)' | .NET 6.0 | 100 | 168.924 ns | 57 B | | 'HashSet.Contains (String)' | .NET 6.0 | 100 | 8.306 ns | 737 B | | 'Array.Contains (Int)' | .NET 8.0 | 100 | 4.381 ns | 40 B | | 'HashSet.Contains (Int)' | .NET 8.0 | 100 | 1.857 ns | 385 B | | 'Array.Contains (String)' | .NET 8.0 | 100 | 93.214 ns | 51 B | | 'HashSet.Contains (String)' | .NET 8.0 | 100 | 7.938 ns | 377 B | | 'Array.Contains (Int)' | .NET 10.0 | 100 | 3.401 ns | 736 B | | 'HashSet.Contains (Int)' | .NET 10.0 | 100 | 1.774 ns | 377 B | | 'Array.Contains (String)' | .NET 10.0 | 100 | 71.121 ns | 562 B | | 'HashSet.Contains (String)' | .NET 10.0 | 100 | 6.806 ns | 233 B |
К сожалению, чуда не случилось. Теперь массив стабильно проигрывает в поиске HashSet'-у. Но разница для типа int всё ещё не такая существенная:
Давайте посмотрим на рост времени поиска в массиве относительно его размера. Для наглядности добавим ещё массив в 1000 элементов:
Как видим, только в .NET 6 начинаем наблюдать линейный рост после 100 элементов. А в 8-й и 10-й версиях рост если не логарифмический, то сильно сглажен.
Пора погружаться глубже, а именно в то, как именно осуществляется поиск по массиву. Вызов метода Contains для массива в конечном итоге приводит к вызову статического метода Array.IndexOf. А вот дальше начинаются различия.
.NET 6
Используя некоторые оптимизации по раскрутке цикла и быстрому доступу к элементам массива .NET проверяет каждый элемент на равенство:
... while (length >= 8) { length -= 8; if (value.Equals(Unsafe.Add(ref searchSpace, index))) goto Found; if (value.Equals(Unsafe.Add(ref searchSpace, index + 1))) goto Found1; if (value.Equals(Unsafe.Add(ref searchSpace, index + 2))) goto Found2; if (value.Equals(Unsafe.Add(ref searchSpace, index + 3))) goto Found3; if (value.Equals(Unsafe.Add(ref searchSpace, index + 4))) goto Found4; if (value.Equals(Unsafe.Add(ref searchSpace, index + 5))) goto Found5; if (value.Equals(Unsafe.Add(ref searchSpace, index + 6))) goto Found6; if (value.Equals(Unsafe.Add(ref searchSpace, index + 7))) goto Found7; index += 8; } // далее проверяется остаток массива меньше 8 элементов
Как видите, мы последовательно проверяем каждый элемент и получаем наши честные O(N) трудоёмкость. Пока ничего необычного.
.NET 8
С этой версии ситуация меняется кардинально. В дело вступает метод SpanHelpers.NonPackedIndexOfValueType, который помимо раскрутки цикла содержит ещё мощную аппаратную оптимизацию — векторизацию:
if (Vector512.IsHardwareAccelerated && length >= Vector512<TValue>.Count) { Vector512<TValue> left = Vector512.Create<TValue>(value); //... } else if (Vector256.IsHardwareAccelerated && length >= Vector256<TValue>.Count) { Vector256<TValue> left = Vector256.Create<TValue>(value); //... } else { Vector128<TValue> left = Vector128.Create<TValue>(value); //... }
Мы видим использование новых типов Vector128, Vector256, Vector512 — коллекции для работы с векторными данными. И обратите внимание на свойство IsHardwareAccelerated, которое проверяется в каждом условии — в этом и есть вся магия. Оно определяет, поддерживает ли ваш процессор работу с векторами длиной 128, 256 и 512 бит соответственно.
Использование класса Vector512 позволяет оперировать сразу 16 элементами массива типа int. 512 бит = 64 байта, значит, в вектор помещается 16 значений типа int по 4 байта.
К сожалению, теперь придётся погрузиться в ассемблер, чтобы лучше понять, как это работает:
cmp r8d,4 jl near ptr M01_L03 ; Если элементов < 4, то обрабатываем поштучно cmp r8d,10 jl near ptr M01_L18 ; Если элементов < 16, то переходим обработку с помощью 256-битного регистра (ymm) vpbroadcastd zmm0,edx ; В 512-битный регистр zmm0 загружаем искомое значение edx. Теперь zmm0 выглядит как [edx, edx, edx, ..., edx] ... vmovups zmm1,[rcx] ; Загружаем первые 16 элементов из памяти в 512-битный регистр zmm1 vpcmpeqd k1,zmm1,zmm0 ; Сравниваем zmm1 и zmm0 на равенство kortestw k1,k1 ; Проверяем, есть ли хотя бы одно совпадение ...
vpcmpeqd— инструкция, которая сравнивает 2 вектора поэлементно и сохраняет результат в специальный регистрk1. Если 5-й элемент совпал, то 5-й бит вk1станет равен1.kortestwпроверяет эту битовую маску. Если она равна0— значит, в первых 16 элементах искомого числа нет.
На первый взгляд выглядит сложно, но, по сути — это продолжение концепции раскрутки цикла, но уже на уровне «железа». А новые версии фреймворка скрывают от нас всю сложность таких оптимизаций. В итоге, никакой магии и поиск по массиву всё ещё O(N). Даже если это O(N/16).
Эта магия работает только на современных процессорах, поддерживающих инструкции AVX-512 (или AVX-2 для 256 бит). Если вы запустите код на старом железе, .NET плавно откатится до Vector128 или обычного цикла.
.NET 10
Напомню, что в этой версии результаты для массива длиной 10 стали еще лучше и даже обгоняют HashSet. При этом, сам алгоритм поиска не поменялся, код тот же самый. Регистров более 512 пока не изобрели. В чём же дело? Предположу, что сработал PGO и компилятор решил, что чаще всего поиск будет в средних массивах (8-15 элементов), поменял блоки сравнения местами, чтобы не делать лишних прыжков и сэкономить ещё пару тактов процессору.
А помните, мы там вначале запоминали, почему поиск по массиву строк стал так хорош в .NET 10? Настало время разобраться и с этим.
Давайте ещё раз посмотрим на бенчмарк:
| Method | Runtime | Size | Mean | Code Size | |---------------------------- |---------- |----- |-----------:|----------:| | 'Array.Contains (String)' | .NET 8.0 | 1 | 9.639 ns | 51 B | | 'Array.Contains (String)' | .NET 10.0 | 1 | 2.285 ns | 548 B |
Помимо почти четырёхкратной разницы в скорости мы видим кратную разницу в размере кода (Code Size). Для .NET 8 компилятор долго не думал и вызов метода Contains перенаправил в generic-метод Array.IndexOf, который будет для каждого элемента массива вызывать виртуальный метод bool Equals(object obj). Надёжно, но не быстро.
А вот в .NET 10 компилятор применил новую технику под названием «девиртуализация», если точнее, то это Guarded Devirtualization. Он понял, что наша коллекция — это массив строк и только строк. А значит, можно пропустить все эти generic-вызовы и прыжки по таблице виртуальных методов и просто заинлайнить весь цикл сравнения строк. Отсюда мы и получаем 548 байт кода против 51. Но! Мы получаем специфичный код поиска строки в массиве, который работает намного быстрее. Чтобы это увидеть опять же обратимся к ассемблерному коду:
... mov r8,offset MT_System.String cmp [rcx],r8 ; Проверяем, что у нас точно строка. Поэтому и Guarded Devirtualization. jne short M00_L08 ; Иначе сравниваем через классический Equals ... mov r8d,[rcx+8] ; Читаем длину текущей строки cmp r8d,[rsi+8] ; Сравниваем с длиной искомой строки je short M00_L07 ; Если длины совпали - побайтово сравниваем сами строки ... M00_L07: lea rax,[rcx+0C] ... lea rdx,[rsi+0C] ; Получаем указатель на массив байт, в которых хранятся строки mov rcx,rax call qword ptr [7FFD2A46C330] ; System.SpanHelpers.SequenceEqual - вызываем метод, который сравниваем 2 массива байт ...
При этом, SequenceEqual так же поддерживает векторные операции и аппаратное ускорение. Ух! Вот это мощь! Я даже не догадывался, какая огромная работа скрывается за простым поиском строки в массиве.
Выводы
Опять напрашивается очевидный вывод — простое обновление .NET позволит получить прирост производительности (а значит, и экономии на ресурсах). Ну и никакой магии не существует, O(N) — это всё еще O(N), что прекрасно видно на больших значениях. А вот на малых (5-10 элементов) всё может быть не так однозначно.
А можно ли лучше? Чтобы и не O(N), хоть и с аппаратным ускорением, но и не тратиться постоянно на хеширование? Посмотрим…
Анализатор
В свой анализатор я добавил правило, которое подскажет вам, что можно заменить массив (или список) на HashSet, если на нём вызывается Contains. Это точно будет полезно для версий .NET 8 или ниже. Для более тонкой настройки можно отрегулировать порог срабатывания в editor.config, например, только от 5 элементов:
dotnet_diagnostic.CI0008.min_items_count = 5
