Устройство Даффа
В C языке программирования устройство Даффа представляет собой способ ручной реализации развертывания цикла путем чередования двух синтаксических конструкций C: делать - Цикл while и оператор переключения . Его открытие приписывают Тому Даффу в ноябре 1983 года, когда Дафф работал на Lucasfilm и использовал его для ускорения программы анимации в реальном времени.
Развертывание цикла пытается уменьшить накладные расходы на условное ветвление, необходимое для проверки выполнения цикла, путем выполнения пакета тел цикла на итерацию. Для обработки случаев, когда количество итераций не делится на приращения развернутого цикла, программисты на ассемблере обычно используют метод перехода непосредственно в середину тела развернутого цикла для обработки остатка. [ 1 ] Дафф реализовал эту технику в C, используя функцию пропускания метки регистра C для перехода в развернутое тело. [ 2 ]
Оригинальная версия
[ редактировать ]Задача Даффа заключалась в копировании 16-битных целых чисел без знака («коротких» в большинстве реализаций C) из массива в отображаемый в памяти выходной регистр, обозначаемый в C указателем . Его исходный код на C выглядел следующим образом: [ 3 ] [ 4 ]
send(to, from, count)
register short *to, *from;
register count;
{
do { /* count > 0 assumed */
*to = *from++;
} while (--count > 0);
}
Этот код предполагает, что начальный счет > 0 . Поскольку местом вывода является регистр, отображаемый в памяти, указатель to не увеличивается, как это требуется для копирования из памяти в память.
Если count всегда делились на восемь, развертывание этого цикла в восемь раз привело бы к следующему:
send(to, from, count)
register short *to, *from;
register count;
{
register n = count / 8;
do {
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
} while (--n > 0);
}
Дафф понял, что для обработки случаев, когда число не делится на восемь, метод ассемблерного программиста перехода в тело цикла может быть реализован путем переплетения структур оператора переключателя и цикла, помещая метки регистра в точках тела цикла, которые соответствуют остатку количество/8 : [ 1 ]
send(to, from, count)
register short *to, *from;
register count;
{
register n = (count + 7) / 8;
switch (count % 8) {
case 0: do { *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
} while (--n > 0);
}
}
Устройство Даффа аналогичным образом можно применить и с любым другим размером развернутой петли, а не только с восьмым, как в примере выше.
Механизм
[ редактировать ]Основанное на алгоритме, широко используемом программистами, пишущими на ассемблере для минимизации количества тестов и ветвей во время копирования, устройство Даффа выглядит неуместным при реализации на C. Устройство валидно на языке C в силу двух атрибутов в C:
- Смягченная спецификация оператор переключения в определении языка. На момент изобретения устройства это было первое издание языка программирования C , для которого требуется только, чтобы тело переключатель должен быть синтаксически допустимым (составным) оператором, внутри которого метки случая могут появляться перед любым подвыражением. В связи с тем, что в отсутствие Break , поток управления провалится из оператора, контролируемого одним метка случая соответствует той, которая контролируется следующей, это означает, что код определяет последовательность подсчитывать копии из последовательных исходных адресов в отображаемый в памяти выходной порт.
- Возможность перейти в середину цикла в C.
Это приводит к тому, что в Jargon File называется «самым драматическим применением провала в C, которое когда-либо наблюдалось». [ 5 ] Провал C по умолчанию в утверждениях случая уже давно является одной из его наиболее спорных особенностей; Сам Дафф сказал: «Этот кодекс служит своего рода аргументом в этих дебатах, но я не уверен, за или против». [ 5 ]
Несмотря на то, что устройство Даффа применимо для C, оно противоречит общим рекомендациям C, таким как рекомендации MISRA . Некоторые компиляторы (например, CompCert ) ограничиваются такими рекомендациями и поэтому отвергают устройство Даффа, если не указано иное.
Упрощенное объяснение
[ редактировать ]| Функционально эквивалентная версия с switch и while распутанный
|
|---|
send(to, from, count)
register short *to, *from;
register count;
{
register n = (count + 7) / 8;
switch (count % 8) {
case 0: *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
}
while (--n > 0) {
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
}
}
|
Основная идея развертывания цикла заключается в том, что количество инструкций, выполняемых в цикле, можно уменьшить за счет уменьшения количества тестов цикла, а иногда и за счет сокращения времени, затрачиваемого в цикле. Например, в случае цикла, содержащего только одну инструкцию в блочном коде, проверка цикла обычно выполняется для каждой итерации цикла, то есть каждый раз, когда выполняется инструкция. Если вместо этого в цикл поместить восемь копий одной и той же инструкции, то тест будет выполняться только каждые восемь итераций, и это может выиграть время, избегая семи тестов. Однако это обрабатывает только число итераций, кратное восьми, и для обработки оставшихся итераций требуется что-то еще. [ 1 ]
Устройство Даффа обеспечивает решение, сначала выполняя оставшуюся часть итераций, а затем повторяя столько раз, сколько необходимо, кратное восьми подобным инструкциям. Чтобы определить количество итераций остатка, код сначала вычисляет общее количество итераций по модулю восемь. Согласно этому остатку, выполнение программы затем перейдет к case За оператором следует точное количество необходимых итераций . Как только это будет сделано, все станет просто: код продолжает выполнять итерации групп по восемь инструкций; это стало возможным, поскольку оставшееся количество итераций кратно восьми. [ 1 ]
Устройство Даффа обеспечивает компактное развертывание цикла за счет использования ключевого слова case как внутри, так и вне цикла . Это необычно, поскольку содержимое оператора Case традиционно рассматривается как блок кода, вложенный в оператор Case, и читатель обычно ожидает, что он завершится до следующего оператора Case. Согласно спецификациям языка C, в этом нет необходимости; действительно, операторы case могут появляться где угодно внутри блока кода переключателя и на любой глубине; выполнение программы просто перейдет к следующему оператору, где бы он ни находился.
Производительность
[ редактировать ]Многие компиляторы оптимизируют переход на таблицу ветвей так же, как это было бы сделано в реализации на ассемблере.
Основное увеличение скорости по сравнению с простым и понятным циклом происходит за счет раскручивания цикла , которое уменьшает количество выполняемых ветвей, которые являются дорогостоящими в вычислительном отношении из-за необходимости сбрасывать - и, следовательно, останавливать - конвейер команд . switch используется для обработки оставшейся части данных, не кратной числу развернутых операций (в этом примере развернуто восемь коротких ходов, поэтому switch автоматически обрабатывает дополнительные 1–7 коротких видео).
Такая автоматическая обработка остатка может быть не лучшим решением для всех систем и компиляторов — в некоторых случаях два цикла могут фактически работать быстрее (один развернутый цикл для выполнения основной копии, а второй цикл для обработки остатка). Проблема, похоже, сводится к способности компилятора правильно оптимизировать устройство; это также может мешать конвейеризации и прогнозированию ветвей на некоторых архитектурах. [ 6 ] Когда многочисленные экземпляры устройства Даффа были удалены с сервера XFree86 в версии 4.0, произошло улучшение производительности и заметное уменьшение размера исполняемого файла. [ 7 ] Поэтому, рассматривая этот код как оптимизацию программы , возможно, стоит провести несколько тестов , чтобы убедиться, что это действительно самый быстрый код на целевой архитектуре, на целевом уровне оптимизации, с целевым компилятором, а также взвесить риск. что оптимизированный код в дальнейшем будет использоваться на разных платформах, где это не самый быстрый код.
Для копирования из памяти в память (что, как упоминалось выше, не было первоначальным использованием устройства Даффа) стандартная библиотека C предоставляет функцию memcpy; [ 8 ] он будет работать не хуже, чем версия этого кода, копируемая из памяти в память, и может содержать оптимизации, специфичные для архитектуры, которые делают его значительно быстрее. [ 9 ] [ 10 ]
См. также
[ редактировать ]
- Вычисленный ПЕРЕЙТИ
- Сопрограмма — устройство Даффа можно использовать для реализации сопрограмм на C/C++ (см. внешнюю ссылку Tatham).
- Устройство Дженсена
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с д Холли, Ральф (1 августа 2005 г.). «Многоразовое устройство для даффов» . Доктор Добб . Журнал доктора Добба . Проверено 18 сентября 2015 г.
- ^ Дафф, Том (29 августа 1988 г.). «Тема: Re: Объясните, пожалуйста!» . Лисатор . Проверено 3 ноября 2015 г.
- ^ «Удивительное устройство Даффа от Тома Даффа!» . doc.cat-v.org . Проверено 8 июня 2017 г.
- ^ Кокс, Расс (30 января 2008 г.). "research!rsc: Об устройстве Даффа и сопрограммах" . www.research.swtch.com . Проверено 24 января 2017 г.
- ^ Перейти обратно: а б Файл жаргона
- ^ Журнал USENIX Джеймса Ралстона, 2003 г. [ постоянная мертвая ссылка ]
- ^ Цо, Тед (22 августа 2000 г.). «Re: [PATCH] Re: Перемещение драйверов ввода, нужно несколько слов от вас» . lkml.indiana.edu . Список рассылки ядра Linux . Проверено 22 августа 2014 г.
У Джима Геттиса есть замечательное объяснение этого эффекта на X-сервере. Оказывается, что с учетом прогнозов ветвей и изменения относительной скорости процессора по сравнению с памятью за последнее десятилетие, развертывание цикла практически бессмысленно. Фактически, за счет исключения всех экземпляров Duff's Device с сервера XFree86 4.0 размер сервера уменьшился на _половину_а_ _мегабайт_ (!!!) и стал загружаться быстрее, поскольку удаление всего этого лишнего кода означало, что X-сервер не так сильно терял строки кэша.
- ^ «memcpy — cppreference.com» . En.cppreference.com . Проверено 6 марта 2014 г.
- ^ Уолл, Майк (19 марта 2002 г.). «Использование предварительной выборки блоков для оптимизации производительности памяти» (PDF) . mit.edu . Архивировано из оригинала (PDF) 30 августа 2017 г. Проверено 22 сентября 2012 г.
- ^ Туман, Агнер (29 февраля 2012 г.). «Оптимизация подпрограмм на языке ассемблера» (PDF) . Инженерный колледж Копенгагенского университета . стр. 100 и далее . Проверено 22 сентября 2012 г.
Дальнейшее чтение
[ редактировать ]- Керниган, Брайан ; Ричи, Деннис (март 1988 г.). Язык программирования C (2-е изд.). Энглвуд Клиффс, Нью-Джерси: Прентис Холл. ISBN 0-13-110362-8 .
Внешние ссылки
[ редактировать ]- Описание и исходное письмо от Даффа из Lysator.
- Сопрограммы Саймона Тэтэма на C используют тот же трюк с переключением/регистром.
- В книге Адама Данкелса Protothreads — Lightweight, Stackless Threads в C также используются вложенные операторы switch/case (см. также Самые легкие облегченные потоки, Protothreads ).
- Устройство Голубя — это схожий метод: переплетение операторов switch/case и if/else.