Метод дыхания
- 1 year ago
- 0
- 0
Метод Даффа
(
англ.
Duff's device
) в программировании — это
оптимизированная
реализация последовательного копирования, использующая ту же технику, что применяется для
размотки циклов
. Первое описание сделано в ноябре
1983 года
(
англ.
Tom Duff
), который в то время работал на
Lucasfilm
. Пожалуй, это самое необычное использование того факта, что в
языке Си
инструкции внутри блока
switch
выполняются «насквозь» через все метки
case
.
Следует отметить, что Дафф не претендует на открытие самой концепции раскрутки циклов, ему принадлежит лишь её конкретное выражение на языке Си.
В современных решениях польза от применения метода Даффа сомнительна. Оно затрудняет работу оптимизирующих компиляторов и предсказателя переходов. Например, после удаления кода Даффа из XFree86 версии 4.0 (2000 год) бинарные файлы уменьшились примерно на 0,5 МБ и сервер стал загружаться быстрее.
Традиционный способ последовательного копирования (до открытия Даффа) выглядел так:
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 вполне допускает такое использование:
Сочетание этих двух фактов приводит к тому, что вышеприведённый код выполнит копирование из последовательно расположенных адресов ( *from ) в отображаемый порт вывода ( *to ) заданное число раз ( count ).
Первоначальный вариант метода Даффа предназначался для копирования в регистр ввода-вывода. Чтобы просто скопировать фрагмент памяти из одного места в другое, нужно добавить автоматическую инкрементацию к каждому упоминанию to :
*to++ = *from++;
Метод Даффа в таком виде приводится в качестве упражнения
в книге
Бьёрна Страуструпа
«Язык программирования C++»
. По-видимому, изменение связано с тем, что автор не ожидает от начинающего программиста знакомства с регистрами ввода-вывода. Практического применения такой вариант не имеет, так как в стандартной библиотеке языка Си уже есть функция копирования участка памяти (
memcpy
).
Прямое использование конечных автоматов программистами часто затруднено тем, что выбранный язык программирования не позволяет ясно и просто представить состояния и переходы автомата в коде (см. примеры в статье « Автоматное программирование »).
Один из удачных вариантов предложен Саймоном Тэтхемом и представляет собой способ реализации неявного конечного автомата при помощи метода Даффа. В свою очередь, конечные автоматы были использованы Тэтхемом для реализации сопрограмм , что позволило ему реализовать без использования многопоточности и сопутствующих проблем.
Тот же подход, в числе прочих, был использован и ( англ. Adam Dunkels ) в его библиотеке «protothreads» , посвящённой различным способам реализации псевдо-многопоточности при помощи неявных конечных автоматов.
Предложенный подход состоит в конструировании конечного автомата по частям, с использованием нескольких макросов языка Си. В упрощённом виде макросы выглядят так:
#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;
}
Эта программа выведет «мама мыла раму», причём каждое слово будет сгенерировано отдельным шагом конечного автомата.