Реализация коллекций в CLR

179

В состав .NET Framework входит большое число коллекций, но мы не ставим целью рассмотреть каждую из них в этой статье - для этого лучше обратиться к статьям в разделе Руководство по C# - Часть 2, связанным с коллекциями. Однако, коллекции обладают некоторыми непростыми особенностями, которые следует учитывать при выборе для использования, особенно в коде, где требуется высокая производительность. Именно исследованием этих особенностей мы и займемся.

Некоторые разработчики опасаются использовать какие-либо классы коллекций и предпочитают встроенные массивы. Массивы очень неудобны: они не гибки, не позволяют динамически изменять их размер и на их основе очень сложно эффективно реализовать некоторые операции, но они, как известно, отличаются от других типов коллекций минимальными накладными расходами. Не нужно бояться использовать встроенные коллекции, пока в вашем распоряжении имеются отличные инструменты измерения производительности. Внутренние особенности реализации коллекций .NET, обсуждаемые в этой статье, также помогут вам сделать удачный выбор. Один простой пример: обход коллекции List<T> в цикле foreach выполняется лишь немногим дольше, чем в цикле for, потому что цикл foreach проверяет - не изменилась ли коллекция между итерациями.

Для начала вспомним, какие классы коллекций входят в состав .NET 4.5 - исключая параллельные коллекции, которые будут обсуждаться отдельно - и их характеристики производительности. Сравнение производительности операций вставки, удаления и поиска - отличный способ подобрать кандидата, лучше всего подходящего для ваших потребностей. В таблице ниже перечислены только обобщенные коллекции (необобщенные версии были удалены в версии .NET 2.0):

Коллекции и обобщенные типы
Коллекция Описание Время вставки Время удаления Время поиска Сортировка Доступ по индексу
List<T> Массив с автоматическим изменением размера Амортизированная O(1) O(n) O(n) Нет Да
LinkedList<T> Двусвязный список O(1) O(1) O(n) Нет Нет
Dictionary<K,V> Хеш-таблица O(1) O(1) O(1) Нет Нет
HashSet<T> Хеш-таблица O(1) O(1) O(1) Нет Нет
Queue<T> Циклический массив с автоматическим изменением Амортизированная O(1) O(1) - Нет Нет
Stack<T> Циклический массив с автоматическим изменением Амортизированная O(1) O(1) - Нет Нет
SortedDictionary<K,V> Дерево бинарного поиска, в котором все элементы отсортированы на основе ключа O(log n O(log n) O(log n) Да (по ключам) Нет
SortedList<K,V> Сортированный массив с автоматическим изменением размера O(n) O(n) O(log n) Да (по ключам) Да
SortedSet<T> Сортированная коллекция, содержащая только отличающиеся элементы O(log n) O(log n) O(log n) Да (по ключам) Нет

Под «амортизированной» производительностью в данном случае подразумевается, что некоторые операции могут показывать производительность O(n), но большинство операций будут показывать производительность O(1), поэтому средняя производительность по n операциям составит O(1).

Существует несколько обстоятельств и особенностей реализации, которые необходимо учитывать при выборе коллекции из числа включенных в .NET Framework:

Сейчас самое время напомнить, что строки также являются одной из разновидностей коллекций - коллекцией символов. Внутренне класс System.String реализован как неизменяемый массив символов. Все операции над строками создают новый объект. Именно поэтому создание длинных строк путем конкатенации тысяч маленьких строк оказывается чрезвычайно неэффективной тратой времени. Эту проблему решает класс System.Text.StringBuilder, с реализацией, похожей на List<T>, удваивающей размер внутреннего хранилища при изменении содержимого. Всякий раз, когда возникает необходимость сконструировать строку из большого (или заранее неизвестного) числа маленьких строк, используйте StringBuilder для выполнения промежуточных операций.

Такое богатство классов коллекций может показаться ошеломляющим, но иногда ни одна из встроенных коллекций не подходит для решения конкретной задачи. Ниже мы рассмотрим несколько примеров таких ситуаций. До выхода версии .NET 4.0, программисты часто ощущали нехватку поддержки конкурентного доступа во встроенных коллекциях: ни одна из коллекций, перечисленных в таблице, не поддерживает работу в многопоточном окружении. В .NET 4.0 появилось пространство имен System.Collections.Concurrent с несколькими новыми коллекциями, изначально предназначенными для использования в конкурентном окружении.

Параллельные коллекции

С появлением библиотеки Task Parallel Library в .NET 4.0 потребность в параллельных коллекциях встала особенно остро. В одной из следующих статей будет представлено несколько интересных примеров организации параллельного доступа к источникам данных или выходным буферам из нескольких потоков выполнения. А пока мы сосредоточимся на доступных параллельных коллекциях и их характеристиках производительности в духе стандартных (не параллельных) коллекций:

Параллельные коллекции в .NET Framework
Коллекция Особенности Синхронизация
ConcurrentStack<T>

Односвязный список

Свободный от блокировок алгоритм CAS (Compare-And-Swap - сравнить и заменить), экспоненциальное падение производительности при пробуксовке

ConcurrentQueue<T>

Класс ConcurrentQueue<T> управляет связанным списком сегментов массива, что позволяет имитировать неограниченную очередь в ограниченном объеме памяти. Для добавления элементов в очередь и удаления их из очереди достаточно увеличивать указатели в сегментах массива. В некоторых случаях требуется синхронизация, например, чтобы гарантировать, что элемент не будет удален из очереди до того, как поток, добавивший этот элемент, закончит операцию добавления. Однако вся синхронизация основана на CAS (Compare-And-Swap - сравнить и заменить).

Свободный от блокировок алгоритм (CAS), короткая пробуксовка при удалении из очереди элемента, который только что был включен в очередь

ConcurrentBag<T>

Класс ConcurrentBag<T> управляет неупорядоченным списком элементов. Элементы хранятся в локальных (для потоков выполнения) списках; добавление элементов в локальный список и их удаление обычно не требуют синхронизации, так как добавление или удаление производится в голове списка. Когда потоку требуется получить элементы из списка другого потока, он захватывает хвост этого списка и конкурирует с другим потоком, только когда в списке содержится меньше трех элементов.

Обычно не требуется для локальных списков, для захвата используется Monitor

ConcurrentDictionary<K,V>

Класс ConcurrentDictionary<K,V> использует классическую реализацию хеш-таблицы (связанные списки в каждом блоке). Блокировки выполняются на уровне блоков - все операции с определенным блоком требуют захвата блокировки, количество которых ограничено параметром concurrencyLevel конструктора. Операции над блоками, связанными с разными блокировками, могут выполняться параллельно. Наконец, все операции чтения не требуют блокировки, потому что все операции, производящие изменения, выполняются атомарно (например, операция вставки нового элемента в список блока).

Для изменения: один Monitor на каждую группу блоков хеш-таблицы (независимый от других блоков). Для чтения: нет

Хотя большинство параллельных коллекций весьма похожи на свои непараллельные аналоги, они имеют несколько отличающийся набор методов, объясняемый их параллельной природой. Например, класс ConcurrentDictionary<K,V> имеет вспомогательные методы, существенно уменьшающие потребность в обязательных блокировках и решающие проблемы, связанные с состоянием гонки (race condition), которые могут возникать при неосторожном обращении со словарем:

// Этот код подвержен состоянию гонки между вызовами методов ContainsKey и Add
Dictionary<string, int> expenses = // ...

if (!expenses.ContainsKey("ParisExpenses"))
    expenses.Add("ParisExpenses", currentAmount);
else
    // Этот код подвержен состоянию гонки при выполнении несколькими потоками
    expenses["ParisExpenses"] += currentAmount;

// Следующий код использует метод AddOrUpdate, чтобы гарантировать корректную 
// синхронизацию при добавлении нового или изменении существующего элемента
ConcurrentDictionary<string, int> expenses = // ...
expenses.AddOrUpdate("ParisExpenses", currentAmount, 
    (key, amount) => amount + currentAmount);

Метод AddOrUpdate обеспечивает необходимую синхронизацию для составной операции «добавить или изменить». Существует похожий вспомогательный метод GetOrAdd, который может извлекать существующий элемент или добавлять новый элемент и возвращать его.

Проблемы, связанные с кешем

При выборе коллекции следует руководствоваться не только характеристиками производительности. Часто организация данных в памяти играет более важную роль для преимущественно вычислительных приложений, и коллекции очень разнятся в этом отношении. Основным фактором, вынуждающим очень внимательно относиться к особенностям организации коллекций в памяти, является кеш процессора.

Современные системы снабжаются большими объемами памяти. Восемь гигабайт памяти является стандартным значением для заурядной рабочей станции или игрового ноутбука. Микросхемы памяти типа DDR3 SDRAM дают задержки доступа к памяти порядка 15 наносекунд, что теоретически может обеспечить скорость передачи данных примерно 15 Гбайт/сек. С другой стороны быстрые процессоры могут выполнять миллиарды инструкций в секунду, то есть, рассуждая теоретически, задержка на 15 наносекунд в ожидании доступа к памяти - это десятки (а иногда сотни) невыполненных инструкций. Явление простоя в ожидании доступа к памяти известно под названием удар о стену памяти (hitting the memory wall).

Чтобы увеличить расстояние между приложением и этой «стеной», современные процессоры снабжаются несколькими уровнями внутренней кеш-памяти, имеющей другие характеристики производительности, но очень дорогой и имеющей небольшой объем. Например, процессор Intel i7-860 на моем компьютере имеет три уровня кеша:

Схема взаимосвязей между ядрами, кешем и ОЗУ в микропроцессоре Intel

Когда процессору требуется обратиться к ячейке памяти, он сначала проверяет, не хранятся ли необходимые данные в кеше первого уровня (L1). Если данные найдены в кеше, они извлекаются оттуда, на что тратится примерно 5 тактов процессорного времени (это называется попаданием в кеш (cache hit)). В противном случае проверяется кеш второго уровня (L2); на извлечение данных из этого кеша тратится примерно 10 тактов. Аналогично выполняется проверка кеша третьего уровня (L3), на извлечение данных из которого тратится примерно 40 тактов. Наконец, если данные не найдены ни в одном из кешей, процессор обращается к главной памяти системы (это называется промахом кеша (cache miss)) . Когда процессор обращается к главной памяти, он читает из нее не один байт или слово, а строку кеша (cache line), размер которой в современных системах составляет 32 или 64 байта. Обращение к любому слову в той же строке кеша уже не будет вызывать промах кеша, пока эта строка не будет вытеснена из кеша.

Хотя данное описание не позволяет получить полное представление об истинной сложности аппаратной реализации кеширования памяти SRAM и DRAM, тем не менее, оно дает достаточно пищи для ума и дальнейшего обсуждения влияния организации данных в памяти на высокоуровневые программные алгоритмы. Сейчас мы рассмотрим простой пример с одним ядром и одним кешем. Допустим, что требуется реализовать обход большой коллекции целых чисел и выполнить некоторые агрегатные операции над ними, такие как вычисление суммы или среднего значения. Ниже приводятся два альтернативных решения; в одном используется LinkedList<int>, а в другом - массив целых чисел (int[]), две коллекции, встроенные в .NET:

LinkedList<int> numbers = new LinkedList<int>(Enumerable.Range(0, 20000000));
int sum = 0;
for (LinkedListNode<int> curr = numbers.First; curr != null; curr = curr.Next)
{
    sum += curr.Value;
}

int[] numbers = Enumerable.Range(0, 20000000).ToArray();
int sum = 0;
for (int curr = 0; curr < numbers.Length; ++curr)
{
    sum += numbers[curr];
}

В системах, упомянутых выше, вторая версия действует в 2 раза быстрее первой. Это весьма существенная разница, но судя по количеству машинных инструкций, сгенерированных JIT-компилятором, такой разницы не должно быть. Обход связанного списка заключается в переходе от одного узла к другому, а обход массива - в наращивании индекса. (Фактически, без оптимизаций со стороны JIT-компилятора, доступ к массиву требует также проверки на выход за его границы.)

; инструкции на языке ассемблера x86 для первого цикла, 
; предполагается, что "сумма" хранится в EAX, а "числа" - в ECX
xor eax, eax
mov ecx, dword ptr [ecx+4]		; curr = numbers.First
test ecx, ecx
jz LOOP_END
LOOP_BEGIN:
add eax, dword ptr [ecx+10]		; sum += curr.Value
mov ecx, dword ptr [ecx+8]		; curr = curr.Next
test ecx, ecx
jnz LOOP_BEGIN					; всего 4 инструкции на итерацию
LOOP_END:
...


; инструкции на языке ассемблера x86 для второго цикла,
; предполагается, что "сумма" хранится в EAX, а "числа" - в ECX
mov edi, dword ptr [ecx+4]			; numbers.Length
test edi, edi
jz LOOP_END
xor edx, edx						; индекс цикла
LOOP_BEGIN:
add eax, dword ptr [ecx+edx*4+8]	; sum += numbers[i], без проверки границ
inc edx
cmp esi, edx
jg LOOP_BEGIN						; всего 4 инструкции на итерацию
LOOP_END:
...

Опираясь только на один этот код, сгенерированный компилятором для обоих циклов (при запрещенных оптимизациях, таких как использование инструкций SIMD для обхода массива, занимающего непрерывную область памяти), сложно объяснить существенное различие в производительности. В действительности, чтобы дать достаточно обоснованное объяснение, необходимо исследовать порядок обращения к памяти.

В обоих циклах доступ к каждому целому числу осуществляется всего один раз, поэтому может показаться, что ускорение, которое дает кеш процессора, здесь ни при чем, потому что не используется преимущество попадания в кеш при повторном обращении к данным. Тем не менее, организация размещения данных в памяти оказывает существенное влияние на производительность, но не из-за того, что данные повторно используются, а из-за способа их загрузки в кеш-память.

При обращении к элементу массива, вначале происходит промах кеша и загрузка строки кеша, содержащей 16 последовательно расположенных целых чисел (строка кеша = 64 байта = 16 целых чисел). Так как доступ к элементам массива выполняется последовательно, следующие 15 чисел оказываются в кеше и при обращении к ним не возникает промаха кеша. Это почти идеальный сценарий с соотношением промахов кеша 1:16.

С другой стороны, при обращении к элементам связанного списка, вначале происходит промах кеша и загрузка строки кеша, содержащей не более 3 последовательно расположенных узлов списка, что дает в результате соотношение промахов кеша 1:31 (Узел содержит указатели на следующий и предыдущий элементы, и само целое число, что составляет 12 байт в 32-разрядной системе; заголовок ссылочного типа увеличивает этот объем до 20 байт на узел.)

Более высокое соотношение промахов кеша и является основной причиной, объясняющей разницу в производительности. Кроме того, мы взяли за основу идеальный сценарий, когда узлы связанного списка хранятся в памяти последовательно, без разрывов между ними, что может быть, только если память для них выделялась почти одновременно, без других операций выделения памяти между ними, а это весьма маловероятно. Если бы узлы связанного списка оказались разбросаны в памяти не так идеально, соотношение промахов кеша было бы еще выше, а производительность - хуже.

В заключение рассмотрим еще один пример, демонстрирующий другой эффект, связанный с кешем - реализацию алгоритма умножения матриц. Алгоритм умножения матриц - очень прост и может извлечь существенные выгоды от использования кеша процессора, потому что использует каждый элемент матриц несколько раз. Ниже приводится наивная реализация этого алгоритма «в лоб»:

public static int[,] MultiplyNaive(int[,] A, int[,] B)
{
    int[,] C = new int[N, N];
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            for (int k = 0; k < N; ++k)
                C[i, j] += A[i, k] * B[k, j];
    return C;
}

Основу реализации составляет внутренний цикл, вычисляющий скалярное произведение i-й строки в первой матрице на j-й столбец - во второй; он выполняет полный обход i-й строки j-го столбца. Предпосылкой, позволяющей говорить о возможности увеличить производительность за счет использования кеша, является тот факт, что при вычислении i-й строки матрицы результата многократно выполняется обход j-й строки первой матрицы. Один и тот же элемент используется многократно.

При обходе первой матрицы, казалось бы, кеш используется достаточно эффективно: сначала выполняется N итераций по ее первой строке, затем N итераций по второй строке, и так далее. Однако это не так, потому что после i-й итерации внешнего цикла, не происходит возврат к j-й строке. К сожалению, обход второй матрицы полностью исключает возможность использовать кеш: сначала выполняется обход элементов ее первого столбца N раз, затем второго столбца, и так далее. Причина отсутствия возможности использовать кеш в том, что матрица - массив типа int [,], хранится в памяти построчно, как показано на рисунке ниже:

Размещение двумерного массива в памяти

Если бы кеш имел достаточно большой объем, чтобы вторая матрица уместилась в нем целиком, тогда после одной итерации внешнего цикла вторая матрица оказалась бы в кеше и последующие обращения к ее элементам удовлетворялись бы из кеша. Однако, если размер второй матрицы превышает объем кеша, промахи кеша будут происходить слишком часто: промах кеша при обращении к элементу (i,j) повлечет за собой чтение строки кеша, содержащей элементы строки i, но другие элементы столбца j в кеш не попадут, то есть промахи будут происходить при каждом обращении!

Умножение матриц с разделением на блоки приводит к следующей идее. Умножение матриц можно выполнять, как показано выше, или разбив их на более маленькие матрицы (блоки), а затем умножая блоки и выполняя некоторые дополнительные арифметические операции для получения окончательного результата. В частности, если матрицы A и B разбить на блоки, как показано на рисунке ниже, тогда матрицу C = A*B можно вычислить поблочно, то есть:

Матрицы А и В, разбитые на блоки размером k x k
public static int[,] MultiplyBlocked(int[,] A, int[,] B, int bs)
{
    int[,] C = new int[N, N];
    for (int ii = 0; ii < N; ii += bs)
        for (int jj = 0; jj < N; jj += bs)
            for (int kk = 0; kk < N; kk += bs)
                for (int i = ii; i < ii + bs; ++i)
                    for (int j = jj; j < jj + bs; ++j)
                        for (int k = kk; k < kk + bs; ++k)
                            C[i, j] += A[i, k] * B[k, j];
    return C;
}

Шесть вложенных циклов очень просты - три внутренних цикла выполняют матричное умножение двух блоков, а три внешних выполняют итерации по блокам. Чтобы проверить алгоритм поблочного умножения, мы использовали тот же компьютер, что и в предыдущем примере (имеющем кеш 3-го уровня объемом 8 Мбайт) и выполнили умножение двух матриц размером 2048 х 2048 целых чисел. Общий размер двух матриц составляет 2048 х 2048 х 4 х 2 = 32 Мбайт, что явно больше размера кеша. Результаты, полученные для блоков разного размера, показаны в таблице ниже, где можно видеть, что разделение на блоки может существенно повысить производительность, и что выбор оптимального размера блока может дать существенную прибавку к скорости:

Хронометраж алгоритма поблочного умножения матриц с блоками различного размера
Без деления
на блоки
bs=4 bs=8 bs=16 bs=32 bs=64 bs=512 bs=1024
Время (сек) 178 92 81 81 79 106 117 147

Можно привести массу примеров, где учет особенностей кеша оказывает существенное влияние на производительность, при чем не только среди алгоритмов обработки коллекций. Имеются и другие, более тонкие аспекты использования кеша и организации хранения данных в памяти: взаимоотношения между кешами разных уровней, влияние ассоциативности кеша, упорядоченность данных в памяти и многие другие. Дополнительные примеры можно найти в статье Игоря Островского - Gallery of Processor Cache Effects.

Пройди тесты
Лучший чат для C# программистов