Количество обрабатываемых инструкций за такт как узнать

Заинтересовал меня вопрос — а сколько инструкций за такт выполняют современные Arm и Intel процессоры. И мои 0.8 инструкции на такт — это хорошо или плохо?

Будем тестировать такой код.

int32_t asin[1000];
int32_t adata[1000];
int64_t sum;
void Test::process(int count)
{
    sum = 0;
    for (int i = 0; i < count; i++)
    {
        sum += asin[i] * adata[i];
    }
}

count = 1000, функция эта вызывается 100000. Т.е. всего 1e8 итераций. Включаем везде максимальную оптимизацию, но принимаем меры против того, чтобы функция process заинлайнилась. И что-бы count не считался константой, которой можно сделать unwind цикла.

Сначала общая таблица.
time=0.180 sec Intel Core i7 4 GHz x86. 8 инструкций в цикле. Примерно 7.2 такта на цикл.
time=0.056 sec Intel Core i7 4 GHz x64. 8 инструкций в цикле. Примерно 2.4 такта на цикл.
time=0.350 sec Cortex-A53 2.016 GHz arm64-v8a      7 инструкций в цикле. Примерно 7.05 такта на цикл.
time=0.355 sec Cortex-A53 2.016 GHz armeabi-v7a    9 инструкций в цикле. Примерно 7.16 такта на цикл.
time=0.850 sec Cortex-A53 2.016 GHz armeabi 17 инструкций в цикле. Примерно 17.1 такта на цикл.

Ниже приведу asm вырезки кода цикла, сгенерированного компиляторами.

[Intel Core i7 4 GHz x86]
Intel Core i7 4 GHz x86

00E31092  mov         eax, dword ptr[ecx + esi * 4 + 0FA0h]
00E31099  imul        eax, dword ptr[ecx + esi * 4]
00E3109D  cdq
00E3109E  add         dword ptr[ecx + 1F40h], eax
00E310A4  adc         dword ptr[ecx + 1F44h], edx
00E310AA  inc         esi
00E310AB  cmp         esi, edi
00E310AD  jl          Test::process + 22h (0E31092h)

[Intel Core i7 4 GHz x64]
Intel Core i7 4 GHz x64

00007FF70CF91015  mov         ecx,dword ptr [r8+rax*4+0FA0h]
00007FF70CF9101D  inc         rax
00007FF70CF91020  imul        ecx,dword ptr [r8+rax*4-4]
00007FF70CF91026  movsxd      rcx,ecx
00007FF70CF91029  add         rdx,rcx
00007FF70CF9102C  mov         qword ptr [r8+1F40h],rdx
00007FF70CF91033  cmp         rax,r9
00007FF70CF91036  jl          Test::process+15h (07FF70CF91015h)

[Cortex-A53 2.016 GHz arm64-v8a]
Cortex-A53 2.016 GHz arm64-v8a

.LBB1_2:
ldrsw   x11, [x10, #4000]
ldrsw   x12, [x10]
sub     x9, x9, #1
add     x10, x10, #4
madd    x8, x11, x12, x8
str     x8, [x0, #8000]
cbnz    x9, .LBB1_2

[Cortex-A53 2.016 GHz armeabi-v7a]
Cortex-A53 2.016 GHz armeabi-v7a

.LBB1_1:
ldr.w   lr, [r0]
ldr.w   r4, [r0, #4000]
adds    r0, #4
mul     r4, r4, lr
adds    r3, r3, r4
adc.w   r2, r2, r4, asr #31
subs    r1, #1
strd    r3, r2, [r12]
bne     .LBB1_1

[Cortex-A53 2.016 GHz armeabi]
Cortex-A53 2.016 GHz armeabi

.LBB1_2:
lsls    r6, r3, #5
subs    r6, r6, r0
ldr     r6, [r6]
movs    r4, r3
rsbs    r3, r0, #0
ldr     r3, [r3]
muls    r3, r6, r3
ldr     r6, [sp]
adds    r2, r2, r3
str     r2, [r6]
asrs    r3, r3, #31
adcs    r5, r3
movs    r3, r4
str     r5, [r6, #4]
subs    r0, r0, #4
subs    r1, r1, #1
bne     .LBB1_2

Практически по всех вариантах количество инструкций на такт попадает в интервал [0.9, 1.1], т.е. около одной инструкции на такт. Особняком стоит Intel Core i7 4 GHz x64 который вдруг разогнался неимоверно и выдает нам 3.3 инструкции на такт!!!

Делаем выводов пачку всяких.

1. Одна инструкция на такт это нормально. Так что мы со своими 0.8 инструкциями на такт не слишком отстаем от «крутых» процессоров.
2. Суперскалярный процессор это круто, но легко может случиться, что его суперскалярность сломается и будет он работать как обычный процессор с одной инструкцией на такт. Это подтверждает вариант x86 который делает одну инструкцию на такт.
3. Инструкции должны быть функциональными. Instruction set это не только про инструкции которые просто парсить. Instruction set это еще и про запаковку максимальной информации в минимальное количество инструкций. armeabi вариант нам показывает, почему 17 инструкций на цикл — это плохо.

PS: Еще парочка замечаний по сравнительному ассемблеру.
В arm64-v8a используется инструкция перехода cbnz x9, .LBB1_2 Это аналог моей инструкции if(rx!=0) goto Label. Т.е. вариант без слова состояния alu является вполне живым.

Если сравнивать rm64-v8a и armeabi-v7a код, то видно, что идет отказ от инструкций вида adds r3, r3, r4. Тоесть инструкций, в которых три разных регистра используются. Мне это тоже кажется логичным развитием событий.

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 10

Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения

Лаборатория

Если вы изучали производительность CPU при покупке следующего процессора, вы наверняка встречали термин «IPC» здесь и там.

Вот слайд с недавнего мероприятия по запуску AMD Ryzen серии 7000, который рекламирует улучшение IPC:

В этой статье я объясню, что такое IPC (Instructions Per Clock/Cycle) и как это влияет на производительность процессора.

К сожалению, один из самых простых способов объяснить IPC всё ещё немного сложен: это количество инструкций, которые ЦП может обработать за один такт.

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

Что такое IPC

Тактовые циклы и тактовые частоты: погружение с головой в микроархитектуру центрального процессора.

Какой тактовый цикл?

Не этот.

Это, на самом деле, что-то вроде этого:

Теперь без шуток, позвольте мне объяснить.

Цифровые схемы полагаются на тактовые сигналы, чтобы знать, когда и как выполнять инструкции.

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

Один «цикл» CPU – это временной интервал между двумя этими импульсами, синхронизированными внутренним генератором. Это время, необходимое для перехода из низкого состояния в высокое и обратно в низкое.

Количество этих «циклов», которые он может обрабатывать в секунду, – это то, что мы называем «тактовой частотой» процессора.

Так как тактовая частота и тактовый цикл процессора могут быть разными для каждой архитектуры ЦП, мы никогда не сравниваем ЦП разных марок/поколений, используя только их тактовую частоту.

Определение IPC – на что влияет тактовая частота

Теперь, когда вы знаете, что такое тактовый цикл, определение IPC становится намного проще.

IPC (Instructions Per Clock) – это количество инструкций, которые ЦП может выполнить за один такт.

С другой стороны, тактовая частота процессора (указываемая в ГГц) – это количество тактов, которые он может выполнить за одну секунду. Таким образом, процессор с частотой 3 ГГц может выполнять целых 3 миллиарда циклов за одну секунду!

Даже в рамках одного и того же бренда IPC могут сильно различаться.

Вот один пример:

Просто взгляните на показатели производительности при запуске одноядерного теста Cinebench R20 на всех этих процессорах.

Поскольку все процессоры заблокированы на постоянной частоте 4 ГГц, единственным аспектом, который может варьироваться, является количество инструкций, которые эти процессоры могут обрабатывать за такт (их IPC).

Вы можете ясно видеть скачки производительности между поколениями с каждым новым Ryzen.

AMD поднялась с 404 (Ryzen 7 1800X) для одного ядра до 517 (Ryzen 7 5800X) на той же частоте 4 ГГц!

Часто задаваемые вопросы

Как улучшается IPC?

Каждое поколение ЦП улучшает предыдущее (за некоторыми заметными исключениями).

Хотя объяснение того, как вы можете улучшить IPC, перенесёт эту статью на территорию микроархитектуры ЦП, я могу дать вам краткий обзор того, что происходит за кулисами.

Давайте снова воспользуемся слайдами презентации AMD Ryzen 7000? Вот часть, где Марк Пейпермастер из AMD объясняет, как процессоры Zen 4 достигли 13-процентного увеличения IPC по сравнению с предыдущим поколением.

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

Давайте рассмотрим, что они из себя представляют?

• Кэш L2: банк памяти, построенный на микросхеме ЦП и более медленный, чем кеш L1. Его также называют вторичным кэшем.
• Механизм выполнения: обрабатывает целочисленные операции и операции с памятью, а также операции с плавающей запятой.
• Предсказание ветвления: ускоряет обработку инструкций ветвления с использованием конвейеров.
• Загрузка/сохранение: специализированный блок, отвечающий за выполнение всех инструкций по загрузке и сохранению.
• Внешний интерфейс: имеет дело с упорядоченными операциями, такими как выборка инструкций и декодирование.

Означает ли более высокая частота более быстрый процессор?

Только при сравнении процессоров одной марки и одного поколения.

Никогда не следует использовать тактовые частоты для сравнения производительности двух процессоров в любом другом сценарии.

У вас вполне могут быть «процессоры с частотой 4 ГГц» десятилетней давности, которые будут вытеснены современными процессорами с частотой «3 ГГц».

Вот аналогия, которая может помочь:

Допустим, каждому из двух парней поручено заполнить большую яму гравием, и они могут работать лопатой с постоянной скоростью – 1 лопата в секунду.

Думайте о IPC как о лопате, а о тактовой частоте – как о скорости, с которой кто-то сгребает гравий.

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

Но, если вы поменяете одну лопату на большую, и оба парня продолжат лопатить с одинаковой скоростью – как вы думаете, кто закончит свою работу первым? Конечно же, тот, у кого большая лопата, финиширует первым!

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

Можно ли измерить IPC процессора?

Так как тактовая частота предлагает относительно простой способ оценить этот аспект производительности ЦП, некоторые по понятным причинам ожидают аналогичного показателя и для IPC.

К сожалению, нет никакого способа количественно оценить IPC, потому что не все инструкции равны, и эти инструкции будут сильно различаться в зависимости от рабочей нагрузки.

Даже относительно простая задача разбивается на машинный код, который может переварить ваш ЦП.

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

Тем не менее, вы можете получить приблизительную оценку относительного прироста IPC.

Установите для двух ЦП одинаковые тактовую частоту и множитель и запустите одноядерный тест, такой как однопоточный Cinebench R20. Разница в производительности, которую вы увидите здесь, будет очень близка к разнице в IPC.

The computation of instructions per cycles is a measure of the performance of an architecture, and, a basis of comparison all other things being equal.  IPC can be used to compare two designs for the same instruction set architecture, as in the question you’re asking comparing two design alternatives for a MIPS architecture.

Or, IPC can be used to compare vastly different designs (like CISC vs. RISC).  If the processor can execute one instruction per cycle, then the IPC=1. Especially processors in the 1970’s were usually were microcoded, and instructions completed in a variable number of cycles, like some in 2 cycles or some instructions in 4.  So, for these machines IPC < 1.  Some processors using VLIW or EPIC or other architectural designs might complete several instructions in one cycle.

A MIPS processor attempts to execute one instruction per cycle using its pipelined design.  However, certain conditions cause it to stall:

• waiting for a result that isn’t ready, like multiply or divide
• waiting for a cache miss to resolve

Other times, it does work, but the work must be thrown away — this is the case of the branch instruction.  More specifically, the issue of how soon the processor can get back onto the right instruction stream.

Let’s look more closely at the pipeline for the question you’re asking about:
Here the code sequence is

<x>
B trg
<a>
<b>
<c>

In the following, @trg represents the instruction at the target of the branch, and this is the proper instruction to execute immediately after the branch.

    IF       ID      EX     MEM      WB 
-1  <x>                                 
0   B trg   <x>                         
1   <a>     B trg   <x>                 
2   <b>     <a>     B trg   <x>         
3   <c>     <b>     <a>     B trg   <x> <--- if the branch executes here in the MEM stage, then <a>,<b><c> are unwanted and have to be discarded.
4   @trg    <c>     <b>     <a>     B   
5           @trg    <c>     <b>     <a> 
6                   @trg    <c>     <b> 
7                           @trg    <c> 
8                                   @trg    

The above shows the branch executing in the MEM stage.  Thus, the fetches the processor did for < a >, < b >, and < c > are invalid and have to be discarded.  Three cycles are lost or wasted.

    IF       ID      EX     MEM      WB 
-1  <x>                                 
0   B trg   <x>                         
1   <a>     B trg   <x>                 <--- if the branch executes here in the ID stage, then only <a> is lost
2   @trg    <a>     B trg   <x>         
3             @trg  <a>     B trg   <x> 
4                   @trg    <a>     B   
5                           @trg    <a> 
6                                   @trg

Since the ID stage is 2 stages earlier, this processor has a larger IPC.  We can use the IPC to ascertain exactly how much faster this design would be, and this demonstrates the value of the IPC definition.

---

(There is term in sailing and yachting called Velocity Made Good, VMG — the idea is that even though you’re going a certain speed (in sailing: knots, in computing: cycles per second aka hertz), only some of that speed goes to useful work being done (in sailing: reaching the finish line, in computing: completing instructions from the program).  VMG for a processor would be instructions / hertz.  So, compared to VMG which includes a time component, IPC factors out the time component.)

Стоимость операций в тактах ЦП

Всем доброго! Вот мы и добрались до тематики С++ на наших курсах и по нашей старой доброй традиции делимся тем, что мы нашли достаточно интересным при подготовке программы и то, что будем затрагивать во время обучения.

Инфографика:

Когда нам нужно оптимизировать код, мы должны отпрофилировать его и упростить. Однако, иногда имеет смысл просто узнать приблизительную стоимость некоторых популярных операций, чтобы не делать с самого начала неэффективных вещей (и, надеюсь, не профилировать программу позже).

Итак, вот она — инфографика, которая должна помочь оценить стоимость конкретных операций в тактах ЦП — и ответить на такие вопросы, как “эй, сколько обычно стоит операция чтения L2?”. Хотя ответы на все эти вопросы более или менее известны, я не знаю ни одного места, где все они перечислены и представлены в перспективе. Также отметим, что, хотя перечисленные стоимости, строго говоря, применяются только к современным процессорам x86/x64, ожидается, что аналогичное отношение стоимостей будут наблюдаться на других современных процессорах с большими многоуровневыми кэшами (такими как ARM Cortex A или SPARC); с другой стороны, MCU (включая ARM Cortex M) достаточно отличны, чтобы некоторые из закономерностей могли быть к ним не применимы.

И последнее, но не менее важное, предостережение: все оценки здесь лишь указывают на порядок; однако, учитывая масштаб различий между различными операциями, эти показания могут по-прежнему использоваться (по крайней мере, следует помнить, что нужно избегать «преждевременной пессимизации»).

С другой стороны, я все еще уверен, что такая диаграмма полезна, чтобы не говорить «эй, вызовы виртуальных функций ничего не стоят» — что может быть или не быть истинным в зависимости от того, как часто вы их вызываете. Вместо этого, используя инфографику выше, вы сможете увидеть, что если вы вызовете свою виртуальную функцию 100K раз в секунду на процессоре с частотой 3 ГГц — это, вероятно, не будет стоить вам более 0,2% от общего объема вашего процессора; однако, если вы вызываете одну и ту же виртуальную функцию 10M раз в секунду, это легко может означать, что виртуализация поглощает двузначные проценты ядра вашего процессора.

Другой способ приблизиться к тому же вопросу — сказать «эй, я вызываю виртуальную функцию один раз за кусок кода, который составляет 10000 тактов, поэтому виртуализация не будет потреблять более 1% от времени программы», — но вам все равно нужен какой-то способ увидеть порядок величины связанных затрат — и приведенная выше диаграмма по-прежнему будет полезна.

Теперь давайте более подробно рассмотрим пункты в нашей инфографике выше.

Операции ALU и FPU

Для наших целей, говоря об операциях ALU, мы будем рассматривать только операции типа регистр-регистр. Если задействована память, затраты могут быть ОЧЕНЬ разными — это будет зависеть от того, “насколько велик был промах кэша” при доступе к памяти, как описано ниже.

“Простые” операции

В наши дни (и на современных процессорах), «простые» операции, такие как ADD/MOV/OR/…, могут легко выполняться быстрее одного такта ЦП. Это не означает, что операция будет выполняться буквально в течение половины такта. Напротив — в то время, как все операции все еще выполняются за целое число тактов, некоторые из них могут выполняться параллельно.

В [Agner4] (который, кстати, ИМХО является лучшим справочным руководством по оценке операций процессора) эта особенность отражается в наличии двух величин характеризующих каждую операцию: одна — это задержка (которая всегда представлена целым числом тактов), а другая — производительность. Следует отметить, однако, что в реальном мире, когда выходят за рамки оценок порядка, точное время будет сильно зависеть от характера вашей программы и от порядка, в котором компилятор поставил, казалось бы, несвязанные инструкции; вкратце — если вам нужно что-то лучше, чем порядок ожидания, вам нужно профилировать свою конкретную программу, скомпилированную вашим конкретным компилятором (и в идеале — на конкретном целевом процессоре тоже).

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

Целочисленное умножение/деление

Целочисленное умножение/деление достаточно дорогое по сравнению с «простыми» операциями выше. [Agner4] оценивает стоимость 32/64-битного умножения (MUL/IMUL в мире x86/x64) в 1-7 тактов (на практике я наблюдал более узкий диапазон значений, например 3-6 тактов), и стоимость 32/64-разрядного деления (известного как DIV/IDIV на x86/64) — около 12-44 тактов.

Операции с плавающей запятой

Стоимость операций с плавающей запятой взята из [Agner4] и варьируется от 1-3 тактов ЦП для сложения (FADD/FSUB) и 2-5 тактов для умножения (FMUL) до 37-39 тактов для деления (FDIV).

Если использовать скалярные SSE-операции (которыми, по-видимому, пользуется “каждая собака” в наши дни), показатели уменьшаться до 0,5-5 тактов для умножения (MULSS/MULSD) и до 1-40 тактов для деления (DIVSS/DIVSD); на практике, однако, вы должны ожидать скорее 10-40 тактов для деления (1 такт — это «взаимная пропускная способность», что на практике редко реализуется).

128-битные векторные операции

В течении уже нескольких лет ЦП поддерживают «векторные» операции (точнее — операции множественных данных Single Instruction Multiple Data или SIMD); в мире Intel они известны как SSE и AVX и в мире ARM — как ARM Neon. Забавно, что они работают с «векторами» данных, причем данные имеют одинаковый размер (128 бит для SSE2-SSE4, 256 бит для AVX и AVX2 и 512 бит для предстоящего AVX-512), но интерпретировать их можно по-разному. Например, 128-битный регистр SSE2 может быть интерпретирован как (a) два double, (b) четыре float, © два 64-битных integer, (d) четыре 32-битных integer, (e) восемь 16-битных integer, (f) шестнадцать 8-битных integer.

[Agner4] оценивает целочисленное сложение над 128-битным вектором в < 1 такт, если вектор интерпретируется как 4 × 32-битных целых числа и в 4 такта, если это 2 × 64-битных целых числа; умножение (4 × 32 бита) оценивается в 1-5 тактов — и в последний раз, когда я проверял, не было операций целочисленного векторного деления в наборе команд x86/x64. Операций с плавающей запятой над 128-битными векторами оцениваются от 1-3 тактов ЦП для сложения и 1-7 тактов ЦП для умножения, для деления до 17-69 тактов.

Задержки перехода

Не такая очевидная вещь, связанная с затратами на вычисления, заключается в том, что переключение между целыми и плавающими инструкциями не бесплатно. [Agner3] оценивает эту стоимость (известную как «задержка перехода») в 0-3 такта в зависимости от процессора. На самом деле проблема более общая, и (в зависимости от ЦП) также могут быть штрафы за переключение между векторными (SSE) целочисленными инструкциями и обычными (скалярными) целочисленными инструкциями.

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

Ветвление

Следующее, что мы будем обсуждать, — это ветвление кода. Переход (if внутри вашей программы), по сути, является сравнением и изменением в счетчике команд. В то время как обе эти вещи просты, ветвление может быть достаточно затратным. Обсуждение, почему это так, опять получится слишком аппаратно-ориентированным (в частности, это затрагивает конвейерную обработку и спекулятивное исполнение), но с точки зрения разработчика программного обеспечения это выглядит так:

• если процессор правильно угадывает, куда будет направлено выполнение (это до фактического вычисления условия if), тогда стоимость перехода составляет около 1-2 тактов ЦП
• однако, если процессор делает неправильное предположение — это приводит к тому, что ЦП «глохнет»

Продолжительность этой задержки оценивается в 10-20 тактов процессора, для последних процессоров Intel — около 15-20 тактов [Agner3].

Отметим, что в то время как макрос GCC __builtin_expect(), как полагают, влияет на предсказание ветвления — и он работал таким образом всего 15 лет назад, он больше не актуален, по крайней мере, для процессоров Intel (начиная с Core 2 или около того).
Как описано в [Agner3], на современных Intel-процессорах предсказание перехода всегда динамично (или, по крайней мере, доминируют динамические решения); это, в свою очередь, подразумевает, что ожидаемые отклонения от кода __builtin_expect() не будут влиять на предсказание переходов (на современных процессорах Intel). Однако __builtin_expect() все еще влияет на способ генерации кода, как описано в разделе «Доступ к памяти» ниже.

Доступ к памяти

В 80-е годы скорость процессора была сопоставима с задержкой памяти (например, процессор Z80, работающий на частоте 4 МГц, тратил 4 такта на команду типа регистр-регистр и 6 тактов на команду типа регистр-память). В то время можно было вычислить скорость программы, просто посмотрев на сборку.

С тех пор скорости процессоров выросли на 3 порядка, а задержки памяти улучшились только в 10-30 раз или около того. Чтобы справиться с оставшимся более чем тридцати кратным несоответствием, были введены все эти виды кэшей. Современный процессор обычно имеет 3 уровня кэшей. В результате скорость доступа к памяти очень сильно зависит от ответа на вопрос «где хранятся данные, которые мы пытаемся прочитать?». Чем ниже уровень кэша, где был найден ваш запрос, тем быстрее вы можете его получить.

Время доступа к кэшу L1 и L2 можно найти в официальных документациях, таких как [Intel.Skylake]; он оценивает время доступа к L1 / L2 / L3 в 4/12/44 такта процессора соответственно (обратите внимание: эти цифры немного варьируются от одной модели процессора к другой). Вообще, как упоминается в [Levinthal], время доступа к L3 может достигать 75 тактов, если кэш совместно используется с другим ядром.

Однако, что сложнее найти, так это информацию о времени доступа к основной ОЗУ. [Levinthal] оценивает его в 60нс (~ 180 тактов, если процессор работает на частоте 3ГГц).

Совет по оптимизации: улучшайте локальность данных. Подробнее об этом см., например, [NoBugs].

Помимо чтения из памяти, есть также запись. В то время как запись интуитивно воспринимается как более дорогая, чем чтение, чаще всего это не так; причина для этого проста: процессору не нужно ждать завершения записи перед тем, как идти вперед (вместо этого он только начинает писать — и сразу переходит к другим делам). Это означает, что большую часть времени процессор может выполнять запись в 1 такт; это согласуется с моим опытом и, по-видимому, достаточно хорошо коррелирует с [Agner4]. С другой стороны, если ваша система завязана на пропускной способности памяти, цифры могут получиться ЧРЕЗВЫЧАЙНО высокие; все же, из того, что я видел, перегрузка шины операциями записи является очень редким явлением, поэтому я не отразил его на диаграмме.

Еще помимо данных, есть и код.

Еще один совет по оптимизации: постарайтесь улучшить также и локальность кода. Это менее очевидно (и, как правило, оказывает меньшее влияние на производительность, чем плохая локализация данных). Обсуждение способов улучшения локальности кода можно найти в [Drepper]; эти способы включают такие вещи, как inlining, и __builtin_expect().

Следует отметить, что хотя __builtin_expect(), как упоминалось выше, больше не влияет на предсказание переходов на процессорах Intel, она все равно влияет на разметку кода, что, в свою очередь, влияет на пространственную локальность кода. В результате __builtin_expect() не имеет эффектов, которые слишком выражены на современных процессорах Intel (на ARM — понятия не имею, если быть честным), но все равно может повлиять на производительность в той или иной степени. Также сообщалось, что под MSVC замена if и else переходов условного оператора имеет эффекты, сходные с __builtin_expect() (если предполагаемый переход является if-переходом условного оператора с двумя переходами), но к этому следует относится с сомнением.

NUMA (Архитектура с неравномерной памятью)

Еще одна вещь, связанная с доступом к памяти и производительностью, редко наблюдается на настольных компьютерах (так как для этого требуются многопроцессорные машины — не следует путать с многоядерными). Таким образом, это, в основном, серверная парафия; однако это существенно влияет на время доступа к памяти.

Когда задействованы несколько сокетов, современные процессоры имеют тенденцию реализовывать так называемую архитектуру NUMA, причем каждый процессор (где «процессор» = «эта штука, вставленная в сокет») имеет свою собственную ОЗУ (в отличие от архитектуры FSB более раннего возраста с общей FSB aka Front-Side Bus и общая оперативная память). Несмотря на то, что каждый процессор имеет собственную ОЗУ, ЦП совместно используют адресное пространство ОЗУ — и всякий раз, когда требуется доступ к ОЗУ, физически находящемуся в другом, это делается путем отправки запроса на другой сокет через сверхбыстрый протокол, такой как QPI или Hypertransport.

Удивительно, но это не так долго, как вы могли бы ожидать — [Levinthal] дает 100-300 тактов ЦП, если данные были в кэше L3 удаленного процессора и 100нс (~ = 300 тактов), если данные были не там, и удаленный процессор должен был перейти в свою основную ОЗУ для этих данных.

CAS (сравнение с обменом)

Иногда (в частности, в неблокирующих алгоритмах и при реализации мьютексов) мы хотим использовать так называемые атомарные операции. Академически обычно рассматривается только одна атомарная операция, известная как CAS (Compare-And-Swap — сравнение с обменом) (на том основании, что все остальное может быть реализовано через CAS); в реальном мире их обычно больше (см., например, std::atomic в C++ 11, Interlocked*() в Windows или __sync _*_ и _*() в GCC/Linux). Эти операции — довольно странные звери: в частности, им нужна специальная поддержка ЦП для правильной работы. В x86 / x64 соответствующие инструкции ASM характеризуются наличием префикса LOCK, поэтому CAS на x86 / x64 обычно записывается как LOCK CMPXCHG.

С нашей нынешней точки зрения важно то, что эти операции, подобные CAS, будут выполняться значительно дольше обычного доступа к памяти (чтобы гарантировать атомарность, процессор должен синхронизировать процессы, по крайней мере, между разными ядрами, или в случае мультисокетных конфигураций, также между различными сокетами).

[AlBahra] оценивает стоимость операций CAS примерно в 15-30 тактов (с небольшой разницей между семействами x86 и IBM Power). Стоит отметить, что это число обоснованно только при выполнении двух допущений: (а) мы работаем с одноядерной конфигурацией и (б), что сравниваемая память уже находится в L1.

Касательно затрат CAS в мультисокетных NUMA-конфигурациях, я не смог найти данные о CAS, поэтому мне пока не обойтись без спекуляций. С одной стороны, ИМХО будет почти невозможным иметь задержки работы CAS на «удаленной» памяти меньше, чем кругооборот HyperTransport между сокетами, что в свою очередь сопоставимо со стоимостью чтения NUMA кэша L3.

С другой стороны, я действительно не вижу причин, чтобы превысить эти показатели :-). В результате я оцениваю стоимость NUMA раздельных CAS (и CAS-подобных) операций в 100-300 тактов ЦП.

TLB (Буфер ассоциативной трансляции)

Всякий раз, когда мы работаем с современными процессорами и современными ОС, на уровне приложений мы обычно имеем дело с «виртуальным» адресным пространством; другими словами, если мы запускаем 10 процессов, каждый из этих процессов может (и, вероятно, будет) иметь свой собственный адрес 0x00000000. Для поддержки такой изоляции процессоры реализуют так называемую «виртуальную память». В мире x86 она была впервые реализована через «защищенный режим», введенный еще в 1982 году на 80286.

Обычно «виртуальная память» работает постранично (для x86 каждая страница имеет размер либо 4K, либо 2M или, по крайней мере, теоретически, даже 1G (!)), когда ЦП знает какой процесс выполняется (!), и переразмечает виртуальные адреса на физические адреса при каждом доступе к памяти. Обратите внимание, что эта повторная разметка происходит полностью за кулисами, в том смысле, что все регистры процессора (кроме тех, которые имеют дело с разметкой) содержат все указатели в формате «виртуальной памяти».

И раз уж мы заговорили о «разметке» — ну, информация об этой разметке должна быть где-то сохранена. Более того, поскольку эта разметка (из виртуальных адресов в физические) происходит при каждом доступе к памяти, это должно быть Чертовски Быстро. Для этого обычно используется специальный вид кэша, называемый Буфер ассоциативной трансляции (TLB).
Так же как и для любого типа кэша, существует стоимость промаха TLB; для x64 она колеблется между 7-21 тактами ЦП [7cpu]. В целом, на TLB довольно сложно повлиять; однако здесь еще можно дать несколько рекомендаций:

• еще раз — улучшение общей локальности памяти помогает уменьшить промахи TLB; чем локальнее ваши данные, тем меньше шансов выйти из TLB.
• рассмотрите возможность использования «больших страниц» (те 2 MБ страницы на x64). Чем больше страницы, тем меньше записей в TLB вам понадобится; с другой стороны, использовать «больший страницы» нужно с осторожностью, это палка о двух концах. Это означает, что вам нужно протестировать его для своего конкретного приложения.
• рассмотрите возможность отключения ASLR (=«рандомизация размещения адресного пространства»). Как обсуждалось в [Drepper], в то время как включение ASLR хорошо для безопасности, оно убивает производительность, и в том числе именно из-за промахов TLB .

Примитивы программного обеспечения

Теперь мы закончили с теми вещами, которые напрямую связаны с “железом”, и будем говорить о некоторых вещах, связанных с программным обеспечением; они действительно все еще повсюду встречаются, поэтому давайте посмотрим, сколько мы тратим каждый раз, когда используем их.

Вызовы функций в С/С++

Сначала давайте рассмотрим стоимость вызова функций в C/C++. На самом деле, то, что вызывает функции в C/C++ делает чертовски много дел перед вызовом, и вызываемое тоже не сидит сложа руки.

[Efficient C++] оценивает затраты ЦП для вызова функции в 25-250 тактов в зависимости от количества параметров; однако, это довольно старая книга, а у меня нет лучшей ссылки того же калибра. С другой стороны, по моему опыту, для функции с достаточно небольшим числом параметров это скорее будет 15-30 тактов; это также, по-видимому, относится к процессорам, отличным от Intel, как выяснил [eruskin].

Совет по оптимизации: используйте inline-функции, где это применимо. Однако имейте в виду, что в наши дни компиляторы чаще всего игнорируют встраиваемые спецификации. Поэтому для действительно критически важных фрагментов кода вы можете использовать __attribute __ ((always_inline)) для GCC и __forceinline для MSVC, чтобы заставить их делать то, что вам нужно. Тем не менее, НЕ используйте эти принудительные inline для не очень критических фрагментов кода, это может сделать намного хуже.

Кстати, во многих случаях выигрыш от встраивания может превышать стоимость простого удаления вызова. Это происходит из-за того, что встраивание обеспечивает довольно много дополнительных оптимизаций (в том числе связанных с переупорядочением для обеспечения правильного использования аппаратного конвейера). Также давайте не будем забывать, что встраивание улучшает пространственную локальность для кода, что также немного помогает (см., например, [Drepper]).

Косвенные и виртуальные вызовы

Дискуссия выше была связана с обычными («прямыми») вызовами функций. Стоимость косвенных и виртуальных вызовов, как известно, выше, и многие согласны с тем, что косвенный вызов вызывает ветвление (однако, как отмечает [Agner1], до тех пор, пока вы вызываете одну и ту же функцию из одной и той же точки кода, механизмы предсказания переходов современных процессоров могут предсказать это довольно хорошо, в противном случае, вы получите штраф за ложное предсказание в 10-30 тактов). Что касается виртуальных вызовов — это одно дополнительное чтение (чтение указателя VMT), поэтому, если в этот момент все кэшируется (как обычно и есть), мы говорим о дополнительных 4 тактах процессора или около того.

С другой стороны, практические измерения [eruskin] показывают, что стоимость виртуальных функций примерно вдвое меньше стоимости прямых вызовов для небольших функций; в пределах нашей погрешности (которая является «порядком») это вполне согласуется с вышеприведенным анализом.

Совет по оптимизации: если ваши виртуальные вызовы стоят дорого, вместо этого в C++ вы можете подумать об использовании шаблонов (реализация так называемого полиморфизма времени компиляции); CRTP — это один (хотя и не единственный) способ сделать это.

Аллокации

В наши дни аллокаторы как таковые могут быть довольно быстрыми; в частности, аллокаторы tcmalloc и ptmalloc2 могут потратить всего 200-500 тактов ЦП для выделения/освобождения небольшого объекта [TCMalloc].

Тем не менее, есть существенное предостережение, связанное с аллокацией, и добавление к косвенным затратам на использование аллокаций: аллокация, как старое доброе правило большого пальца, означает уменьшение локальности памяти, что, в свою очередь, отрицательно влияет на производительность (из-за взаимодействий с незакэшированной памятью, описанных выше). Чтобы проиллюстрировать, насколько это плохо на практике, мы можем взглянуть на 20-строчную программу в [NoBugs]; эта программа при использовании vector<> выполняется от 100 до 780 раз быстрее (в зависимости от компилятора и конкретного поля), чем эквивалентная программа, использующая list<> — все из-за плохой локальности памяти последнего :-(.

Совет по оптимизации: думайте о сокращении количества аллокаций в ваших программах, особенно если есть этап, когда большая часть работы выполняется с данными только для чтения. В некоторых реальных случаях сглаживание ваших структур данных (т.е. замена выделенных объектов упакованными) может ускорить вашу программу до 5 раз.

Реальная история по теме. Когда-то давным-давно была программа, в которой использовались гигабайты оперативной памяти, что считалось слишком большим; окей, я переписал ее в «сплющенную» версию (то есть каждый узел был сначала сконструирован динамически, а затем в памяти был создан эквивалентный «сплющенный» объект только для чтения); идея «сглаживания» заключалась в уменьшении объема памяти. Когда мы запускали программу, мы заметили, что не только объем памяти уменьшился в 2 раза (что и было тем, что мы ожидали), но также, как очень хороший побочный эффект, скорость выполнения увеличилась в 5 раз.

Вызовы ядра ОС

Если наша программа работает под операционной системой (да, есть еще программы, которые работают без нее), то у нас есть целая группа системных API. На практике (по крайней мере, если мы говорим о более или менее обычной ОС) многие из этих системных вызовов приводят к вызовам ядра, которые включают в себя переключения в режим ядра и обратно; это включает в себя переключение между различными «кольцами защиты» (на процессоре Intel обычно между «кольцом 3» и «кольцом 0»). В то время как переключение между уровнями процессора занимает всего около 100 тактов, другие связанные с этим накладные расходы, как правило, делают вызовы ядра намного более дорогими, поэтому обычный вызов ядра занимает не менее 1000-1500 тактов процессора [Wikipedia.ProtectionRing].

Исключения C++

В наши дни про исключения C++ говорят, что они ничего не стоят до тех пор, пока не сработают. Действительно ли ничего — все еще не на 100% ясно (ИМО даже не ясно, может ли вообще задаваться такой вопрос), но он, безусловно, очень близок.

Тем не менее, эти «беззатратные пока не сработавшие» реализации стоят за огромной кучей работы, которая должна выполняться всякий раз, когда возникает исключение. Все согласны с тем, что стоимость брошенного исключения огромна, однако (как обычно) экспериментальных данных мало. Тем не менее, эксперимент [Ongaro] дает нам примерное количество около 5000 тактов процессора (чума!). Более того, в более сложных случаях я бы ожидал, что это число будет еще больше.

Возврат ошибки и проверка

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

В принципе, стоимость возврата-и-проверки состоит из трех отдельных стоимостей. Первая из них — это стоимость самого условного перехода, и мы можем с уверенностью предположить, что в 99+% случаев он будет предсказан правильно; это означает, что стоимость условного перехода в этом случае составляет около 1-2 тактов. Вторая стоимость — это затраты на копирование кода ошибки, и до тех пор, пока он остается в пределах регистров, это простое MOV, которое при данных обстоятельствах составляет от 0 до 1 такта (0 тактов означает, что MOV не имеет дополнительную стоимость, поскольку она выполняется параллельно с некоторыми другими операциями). Третья стоимость гораздо менее очевидна — это стоимость дополнительного регистра, необходимого для переноса кода ошибки; если мы вышли из регистров — нам понадобится пара PUSH/POP (или разумная факсимиле), которая, в свою очередь запись + чтение L1 или 1 + 4 такта. С другой стороны, давайте иметь в виду, что шансы PUSH/POP быть необходимыми, варьируются от одной платформы к другой; например, на x86 любая реалистическая функция потребует их почти наверняка; однако на x64 (у которого есть двойное число регистров) вероятность того, что PUSH/POP будут необходимы, значительно снизится (и в довольно многих случаях, даже если регистр не является полностью свободным, компилятор сделать его доступным дешевле, чем тривиальный PUSH/POP).

Объединив все три стоимости, я бы оценил затраты на возврат-кода-ошибки-и-проверку (в нормальном случае) в пределах от 1 до 7 тактов ЦП. Это, в свою очередь, означает, что если у нас есть одно исключение на 10000 вызовов функций, нам, вероятно, будет лучше с исключениями; однако, если у нас есть одно исключение на 100 вызовов функций, нам, вероятно, будем лучше с кодами ошибок. Другими словами, мы только что подтвердили очень хорошо известную передовую практику — «используйте исключения только для ненормальных ситуаций».

Переключения контекста потока

Последнее, но, конечно, не менее важное, нам нужно поговорить о стоимости переключения контекста потока. Одна из проблем с их оценкой заключается в том, что их очень сложно понять. Общая мудрость говорит, что они «чертовски дороги» (эй, должна же быть причина, почему nginx превосходит Apache), но насколько это «чертовски дорого»?

Из моих личных наблюдений цена составляла не менее 10000 тактов ЦП; однако есть много источников, которые дают НАМНОГО более низкие цифры. Фактически, однако, речь идет о том, «что именно мы пытаемся измерить». Как отмечено в [LiEtAl], существуют две разные стоимости по отношению к переключениям контекста.

• Первая стоимость — прямые затраты на переключение контекста потока, и они измеряются примерно в 2000 тактов ЦП (3 то есть, если моя математика правильна при преобразовании из микросекунд в такты)
• Однако вторая стоимость намного выше; это связано с аннулированием кэша потоком; согласно [LiEtAl], он может быть примерно 3M тактов ЦП. Теоретически, с полностью случайным шаблоном доступа, современный процессор с 12M кэша L3 (и с учетом штрафа порядка 50 тактов за доступ) может вызвать задержку в 10M тактов за контекстный переключатель; однако на практике штрафы обычно несколько ниже, поэтому число 1M от [LiEtAl] имеет смысл. Эта «намного более высокая» оценка также согласуется с количеством спинлоков на x64 (по умолчанию это 4000, по крайней мере для Windows/x64): если обычно полезно ждать 4000 итераций (в сумме, по крайней мере, до 15-20 тыс. тактов ЦП и больше, чем 40-50K тактов, из моего опыта), считывая эту переменную-которая-в-настоящее-время-заблокирована в замкнутом цикле — просто в надежде, что переменная откроется до того, как закончится 4000 итераций, все эти проблемы и такты ЦП просто для того, чтобы избежать переключения контекста — это означает, что стоимость переключения контекста обычно намного выше, чем те десятки-тысяч-процессорных-тактов-которые-мы-готовы-потратить-на-замкнутый-цикл-не-делающий-ничего-полезного.

Подытожим

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

Также учтите, что, хотя я честно пытался собрать все связанные цены в одном месте (проверяя сторонние выводы на моем собственном опыте в процессе), это всего лишь первая попытка, поэтому, если вы найдете достаточно убедительные доказательство того, что что-то неправильно — сообщите мне, я буду рад сделать диаграмму более точной.

THE END

Как всегда ждём тапков, вопросов в комментариях или на Дне открытых дверей