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

Question

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); 
    } 
} 

Answer 1

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

Answer 2

Читайте о Duff's Device

Answer 3

Этого смешения распределительного заявления и петля в то время как называется «Device Даффа». Это способ разворачивания циклов, который был оптимизацией, часто используемой в более ранние времена.

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

Answer 4

Duff's device

В computer science, Даффа является optimizedimplementation серийного экземпляра, который использует технику широко применяется в assembly language для loop unwinding. Его открытие зачислено в Tom Duff в ноябре 1983 года, который в то время работал на Lucasfilm. Это, пожалуй, самое драматичное использование case label fall-through в C programming language на сегодняшний день. Дафф не претендует на кредит для открытия концепции loop unrolling, только это определенное выражение его в С.

Answer 5

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

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

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

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

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

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

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

обновление

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

Answer 6

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

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

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

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

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

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