У меня есть критически важное для производительности двоичное дерево решений, и я хотел бы сосредоточить этот вопрос на одной строке кода. Ниже приведен код итератора двоичного дерева с результатами анализа его производительности.
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 сильно снижает производительность. Дерево массивное, поэтому я ожидал, что поиск листа займет некоторое время, но я хотел бы понять, какое непропорциональное количество времени потрачено на эту одну строку.
Я пробовал:
- Отделение проверки обнуления от времени - это проверка на обнуление.
- Добавление логического поля к объекту и проверка по нему не имело никакого значения. Неважно, что сравнивается, проблема в сравнении.
Это проблема с предсказанием ветвления? Если да, что я могу с этим поделать? Если что-нибудь?
Я не буду делать вид, что понимаю 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Изменить: я решил сделать тест на предсказание ветвления, я добавил идентичный if в течение некоторого времени, поэтому у нас есть
while (node.BranchData != null)и
if (node.BranchData != null)внутри этого. Затем я провел анализ производительности для этого, и на выполнение первого сравнения ушло в шесть раз больше времени, чем на выполнение второго сравнения, которое всегда возвращало истину. Так что похоже, что это действительно проблема с предсказанием ветвления - и я думаю, что я ничего не могу с этим поделать ?!
Другое редактирование
Вышеупомянутый результат также имел бы место, если бы node.BranchData нужно было загрузить из ОЗУ для проверки while - тогда он был бы кеширован для оператора if.
Это мой третий вопрос по аналогичной теме. На этот раз я сосредоточусь на одной строчке кода. Мои другие вопросы по этому поводу:
источник
BranchNodeсвойства. Пожалуйста, попробуйте заменитьnode.BranchData != nullReferenceEquals(node.BranchData, null). Какая разница?while(true) { /* current body */ if(node.BranchData == null) return node; }. Это что-то меняет?while(true) { BranchNodeData b = node.BranchData; if(ReferenceEquals(b, null)) return node; node = b.Child2; if (inputs[b.SplitInputIndex] <= b.SplitValue) node = b.Child1; }это будет извлекатьсяnode. BranchDataтолько один раз.Ответы:
Безусловно, самое дорогое, что делает процессор, - это не выполнение инструкций, а доступ к памяти. Ядро исполнения современного процессора во много раз быстрее, чем шина памяти. Проблема, связанная с расстоянием , заключается в том , что чем дальше должен пройти электрический сигнал, тем сложнее доставить этот сигнал на другой конец провода без его повреждения. Единственное лекарство от этой проблемы - сделать это медленнее. Большая проблема с проводами, которые соединяют ЦП с ОЗУ на вашем компьютере, вы можете открыть корпус и увидеть провода.
У процессоров есть противодействие этой проблеме, они используют кеши , буферы, которые хранят копию байтов в ОЗУ. Важным является кеш L1 , обычно 16 килобайт для данных и 16 килобайт для инструкций. Маленький, что позволяет ему быть близко к механизму исполнения. Чтение байтов из кэша L1 обычно занимает 2 или 3 цикла ЦП. Далее идет кэш L2, больше и медленнее. У высококлассных процессоров также есть кэш L3, но он больше и медленнее. По мере совершенствования технологического процесса эти буферы занимают меньше места и автоматически становятся быстрее по мере приближения к ядру, что является важной причиной того, почему новые процессоры лучше и как им удается использовать постоянно увеличивающееся количество транзисторов.
Однако эти кеши не являются идеальным решением. Процессор по-прежнему будет останавливаться при доступе к памяти, если данные недоступны в одном из кешей. Это не может продолжаться до тех пор, пока очень медленная шина памяти не предоставит данные. Потеря целых сотен циклов процессора возможна на одной инструкции.
Древовидные структуры представляют собой проблему, они не подходят для кеширования. Их узлы обычно разбросаны по адресному пространству. Самый быстрый способ доступа к памяти - чтение с последовательных адресов. Единица хранения кеш-памяти L1 составляет 64 байта. Или, другими словами, как только процессор читает один байт, следующие 63 байта выполняются очень быстро, поскольку они будут присутствовать в кэше.
Что делает массив на сегодняшний день наиболее эффективной структурой данных. Также причина того, что класс .NET List <> вообще не является списком, он использует массив для хранения. То же самое для других типов коллекций, таких как Dictionary, структурно не похожее на массив удаленно, но внутренне реализованное с помощью массивов.
Таким образом, ваш оператор while (), скорее всего, будет страдать от остановки процессора, потому что он разыменовывает указатель для доступа к полю BranchData. Следующий оператор очень дешевый, потому что оператор while () уже выполнил тяжелую работу по извлечению значения из памяти. Назначение локальной переменной дешево, процессор использует буфер для записи.
Сложить дерево в массивы не так уж и просто. Скорее всего, это будет непрактично. Не в последнюю очередь потому, что вы обычно не можете предсказать, в каком порядке будут посещаться узлы дерева. Красно-черное дерево может помочь, не понятно из вопроса. Таким образом, простой вывод: он уже работает так быстро, как вы можете надеяться. И если вам нужно, чтобы он работал быстрее, вам понадобится лучшее оборудование с более быстрой шиной памяти. В этом году DDR4 становится мейнстримом.
источник
В дополнение к замечательному ответу Ханса об эффектах кэширования памяти я добавляю обсуждение виртуальной памяти к трансляции физической памяти и эффектам NUMA.
На компьютере с виртуальной памятью (весь текущий компьютер) при доступе к памяти каждый адрес виртуальной памяти должен быть преобразован в адрес физической памяти. Это делается аппаратным обеспечением управления памятью с помощью таблицы трансляции. Эта таблица управляется операционной системой для каждого процесса и хранится в оперативной памяти. Для каждой страницы виртуальной памяти есть запись в этой таблице преобразования, которая сопоставляет виртуальную страницу с физической. Вспомните дискуссию Ханса о дорогостоящих доступах к памяти: если для каждого преобразования из виртуального в физическое требуется поиск в памяти, то весь доступ к памяти будет стоить вдвое дороже. Решение состоит в том, чтобы иметь кеш для таблицы перевода, который называется резервным буфером перевода.(TLB для краткости). TLB невелики (от 12 до 4096 записей), а типичный размер страницы в архитектуре x86-64 составляет всего 4 КБ, что означает, что с обращениями TLB напрямую доступно не более 16 МБ (вероятно, даже меньше, чем у Sandy Мост с размером TLB 512 элементов ). Чтобы уменьшить количество промахов TLB, вы можете заставить операционную систему и приложение работать вместе, чтобы использовать больший размер страницы, например 2 МБ, что приведет к гораздо большему пространству памяти, доступному для обращений TLB. На этой странице объясняется, как использовать большие страницы с Java, что может значительно ускорить доступ к памяти .
Если на вашем компьютере много сокетов, вероятно, это архитектура NUMA . NUMA означает неоднородный доступ к памяти. В этих архитектурах некоторые обращения к памяти стоят дороже, чем другие.. Например, для компьютера с двумя сокетами и 32 ГБ оперативной памяти каждый сокет, вероятно, имеет 16 ГБ. На этом примере компьютера доступ к локальной памяти дешевле, чем доступ к памяти другого сокета (удаленный доступ на 20-100% медленнее, может быть, даже больше). Если на таком компьютере ваше дерево использует 20 ГБ ОЗУ, не менее 4 ГБ ваших данных находится на другом узле NUMA, а если доступ к удаленной памяти на 50% медленнее, доступ к NUMA замедляет доступ к вашей памяти на 10%. Кроме того, если у вас есть свободная память только на одном узле NUMA, всем процессам, которым требуется память на голодном узле, будет выделена память из другого узла, доступ к которому является более дорогим. В худшем случае операционная система может подумать, что выгрузить часть памяти голодного узла - это хорошая идея.что приведет к еще более дорогостоящему доступу к памяти . Это объясняется более подробно в статье MySQL «Проблема безумия подкачки» и влияние архитектуры NUMA, где некоторые решения даны для Linux (распространение доступа к памяти на все узлы NUMA, резкое сокращение удаленных обращений к NUMA во избежание подкачки). Я также могу подумать о том, чтобы выделить больше оперативной памяти для сокета (24 и 8 ГБ вместо 16 и 16 ГБ) и убедиться, что ваша программа запланирована на большем узле NUMA, но для этого нужен физический доступ к компьютеру и отвертка ;-) .
источник
Это не ответ как таковой, а скорее акцент на том, что Ханс Пассан писал о задержках в системе памяти.
Действительно высокопроизводительное программное обеспечение, такое как компьютерные игры, не только написано для реализации самой игры, но и адаптировано таким образом, что код и структуры данных максимально используют системы кеш-памяти и памяти, т.е. рассматривают их как ограниченный ресурс. Когда я имею дело с проблемами кеша, я обычно предполагаю, что L1 выполнит доставку за 3 цикла, если данные там присутствуют. Если это не так, и мне нужно перейти в L2, я предполагаю, что 10 циклов. Для L3 30 циклов и для оперативной памяти 100.
Существует дополнительное действие, связанное с памятью, которое - если вам нужно его использовать - налагает еще больший штраф, и это блокировка шины. Блокировки шины называются критическими секциями, если вы используете функциональность Windows NT. Если вы используете выращенный в домашних условиях сорт, вы можете назвать это спин-блокировкой. Каким бы ни было имя, он синхронизируется с самым медленным устройством управления шиной в системе, прежде чем блокировка будет установлена. Самым медленным устройством для управления шиной может быть классическая 32-битная PCI-карта, подключенная с частотой 33 МГц. 33 МГц - это одна сотая частоты типичного процессора x86 (@ 3,3 ГГц). Я предполагаю, что для завершения блокировки шины потребуется не менее 300 циклов, но я знаю, что это может занять во много раз больше времени, поэтому, если я увижу 3000 циклов, я не удивлюсь.
Начинающие разработчики многопоточного программного обеспечения будут повсюду использовать блокировки шины, а затем удивляться, почему их код работает медленно. Уловка - как и во всем, что связано с памятью - состоит в том, чтобы сэкономить на доступе.
источник