Источник: habr.com

Date: 2020-02-21

На написание этой небольшой заметки меня подтолкнуло несколько проведенных в последнее время собеседований на должность ведущего разработчика в нашу компанию. Некоторые соискатели, как оказалось, недостаточно разбираются в том, что же это за механизм такой, Dictionary, и как его нужно использовать. Столкнулся даже с весьма радикальным мнением: мол, словарь работает очень медленно, причем из-за того, что при создании сразу же помещается в куче больших объектов (LOH), использовать его в коде нельзя и лучше применять запросы к обычным коллекциям с помощью фильтров LINQ!

Конечно же, это не совсем верные утверждения. Словарь как механизм очень часто бывает востребован как при построении высоконагруженного кода, так и при реализации бизнес-логики. Разработчик должен представлять, как устроен словарь, как он работает с памятью, насколько затратен, сколько «следов» оставит в поколениях и LOH, вызывая излишнюю нагрузку на сборщик мусора; как его лучше инициализировать, в каких случаях вместо него лучше использовать коллекцию пар ключ-значение, в каких – сортированную коллекцию и т.д.

В этой заметке мы постараемся разобраться с некоторыми из этих вопросов.

Реализация словаря от Майкрософт базируется, как всем известно, на механизме хэш-таблиц. Это дает в некоторых сценариях недостижимую для других алгоритмов идеальную константную сложность O(1) на операции вставки, поиска, удаления. В некоторых же сценариях отказ от использования этого механизма чреват существенными проблемами с производительностью и потреблением памяти.

Важной особенностью архитектуры является то, что хранение данных организовано с помощью двух массивов одинакового размера:

int[] _buckets = new int[size];Entry[] _entries = new Entry[size];

Эти массивы хранят полезные данные и служебные элементы для быстрого доступа к ним. Массивы создаются с запасом, то есть они практически всегда не заполнены.

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

private struct Entry{    public uint hashCode;    public int next;    public TKey key;    public TValue value;}

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

С другой стороны такой массив _entries при активной работе с Dictionary достаточно быстро достигнет 85000 байт и переместится в кучу больших объектов LOH (например, если ключ и значение будут ссылочного типа, то для 64 разрядного приложения это случится при 3372 добавленных значений, а в некоторых случаях и при 1932). Как известно, куча больших объектов при активной работе подвержена фрагментации, что ведет к росту потребляемой приложением неиспользуемой памяти.

Почему разработчики Microsoft не разделили _entries на четыре массива, соответствующих полям Entry? Это бы отдалило перспективу попадания в LOH и в некоторых сценариях снизило потребление памяти (увеличив, скорее всего, частоту сборок мусора). Видимо, посчитали, что выигрыш не настолько велик.

При работе со словарем разработчик должен учитывать, что это не бесплатная структура данных. Для хранения одного значения дополнительно потребляется как минимум 12 байт памяти (4 байта в массиве _buckets и по 4 байта на поля hashCode и next сущности Entry). Создавая в памяти приложения словарь и заполняя его, например, миллионом значений, мы получим как минимум 12МБ перерасхода памяти. Однако только ли этим все ограничится? Нет.

Механизм Dictionary всегда резервирует определенное количество памяти для еще не добавленных элементов. Иначе ни о какой быстрой вставке не могло бы быть и речи. На графике представлена динамика выделения памяти для словаря типа Dictionary<int, int> при добавлении значений (красный цвет). Для сравнения показано, сколько байт занимает полезная нагрузка – хранимые в словаре данные (синий цвет). Количество добавленных элементов от 500 тыс. до 13 млн. Словарь инициализируется на стартовую емкость 500 тыс.

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

Еще одна особенность работы механизмов алгоритма заключается в том, что при каждом расширении емкости _buckets и _entries создаются заново и все существующие значения просто копируются из старых массивов в новые, после чего ссылки на старые «отпускаются», становятся доступными для сборщика мусора. Для словарей с большим количеством значений каждое такое выделение памяти осуществляется сразу в LOH, что приближает вызов полной сборки мусора. Например, при работе тестов для создания представленного выше графика приложение аллоцировало суммарно 746МБ и выполнило 3 сборки мусора во втором поколении.