Что делает этот код C [устройство Duff]?

void Send(int * to, const int* from, const int count)
{
    int 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);
    }
}

Ответ 1

Это Duff Device для копирования буферов памяти.

Ответ 2

Это Duff Device. Это метод разворачивания циклов, который позволяет не добавлять вторичный цикл исправления, чтобы иметь дело со временем, когда число итераций цикла не известно, чтобы быть точным кратным разворачивающему коэффициенту.

Так как большинство ответов здесь, похоже, в целом положительно относятся к этому, я собираюсь выступить против него.

С помощью этого кода компилятор будет пытаться применить любую оптимизацию к телу цикла. Если вы просто написали код как простой цикл, современный компилятор должен иметь возможность обрабатывать разворот для вас. Таким образом, вы сохраняете читаемость и производительность и надеетесь на то, что другие методы оптимизации будут применены к телу цикла.

Статья в Википедии, на которую ссылаются другие, даже говорит, что когда этот "шаблон" был удален из производительности исходного кода Xfree86, фактически улучшилось.

Этот результат типичен для слепого ручного оптимизации любого кода, который, по вашему мнению, может понадобиться. Это не позволяет компилятору правильно выполнять свою работу, делает ваш код менее читаемым и более подверженным ошибкам и обычно замедляет его. Если вы делаете все правильно, в первую очередь, то есть написание простого кода, затем профилирование для узких мест, а затем оптимизацию, вы даже не подумали бы использовать что-то вроде этого. В любом случае, не с современным процессором и компилятором.

Это прекрасно, чтобы понять это, но я был бы удивлен, если бы вы когда-либо использовали его.

Ответ 3

Это смешение оператора switch и цикла while называется "Duff Device". Это способ разворачивания циклов, который был оптимизацией, часто используемой в более ранние времена.

Таким образом, этот код по-прежнему копирует содержимое памяти из одного места в другое, но может быть более эффективным. Опасайтесь, что на сегодняшних архитектурах вы всегда должны это измерять, потому что с локальностью кэша и ослепительно быстрым циклом разворота циклов часто бывает плохой идеей.

Ответ 4

Это функционально идентично приведенному ниже коду:

for(int i=0;i<n;i++)
{
  *to++=*from++;
}

Разница в том, что ваш код разворачивает цикл, так что для каждого 8 целых копий требуется только 1 итерация цикла. Так как нет разрывов для любого из случаев, выполнение выполняется с каждого ярлыка случая до следующего.

Когда count% 8 == 0, внутри цикла выполняется 8 копий

когда count% 8 == 7, выполняется 7 копий для первой итерации

и т.д. После первой итерации с% 8 копий на каждой итерации происходит ровно 8 копий.

Развертывая цикл таким образом, накладные расходы цикла значительно уменьшаются. Важно отметить порядок значений case (0,7,6,5,4,3,2,1), которые могут быть переведены в таблицу перехода компилятором.

Обновление

Проблема с кодом примера, отправленным OP, заключается в том, что значение count из 0 приведет к 8 копиям, что может привести к переполнению буфера.

Ответ 5

Устройство Duff

В информатика, Устройство Duff - implementation серийной копии, которая использует технику, широко применяемую в язык ассемблера для loop unwinding. Его открытие приписывается Tom Duff в ноябре 1983 года, который в то время работал на Lucasfilm. Это, пожалуй, самое драматическое использование case label pass-through в Язык программирования C на сегодняшний день. Дафф не претендует на кредит для открытия концепции разворачивания цикла, просто это конкретное выражение в C.

Ответ 6

Читайте о Duff Device