Количество инструкций с плавающей запятой на такт

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

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

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

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

Итак, вот она — инфографика, которая должна помочь оценить стоимость конкретных операций в тактах ЦП — и ответить на такие вопросы, как “эй, сколько обычно стоит операция чтения 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

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

Nehalem is capable of executing 4 DP or 8 SP FLOP/cycle. This is accomplished using SSE, which operates on packed floating point values, 2/register in DP and 4/register in SP. In order to achieve 4 DP FLOP/cycle or 8 SP FLOP/cycle the core has to execute 2 SSE instructions per cycle. This is accomplished by executing a MULDP and an ADDDP (or a MULSP and an ADDSP) per cycle. The reason this is possible is because Nehalem has separate execution units for SSE multiply and SSE add, and these units are pipelined so that the throughput is one multiply and one add per cycle. Multiplies are in the multiplier pipeline for 4 cycles in SP and 5 cycles in DP. Adds are in the pipeline for 3 cycles independent of SP/DP. The number of cycles in the pipeline is known as the latency. To compute peak FLOP/cycle all you need to know is the throughput. So with a throughput of 1 SSE vector instruction/cycle for both the multiplier and the adder (2 execution units) you have 2 x 2 = 4 FLOP/cycle in DP and 2 x 4 = 8 FLOP/cycle in SP. To actually sustain this peak throughput you need to consider latency (so you have at least as many independent operations in the pipeline as the depth of the pipeline) and you need to consider being able to feed the data fast enough. Nehalem has an integrated memory controller capable of very high bandwidth from memory which it can achieve if the data prefetcher correctly anticipates the access pattern of the data (sequentially loading from memory is a trivial pattern that it can anticipate). Typically there isn’t enough memory bandwidth to sustain feeding all cores with data at peak FLOP/cycle, so some amount of reuse of the data from the cache is necessary in order to sustain peak FLOP/cycle.

Details on where you can find information on the number of independent execution units and their throughput and latency in cycles follows.

See page 105 8.9 Execution units of this document

http://www.agner.org/optimize/microarchitecture.pdf

It says that for Nehalem

The floating point multiplier on port 0 has a latency of 4 for single precision and 5 for double and long double precision. The throughput of the floating point multiplier is 1 operation per clock cycle, except for long double precision on Core2. The floating point adder is connected to port 1. It has a latency of 3 and is fully pipelined.

In order to get 8 SP FLOP/cycle you need 4 SP ADD/cycle and 4 SP MUL/cycle. The adder and the multiplier are on separate execution units, and dispatch out of separate ports, each can execute on 4 SP packed operands simultaneously using SSE packed (vector) instructions (4x32bit = 128bits). Both have throughput of 1 operation per clock cycle. In order to get that throughput, you need to consider the latency… how many cycles after the instruction issues before you can use the result.. so you have to issue several independent instructions to cover the latency. The multiplier in single precision has a latency of 4 and the adder of 3.

You can find these same throughput and latency numbers for Nehalem in the Intel Optimization guide, table C-15a

http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-optimization-manual.html

Автор	Сообщение
	Добавлено: 01.12.2009 21:43  [профиль]
Member Статус: Не в сети Регистрация: 20.09.2005 Фото: 0	Подскажите, где можно раздобыть информацию о количестве операций за такт всех выпускаемых сегодня компаниями Intel и AMD ЦП? В частности интересуют: * Число операций с плавающей запятой (floating point operations) за такт, * Число целочисленных операций (integer operations (?)) за такт, * Общее число операций за такт (включая различные адресные команды и прочее), * Число декодеров операций x86/x64 (или хотя бы первый пункт, остальные не обязательно). Смог найти только для AMD Atlon XP (3-3-3-9-3). И то, нашёл на каком-то фанатском сайте. Знаю, что у Core 2 Duo 4 FLO за такт, а у Athlon 64 — 3. Но всё остальное не могу никак найти. Подскажите! Может кто-нибудь составлял таблички такие или они где-то выложены? На предложение погуглить не реагирую, уже много гуглил, не получается найти… поэтому и прошу у вас помощи, друзья-оверы ! Буду рад вашему отклику! _________________ This account is deleted. Последний раз редактировалось I.N. 03.12.2009 16:54, всего редактировалось 4 раз(а). Перенёс во Флейм

Реклама
Партнер

maco
Member Статус: Не в сети Регистрация: 04.10.2004	У Фога поглядите, по IPC у него были данные, по декодерам — не знаю.

McArcher

Member Статус: Не в сети Регистрация: 20.09.2005 Фото: 0

maco писал(а): У Фога поглядите, по IPC у него были данные, по декодерам — не знаю. там про ЦП 2 файлика, в них такое море инфы, но самого интересного для меня, выведенного в табличку не могу найти… плюс нету K10.5… там всё разжёвано под микроскопом дял разработчика низкоуровневого софта, но нет общих чисел для «ламмеров»))) как из этих цифр задержек понять сколько, что и как? я окончательно запутался… _________________ This account is deleted.

maco

Member Статус: Не в сети Регистрация: 04.10.2004

Цитата: Instruction tables: Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs Contains detailed lists of instruction latencies, execution unit throughputs, micro-operation breakdown and other details for all application instructions of most microprocessors from Intel, AMD and VIA. Intended as an appendix to the preceding manuals. File name: instruction_tables.pdf, size: 1280593, last modified: 2009-Sep-26. Там этих таблиц как на табличной фабрике . А для ламеров никто не запрещает почитать разнокалиберные рекламные материалы на оф. сайтах производителей и соответствующие статьи (на тему анонса/выхода нового семейства процессоров) на сайтах, занимающихся обзорами процессоров.

McArcher

Member Статус: Не в сети Регистрация: 20.09.2005 Фото: 0

Цитата: А для ламеров никто не запрещает почитать разнокалиберные рекламные материалы на оф. сайтах производителей и соответствующие статьи (на тему анонса/выхода нового семейства процессоров) на сайтах, занимающихся обзорами процессоров. Не могу найти. Обычно такие вещи очень редко пишут =( Добавлено спустя 6 минут 27 секунд: Можете помочь, проверьте и подскажите количество операций с плавающей точкой для следующих процессоров/семейств процессоров (на ядро) (включая некоторые древние камни): ————————— Core 2 Duo — 4 (?) Core 2 Quad — 4 (?) Celeron E3xxx/Е1xxx — Pentium 4 — 2 (?) Celeron 4xx — Core i5 — 4 (?) Core i7 — 4 (?) Pentium E5xxx/E6xxx — ————————— Athlon XP — 3 Athlon 64 — 3 (?) Athlon II X2/X3/X4 — 4 (?) Athlon LE-1640 — Athlon 64 X2 — 3 (?) Phenom X3/X4 — Phenom II X2/X3/X4 — 4 (?) Sempron 140 — Sempron LE-1250 — ————————— (буду обновлять, что узнаю/уточню) _________________ This account is deleted.

maco
Member Статус: Не в сети Регистрация: 04.10.2004	McArcher писал(а): проверьте и подскажите количество операций с плавающей точкой для следующих процессоров/семейств процессоров (на ядро) Подсказываю — количество операций с плавающей точкой слегка превышает названные вами цифры , а сами операции могут быть достаточно различными . Не путайте IPC и количество операций . Кстати, вот тут, например, можно поглядеть одним глазом для общего развития.

Walkie
Member Статус: Не в сети Регистрация: 06.06.2008 Откуда: Таганрог Фото: 18	Как раньше было хорошо : за сколько тактов выполняется операция. А теперь дожили : кол-во операций/такт. Ужас.

McArcher
Member Статус: Не в сети Регистрация: 20.09.2005 Фото: 0	Walkie писал(а): Как раньше было хорошо : за сколько тактов выполняется операция. А теперь дожили : кол-во операций/такт. Ужас. _________________ This account is deleted.

—

Лаборатория

Заинтересовал меня вопрос — а сколько инструкций за такт выполняют современные 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. Тоесть инструкций, в которых три разных регистра используются. Мне это тоже кажется логичным развитием событий.