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

C# и .NET Framework --- Оптимизация приложений .NET Framework --- Реализация коллекций в CLR

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

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

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

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

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

• Требования, предъявляемые к разным коллекциям, существенно разнятся. Далее в этой статье будет показано, как внутренняя организация коллекций влияет на работу кеша процессора с коллекциями List<T> и LinkedList<T>. Другой пример - классы SortedSet<T> и List<T>; первый реализует поиск по двоичному дереву с n узлами для n элементов, а второй - в непрерывном массиве из n элементов. В 32-разрядных системах для хранения n экземпляров типа значения размером s в сортированном множестве требуется (20 + s)n байт, тогда как при использовании списка требуется всего s*n байт.

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

• Амортизированная производительность O(1) коллекций, хорошо организованных, едва отличается от истинной производительности O(1). В конце концов, немногие программисты (и программы!) опасаются, что в течение продолжительного времени использования List<T>.Add иногда может вызывать дополнительные задержки из-за выделения памяти, прямо пропорциональные числу элементов в списке. Анализ амортизированной производительности - отличный способ определения оптимальных границ для различных алгоритмов и коллекций.

• Извечный компромисс «пространство-время» уже заложен в архитектуру коллекций и, разумеется, влияет на выбор той или иной коллекции из числа включенных в .NET Framework. Коллекция SortedList<K,V> предлагает очень компактный способ хранения элементов за счет линейного увеличения времени вставки и удаления, тогда как коллекция SortedDictionary<K,V> занимает больше места, но обеспечивает логарифмическое увеличение времени выполнения всех операций.

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

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

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

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

Хотя большинство параллельных коллекций весьма похожи на свои непараллельные аналоги, они имеют несколько отличающийся набор методов, объясняемый их параллельной природой. Например, класс 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 на моем компьютере имеет три уровня кеша:

• кеш первого уровня для программных инструкций, 32 Кбайта, по одному на каждое ядро (всего 4 кеша);

• кеш первого уровня для данных, 32 Кбайта, по одному на каждое ядро (всего 4 кеша);

• кеш второго уровня для данных, 256 Кбайт, по одному на каждое ядро (всего 4 кеша);

• кеш третьего уровня для данных, 8 Мбайт, общий (всего 1 кеш).

Когда процессору требуется обратиться к ячейке памяти, он сначала проверяет, не хранятся ли необходимые данные в кеше первого уровня (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 можно вычислить поблочно, то есть:

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 Мбайт, что явно больше размера кеша. Результаты, полученные для блоков разного размера, показаны в таблице ниже, где можно видеть, что разделение на блоки может существенно повысить производительность, и что выбор оптимального размера блока может дать существенную прибавку к скорости:

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