Метод Даффа ( англ. 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 вполне допускает такое использование:

1. На момент изобретения увидело свет лишь первое издание книги « Язык программирования Си », в которой требовалось лишь, чтобы частью конструкции switch была синтаксически правильная инструкция, в том числе блок (составная инструкция), в котором все метки case должны предшествовать какой-либо инструкции внутри блока.
2. Вторая особенность синтаксиса Си состоит в том, что при отсутствии break , управление внутри блока передаётся «вниз и насквозь» от инструкции, стоящей под одной меткой case , к инструкции, стоящей под следующей меткой case .

Сочетание этих двух фактов приводит к тому, что вышеприведённый код выполнит копирование из последовательно расположенных адресов ( *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;
}

Эта программа выведет «мама мыла раму», причём каждое слово будет сгенерировано отдельным шагом конечного автомата.

Примечания

Ссылки

• на сайте Lysator (англ.) .
• в архиве Google (англ.) .
• // Dr Dobbs , Ralf Holly, August 01, 2005