Почему мое приложение тратит 24% своей жизни на нулевую проверку?
У меня есть дерево решений с критическими характеристиками производительности, и я хотел бы сфокусировать этот вопрос на одной строке кода. Ниже приведен код для итератора двоичного дерева с результатами анализа производительности от него.
public ScTreeNode GetNodeForState(int rootIndex, float[] inputs)
{
0.2% ScTreeNode node = RootNodes[rootIndex].TreeNode;
24.6% while (node.BranchData != null)
{
0.2% BranchNodeData b = node.BranchData;
0.5% node = b.Child2;
12.8% if (inputs[b.SplitInputIndex] <= b.SplitValue)
0.8% node = b.Child1;
}
0.4% return node;
}
BranchData - это поле, а не свойство. Я сделал это, чтобы предотвратить риск его не встраивания.
Класс BranchNodeData выглядит следующим образом:
public sealed class BranchNodeData
{
/// <summary>
/// The index of the data item in the input array on which we need to split
/// </summary>
internal int SplitInputIndex = 0;
/// <summary>
/// The value that we should split on
/// </summary>
internal float SplitValue = 0;
/// <summary>
/// The nodes children
/// </summary>
internal ScTreeNode Child1;
internal ScTreeNode Child2;
}
Как вы можете видеть, проверка цикла while/null - это огромный удар по производительности. Дерево массивное, поэтому я ожидаю, что поиск листа займет некоторое время, но я хотел бы понять непропорциональное количество времени, затраченного на эту линию.
Я пробовал:
- Отделяя проверку Null от времени - это Null проверяет, что ударил.
- Добавление логического поля к объекту и проверка на него не имеет значения. Неважно, что сравнивать, это сравнение, в котором проблема.
Является ли это проблемой прогноза ветвления? Если да, то что я могу с этим поделать? Если что-нибудь?
Я не буду притворяться, что понимаю CIL, но я отправлю его для всех, чтобы они могли попытаться очистить некоторую информацию от него.
.method public hidebysig
instance class OptimalTreeSearch.ScTreeNode GetNodeForState (
int32 rootIndex,
float32[] inputs
) cil managed
{
// Method begins at RVA 0x2dc8
// Code size 67 (0x43)
.maxstack 2
.locals init (
[0] class OptimalTreeSearch.ScTreeNode node,
[1] class OptimalTreeSearch.BranchNodeData b
)
IL_0000: ldarg.0
IL_0001: ldfld class [mscorlib]System.Collections.Generic.List`1<class OptimalTreeSearch.ScRootNode> OptimalTreeSearch.ScSearchTree::RootNodes
IL_0006: ldarg.1
IL_0007: callvirt instance !0 class [mscorlib]System.Collections.Generic.List`1<class OptimalTreeSearch.ScRootNode>::get_Item(int32)
IL_000c: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.ScRootNode::TreeNode
IL_0011: stloc.0
IL_0012: br.s IL_0039
// loop start (head: IL_0039)
IL_0014: ldloc.0
IL_0015: ldfld class OptimalTreeSearch.BranchNodeData OptimalTreeSearch.ScTreeNode::BranchData
IL_001a: stloc.1
IL_001b: ldloc.1
IL_001c: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.BranchNodeData::Child2
IL_0021: stloc.0
IL_0022: ldarg.2
IL_0023: ldloc.1
IL_0024: ldfld int32 OptimalTreeSearch.BranchNodeData::SplitInputIndex
IL_0029: ldelem.r4
IL_002a: ldloc.1
IL_002b: ldfld float32 OptimalTreeSearch.BranchNodeData::SplitValue
IL_0030: bgt.un.s IL_0039
IL_0032: ldloc.1
IL_0033: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.BranchNodeData::Child1
IL_0038: stloc.0
IL_0039: ldloc.0
IL_003a: ldfld class OptimalTreeSearch.BranchNodeData OptimalTreeSearch.ScTreeNode::BranchData
IL_003f: brtrue.s IL_0014
// end loop
IL_0041: ldloc.0
IL_0042: ret
} // end of method ScSearchTree::GetNodeForState
Изменить: Я решил выполнить тест предсказания ветвления, я добавил то же самое, если в течение этого времени, поэтому мы имеем
while (node.BranchData != null)
и
if (node.BranchData != null)
внутри этого. Затем я выполнил анализ производительности, и потребовалось шесть раз дольше, чтобы выполнить первое сравнение, как это было сделано для выполнения второго сравнения, которое всегда возвращалось true. Итак, похоже, что это действительно проблема предсказания ветвей - и я предполагаю, что я ничего не могу с этим поделать?
Другое Редактирование
Вышеприведенный результат также возникнет, если node.BranchData должен быть загружен из ОЗУ для проверки while - тогда он будет кэшироваться для оператора if.
Это мой третий вопрос по аналогичной теме. На этот раз я сосредоточен на одной строке кода.
Мои другие вопросы по этому вопросу:
Ответы
Ответ 1
Дерево массивное
Самым дорогим, что когда-либо делает процессор, является не выполнение инструкций, он обращается к памяти. Ядро выполнения современного CPU во много раз быстрее, чем шина памяти. Проблема, связанная с расстоянием, чем дальше должен пройти электрический сигнал, тем сложнее получить этот сигнал, подаваемый на другой конец провода, без его повреждения. Единственное лекарство от этой проблемы - сделать его медленнее. Большая проблема с проводами, которые соединяют процессор с ОЗУ на вашем компьютере, вы можете вытащить корпус и посмотреть провода.
Процессоры имеют контрмер для этой проблемы, они используют кеши, буферы, которые хранят копию байтов в ОЗУ. Важным является кеш L1, обычно 16 килобайт для данных и 16 килобайт для инструкций. Маленький, позволяя ему быть ближе к движку исполнения. Чтение байтов из кэша L1 обычно занимает 2 или 3 цикла ЦП. Далее - кеш L2, больший и медленный. У высококлассных процессоров также есть кеш L3, все больше и меньше. По мере совершенствования технологической технологии эти буферы занимают меньше места и автоматически становятся быстрее по мере приближения к ядру, что является большой причиной того, почему более новые процессоры лучше и как им удается использовать все большее количество транзисторов.
Однако эти кэши не являются идеальным решением. Процессор будет по-прежнему останавливаться на доступе к памяти, если данные недоступны в одном из кэшей. Он не может продолжаться до тех пор, пока очень медленная шина памяти не предоставит данные. Потеря веса в течение нескольких циклов процессора возможна по одной команде.
Древовидные структуры - проблема, они не кэшированы. Их узлы, как правило, разбросаны по всему адресному пространству. Самый быстрый способ доступа к памяти - чтение с последовательных адресов. Единица хранения кеша L1 составляет 64 байта. Или, другими словами, как только процессор считывает один байт, следующие 63 очень быстры, так как они будут присутствовать в кеше.
Что делает массив наиболее эффективной структурой данных. Также причина, по которой класс .NET List < > не является списком вообще, использует массив для хранения. То же самое для других типов коллекций, таких как словарь, структурно не удаленных друг от друга аналогично массиву, но внутренне реализуемых с массивами.
Таким образом, ваш оператор while(), скорее всего, страдает от киосков процессора, потому что он разыменовывает указатель для доступа к полю BranchData. Следующее утверждение очень дешево, потому что оператор while() уже сделал тяжелый подъем извлечения значения из памяти. Присвоение локальной переменной дешево, процессор использует буфер для записи.
В противном случае простая проблема для решения проблемы, сглаживание вашего дерева в массивы, скорее всего, будет непрактичным. Не в последнюю очередь потому, что вы, как правило, не можете предсказать, в каком порядке будут посещаться узлы дерева. Красное-черное дерево может помочь, это не ясно из вопроса. Таким образом, простой вывод состоит в том, что он уже работает так быстро, как вы можете надеяться. И если вам нужно, чтобы он работал быстрее, вам понадобится лучшее оборудование с более быстрой шиной памяти. DDR4 будет в этом году распространяться.
Ответ 2
Чтобы дополнить замечательный ответ Ганса об эффектах кэширования памяти, я добавляю обсуждение виртуальной памяти на перевод физической памяти и эффекты NUMA.
При использовании компьютера виртуальной памяти (всего текущего компьютера) при выполнении доступа к памяти каждый адрес виртуальной памяти должен быть переведен на адрес физической памяти. Это делается с помощью аппаратного обеспечения управления памятью, используя таблицу переводов. Эта таблица управляется операционной системой для каждого процесса и сама хранится в ОЗУ. Для каждой страницы виртуальной памяти в этой таблице переводов есть запись, отображающая виртуальную на физическую страницу. Помните, что обсуждение Ханса относительно доступа к памяти очень дорого: если для каждого виртуального физического перевода необходим поиск в памяти, то доступ к памяти будет в два раза дороже. Решение состоит в том, чтобы иметь кеш для таблицы переводов, который называется буфером просмотра перевода (для краткости TLB). TLB невелики (от 12 до 4096 записей), а типичный размер страницы в архитектуре x86-64 составляет всего 4 КБ, а это означает, что доступно не более 16 МБ с помощью TLB-просмотров (это, вероятно, даже меньше, Sandy Bridge с размером TLB 512 элементов). Чтобы уменьшить количество пропусков TLB, вы можете заставить операционную систему и приложение работать вместе, чтобы использовать больший размер страницы, например, 2 МБ, что приводит к значительно большему объему памяти, доступному с помощью TLB-хитов. На этой странице объясняется, как использовать большие страницы с Java , что может значительно ускорить доступ к памяти.
Если ваш компьютер имеет много сокетов, это, вероятно, архитектура NUMA. NUMA означает неравномерный доступ к памяти. В этих архитектурах некоторые обращения к памяти стоят дороже других. Например, при использовании 2-х гнездового компьютера с 32 ГБ оперативной памяти, каждый сокет, вероятно, имеет 16 ГБ ОЗУ. На этом примере компьютер доступ к локальной памяти дешевле, чем доступ к памяти другого сокета (удаленный доступ на 20-100% медленнее, а может быть, даже больше). Если на таком компьютере ваше дерево использует 20 ГБ ОЗУ, по крайней мере 4 ГБ ваших данных находятся на другом NUMA node, а если доступ на 50% медленнее для удаленной памяти, NUMA обращается к замедлению доступа к вашей памяти на 10%, Кроме того, если у вас есть только свободная память на одном NUMA node, всем процессам, требующим памяти на голодающем node, будет выделена память из другого node, доступ к которым более дорогой. Даже хуже всего, операционная система могла подумать, что неплохо поменять часть памяти голодающих node, , что приведет к еще более дорогостоящим обращению к памяти. Это более подробно объясняется в проблеме "безумного обмена" MySQL и эффектах архитектуры NUMA, где некоторые решения предоставляются для Linux (распространение доступа к памяти на всех узлах NUMA, кусание пули на удаленных NUMA доступах, чтобы избежать обмена). Я также могу подумать о распределении большего количества оперативной памяти в сокет (24 и 8 Гбайт вместо 16 и 16 ГБ) и убедиться, что ваша программа является расписанием на более крупном NUMA node, но для этого требуется физический доступ к компьютеру и отвертка; -.)
Ответ 3
Это не ответ как таковой, а скорее акцент на том, что Ханс Пассант писал о задержках в системе памяти.
Действительно высокопроизводительное программное обеспечение, такое как компьютерные игры, не только написано для реализации самой игры, но и адаптировано таким образом, что кодовые и информационные структуры максимально используют системы кеш-памяти и системы памяти в качестве ограниченного ресурса. Когда я занимаюсь проблемами кеша, я обычно предполагаю, что L1 будет поставляться в 3 цикла, если данные там присутствуют. Если это не так, и я должен перейти на L2, я предполагаю 10 циклов. Для L3 30 циклов и для RAM-памяти 100.
Существует дополнительное связанное с памятью действие, которое - если вам нужно использовать его - накладывает еще больший штраф, а это блокировка шины. Блокировки шины называются критическими разделами, если вы используете функциональность Windows NT. Если вы используете домашний образ, вы можете назвать его спин-блокировкой. Каким бы ни было имя, оно синхронизируется до самого медленного устройства для настройки шины в системе до того, как замок будет на месте. Самое медленное устройство для шинирования может быть классической 32-битной PCI-картой, подключенной к 33 МГц. 33 МГц - одна сотая частота типичного процессора x86 (@3,3 ГГц). Я предполагаю, что не менее 300 циклов для завершения блокировки шины, но я знаю, что они могут занимать много раз, поэтому, если я увижу 3000 циклов, я не удивлюсь.
Разработчики программного обеспечения для начинающих многопотоков будут использовать блокировки по всему месту, а затем задаются вопросом, почему их код медленный. Трюк - как и все, что связано с памятью, - это экономить на доступе.
