Метод Даффа
Метод Даффа (англ. Duff's device) в программировании — это оптимизированная реализация последовательного копирования, использующая ту же технику, что применяется для размотки циклов. Первое описание сделано в ноябре 1983 года Томом Даффом[англ.] (англ. Tom Duff), который в то время работал на Lucasfilm. Пожалуй, это самое необычное использование того факта, что в языке Си инструкции внутри блока switch
выполняются «насквозь» через все метки case
.
Следует отметить, что Дафф не претендует на открытие самой концепции раскрутки циклов, ему принадлежит лишь её конкретное выражение на языке Си.
В современных решениях польза от применения метода Даффа сомнительна. Оно затрудняет работу оптимизирующих компиляторов и предсказателя переходов.[1] Например, после удаления кода Даффа из XFree86 версии 4.0 (2000 год) бинарные файлы уменьшились примерно на 0,5 МБ и сервер стал загружаться быстрее.[2]
Применение
[править | править код]Вывод в регистр (первоначальный вариант)
[править | править код]Пример
[править | править код]Традиционный способ последовательного копирования (до открытия Даффа) выглядел так:
send(to, from, count)
register short *to, *from;
register count;
{
do { /* Предполагается count > 0 */
*to = *from++; /* Здесь указатель to не увеличивается */
} while (--count > 0);
}
В этом примере to
не увеличивается потому, что Дафф копировал в единственный регистр ввода-вывода, отображаемый в память. В современном языке Си определение переменной to
должно быть подкреплено с помощью ключевого слова volatile
.
Во время оптимизации этого кода Дафф осознал, что «раскрученный» вариант цикла может быть реализован при помощи наложения конструкций switch и do/while.
send(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[3]).
Копирование памяти
[править | править код]Первоначальный вариант метода Даффа предназначался для копирования в регистр ввода-вывода. Чтобы просто скопировать фрагмент памяти из одного места в другое, нужно добавить автоматическую инкрементацию к каждому упоминанию to:
*to++ = *from++;
Метод Даффа в таком виде приводится в качестве упражнения
в книге Бьёрна Страуструпа «Язык программирования C++»[4]. По-видимому, изменение связано с тем, что автор не ожидает от начинающего программиста знакомства с регистрами ввода-вывода. Практического применения такой вариант не имеет, так как в стандартной библиотеке языка Си уже есть функция копирования участка памяти (memcpy
).
Неявное представление конечных автоматов
[править | править код]Прямое использование конечных автоматов программистами часто затруднено тем, что выбранный язык программирования не позволяет ясно и просто представить состояния и переходы автомата в коде (см. примеры в статье «Автоматное программирование»).
Один из удачных вариантов предложен[5] Саймоном Тэтхемом и представляет собой способ реализации неявного конечного автомата при помощи метода Даффа. В свою очередь, конечные автоматы были использованы Тэтхемом для реализации сопрограмм, что позволило ему реализовать задачу производителя-потребителя без использования многопоточности и сопутствующих проблем.
Тот же подход, в числе прочих, был использован и Адамом Данкелсом[англ.] (англ. Adam Dunkels) в его библиотеке «protothreads»[6], посвящённой различным способам реализации псевдо-многопоточности при помощи неявных конечных автоматов.
Предложенный подход состоит в конструировании конечного автомата по частям, с использованием нескольких макросов языка Си. В упрощённом виде макросы выглядят так:
#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;
}
Эта программа выведет «мама мыла раму», причём каждое слово будет сгенерировано отдельным шагом конечного автомата.
Примечания
[править | править код]- ↑ James Ralston’s USENIX 2003 Journal (недоступная ссылка)
- ↑ Ted Tso on XFree86 and performance, Linux Kernel Archive ML . Дата обращения: 3 декабря 2013. Архивировано 8 января 2014 года.
- ↑ Следует отметить, что здесь предполагается, что count содержит строго положительное значение, о чём указывают комментарии в коде. Если count равен нулю, то поведение не определено.
- ↑ Страуструп Б. Язык программирования C++. Спец. изд. — ISBN 0-201-70073-5, раздел 6.6, упражнение 15.
- ↑ Simon Tatham. Сoroutines in C Архивная копия от 9 ноября 2019 на Wayback Machine (англ.)
- ↑ Adam Dunkels. Protothreads — Lightweight, Stackless Threads in C Архивировано 13 октября 2005 года. (англ.)
Ссылки
[править | править код]- Описание и исходное сообщение Даффа на сайте Lysator (англ.).
- Исходное USENET-сообщение Даффа в архиве Google (англ.).
- A Reusable Duff Device // Dr Dobbs, Ralf Holly, August 01, 2005