Как можно скомпилировать код устройства Даффа?

Question

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

Как может сделать, пока предложение существует в switch предложение? Очень странно.
Есть кто-нибудь, кто может это объяснить?

Edit: Другой вопрос. Почему Дафф использовал 8? Это может быть 16, 65536 или что-то еще. Из-за размера кода? Есть ли другая причина? Например, преимущества кэширования или конвейеризации.

Answer 1

«Как это работает» достаточно просто.

И C, и C ++ являются скомпилированными языками и обычно компилируются в машинный код платформы.Машинный код не имеет понятия блочных структур - все блочные структуры должны быть переведены в форму, которая использует (в действительности) некоторое сочетание безусловных и условных переходов.

Синтаксические правила C позволяют оператору switch и циклу бытьобъединены таким способом, который не является истинной иерархической структурой блоков, но который запутывает поток управления.Пока компилятор может справиться с этим (что должен делать любой хороший компилятор), в базовом машинном коде нет проблем.В результате получаются «спагетти», но сгенерированный машинный код, прошедший через оптимизатор, всегда спагетти - он не предназначен для чтения человеком, поэтому это не проблема.Проблема здесь в том, что исходный код тоже спагетти, хотя gotos были «скрыты».

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

РЕДАКТИРОВАТЬ

Нижеследующее относится к устройству Duffs и может помочь проиллюстрировать основную идею ...

switch (count & 1)
{
  case 0 : goto lbl0;
  case 1 : goto lbl1;
}

lbl0:

while (count != 0)
{
  handle_one ();
  count--;
lbl1:
  handle_one ();
  count--;
}

Наличие предложений case внутри цикла концептуально не отличается от наличия меток goto-target внутри цикла, так каквыше.

Предупреждение - это просто для иллюстрации идеи и не должно копироваться в реальном коде.

Answer 2

Простое объяснение того, почему устройство Даффа компилируется, состоит в том, что синтаксис оператора switch не особенно специфичен для формы, которую может понадобиться блоку оператора switch. Есть несколько ограничений и несколько вещей, разрешенных в контролируемом операторе, которые не разрешены за пределами switch (case и default метки). Но кроме этого, контролируемый оператор - это просто любой другой оператор, с вероятностью, что существуют метки для switch для цели.

Вот синтаксис из C99:

switch ( expression ) statement

Помимо синтаксиса, стандарт накладывает несколько ограничений:

• управляющее выражение должно иметь целочисленный тип
• существуют ограничения относительно того, где могут присутствовать VLA в операторе switch
• case выражения меток должны быть целочисленными константами
• не может быть дубликатов case выражений меток или default меток

Кроме этого, любая конструкция, разрешенная в блоке операторов, должна быть разрешена в контролируемом операторе (с добавлением, что метки case и default в порядке). Помните, что case и default - это просто метки, к которым переключается переход, основываясь на управляющем выражении и выражениях case. Как сказал Потато-вода , switch - это просто вычисленное goto. Так же, как goto может прыгнуть в середину цикла, так и switch.

Кроме того, я думаю, что случаи, когда вы могли бы получить выгоду от устройства Даффа, сегодня довольно редки (я думаю, что они были редки даже в 1980-х годах). Не забывайте, что сам Том Дафф сказал в своем описании следующее:

• "Отвратительно, нет?"
• «Я чувствую сочетание гордости и отвращения к этому открытию».

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

Answer 3

switch - это просто вычисленное goto.Итак, внутри цикла есть несколько меток, а вне цикла - оператор switch.switch решает, к какой метке идти, и goto s там, внутри цикла.

Как только выполнение находится внутри цикла, оно продолжает цикл до тех пор, пока цикл не освободит управление.

Это на самом деле очень просто ... и его не следует использовать, если это не самая прямолинейная альтернатива.

Не верьте никому, кто говорит вам, что это что-то делает быстро.

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

Что касается компиляторов, они разбивают вещи на общие графы потоков управления и не заботятся о switchпротив if против while.Все они if ( … ) goto …; else goto …; для компилятора.

Answer 4

Если мы возьмем реализацию из статьи в Википедии, вы ссылаетесь ...

send(to, from, count)
register short *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);
        }
}

... и замените «высокоуровневый» цикл do / while на уровень сборки if / goto, чтобы компилятор действительно уменьшал его до ...

send(to, from, count)
register short *to, *from;
register count;
{
        register n=(count+7)/8;
        switch(count%8){
        case 0:     do_label: *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++;
                if (--n>0) goto do_label;
        }
}

... это может помочь вам понять, что - в этом случае, когда область действия do / while не вводит локальные переменные, - на самом деле нет ничего большего, чем переход к случаю 0, который обходит переключатель и, следовательно, необходимость оценки количества% 8 (% - довольно дорогая операция в схеме вещей).

Надеюсь, что это помогает щелкнуть, но не может ...? : -)

Почему Дафф использовал 8? Это может быть 16, 65536 или что-то еще. Из-за размера кода? Есть ли другая причина? Например, преимущества кэширования или конвейеризации.

Просто случай убывающей отдачи. Необходимость выполнения проверки --n > 0 и перехода после каждых 8 копий данных не является большой процентной нагрузкой, но размер кода (как в исходном, так и в скомпилированном коде в кеше) все еще довольно узок. Может быть, это будет 90 или 95% работы против накладных расходов, что, очевидно, было достаточно хорошо. Кроме того, чтобы проиллюстрировать концепцию и поделиться ею с другими, Том Дафф, возможно, предпочел, чтобы она соответствовала коду, типичному для терминала 80x25, а не странице или 10.

Answer 5

Несмотря на то, что устройство Даффа устарело для своей первоначальной цели, оно все же полезно для специальных целей, таких как конечный автомат, который обычно циклически повторяет состояния N, но иногда необходимо возвращаться к вызывающей стороне и позже возобновлять работу всостояние, в котором он остановился.Размещение оператора switch вне цикла и меток case внутри цикла (я бы взял это как определение «устройства Даффа»), тогда имеет большой смысл.

С учетом сказанного,не используйте устройства Даффа для «оптимизации вручную».Размещение повсеместно "меток перехода" не поможет компилятору оптимизироваться.