Почему инструкция цикла медленная? Разве Intel не смогла реализовать это эффективно?

LOOP ( Intel ref вручную) уменьшает ecx / rcx, а затем переходит, если не равен нулю. Это медленно, но разве Intel не смогла сделать это дешево? dec/jnz уже макро- слияния в единый моп на семью Sandybridge; единственная разница в том, что это устанавливает флаги.

loop по различным микроархитектурам из таблиц инструкций Agner Fog:

  • K8 / K10: 7 мс

  • Бульдозерная семья / Рызен: 1 мегапиксель (такая же стоимость, как у макрос сплавленного теста и ответвления, или jecxz)

  • P4: 4 моп (так же, как jecxz)

  • P6 (PII / PIII): 8 моп
  • Pentium M, Core2: 11 моп
  • Нехалем: 6 моп. (11 для loope / loopne). Пропускная способность = 4с (loop) или 7с (loope/ne).
  • Семья SnB: 7 моп. (11 для loope / loopne). Пропускная способность = один на 5 циклов, столько же узкого места, сколько хранение счетчика циклов в памяти! jecxz только 2 мопа с той же пропускной способностью, что и обычная jcc
  • Сильвермонт: 7 моп
  • AMD Jaguar (маломощный): 8 моп, пропускная способность 5 с
  • Через Nano3000: 2 мопа

Не могли бы декодеры просто декодировать так же, как lea rcx, [rcx-1] / jrcxz? Это было бы 3 мопс. По крайней мере, так было бы без префикса размера адреса, в противном случае он должен использовать ecx и обрезать RIP в EIP если прыжок сделан; может быть, странный выбор размера адреса, управляющего шириной декремента, объясняет множество мопов?

Или лучше, просто декодировать его как слитый dec-and-branch, который не устанавливает флаги? dec ecx / jnz на SnB декодирует до одного UOP (который устанавливает флаги).

Я знаю, что настоящий код не использует его (потому что он работает медленно, по крайней мере, с P5 или чего-то подобного), но AMD решила, что стоит сделать это быстро для Bulldozer. Наверное, потому что это было легко.

  • Было бы легко для уарха из SnB-семейства быстро loop ? Если так, то почему бы и нет? Если нет, то почему это сложно? Много декодерных транзисторов? Или дополнительные биты в объединенном dec & branch uop для записи того, что он не устанавливает флаги? Что могли делать эти 7 мопов? Это действительно простая инструкция.

  • Что особенного в бульдозере, который сделал быстрый loop легко / стоит? Или AMD потратила кучу транзисторов на изготовление loop быстро? Если так, то, возможно, кто-то думал, что это хорошая идея.

Если loop был бы быстрым, это было бы идеально для BigInteger произвольной точности adc циклы, чтобы избежать частичных задержек / замедлений флагов (см. мои комментарии к моему ответу), или любой другой случай, когда вы хотите выполнить цикл, не касаясь флагов. Он также имеет небольшое преимущество по сравнению с размером кода dec/jnz, (А также dec/jnz только макро-предохранители на семействе SnB).

На современных процессорах, где dec/jnz нормально в цикле АЦП, loop все равно было бы хорошо для циклов ADCX / ADOX (чтобы сохранить OF).

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

Это не помешало бы мне раздражаться на все вопросы с плохим 16-битным кодом, который использует loop для каждого цикла, даже если им также нужен другой счетчик внутри цикла. Но, по крайней мере, это было бы не так плохо.

Источник

3 ответа

В 1988 году сотрудник IBM Гленн Генри только что присоединился к компании Dell, в которой в то время работало несколько сотен человек, и в первый же месяц он выступил с техническим докладом о 386 внутренних устройствах. Многие из нас, программистов BIOS, интересовались, почему LOOP работает медленнее, чем DEC/JNZ, поэтому в разделе "вопросы / ответы" кто-то задавал вопрос.

Его ответ имел смысл. Это было связано с подкачкой.

LOOP состоит из двух частей: уменьшение CX, затем переход, если CX не равен нулю. Первая часть не может вызвать исключение процессора, тогда как часть перехода может. Например, вы можете перейти (или провалиться) к адресу за пределами сегмента, что приведет к SEGFAULT. Для двоих, вы можете перейти на страницу, которая поменялась.

SEGFAULT обычно означает конец процесса, но ошибки страницы различны. Когда происходит сбой страницы, процессор выдает исключение, а ОС выполняет служебную работу для обмена страницей с диска в ОЗУ. После этого он перезапускает инструкцию, вызвавшую ошибку.

Перезапуск означает восстановление состояния процесса до того состояния, в котором оно находилось непосредственно перед ошибочной инструкцией. В частности, в случае инструкции LOOP это означало восстановление значения регистра CX. Можно подумать, что вы можете просто добавить 1 к CX, так как мы знаем, что CX уменьшился, но, очевидно, это не так просто. Например, проверьте эту ошибку от Intel:

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

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

Это дополнительная нагрузка на сохранение CX, которая делает LOOP таким медленным.

Intel, как и все остальные в то время, получала все больше и больше RISC. Старые инструкции CISC (LOOP, ENTER, LEAVE, BOUND) постепенно сокращались. Мы все еще использовали их в сборке с ручным кодированием, но компиляторы полностью их игнорировали.

Источник

Теперь, когда я гуглил после написания своего вопроса, он оказался точным дубликатом одного на comp.arch, который появился сразу же. Я ожидал, что это будет трудно для Google (много "почему мой цикл медленный" хиты), но моя первая попытка (why is the x86 loop instruction slow) получил результаты.

Это не хороший или полный ответ.

Это может быть лучшее, что мы получим, и этого будет достаточно, если кто-то не сможет пролить на него больше света. Я не собирался писать это как пост "ответь на мой вопрос".

Хорошие посты с различными теориями в этой теме:

Роберт

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

Антон Эртль:

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

(Пол и все остальные: вы можете повторно опубликовать собственное письмо как собственный ответ. Я удалю его из своего ответа и проголосую за ваше.)

@Paul A. Clayton (случайный специалист по постерам Paul A. Clayton и архитектуре процессоров) решил, как можно использовать такое количество мопов. (Это выглядит как loope/ne который проверяет счетчик и ZF):

Я мог представить себе разумную версию с 6 микропроцессорами:

virtual_cc = cc; 
temp = test (cc); 
rCX = rCX - temp; // also setting cc 
cc = temp & cc; // assumes branch handling is not 
       // substantially changed for the sake of LOOP 
branch 
cc = virtual_cc

(Обратите внимание, что это 6 моп, а не 11 в SnB для LOOPE/LOOPNE, и это полное предположение, даже не пытающееся принять во внимание что-либо, известное из счетчиков производительности SnB.)

Тогда Павел сказал:

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

резюме: дизайнеры хотели loop поддерживаться только через микрокод, без каких-либо настроек самого оборудования.

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

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

... Павел продолжает:

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

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

Я подозреваю, что такие решения основаны на конкретных деталях реализации. Информация о таких деталях, по-видимому, не является общедоступной, и интерпретация такой информации была бы за пределами уровня квалификации большинства людей. (Я не дизайнер аппаратных средств - я никогда не играл ни одного по телевизору и не останавливался в Holiday Inn Express.:-)

Затем эта тема вышла за рамки темы AMD, что дало нам единственный шанс исправить ошибки в кодировке команд x86. Их сложно обвинить, поскольку каждое изменение - это случай, когда декодеры не могут совместно использовать транзисторы. И до того, как Intel приняла x86-64, не было даже ясно, что это завоевало популярность. AMD не хотела обременять свои процессоры аппаратным обеспечением, которое никто не использовал, если AMD64 не завоевал популярность.

Но все же есть так много маленьких вещей: setcc мог бы измениться на 32 бита. (Обычно вы должны использовать xor-zero / test / setcc, чтобы избежать ложных зависимостей, или потому что вам нужен регистр с нулевым расширением). Сдвиг может иметь безоговорочно записанные флаги, даже с нулевым смещением (устранение зависимости входных данных от eflags для смещения с переменным счетом при выполнении OOO). В прошлый раз, когда я печатал этот список любимых мозолей, я думаю, что был третий... О да, bt / bts и т. д. с операндами памяти имеет адрес, зависящий от старших битов индекса (битовая строка, а не просто бит внутри машинного слова).

bts инструкции очень полезны для битовых полей и работают медленнее, чем нужно, поэтому вы почти всегда хотите загрузить в регистр и затем использовать его. (Обычно быстрее сдвигать / маскировать, чтобы получить адрес самостоятельно, вместо использования 10 моп bts [mem], reg на Skylake, но это требует дополнительных инструкций. Так что это имело смысл на 386, но не на K8). Атомная битовая манипуляция должна использовать форму памяти-дест, но lockВ любом случае, редакция нуждается в большом количестве мопов. Это все еще медленнее, чем если бы он не мог получить доступ за пределами dword это работает на.

Источник

Пожалуйста, ознакомьтесь с прекрасной статьей Абраша, Майкла, опубликованной в журнале Dr. Dobb's Journal в марте 1991 г. v16 n3 p16 (8): http://archive.gamedev.net/archive/reference/articles/article369.html

Краткое содержание статьи следующее:

Оптимизация кода для микропроцессоров 8088, 80286, 80386 и 80486 является сложной задачей, поскольку микросхемы используют существенно различающиеся архитектуры памяти и время выполнения команд. Код не может быть оптимизирован для семейства 80x86; скорее, код должен быть спроектирован так, чтобы обеспечивать хорошую производительность в ряде систем, или оптимизироваться для конкретных комбинаций процессоров и памяти. Программисты должны избегать необычных инструкций, поддерживаемых 8088, которые потеряли преимущество в последующих чипах. Строковые инструкции следует использовать, но не полагаться на них. Регистры должны использоваться, а не операции с памятью. Ветвление также медленно для всех четырех процессоров. Доступ к памяти должен быть выровнен для улучшения производительности. Как правило, оптимизация 80486 требует действий, совершенно противоположных оптимизации 8088.

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

Любой программист 8088 инстинктивно заменит: DEC CX JNZ LOOPTOP на: LOOP LOOPTOP, потому что LOOP значительно быстрее на 8088. LOOP также быстрее на 286. На 386, однако, LOOP фактически на два цикла медленнее, чем DEC/JNZ. Маятник качается еще дальше на 486, где LOOP примерно в два раза медленнее, чем DEC/JNZ- и, заметьте, мы говорим о том, что изначально было, возможно, самой очевидной оптимизацией во всем наборе команд 80x86.

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

Но эта статья просто дает советы, она поощряет тестировать скорость выполнения и выбирать более быстрые варианты. Это не объясняет ПОЧЕМУ некоторые команды становятся очень медленными, поэтому не полностью отвечает на ваш вопрос.

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

Позднее процессоры начали использовать конвейеризацию инструкций - первоначально, простую, для 804086, и, наконец, Pentium Pro (выпущенный в 1995 г.) представил радикально другой внутренний конвейер, назвав его ядром Out Of Order (OOO), где инструкции были преобразованы в небольшие фрагменты. операций, называемых микрооперациями или микрооперациями, а затем все микрооперации с различными инструкциями помещались в большой пул микроопераций, где они должны были выполняться одновременно до тех пор, пока они не зависят друг от друга. Этот принцип конвейера ООО все еще используется, почти без изменений, на современных процессорах. Вы можете найти больше информации о конвейерной обработке команд в этой замечательной статье: https://www.gamedev.net/resources/_/technical/general-programming/a-journey-through-the-cpu-pipeline-r3115

Чтобы упростить конструкцию микросхемы, Intel решила сконструировать процессоры таким образом, чтобы одни инструкции превращались в микрооперации очень эффективным образом, а другие - нет.

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

Например, в "Справочном руководстве по оптимизации архитектуры Intel®" http://download.intel.com/design/PentiumII/manuals/24512701.pdf упоминается следующее: "Избегайте использования сложных инструкций (например, вводите, оставляйте или зацикливайтесь").) которые обычно имеют более четырех мопов и требуют многократных циклов для декодирования. Вместо этого используйте последовательности простых инструкций ".

Итак, Intel почему-то решила, что инструкция "loop" является "сложной", и с тех пор она стала очень медленной. Тем не менее, нет официальной ссылки Intel на разбивку команд: сколько микроопераций производит каждая инструкция и сколько циклов требуется для ее декодирования.

Вы также можете прочитать о механизме выполнения вне очереди в "Справочном руководстве по оптимизации архитектур Intel® 64 и IA-32" http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf раздел 2.1.2.

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