- Устройство Даффа
-
В информатике, Устройство Даффа (англ. Duff's device) — это оптимизированная реализация последовательного копирования, использующая ту же технику, что применяется для размотки циклов. Первое описание сделано Томом Даффом (Tom Duff) в ноябре 1983 года, который в то время работал на Lucasfilm. Пожалуй, это самое необычное использование того факта, что в языке Си инструкции внутри блока
switch
выполняются «насквозь» через все меткиcase
. Отметим, что Дафф не претендует на открытие самой концепции раскрутки циклов, ему принадлежит лишь её конкретное выражение на языке Си.Содержание
Применение
Вывод в регистр (первоначальный вариант)
Пример
Традиционный способ последовательного копирования (до открытия Даффа) выглядел так:
do { /* Предполагается count > 0 */ *to = *from++; /* Здесь указатель to не увеличивается */ } while (--count > 0);
В этом примере
to
не увеличивается потому, что Дафф копировал в единственный регистр ввода/вывода, отображаемый в память. В современном языке Си определение переменнойto
должно быть подкреплено с помощью ключевого словаvolatile
.Во время оптимизации этого кода Дафф осознал, что «раскрученный» вариант цикла может быть реализован при помощи наложения конструкций switch и do/while.
strcpy(to, from, count) register char *to, *from; register count; { register n = (count + 7) / 8; if (!count) return; 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); } }
Пояснения к примеру
Сам алгоритм был широко известен и раньше: программирующие на ассемблере применяли его для уменьшения количества сравнений и ветвлений при копировании.
А вот для программиста на Си реализация устройства Даффа на первый взгляд выглядит необычно. Однако никакой ошибки здесь нет: этот код написан в соответствии с описанием и стандартом языка Си; спецификация конструкции switch вполне допускает такое использование:
- На момент изобретения увидело свет лишь первое издание книги Язык программирования Си, в которой требовалось лишь, чтобы частью конструкции switch была синтаксически правильная инструкция, в том числе блок (составная инструкция), в котором все метки case должны предшествовать какой-либо инструкции внутри блока.
- Вторая интересная особенность синтаксиса Си состоит в том, что, при отсутствии break, управление внутри блока передаётся «вниз и насквозь» от инструкции, стоящей под одной меткой case, к инструкции, стоящей под следующей меткой case.
Сочетание этих двух фактов и означает, что вышеприведённый код выполнит копирование из последовательно расположенных адресов (*from) в отображаемый порт вывода (*to) заданное число раз (count[1]).
Копирование памяти
Первоначальный вариант устройства Даффа предназначался для копирования в регистр ввода/вывода. Чтобы просто скопировать кусок памяти из одного места в другое, нужно добавить авто-инкремент к каждому упоминанию to, вот так:
*to++ = *from++;
Устройства Даффа в таком виде приводится в качестве упражнения в книге Бьёрна Страуструпа «Язык программирования C++»[2]. По-видимому, изменение связано с тем, что автор не ожидает от начинающего программиста знакомства с регистрами ввода/вывода. Прямого практического применения такой вариант не имеет, так как в стандартной библиотеке языка Си уже есть функция копирования участка памяти (
memcpy
), которая скорее всего оптимизирована, причём гораздо более тщательно.Неявное представление конечных автоматов
Прямое использование конечных автоматов программистами часто затруднено тем, что выбранный язык программирования не позволяет ясно и просто представить состояния и переходы автомата в коде (см. примеры в статье «Автоматное программирование»).
Один из удачных вариантов предложен[3] Саймоном Тэтхемом и представляет собой способ реализации неявного конечного автомата при помощи устройства Даффа. В свою очередь, конечные автоматы были использованы Тэтхемом для реализации сопрограмм, что позволило ему реализовать задачу производителя-потребителя без использования многопоточности и сопутствующих проблем.
Тот же подход, в числе прочих, был использован и Адамом Данкелсом (англ. Adam Dunkels) в его библиотеке «protothreads»[4], посвящённой различным способам реализации псевдо-многопоточности при помощи неявных конечных автоматов.
Предложенный подход состоит в конструировании конечного автомата по частям, с использованием нескольких макросов языка Си. В упрощённом виде макросы выглядят так:
#define DECLARE() int state #define INIT() state = 0 #define BEGIN switch (state) { \ case 0: #define YIELD(val) do { \ state = __LINE__; \ return val; \ case __LINE__: \ ; \ } while (0) #define END }
Пример использования (на C++):
#include <iostream> using namespace std; class machine { DECLARE(); public: machine() { INIT(); } const char* next() { BEGIN; YIELD("мама"); YIELD("мыла"); YIELD("раму"); END; return NULL; } }; int main() { machine m; while (const char* val = m.next()) { cout << val << ' '; } return 0; }
Эта программа выведет «мама мыла раму», причём каждое слово будет сгенерировано отдельным шагом конечного автомата.
Примечания
- ↑ Следует отметить, что здесь предполагается, что count содержит строго положительное значение, о чём указывают комментарии в коде. Если count равен нулю, то поведение не определено.
- ↑ Страуструп Б. Язык программирования C++. Спец. изд. — ISBN 0-201-70073-5, раздел 6.6, упражнение 15.
- ↑ Simon Tatham. Сoroutines in C (англ.)
- ↑ Adam Dunkels. Protothreads — Lightweight, Stackless Threads in C (англ.)
Ссылки
- Описание и исходное сообщение Даффа на сайте Lysator (англ.).
- Исходное USENET-сообщение Даффа в архиве Google (англ.).
Категории:- Язык программирования Си
- Оптимизация программного обеспечения
Wikimedia Foundation. 2010.