Интерпретация абсурдно-низкой измеренной латентности в тщательном профиле (эффекты суперскалярности?)

Я написал некоторый код для профилирования небольших функций. На высоком уровне это:

  1. Устанавливает привязку потока только к одному ядру и приоритет потока к максимуму.

  2. Вычисляет статистику от выполнения следующих 100 раз:

    1. Оцените задержку функции, которая ничего не делает.
    2. Оцените задержку тестовой функции.
    3. Вычтите первое из второго, чтобы исключить затраты на выполнение служебных вызовов, тем самым приблизительно получая стоимость содержимого тестовой функции.

Чтобы оценить задержку функции, это:

  1. Делает недействительными кэши (на самом деле это трудно сделать в пользовательском режиме, но я выделяю и записываю в память буфер размером L3, что, возможно, должно помочь).
  2. Возвращает поток, так что цикл профиля имеет как можно меньше переключателей контекста.
  3. Получает текущее время из std::chrono::high_resolution_clock (который, кажется, компилируется в system_clock, но).
  4. Запускает цикл профиля 100000000 раз, вызывая проверенную функцию внутри.
  5. Получает текущее время из std::chrono::high_resolution_clock и вычитает, чтобы получить время ожидания.

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

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

Я ищу объяснение, объясняющее это поведение. Почему мои профилированные функции занимают так мало времени?

Давайте возьмем пример вычисления квадратного корня для float,

Подпись функции float(*)(float) и пустая функция тривиальна:

empty_function(float):
    ret

Давайте вычислим квадратный корень с помощью sqrtss инструкция, и путем умножения путем взаимного взлома квадратного корня. Т.е. проверенными функциями являются:

sqrt_sseinstr(float):
    sqrtss  xmm0, xmm0
    ret
sqrt_rcpsseinstr(float):
    movaps  xmm1, xmm0
    rsqrtss xmm1, xmm0
    mulss   xmm0, xmm1
    ret

Вот петля профиля. Опять же, этот же код вызывается с пустой функцией и с тестовыми функциями:

double profile(float):
    ...

    mov    rbp,rdi

    push   rbx
    mov    ebx, 0x5f5e100

    call   1c20 <invalidate_caches()>
    call   1110 <sched_yield()>

    call   1050 <std::chrono::high_resolution_clock::now()>

    mov    r12, rax
    xchg   ax,  ax

    15b0:
    movss  xmm0,DWORD PTR [rip+0xba4]
    call   rbp
    sub    rbx, 0x1
    jne    15b0 <double profile(float)+0x20>

    call   1050 <std::chrono::high_resolution_clock::now()>

    ...

Сроки результат для sqrt_sseinstr(float) на моем Intel 990X это 3,60±0,13 наносекунды. При этом процессоре с рейтингом 3,46 ГГц это составляет 12,45±0,44 такта. Это кажется довольно точным, учитывая, что документы говорят латентность sqrtss составляет около 13 циклов (он не указан для архитектуры Nehalem этого процессора, но, вероятно, также около 13 циклов).

временные результаты для sqrt_rcpsseinstr(float) незнакомец: 0,01±0,07 наносекунды (или 0,02±0,24 цикла). Это совершенно неправдоподобно, если только не произойдет другой эффект.

Я подумал, что процессор может скрывать задержку тестируемой функции в некоторой степени или идеально, потому что тестируемая функция использует разные порты команд (то есть суперскалярность что-то скрывает)? Я попытался проанализировать это вручную, но не очень далеко, потому что я действительно не знал, что я делал.

(Примечание: для вашего удобства я убрал некоторые обозначения сборок. objdump всей программы, которая включает в себя несколько других вариантов, здесь, и я временно размещаю бинарный файл здесь (x86-64 SSE2+, Linux).)

Снова вопрос: почему некоторые профилированные функции создают невероятно малые значения? Если это эффект высшего порядка, объясните?

Источник

2 ответа

Проблема заключается в базовом подходе вычитания "задержки"1 пустой функции, как описано:

  1. Оцените задержку функции, которая ничего не делает.
  2. Оцените задержку тестовой функции.
  3. Вычтите первое из второго, чтобы исключить затраты на выполнение служебных вызовов, тем самым приблизительно получая стоимость содержимого тестовой функции.

Встроенное допущение состоит в том, что стоимость вызова функции равна X, и если задержка работы, выполняемой в функции, равна Y, то общая стоимость будет примерно равна X + Y,

Это обычно не верно для любых двух блоков работы и особенно не верно, когда один из них "вызывает функцию". Более сложный взгляд был бы на то, что общее время будет где-то между min(X, Y) а также X + Y - но даже это часто неправильно в зависимости от деталей. Тем не менее, достаточно уточнения, чтобы объяснить, что здесь происходит: стоимость функции не складывается с работой, выполняемой в функции: они происходят параллельно.

Стоимость пустого вызова функции в современном Intel составляет от 4 до 5 циклов, вероятно, в узких местах по пропускной способности внешнего интерфейса для двух взятых ветвей и, возможно, из- за задержки предсказания ветвления и возврата.

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

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

Ваша первая функция занимает достаточно времени, чтобы реальная работа доминировала над временем выполнения. Вторая функция, однако, намного быстрее, что позволяет ей "прятаться" под существующим временем, затрачиваемым механиками call / ret.

Решение простое: продублируйте работу внутри функции N раз, чтобы работа всегда доминировала. N=10 или N=50 или что-то в этом роде. Вы должны решить, хотите ли вы проверить задержку, и в этом случае выходные данные одной копии работы должны поступать в следующую, или пропускную способность, в этом случае это не должно быть.

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

1 Я помещаю здесь слово "латентность" в кавычки, потому что не ясно, следует ли нам говорить о латентности call/ret или пропускная способность. call а также ret не имеют явных выходов (и ret не имеет входных данных), поэтому он не участвует в классической цепочке зависимостей на основе регистров - но может иметь смысл подумать о задержке, если вы рассмотрите другие скрытые архитектурные компоненты, такие как указатель инструкции. В любом случае задержка пропускной способности в основном указывает на одно и то же, потому что все call а также ret в потоке работают в том же состоянии, поэтому не имеет смысла говорить "независимые" и "зависимые" цепочки вызовов.

Источник

Ваш подход к сравнительному анализу в корне неверен, а ваш "осторожный код" - обман.

Во-первых, очистка кеша - фальшивка. Мало того, что он будет быстро заполнен необходимыми данными, но и размещенные вами примеры имеют очень мало взаимодействия с памятью (только доступ к кешу call/ret и груз, к которому мы доберемся.

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

Теперь, когда бесполезная непредвиденная сложность исчезла из-за фундаментального недопонимания современных процессоров:

Вы ожидаете loop_time_gross/loop_count быть временем, проведенным в каждой итерации цикла. Это не верно. Современные процессоры не выполняют инструкции один за другим, последовательно. Современные процессоры выполняют конвейеризацию, предсказывают переходы, выполняют несколько команд параллельно и (достаточно быстрые процессоры) выходят из строя.

Таким образом, после первых нескольких итераций цикла бенчмаркинга все ветви отлично прогнозируются для следующих почти 100000000 итераций. Это позволяет процессору строить догадки. Фактически, условная ветвь в цикле сравнительного анализа исчезает, как и большая часть стоимости косвенного вызова. По сути, процессор может развернуть цикл:

movss  xmm0, number
movaps  xmm1, xmm0
rsqrtss xmm1, xmm0
mulss   xmm0, xmm1
movss  xmm0, number
movaps  xmm1, xmm0
rsqrtss xmm1, xmm0
mulss   xmm0, xmm1
movss  xmm0, number
movaps  xmm1, xmm0
rsqrtss xmm1, xmm0
mulss   xmm0, xmm1
...

или, для другого цикла

movss  xmm0, number
sqrtss  xmm0, xmm0
movss  xmm0, number
sqrtss  xmm0, xmm0
movss  xmm0, number
sqrtss  xmm0, xmm0
...

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

Чтобы быть справедливым,

call   rbp
sub    rbx, 0x1
jne    15b0 <double profile(float)+0x20>

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

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

Небольшой взгляд на https://agner.org/optimize/instruction_tables.pdf показывает, почему это параллельное выполнение не работает для sqrtss на Нехалеме:

instruction: SQRTSS/PS
latency: 7-18
reciprocal throughput: 7-18

инструкция не может быть передана по конвейеру и выполняется только на одном порту выполнения. В отличие от movaps, rsqrtss, mulss:

instruction: MOVAPS/D
latency: 1
reciprocal throughput: 1

instruction: RSQRTSS
latency: 3
reciprocal throughput: 2

instruction: MULSS
latency: 4
reciprocal throughput: 1

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

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

float x = INITIAL_VALUE;
for (i = 0; i < 100000000; i++)
    x = benchmarked_function(x);

Очевидно, вы не будете сравнивать один и тот же вход таким образом, если только INITIAL_VALUE является фиксированной точкой benchmarked_function(), Однако вы можете сделать так, чтобы она была фиксированной точкой расширенной функции, вычисляя float diff = INITIAL_VALUE - benchmarked_function(INITIAL_VALUE); а затем сделать петлю

float x = INITIAL_VALUE;
for (i = 0; i < 100000000; i++)
    x = diff + benchmarked_function(x);

с относительно небольшими издержками, хотя вы должны убедиться, что ошибки с плавающей точкой не накапливаются, чтобы значительно изменить значение, передаваемое benchmarked_function(),

Источник
Другие вопросы по тегам