Оптимизация для процессоров семейства Pentium: 27. Специальные темы — Архив WASM.RU
27.1 Инструкция LEA (все процессоры)
Инструкция LEA полезна для самых разных целей, потому что она умеет делать сдвиг, два сложения и перемещение за один такт.
Пример:
Код (Text):
Гораздо быстрее, чем
Код (Text):
Инструкцию LEA можно использовать, чтобы делать сложение или сдвиг без изменения флагов. Источник и назначение не обязательно должны быть размером в слово, поэтому 'LEA EAX,[BX]' может стать возможной заменой для 'MOVZX EAX,BX', хотя на многих процессорах это не совсем оптимально.
Как бы то ни было, вам следует знать, что инструкция LEA вызывает задержку AGI на PPlain и PMMX, если она использует базовый или индексный регистр, в которой была произведена запись в предыдущем такте.
Так как инструкция LEA спариваема в V-конвеер на PPlain и PMMX, а инструкции сдвига - нет, вы можете использовать LEA в качестве замены SHL на 1, 2 или 3, если вы хотите, чтобы инструкция выполнялась в V-конвеере.
У 32-х битных конвееров нет документированного режима адресации с только индексным регистром, поэтому инструкция LEA EAX,[EAX*2] на самом деле записывается как 'LEA EAX,[EAX*2+00000000] с 4-х байтовым смещением. Вы можете снизить размер инструкции, написав 'LEA EAX,[EAX+EAX]' или, что еще лучше, 'ADD EAX,EAX'. Последний вариант не приведет к задержке AGI на PPlain и PMMX. Если случилось так, что у вас есть регистр, равный нулю (например, счетчик цикла после последнего прохода), вы можете использовать его как базовый регистр, чтобы снизить размер кода:
Код (Text):
27.2 Деление (все процессоры)
Деление отнимает очень много времени. На PPro, PII и PIII целочисленное деление занимает 19, 23 или 39 для байта, слова и двойного слова соответственно. На PPlain и PMMX беззнаковое челочисленное деление занимает приблизительно то же время, хотя деление со знаком занимает немного больше. Поэтому более предпочтительно использовать операнды маленького размера, которые не вызовут переполнения, даже если это будет стоить префикса размера операнда, и использовать по возможности беззнаковое деление.
Целочисленное деление на константу (все процессоры)
Целочисленное деление на степень от двух можно сделать, сдвигая значение вправо. Деление беззнакового целого числа на 2N:
Код (Text):
Деление целого числа со знаком на 2N:
Код (Text):
Альтернативный SHR короче, чем 'AND if N > 7, но может попасть только в порт 0 (или U-конвеер), в то время как AND может попасть как в порт 0, так и в порт 1 (U- или V-конвеер).
Деление на константу можно сделать на обратное число. Чтобы произвести беззнаковое целочисленное деление q = x / d, вам вначале нужно посчитать число, обратное делителю, f = 2r / d, где r определяет позицию двоично-десятичной точки (точка основания системы счисления). Затем нужно умножить x на f и сдвинуть полученный результат на r позиций вправо. Максимальное значение r равно 32+b, где b равно числу двоичных цифр в d минус 1. (b - это самое большое целое число, для которого 2b <= d). Используйте r = 32+b, чтобы покрыть максильное количество возможных значений делимого x.
Этот метод требует некоторых приемов, чтобы скомпенсировать ошибки округления. Следующий алгоритм даст вам верные результаты для деления беззнакового целого чила с усечением, то есть тот же результат, что дает инструкция DIV (спасибо Terje Mathisen, который изобрел этот метод):
Код (Text):
Пример:
Предположите, что вы хотите разделить на 5.
Код (Text):
Дробная часть больше, чем половина: используем случай C. Округляем f вверх до 0CCCCCCCDh.
Следующий код делит EAX на 5 и возвращает результат в EDX:
Код (Text):
После умножения EDX содержит значение, сдвинутое вправо на 32. Так как r = 34, вам нужно сдвинуть еще на 2, чтобы получить окончательный результат. Чтобы поделить на 10, вам нужно всего лишь заменить последнюю строку на 'SHR EDX,3'.
В случае B у вас будет следующее:
Код (Text):
Этот код работает для всех значений x, кроме 0FFFFFFFFH, которое дает ноль из-за переполнения в инструкции INC. Если возможно, что x = 0FFFFFFFFH, тогда замените этот код на:
Код (Text):
Если значение x ограничено, тогда вам следует использовать меньшее значение r, то есть меньшее количество цифр. Может быть несколько причин для того, чтобы сделать это:
- вы можете установить r = 32 и избежать 'SHR EDX,b' в конце.
- вы можете установить r = 16+b и использовать инструкции умножения, которые дают 32-х битный результат, вместо 64-х битного. Тогда можно освободить регистр EDX: IMUL EAX,0CCCDh / SHR EAX,18
- вы можете выбрать значение r, которое будет чаще приводить к случаю C, а не B, чтобы избежать инструкции 'INC EAX'.
Максимальное значение x в этих случаях равно по крайней мере 2r-b, иногда выше. Вы должны делать систематические тесты, если хотите узнать точное максимально значение x, при котором ваш код будет работать корректно.
Вы можете заменить медленную инструкцию умножения более быстрыми инструкциями, как это объяснено в главе 26.5.
Следующий пример делит EAX на 10 и возвращает результат в EAX. Я выбрал r=17, а не 19, потому что это дает код, который легче оптимизировать, и он покрывает такое же количество значений x. f = 217 / 10 = 3333h, случай B: q = (x+1)*3333h:
Код (Text):
Проведенные тесты показываеют, что этот код работает правильно для всех значений x < 10004H.
Повторяемое деление целого цисла на одно и то же значение (все процессоры)
Если делитель не известен во время ассемблирования программы, но вы делите на одно и то же число несколько раз, вы тоже можете использовать данный метод. Код должен определить, с каким случаем (A, B и C) он имеет дело, и высчитать f до совершения делений.
Следующий далее код показывает, как делать несколько делений на одно и то же число (беззнаковое деление с усечением). Сначала вызовите SET_DIVISOR, чтобы установить делитель и обратное ему число, затем вызовите DIVIDE_FIXED для каждого значения, которое нужно разделить на один и тот же делитель.
Код (Text):
Этот код даст тот же результат, что и инструкция DIV для 0 <= x < 232, 0 < d < 232.
Обратите внимание, что линия 'JC DOVERFL' и ее цель не нужны, если вы уверены, что x < 0FFFFFFFFH.
Если степени от 2 случаются так редко, что не стоит делать специальную оптимизацию из-за них, то вы можете убрать переход на DSHIFT и делать вместо него умножения с CORRECTION = 0 для случая A.
Если делитель меняется так часто, что процедура SET_DIVISOR нуждается в оптимизации, то вы можете заменить инструкцию BSR кодом, который приведен в главе 26.15 для процессоров PPlain и PMMX.
Деление чисел с плавающей запятой (все процессоры)
Деление чисел с плавающей запятой занимает 38 или 39 тактов при самой высокой точности. Вы можете сэкономить время, указав более низкую точность в контрольном слове (на PPlain и PMMX только FDIV и FIDIV более быстры при низкой точности; на PPro, PII и PIII это также относится к FSQRT. Выполнение других инструкций убыстрить этим способом нельзя).
Параллельное деление (PPlain и PMMX)
На PPlain и PMMX можно производить деление числа плавающей запятой и целочисленное деление параллельно. На PPro, PII и PIII это не возможно, потому что целочисленное деление и деление чисел с плавающей запятой используют один и тот же механизм.
Пример: A = A1 / A2; B = B1 / B2
Код (Text):
Убедитесь, что вы установили в контрольном слове FPU желаемый метод округления.
Использование обратных инструкций для быстрого деления (PIII)
На PIII вы можете использовать быстрые обратные инструкции RCPSS или PCPPS с делителем, а затем умножить на делимое. Правда, точность будет всего 12 бит. Вы можете повысить ее до 23-х, использовав метод Ньютона-Рафсона, объясненного в интеловской сопроводительной заметке AP-803:
Код (Text):
где x0 - это первое приближение к обратному от делителя d, а x1 - лучшее приближение. Вы должны использовать эту формулу перед умножение на делимое:
Код (Text):
Это позволяет сделать 4 деления за 18 тактов с точностью 23 бита. Повышение точность, повторяя формулу Ньютона-Рафсона возможно, но не очень выгодно.
Если вы хотите использовать этот метод для целочисленных делений, тогда вам нужно проверять результаты на ошибки округления. Следующие код делает четыре деления с усечением на упакованных целых числах размером в слово за примерно 42 такта. Это дает точные результаты для 0 <= делимое < 7FFFFH и 0 < делитель lt;= 7FFFFH:
Код (Text):
Этот код проверяет, не слишком ли мал результат и делает соответствующую коррекцию. Не нужно проверять, если результат слишком велик.
Избегание делений (все процессоры)
Очевидно, что вам минимизировать количество делений. Деления плавающей запятой на константу или повторяющиеся деления на одно и то же значения следуюет делать через умножения на обратное число. Но есть много других ситуаций, когда вы можете снизить количество делений. Например: if (A/B >c) можно переписать как if (A > B*C), если B положительны, и как обратное сравнение, если B отрицательны.
A/B + C/D можно переписать как (A*D + C*B) / (B*D)
Если вы используете целочисленное деление, вам стоит остерегаться того, что ошибки округления могут стать другими после переписывания формул.
27.3 Освобождение регистров FPU (все процессоры)
Вы должны освободить все использованные регистры FPU до выходы из подпрограммы, не считая регистра, использованного для возвращения результата.
Самый быстрые способ освободить один регистр - это FSTP ST. Самый быстрый способ освбодить два регистра на PPlain и PMMX - это FCOMPP, на PPro, PII и PIII вы можете использовать как FCOMPP, так и FSTP ST дважды.
Не рекомендуется использовать FFREE.
27.4 Переход от инструкций FPU к MMX и обратно (PMMX, PII и PIII)
Вы должны выполнить инструкцию EMMS после инструкции MMX, за которой может последовать код с инструкциями FPU.
На PMMX переключение между инструкциями FPU и MMX вызывает высокие потери. Выполнение первой инструкции FPU после EMMS занимает примерно на 58 тактов больше, а первой инструкции MMX после инструкции FPU - на 38 тактов больше.
На PII и PIII подобных потерь нет. Задержку после EMMS можно скрыть, поместив целочисленные инструкции между EMMS и первой инструкции FPU.
27.5 Конвертации чисел с плавающей запятой в целые (все процессоры)
Все подобные конверсии и обратно должны осуществляться через память:
Код (Text):
На PPro, PII и PIII этот код может вызвать потерит из-за попытки считать из [TEMP] до того, как закончена запись туда же, потому что инструкция FIST медленная (глава 17). WAIT не поможет (глава 26.6). Рекомендуется поместить другие инструкции между записью в [TEMP] и чтением оттуда, что бы избежать этих потерь. Это относится ко всем примерам, которые последуют в дальнейшем.
Спецификация языка C и C++ требует, чтобы конверсия из чисел с плавающей запятой в целые числа осуществлялась с помощью усечения, а не округления. Метод, используемый большинством библиотек C, это изменение контрольного слова FPU, чтобы указать инструкции FISTP на усечение, и изменение контрольного слова в прежнее состояние после ее выполнения. Это метод очень медленнен на всех процессорах. На PPro, PII и PIII контрольное слово FPU не может быть переименовано, поэтому все последующие инструкции плавающей запятой будут ждать, пока инструкция FLDCW не будет выведена из обращения.
Если вам нужно осуществить конверсию числа с плавающей запятой в C или C++, вам следует подумать о том, не лучше ли вам использовать округление вместо усечения. Если ваша стандартная библиотека не поддерживает быструю функцию округления, тогда сделайте свою собственную, используя примеры примеры, приведенные ниже.
Если вам нужно усечение внутри чикла, вы можете изменить контрольное слово за его пределами, если инструкции плавающей запятой внутри цикла могут корректно работать с данным режимом конвериторования.
Вы можете использовать различные способы, чтобы усекать без изменения контрольного слова, как это показано в примерах ниже. В данных примерах предполагается, что контрольное слово установлено по умолчанию, то есть округление к ближайшему.
Округление к ближайшему
Код (Text):
Усечение к нулю
Код (Text):
Усечение к минус бесконечности
Код (Text):
Эти процедуры работают для -231 < x < 231-1. Они не проверяют на переполнение или NAN'ы.
У PIII есть инструкции для усечения чисел с плавающей запятой одинарной точности: CVTTSS2SI and CVTTPS2PI. Эти инструкции очень полезны, если одинарная точность вас удовлетворяет, но если вы конвертироуете число с более высокой точностью в число с одинарной точностью, чтобы использовать эти инструкции, у вас могут столкнуться с тем, что число может быть округлено вверх во время конверсии.
Альтернатива инструкции FISTP (PPlain и PMMX)
Конвертирование числа с плавающей запятой в целое обычно осуществляется следующим образом:
Код (Text):
Альтернативный метод заключает в:
Код (Text):
Добавление 'волшебного числа' 251+252 есть такой эффект, что любое целое число между -231 и +231 будет выравнено в нижних 32-х битах, когда сохраняется как число с плавающей запятой двойной точности. Результат будет такой же, какой бы вы получили с помощью инструкции FISTP со всеми методами окруления, кроме усечения к нулю. Результат будет отличаться от FISTP, если в контрольном слове задано усечение или в случае переполнения. Вам может потребоваться инструкция WAIT для совместимости со старым 80287 процессором (глава 26.6)
Этот метод не быстрее использования FISTP, но он дает большую гибкость на PPlain и PMMX, потому между FADD и FSTP 3 такта, которые можно заполнить другими инструкциями. Вы можете умножить или разделить число на степень от друх в той же операции, сделав обратно по отношению к магическому числу. Вы также можете добавить константу, добавив ее к магическому числу, которое тогда будет иметь двойную точность.
27.6 Использование целочисленных инструкция для осуществления операций плавающей запятой (все процессоры)
Целочисленные операции в большинстве своем быстрее, чем инструкции плавающей запятой, поэтому зачастую выгоднее использовать их для осуществления простых операций плавающей запятой. Наиболее очевидное применение - это перемещение данных.
Пример:
Код (Text):
Заменить на:
Код (Text):
Тестируем, не равно ли значение с плавающей запятой нулю:
Значение с плавающей запятой, равное нулю, обычно представляется как 32 или 64 обнуленных бита, но здесь есть один подводные камень: бит знака может быть равен нулю! Минус ноль считается правильным числом с плавающей запятой, и процессор может сгенерировать ноль с уставноленным битом знака, если, например, отрицательное число было умножено на ноль. Поэтому если вы хотите узнать, не равно ли число с плавающей запятой нулю, вам не следует тестировать бит знака.
Пример:
Код (Text):
Используйте целочисленные инструкции вместо этого и сдвиньте бит знака:
Код (Text):
Если число с плавающей запятой имеет двойную точность (QWORD), тогда вам нужно протестировать только биты 32-62. Если они равны нулю, тогда нижняя половина будет также равна нулю, если это верное число с плавающей запятой.
Тест на то, отрицательно ли значение:
Число с плавающей запятой отрицательно, если бит знака и установлен по крайней мере один бит.
Пример:
Код (Text):
Манипулирование битом знака:
Вы можете изменить знак числа с плавающей запятой просто инвертирововав бит знака:
Пример:
Код (Text):
Похожим образом вы можете получить асбсолютное значение числа с плавающей запятой, просто сANDив бит знака:
Сравнивание чисел:
Числа с плавающей запятой сохраняются в особом формате, который позволяет использовать целочисленные инструкции для сравнения чисел с плавающей запятой, не считая бита знака. Если вы уверены, что оба сравниваемые числа с плавающей запятой являются правильными и положительными, вы можете простой сравнить их как целые:
Пример:
Код (Text):
Изменить на:
Код (Text):
Этот метод работает только, если у двух чисел одна и та же точность, и вы уверены, что ни у одного из числа не установлен бит знака.
Если возможны отрицательные числа, вы можете их сконвертировать определенным образом и сделать знаковое сравнение:
Код (Text):
Этот метод работает для всех правильных чисел с плавающей запятой, включая -0.
27.7 Использование инструкции с плавающей запятой, чтобы осуществлять целочисленные операции (PPlain и PMMX)
Целочисленное умножение (PPlain и PMMX)
Умножение плавающей запятой быстрее, чем целочисленное умножение на PPlain и PMMX, но цена конверсии целых чисел в числа с плавающей запятой и конвертирование результата обратно в целое число очень высоко, поэтому умножение плавающей запятой имеет смысл только тогда, если количество требуемых преобразование мало сравнимо с количеством умножений. (Довольно соблазнительно использование ненормальных чисел с плавающей запятой, чтобы пропустить часть конвертаций, но обработка таких чисел очень медленна, поэтому это плохая идея!)
На PMMX инструкции умножения MMX быстрее, чем целочисленное умножение, и могут конвееризоваться, поэтому одним из лучших решений на PMMX может быть использование этих инструкций на PMMX, если вы можете жить с 16-ти битной точностью.
Целочисленное умножение быстрее, чем умножение с плавающей запятой на PPro, PII и PIII.
Целочисленное деление (PPlain и PMMX)
Деление плавающей запятой не быстрее, чем целочисленное деление, но вы можете делать другие целочисленные операции (включая целочисленное деление, но не целочисленное умножение), в то время как работает FPU на деление плавающей запятой (смотри пример выше).
Конвертирование двоичных чисел в десятичные (все процессоры)
Использование инструкции FBSTP - простой и удобный путь для того, чтобы конвертировать двоичные числа в десятичные, хотя не обязательно самый быстрый метод.
27.8 Перемещение блоков данных (все процессоры)
Есть несколько способов перемещения блоков данных. Наиболее общий метод - это REP MOVSD, но при определенных условиях другие методы быстрее.
На PPlain и PMMX быстрее переместить 8 байтов за раз, если место назначения не находится в кэше:
Код (Text):
Источник и место назначения должны быть выравнены на 8. Дополнительное время, используемое медленными инструкциями FILD и FISTP компенсируется тем, что вам требуется сделать в два раза меньше операций записывания. Обратите внимание, что этот метод имеет преимущество только на PPlain и PMMX и только тогда, когда место назначения не находится в кэше первого уровня. Вы не можете использовать FLD и FSTP (без I) с противоположными последовательностями битов, потому что ненормальные числа обрабатываются медленно и не гарантируется, что они останутся неизмененными.
На PMMX, если назначение не находится в кэше, быстрее использовать инструкции MMX для перемещения восьми байтов за раз, если место назначения не находится в кэше.
Код (Text):
Данный цикл не нужно оптимизировать или разворачивать, если ожидаются промахи кэша, потому что здесь узкое место - это доступ к памяти, а не выполнение инструкций.
На процессорах PPro, PII и PIII инструкция REP MOVSD особенно быстра, если соблюдены следующие условия:
- источник и назначение должны быть выравнены на 8
- направление должно быть вперед (очищен флаг направления)
- счетчик (ECX) должен быть больше или равен 64
- разность между EDI и ESI должна быть больше или равна 32
На PII быстрее использовать регистры MMX, если вышеприведенные условия не соблюдены и место назначения находится в кэше первого уровня. Цикл можно развернуть в два раза, а источник и назначение должны быть выравнены на 8.
На PIII самый быстрый путь перемещения данных - это использовать инструкцию MOVAPS, если вышеприведенные условия не соблюдены или если место назначения не находится в кэше первого или второго уровня:
Код (Text):
В отличии от FLD, MOVAPS может обрабатывать любую пследовательность битов без всяких проблем. Помните, что источник и назначение должны быть выравнены на 16.
Если количество байтов, которые необходимо переместить, не кратно 16-ти, вы можете округлить его до числа, которое ближе всего к 16, и поместить несколько дополнительных байтов в конце буфера назначения, чтобы получить лишние байты. Если это невозможно, тогда вам необходимо переместить оставшиеся байты с помощью других методов.
На PIII у вас также есть опция прямой записи в RAM-память без вовлечения кэша, используя инструкцию MOVNTQ или MOVNTPS. Это может быть полезным, если вы не хотите, чтобы место назначение попало в кэш. MOVNTPS чуть-чуть быстрее, чем MOVNTQ.
27.9 Самомодифицирующийся код (все процессоры)
Потери при выполнении кода сразу после того, как тот был изменен, занимают примерно 19 тактов на PPlain, 31 на PMMX и 150-300 на PPro, PII и PIII. Процессоры 80486 и более ранние требуют переход между модифицирующим и модифицируемым кодом, чтобы очистить кэш кода.
Чтобы получить разрешение на модифицирование кода в защищенное операционной системе, вам потребуется вызвать специальные системные функции: в 16-битной Windows это ChangeSelector, в 32-х битной Windows - VirtualProtect и FlushInstructionCache (или поместить код в сегмент данных).
Самомодифицирующийся код не считается хорошим тоном программирования, но можно пойти на его применение, если выигрыш в скорости значителен.
27.10 Определение типа процессора (все процессоры)
Я думаю, что теперь достаточно очевидно, что оптимальное для одного процессора может не являться таковым для другого. Вы можете сделать несколько вариантов наиболее критичных участков кода вашей программы, чтобы они выполнялись максимально быстро на любом процессоре. Однако вам потребуется определить, на каком процессоре программа выполняется в настоящий момент. Если вы используете инструкции, которые не поддерживаются всеми процессорами, т.е. условные перемещения, FCOMI, инструкции MMX и XMM), то вы можете сначала проверить, поддерживает ли процессор данные инструкции. Процедура, приведенная ниже, проверяет тип процессора и поддерживаемые им технологии.
Код (Text):
Обратите внимание, что некоторые операционные системы не позволяют использовать инструкции XMM. Информация о том, как узнать, поддерживает ли операционная система инструкции XMM, можно найти в интеловской инструкции AP-900: "Identifying support for Streaming SIMD Extensions in the Processor and Operating System". Больше информации о идентификации процессора можно найти в инструкции AP-485: "Intel Processor Identification and the CPUID Instruction".
Если ассемблер не поддерживает инструкции MMX, XMM, условного перемещения данных, можно использовать специальные макросы (www.agner.org/assem/macros.zip) © Агнер Фог, пер. Aquila
Оптимизация для процессоров семейства Pentium: 27. Специальные темы
Дата публикации 22 авг 2002
