typedef

Duff’s Device

07.09.2009, 23:09
Теги: C, история

9 ноября 1983 года Том Дафф изобрел «устройство» имени себя. Вот так оно выглядело:

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

Такая конструкция предназначалась для раскрутки цикла копирования фрагмента памяти в регистр пословно. Развертывание сокращает количество итераций цикла и, как следствие, количество операций сравнения (в данном случае в 8 раз), тем самым слегка повышая производительность.

Чтобы лучше понять, что происходит, предлагаю читателям запустить следующую программу (я немного изменил изначальный вариант):

#include 
 
int c = 0;
int a = 10;
 
void foo()
{
    printf("%d ", c++);
}
 
void bar()
{
    printf("%d\n", a);
}
 
int main()
{
    switch (a&3) {
    case 0: do { foo(); bar();
    case 3:      foo(); bar();
    case 2:      foo(); bar();
    case 1:      foo(); bar();
	       } while((a -= 4) >= 0);
    }
    return 0;
}

Самое удивительное в этом всем — вовсе не корявое «столбчатое» форматирование. Удивительно то, что язык позволяет размещать цикл внутри блока switch. Интуитивно нам кажется, что каждый case начинает новый блок, и что нельзя соорудить блок, заключающий в себя несколько case’ов. А приведенный выше пример вообще представляется надругательством над синтаксисом C и здравым смыслом. Но стоит задуматься о том, как именно реализована конструкция switch-case, как сразу все становится на свои места:

// исходный код
switch (a) {
    case 0:
        a++;
        break;
    case 1:
        a--;
}
 
// что происходит на самом деле (примерно)
case_0:
    if (a == 1) goto case_1;
    a++;
    goto end;
case_1:
    a--;
end:

Вот так! Теперь понятно, что внутри конструкции switch можно развернуться от души, чем и не преминул воспользоваться Дафф.

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

Жаждущих подробностей отправляю к оригинальному сообщению Даффа и статье в Википедии.