Цикл с нулевыми накладными расходами - Zero-overhead looping

эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью от добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Цикл с нулевыми накладными расходами»  – Новости  · газеты  · книги  · ученый  · JSTOR (Ноябрь 2020) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Цикл с нулевыми накладными расходами это особенность некоторых процессор наборы инструкций чье железо может повторить тело петля автоматически, вместо того, чтобы требовать программных инструкций, которые циклы (и, следовательно, время) сделать это.^[1][2] Петли с нулевыми издержками распространены в цифровые сигнальные процессоры и немного CISC наборы инструкций.

Задний план

Во многих наборах инструкций цикл должен быть реализован с использованием инструкций для увеличения или уменьшения счетчика, проверки, был ли достигнут конец цикла, и, если нет, перехода к началу цикла, чтобы его можно было повторить. Хотя обычно это составляет всего около 3–16 байт для каждого цикла, даже такое небольшое количество может быть значительным в зависимости от размера Кеши процессора. Более важно то, что для выполнения каждой инструкции требуется время, которое не тратится на полезную работу.

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

Например, следующий код C можно скомпилировать и оптимизировать в следующий код сборки x86:

беззнаковый int массив[100];беззнаковый int я;для (я = 0; я < 100; я++) {    массив[я] = я;}

; Установите количество итераций цикла.; Обратите внимание, что компилятор полностью изменил цикл; так что он считает в обратном порядке от 99 до 0,; а не от 0 до 99.mov eax, 99.МЕТКА:; array [i] = imov DWORD PTR массив[0+eax*4], eax; Декремент ясуб eax, 1; Проверьте i> = 0. Если это правда, повторите цикл.jnb .МЕТКА

Реализация

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

Примеры

ПОС

в Набор инструкций PIC, то ПОВТОРЕНИЕ и ДЕЛАТЬ инструкции реализуют циклы с нулевыми накладными расходами.^[1] ПОВТОРЕНИЕ повторяет только одну инструкцию, а ДЕЛАТЬ повторяет указанное количество следующих инструкций.

Blackfin

Blackfin предлагает два контура с нулевыми накладными расходами.^[3] Циклы могут быть вложенными; если оба аппаратных цикла сконфигурированы с одним и тем же адресом «конца цикла», цикл 1 будет вести себя как внутренний цикл и повторяться, а цикл 0 будет вести себя как внешний цикл и повторяться, только если цикл 1 не будет повторяться.

Циклы управляются с помощью LTx и LBx регистры (Икс либо от 0 до 1), чтобы установить начало и конец цикла, то есть первую и последнюю инструкции, которые должны быть выполнены, что может быть одинаковым для цикла только с одной инструкцией - и LCx для количества петель. Цикл повторяется, если LCx отличен от нуля в конце цикла, и в этом случае LCx уменьшается.

Регистры цикла можно установить вручную, но обычно это занимает 6 байтов для загрузки регистров и 8–16 байтов для установки значений для загрузки. Чаще всего используется инструкция по настройке цикла (представленная в сборке как ПЕТЛЯ с псевдоинструкцией LOOP_BEGIN и LOOP_END, или в одной строке как LSETUP), который при необходимости инициализирует LCx и устанавливает LTx и LBx до желаемых значений. Для этого требуется всего 4–6 байтов, но можно установить только LTx и LBx в ограниченном диапазоне относительно того, где находится инструкция по настройке цикла.

P0 = массив + 396;R0 = 100;LC0 = R0;ПЕТЛЯ my_loop LC0;   // устанавливает LT0 и LB0LOOP_BEGIN my_loop;   // псевдо-инструкция; генерирует метку, используемую для вычисления LT0// LC0 нельзя записать напрямую в память,// поэтому мы должны использовать временный регистр.R0 += -1;   // одинаково быстро и мало будет R0 = LC0[P0--] = R0;LOOP_END my_loop;   // псевдо-инструкция; генерирует метку, используемую для вычисления LB0

x86

В язык ассемблера x86 REP префиксы реализуют циклы с нулевыми издержками для нескольких инструкций (а именно MOVS / STOS / CMPS / LODS / SCAS).^[4] В зависимости от префикса и инструкции инструкция будет повторяться несколько раз с (E) CX удерживая счетчик повторов, или пока не будет найдено совпадение (или несовпадение) с AL / AX / EAX или с DS: [(E) SI]. Это может быть использовано для реализации некоторых типов поиска и операций с строки с завершающим нулем.

использованная литература