Устройство Даффс - Duffs device - Wikipedia

в C язык программирования, Устройство Даффа это способ вручную реализовать разворачивание петли чередуя две синтаксические конструкции языка C: делать-пока петля и оператор переключения. Его открытие приписывают Том Дафф в ноябре 1983 года, когда Дафф работал на Лукасфильм и использовал его для ускорения анимационной программы в реальном времени.

Развертывание цикла пытается уменьшить накладные расходы условное ветвление необходимо проверить, выполнен ли цикл, выполнив пакет тел цикла за итерацию. Для обработки случаев, когда количество итераций не делится на приращения развернутого цикла, распространенный метод среди язык ассемблера программисты должны перейти прямо в середину развернутого тела цикла, чтобы обработать остаток.[1]Дафф реализовал эту технику в C, используя C провал ярлыка ящика возможность прыгнуть в развернутое тело.[2]

Оригинальная версия

Проблема Даффа заключалась в том, чтобы скопировать 16-битные целые числа без знака («шорты» в большинстве реализаций C) из массива в вывод с отображением памяти регистр, обозначенный в C как a указатель. Его исходный код в C, выглядело так:[3][4]

Отправить(к, из, считать)регистр короткая *к, *из;регистр считать;{    делать {                          / * предполагается count> 0 * /        *к = *из++;    } пока (--считать > 0);}

Этот код предполагает, что начальный count> 0. Указатель к не увеличивается, как это требуется для копирования из памяти в память. Если считать всегда делятся на восемь, при восьмикратном развертывании этого цикла получится следующее:

Отправить(к, из, считать)регистр короткая *к, *из;регистр считать;{    регистр п = считать / 8;    делать {        *к = *из++;        *к = *из++;        *к = *из++;        *к = *из++;        *к = *из++;        *к = *из++;        *к = *из++;        *к = *из++;    } пока (--п > 0);}

Дафф понял, что для обработки случаев, когда считать не делится на восемь, техника перехода программиста на ассемблере в тело цикла может быть реализована путем чередования структур оператора switch и цикла, помещая переключатель дело метки в точках тела цикла, которые соответствуют оставшейся части count / 8:[1]

Отправить(к, из, считать)регистр короткая *к, *из;регистр считать;{    регистр п = (считать + 7) / 8;    выключатель (считать % 8) {    дело 0: делать { *к = *из++;    дело 7:      *к = *из++;    дело 6:      *к = *из++;    дело 5:      *к = *из++;    дело 4:      *к = *из++;    дело 3:      *к = *из++;    дело 2:      *к = *из++;    дело 1:      *к = *из++;            } пока (--п > 0);    }}

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

Механизм

На основе алгоритма, широко используемого программистами, пишущими на сборка для минимизации количества тестов и переходов во время копирования устройство Даффа выглядит неуместным при реализации в C. Устройство является действительным C в силу двух атрибутов в C:

  1. Расслабленная спецификация выключатель заявление в определении языка. На момент изобретения устройства это было первое издание Язык программирования C что требует только, чтобы тело выключатель быть синтаксически правильным (составным) утверждением, внутри которого дело метки могут появляться перед любым вложенным утверждением. В сочетании с тем, что при отсутствии перемена заявление, поток управления будет провалиться из заявления, контролируемого одним дело метка к тому, что контролируется следующим, это означает, что код определяет последовательность считать копирует последовательные исходные адреса в выходной порт с отображением памяти.
  2. Возможность прыгнуть в середину петли в C.

Это приводит к тому, что Файл жаргона называет «самым драматическим применением провала в C».[5] Провал C по умолчанию в операторах case долгое время был одной из его самых спорных особенностей; Сам Дафф сказал, что «этот кодекс является своего рода аргументом в этой дискуссии, но я не уверен, за или против».[5]

Упрощенное объяснение

Функционально эквивалентная версия
с выключатель и пока распутанный
Отправить(к, из, считать)регистр короткая *к, *из;регистр считать;{    регистр п = (считать + 7) / 8;    выключатель (считать % 8) {        дело 0: *к = *из++;        дело 7: *к = *из++;        дело 6: *к = *из++;        дело 5: *к = *из++;        дело 4: *к = *из++;        дело 3: *к = *из++;        дело 2: *к = *из++;        дело 1: *к = *из++;    }    пока (--п > 0) {        *к = *из++;        *к = *из++;        *к = *из++;        *к = *из++;        *к = *из++;        *к = *из++;        *к = *из++;        *к = *из++;    }}

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

Устройство Даффа предоставляет решение, сначала выполняя оставшуюся часть итераций, а затем повторяя столько раз, сколько необходимо, кратное восьми аналогичным инструкциям. Чтобы определить количество итераций остатка, код сначала вычисляет общее количество итераций по модулю 8. Согласно этому остатку, выполнение программы будет затем Прыгать к дело заявление, за которым следует ровно необходимое количество итераций. Как только это будет сделано, все будет просто - код продолжает выполнять итерации групп из восьми инструкций, это стало возможным, поскольку оставшееся количество итераций кратно восьми.[1]

Устройство Даффа обеспечивает компактное развертывание цикла с помощью ключевого слова case как внутри, так и вне петли. Это необычно, потому что содержимое оператора case традиционно считается блоком кода, вложенным внутри оператора case, и читатель обычно ожидает, что он завершится до следующего оператора case. Согласно спецификациям языка C, в этом нет необходимости; действительно, операторы case могут появляться где угодно внутри выключатель кодовый блок, причем на любой глубине; выполнение программы просто перейдет к следующему оператору, где бы он ни находился.

Спектакль

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

Основное увеличение скорости по сравнению с простой и понятной петлей происходит от разматывание петли это уменьшает количество выполняемых ветвей, которые требуют больших вычислительных ресурсов из-за необходимости промывки - и, следовательно, остановки - - конвейер команд. В выключатель оператор используется для обработки оставшейся части данных, не делимых без остатка на количество развернутых операций (в этом примере развернуто восемь коротких ходов, поэтому выключатель автоматически обрабатывает лишние 1–7 шорт).

Эта автоматическая обработка остатка может быть не лучшим решением для всех систем и компиляторов - в некоторых случаях два цикла могут быть быстрее (один развернутый цикл для выполнения основной копии и второй цикл для обработки остатка). Проблема, похоже, сводится к способности компилятора правильно оптимизировать устройство; это также может мешать конвейерной обработке и предсказание ветвления на некоторых архитектурах.[6] Когда многочисленные экземпляры устройства Даффа были удалены из XFree86 На сервере версии 4.0 произошло улучшение производительности и заметное уменьшение размера исполняемого файла.[7] Поэтому, рассматривая этот код как оптимизация программы, возможно, стоит запустить несколько ориентиры чтобы убедиться, что это действительно самый быстрый код в целевой архитектуре, на целевом уровне оптимизации, с целевым компилятором, а также взвесить риск того, что оптимизированный код позже будет использоваться на разных платформах, где это не самый быстрый код.

Для копирования из памяти в память (что, как упоминалось выше, не было первоначальным использованием устройства Даффа), стандартная библиотека C обеспечивает функцию memcpy;[8] он не будет работать хуже, чем версия этого кода, копирующая память в память, и может содержать специфичные для архитектуры оптимизации, которые делают его значительно быстрее.[9][10]

Смотрите также

Рекомендации

  1. ^ а б c d Холли, Ральф (1 августа 2005 г.). "Многоразовое устройство Дафф". Журнал доктора Добба. Получено 18 сентября, 2015.
  2. ^ Дафф, Том (29 августа 1988 г.). "Тема: Re: Объяснение, пожалуйста!". Лизатор. Получено 3 ноября, 2015.
  3. ^ "Удивительное устройство Даффа от Тома Даффа!". doc.cat-v.org. Получено 2017-06-08.
  4. ^ Кокс, Расс (30.01.2008). "research! rsc: На устройстве Даффа и сопрограммах". research.swtch.com. Получено 2017-01-24.
  5. ^ а б Файл жаргона
  6. ^ Журнал USENIX 2003 Джеймса Ралстона[постоянная мертвая ссылка ]
  7. ^ Цо, Тед (22 августа 2000 г.). "Re: [PATCH] Re: Перенос драйверов ввода, нужно кое-что от вас". lkml.indiana.edu. Список рассылки ядра Linux. Получено 22 августа, 2014. У Джима Геттиса есть прекрасное объяснение этого эффекта на X-сервере. Оказывается, что с прогнозами ветвлений и относительной скоростью процессора по сравнению с памятью, меняющейся за последнее десятилетие, развертывание цикла в значительной степени бессмысленно. Фактически, удалив все экземпляры устройства Даффа из XFree86 4.0 сервер уменьшился в размере на _half_ _a_ _megabyte_ (!!!) и был быстрее загружен, потому что устранение всего этого лишнего кода означало, что X-сервер не так сильно загружал строки кэша.
  8. ^ "memcpy - cppreference.com". En.cppreference.com. Получено 2014-03-06.
  9. ^ Уолл, Майк (2002-03-19). «Использование предварительной выборки блоков для оптимизации производительности памяти» (PDF). mit.edu. Получено 2012-09-22.
  10. ^ Туман, Агнер (29 февраля 2012). «Оптимизация подпрограмм на ассемблере» (PDF). Инженерный колледж Копенгагенского университета. стр. 100 и далее. Получено 2012-09-22.

дальнейшее чтение

внешняя ссылка