dotMemory — это профилировщик памяти для .NET от компании JetBrains. А меня зовут Илья, и я из команды разработки этого инструмента.

Хочу поделиться историей классического догфудинга: как мы оптимизировали один из алгоритмов в dotMemory с помощью своих же инструментов — dotMemory и dotTrace (часть 1). Потом еще раз — с помощью dotTrace, а напоследок еще и с использованием BenchmarkDotNet (часть 2).

Поделиться этой историей меня мотивировали статьи 1 и 2, за что их авторам отдельное большое спасибо.

Началось все с того, что коллега написал в Slack, что у него очень долго рассчитываются данные для показа дерева доминаторов. Настолько долго, что он не дождался. Поскольку проблема проявилась внутри компании, получить проблемный снапшот (снимок состояния памяти) для исследования не составило труда.

Попытка воспроизвести проблему на локальной машине сразу показала, что с некоторого момента наблюдается быстрый рост потребляемой памяти (~1,17 ГБ/с) и в результате процесс уходит в своп. А это почти наверняка означает, что дождаться результата за сколько-нибудь вменяемое время не удастся. Что ж, отличный повод применить dotMemory для поиска проблемы в dotMemory.

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

Данная команда запустит dotMemory.UI.64.exe в режиме профилирования, сделает снапшот, когда показатель «private bytes» превысит 20 ГБ, а по завершении профилирования откроет снапшот в dotMemory. В нашем случае остановить профилирование придется вручную (иначе опять уйдем в своп) — дожидаемся когда все данные запишутся и жмем Ctrl-C.

Итак, снапшот получен и открыт в dotMemory. Я предпочитаю начинать исследование с представления в виде дерева доминаторов (да, того самого, которое не открылось у коллеги, но на текущем снапшоте с ним все в порядке):

Сразу видно, что большую часть памяти занимают ~60 млн объектов CompactDominatorTreeNode+Builder и в каждом из них есть по словарю. Для подавляющего большинства словарей Size < Capacity, т. е. много памяти расходуется впустую. Посмотрим по коду, как используются эти словари и нельзя ли избавиться от такого их количества. Выделяем узел CompactDominatorTreeNode+Builder и делаем Navigate to declaration (из контекстного меню или по Ctrl-L) — попадаем в IDE (в моем случае это Rider) к соответствующему классу. Делаем Find Usages и по первому же использованию попадаем в метод CompactDominatorTree.Build. Это алгоритм сжатия дерева доминаторов.

Изначально dotMemory строит полное дерево доминаторов, т. е. для каждого объекта из снапшота вычисляется и сохраняется объект, эксклюзивно удерживающий его (доминирующий), либо признак отсутствия такого объекта. Это потенциально очень большое дерево, и показывать его пользователю «как есть» бессмысленно. Поэтому следующим шагом dotMemory группирует узлы полного дерева доминаторов по типам объектов на каждом уровне дерева. CompactDominatorTreeNode+Builder — это узел сжатого (компактифицированного) дерева в процессе построения, а словари — это как раз группировка по типам.

Собственно алгоритм получает на вход полное дерево в формате «ребенок → родитель» (т. е. для каждого объекта сохраняется его родитель-доминатор) и последовательно проходит по всем объектам в снапшоте. Если родитель-доминатор объекта еще не обрабатывался, то для него создается новый групповой узел компактифицированного дерева. Текущий объект добавляется в групповой узел (имеющийся либо новый) в качестве дочернего. 

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

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

А что если посмотреть шире и поменять порядок обхода дерева, скажем, на обход в ширину? Во! Выглядит многообещающе. Можно обойтись одним словарем с простым ключом: построив очередной уровень компактифицированного дерева, мы будем очищать словарь и переиспользовать его для следующего уровня. Правда формат «ребенок → родитель» плохо подходит для обхода в ширину: операция получения дочерних узлов для заданного узла оказывается вычислительно слишком дорогой. Нам нужно исходное дерево в другом формате. По удачному стечению обстоятельств такой формат у нас уже есть — dotMemory хранит дерево доминаторов также и в виде списка смежности «родитель → дети». Таким образом, мы можем поменять алгоритм на обход в ширину, не добавив при этом вычислительной сложности.

Переделываем алгоритм, запускаем. Стало лучше: прежних темпов роста (1,17 ГБ/с) уже не наблюдается, однако потребление памяти все равно растет — в среднем по 7,5 МБ/с. В конечном счете, не дотянув до результата, процесс опять уходит в своп.

О-о-кей... идем на второй круг. Снова делаем снапшот, открываем его и смотрим на дерево доминаторов:

На сей раз 16 ГБ занимает само компактифицированное дерево. Давайте оценим, адекватный ли это размер или можно хранить дерево экономнее. Нам нужно узнать общее количество узлов — для этого переключаемся на группировку по типам:

Видим, что 90 млн узлов удерживают 16 ГБ при суммарном собственном размере в 6 ГБ — уже выглядит подозрительно. Переходим в код и смотрим декларацию CompactDominatorTree2+Node:

public sealed class Node
{
  public DfsNumber DfsNumber { get; }      // 8 bytes
  public TypeId ObjectsType { get; }       // 4 bytes
  public int ObjectsCount { get; }         // 4 bytes
  public int RetainedObjectsCount { get; } // 4 bytes
  public ulong RetainedBytes { get; }      // 8 bytes
  public bool IsContainedInSet { get; }    // 1 byte
  public Node Parent { get; }              // 8 bytes

  internal JetArray<Node> ChildrenImpl { get; } // 8 bytes

  // несущественные для понимания детали опущены
}

Полезной нагрузки здесь 45 байт, но с учетом заголовка объекта и выравнивания экземпляр Node занимает 72 байта, а удерживает в среднем по 192 байта. Чтобы посмотреть детали, переключаемся на экземпляры и фильтруем по «CompactDominatorTree2+Node !g !a» («!g» исключает дженерики, «!a» исключает массивы). Открываем первый попавшийся экземпляр:

Смотрим детали выбранного экземпляра:

«…Как же это вышло?... Понимаю! Накладные расходы! Бюрократический аппарат съел все байты деньги». (с) О.Бендер

Теперь видно, что это накладные расходы на хранение дочерних узлов в виде JetMutableArray — очевидно не самый оптимальный способ хранения для большого дерева. Естественно, первое, что приходит в голову — бежать разбираться с выравниванием и оптимизировать хранение дочерних узлов. Например, можно свести их к одному стандартному массиву. Но мы решили пойти более радикальным путем. 

Объемные структуры данных — не редкость для dotMemory. Например, граф объектов мы храним в виде списка смежности, реализованного через два массива struct-ов, ссылающихся друг на друга при помощи целочисленных индексов в этих массивах. Причем в последних версиях мы даже отказались от управляемых массивов и постепенно переходим на собственную реализацию поверх отображаемых в память файлов. Это дает нам минимальные накладные расходы на доступ к элементам (индексация нативной памяти в стиле старого доброго Си), быструю загрузку/сохранение (полностью на уровне ОС) и бесплатную сериализацию/десериализацию. Кроме того, такие массивы могут фрагментарно выгружаться из памяти (без нашего участия), что позволяет освободить физическую память при более-менее последовательном обходе массива. 

Применим этот же подход для компактифицированного дерева доминаторов. Попутно мы сделали признак IsContainedInSet битовым флагом и отказались от поля Parent (оно нигде не использовалось). В итоге узел дерева представляется следующей структурой:

[StructLayout(LayoutKind.Sequential, Pack = 4)]
public readonly struct Node
{
  public readonly TypeId ObjectsType;
  
  private readonly uint _objectsCount;
  public int ObjectsCount => (int)(_objectsCount & 0x7FFFFFFF);

  public bool IsContainedInSet => (_objectsCount & 0x80000000) != 0;
  public readonly int RetainedObjectsCount;
  public readonly ulong RetainedBytes; 
  public readonly DfsNumber DfsEnter;
  public readonly Range<uint> Children;
}

Можно заметить, что при таком последовательном представлении хватило бы и одной целочисленной ссылки — на первый дочерний узел. Однако мы используем диапазон, потому что в конце нам нужно будет упорядочить дочерние узлы уже построенного дерева по убыванию величины RetainedBytes — так удобнее строить sunburst-диаграмму. Например, для представления, изображенного выше, может измениться порядок узлов #1, #2, #3.

Запускаем... Бинго! Теперь пик потребления — всего 12 ГБ. Дерево доминаторов благополучно открывается за 55 мин — дольше, чем хотелось бы, но все же терпимо. Всего снапшот содержит 275 млн объектов, а в компактифицированном дереве 200 млн узлов.

Что ж, весьма приличный результат. В начале нам не хватало 32 ГБ и мы вообще не могли дождаться окончания расчета, а теперь уложились в 12 ГБ и 55 мин. Но… все же осталось чувство неудовлетворенности. 55 мин — это как-то долго. Давайте посмотрим, на что тратится время, с помощью dotTrace:

Не обязательно дожидаться окончания расчетов. Достаточно снять данные для нескольких минут — используем ключ --timeout=3m, который автоматически завершит профилирование через 3 минуты. Открываем полученный файл, устанавливаем фильтр на поток, выполняющий нашу задачу (его легко найти, т. к. он полностью загружен долгое время), и смотрим на дерево вызовов:

Вот так неожиданность: Dictionary.Clear 92%! Да ладно! Не может же Clear так плохо работать на стандартном библиотечном словаре! Оказывается, может — фокус в том, что на самой первой итерации нашего алгоритма словарь расширяется до ~22 тыс. элементов, а дальше элементов обычно не больше пары десятков. При этом сложность Clear для словаря зависит от Capacity (точнее от buckets.Length, который линейно зависит от Capacity), а не от Count. Получается, что мы каждый раз чистим и без того пустые элементы! Кажется, мы перестарались с оптимизацией, когда решили очищать и переиспользовать словарь. 

Тогда возвращаемся на шаг назад и пробуем самое простое — каждый раз выделять новый словарь. Запускаем, засекаем время и-и-и… теперь расчет занимает всего 1 минуту и 46 секунд! Да, нагрузка на GC увеличилась, но она равномерно распределена, и сборщик отлично справляется — в этом можно убедиться с помощью dotTrace.

275 млн объектов, менее 2 минут времени, пиковое потребление памяти — 12 ГБ. Вот это уже действительно достойный результат! Коммитим!

Сцена после титров

Чтобы достичь уж совсем полного-преполного удовлетворения, мы решили сравнить время расчета старым и новым алгоритмом на снапшоте сопоставимого объема, но с другой топологией — так, чтобы справлялся и старый алгоритм. Нашли подходящий снапшот, замерили… и вот незадача! Опять сюрприз: хотя вычислительная сложность не поменялась, новый алгоритм оказался в полтора раза медленнее старого. Но это уже другая история...

UPD

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

Сложность алгоритма в терминах O действительно не изменилась, но увеличилась константа, которая прячется за O. А увеличилась она из-за изменившегося порядка обхода массивов. Если в исходном варианте это был почти последовательный проход, то в новом - произвольный. В результате на порядок вырос показатель CPU cache misses. Нашли с помощью BenchmarkDotNet с включенным [HardwareCounters(HardwareCounter.CacheMisses)]. Поскольку порядок обхода - это неотемлемая часть алгоритма, то тут ничего уже не оптимизируешь. Но нам удалось оптимизациями "вокруг" добиться все же сопоставимого времени с исходным алгоритмом.