Устройство Даффа

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

В информатике, Устройство Даффа (англ. 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;
    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[1]).

Упражнение

Следующий пример может служить более наглядной иллюстрацией (в нём а также исправлена ошибка для count == 0, присутствующая в вышеприведённом коде):

#include <stdio.h>
 
send(int count) {
    if (!count) return;
    int n = (count + 7) / 8;
    switch (count % 8) {
      case 0: do { puts("case 0");
      case 7:      puts("case 7");
      case 6:      puts("case 6");
      case 5:      puts("case 5");
      case 4:      puts("case 4");
      case 3:      puts("case 3");
      case 2:      puts("case 2");
      case 1:      puts("case 1");
                 } while (--n > 0);
    }
}
 
main(int argc, char *argv[]) {
 puts("duff's device.");
 if (argc > 1) {
   int count = atoi(argv[1]);
   send(count);
 }
}

Читателю предлагается скомпилировать эту программу и самостоятельно проанализировать её работу. Число-счётчик задаётся параметром командной строки.

Копирование памяти

Первоначальный вариант устройства Даффа предназначался для копирования в регистр ввода/вывода. Чтобы просто скопировать кусок памяти из одного места в другое, нужно добавить авто-инкремент к каждому упоминанию 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;
}

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

Примечания

  1. Следует отметить, что в здесь предполагается, что count содержит строго положительное значение, о чём указывают комментарии в коде. Если count равен нулю, то поведение не определено.
  2. Страуструп Б. Язык программирования C++. Спец. изд. — ISBN 0-201-70073-5, раздел 6.6, упражнение 15.
  3. Simon Tatham. Сoroutines in C (англ.)
  4. Adam Dunkels. Protothreads — Lightweight, Stackless Threads in C (англ.)

Ссылки

en:Duff's device es:Dispositivo de Duff ja:Duff's device pl:Mechanizm Duffa tr:Duff aygıtı

Личные инструменты

Served in 0.183 secs.