|
Все, что здесь написано, является выборкой наиболее важных на мой взгляд фактов из документации от Agner Fog. Если вы серьезно интересуетесь оптимизацией для Intel Pentium (plain, MMX, PPro, P2), найдите и прочтите эту документацию (я нашел на http://www.agner.org/assem, относительно старая версия есть на ftp://ftp.cdrom.com/pub/sac/text/pentopt.zip).
По-моему, основной прием ускорения. Дело в том, что у процессоров Pentium есть два конвейера обработки команд, U-pipe и V-pipe. В результате некоторые пары команд могут исполняться одновременно, а это практически удваивает скорость. Эти команды могут быть исполнены и в U-pipe, и в V-pipe, и при этом могут быть спарены (с какой-либо другой командой): mov reg/mem,reg/mem/imm Эти команды могут быть исполнены только в U-pipe, но при этом все-таки могут быть спарены: adc, sbb Эти команды могут быть исполнены в любом конвейере, но могут быть спарены только в V-pipe: near call (близкий вызов) Все остальные целочисленные команды могут быть исполнены только в U-pipe и не могут быть спарены вообще. Две последовательно идущих команды будут спарены в случае выполнения всех нижеследующих условий. Если хотя бы одно из условий не выполняется, то исполняется только первая команда, вторая (и, возможно, следующая за ней) команда будет исполнена лишь в следующем такте. Вот условия спаривания:
Спаривающаяся команда, которая читает из памяти, считает и записывает результат в регистр или в регистр флагов занимает 2 такта. Спаривающаяся команда, которая читает из памяти, считает и записывает результат обратно в память занимает 3 такта. Примеры таких команд: add eax,[ebx] ; 2 такта add [ebx],eax ; 3 такта Существует также так называемое неполное спаривание (imperfect pairing), когда обе команды выполняются в разных конвейерах, но НЕ одновременно (возможно, частично перекрываясь по времени исполнения), а следующие за ними команды не могут начать исполнение, пока обе команды не закончатся. Такое случается в следующих случаях:
У процессора Pentium непосредственно на кристалле есть 8k кэш-памяти (это т.н. кэш-память первого уровня, L1 cache) для кода и 8k - для данных. Данные из L1 cache считываются/записываются за один такт; кэш-промах же может стоить довольно много тактов. Таким образом, для наиболее эффективного использования кэша необходимо знать, как он работает. Итак, L1 cache состоит из 256 кэш-линий (cachelines), по 32 байта в каждой. При чтении данных, которых нет в кэше, процессор считывает из памяти целую кэш-линию. Кэш-линии всегда выравнены на физический адрес, делящийся на 32; так что если прочитать байт по адресу, делящемуся на 32, то можно читать и писать в следующий за ним 31 байт без всяких задержек. Свои данные имеет смысл располагать с учетом этого факта - например, выравнивать массивы из структур длиной 32 байта на 32; перед записью в видеопамять читать оттуда один байт (один раз на 32 записываемых байта); используемые вместе данные располагать вместе; и так далее. Но кэш-линия не может быть связана с любым физическим адресом. У каждой кэш-линии есть некое 7-битное "заданное значение" (set-value), которое должно совпадать с битами адреса 5-11. Для каждого из 128 возможных значений set-value есть две кэш-линии. Отсюда следует то, что в кэше не может одновременно содержаться более двух блоков данных с одинаковыми битами адреса 5-11. Чем это чревато, покажем на примере.
; пусть в esi - адрес, делящийся на 32
loop_label:
mov eax,[esi]
mov ebx,[esi+13*4096+4]
mov ecx,[esi+20*4096+28]
dec edx
jnz loop_label
У используемых трех адресов будет одинаковое значение в битах 5-11. Поэтому к моменту самого первого чтения в ecx в кэше точно не окажется свободной кэш-линии, процессор выберет для нее наименее использованную (least recently used) линию, ту самую, которая была использована при чтении eax. При чтении ebx, соответственно, будет заново перекрыта линия, использованная при чтении ecx... В результате цикл будет состоять из сплошных кэш-промахов и съест порядка 60 тактов. Если же поменять 28 на 32, изменив, таким образом, на единичку биты 5-11 для адреса [esi+20*4096+28], то для чтения в eax и ebx будут как раз использованы две имеющихся линии, для чтения в ecx - третья, не совпадающая ни с одной из этих двух. В результате - скорость порядка трех тактов на один проход и ускорение примерно в 20 (!!!) раз. Еще одна интересная вещь, которую стоит учесть - Pentium НЕ загружает кэш-линию при промахе записи; только при промахе чтения. При промахе записи данные пойдут в L2 cache или память (в зависимости от настроек L2 cache). А это довольно медленно. Поэтому, если мы последовательно пишем в один и тот же 32-байтовый блок, но не читаем оттуда, то имеет смысл сначала сделать холостое чтение из этого блока, чтобы загрузить его в L1 cache; тогда все последовательные операции записи будут есть только по одному такту.
Трюков есть много, перечислим здесь только наиболее часто используемые: работа с fixed point вместо floating point иногда (если код не слишком сильно насыщен математикой) быстрее; практически всегда быстрее для клонов; все данные желательно выравнивать по адресам, кратным размеру данных (то есть, переменные-байты можно не выравнивать, слова - выравнивать на 2, двойные слова - на 4); обращение к невыравненной переменной влечет за собой задержку минимум на три такта; деление на заранее известное число можно заменить умножением на обратное ему число; деление на степень двойки для целых чисел заменяется на сдвиг влево; деление чисел с плавающей точкой (fdiv) на Intel Pentium (на клонах, к несчастью, это не так) может исполняться параллельно с целочисленными командами. | |||
 |
|
|
|
|
