Программирование поэзии: устройство Даффа

Duff’s Device - действительно умная реализация динамического разворачивания цикла. Том Дафф написал код в 1983 году, работая в Lucasfilm. Дафф изобрел свою конкретную реализацию разворачивания цикла, чтобы оптимизировать процедуру, которая копировала массив коротких замыканий в регистр данных программируемого ввода-вывода системы изображений Evans & Sutherland Picture System II. Давайте сначала проверим код, а затем рассмотрим некоторую справочную информацию, которая поможет понять его.

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

Магия. Теперь давайте вернемся и попытаемся понять это.

Система изображений Эванса и Сазерленда

Код был написан для The Evans & Sutherland Picture System II. Посмотрите эту первую страницу брошюры о Picture System I 1974 года. Это взрыв из прошлого!

Дафф написал свой код для Picture System II, но можно с уверенностью предположить, что он был очень похож на версию I. Машина использовалась для визуализации и управления 3D-моделями в реальном времени. В его состав входили планшет и перо, которые вместе служили стандартным графическим устройством ввода. Изображения ниже должны дать вам представление о том, как использовалась Система изображений.

Импетус

Вот пример процедуры из программы, над которой Дафф работал для Picture System.

send(to, from, count)
	register short *to, *from;
	register count;
	{
		do
			*to = *from++;
		while(--count>0);
	}

В электронном письме от 1983 года, где Дафф официально представил свое устройство, он также описал импульс для его написания. Он включил процедуру, описанную выше, и отметил следующее:

Как оказалось, этот цикл был узким местом в программе воспроизведения анимации в реальном времени, которая работала слишком медленно примерно на 50%.

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

Развертывание петли

Развертывание цикла - это метод оптимизации, в котором размер программы меняется на скорость. Бинарный размер программы увеличивается, но увеличивается скорость выполнения. Этот метод работает путем преобразования цикла, чтобы исключить инструкции сборки, которые управляют циклом. В случае компилятора VAX C, который использовал The Picture System II, рассматриваемый цикл do-while будет скомпилирован в две инструкции: movw и subleq. Инструкция movw копирует одну регистровую пару в другую регистровую пару, а инструкция subleq указывает «SUbtract and Branch if Less than или EQual to zero». Давайте рассмотрим интересующий цикл do-while и изучим инструкции по сборке.

{
       	do
		*to = *from++;        // compiles to a movw
	while(--count>0);             // compiles to a subleq
}

Если бы count было, скажем, 20, то в приведенном выше цикле было бы скомпилировано до 20 инструкций movw и 20 инструкций subbleq. Теперь давайте рассмотрим разворачивание цикла, чтобы уменьшить количество инструкций subleq, выполняемых компьютером.

int n = count / 5;                // if count is 20, n is 4
{
       	do
	       *to = *from++;     // 5 copies will be executed
               *to = *from++;     // each iteration of the 
               *to = *from++;     // loop
               *to = *from++;
               *to = *from++; 
	while(--n>0);             // the loop will run 4 times 
}                                 // for the same total of 20 copies

Дублировав тело цикла, он был развернут 5 раз. Результирующий скомпилированный код C включает те же 20 инструкций movw, что и исходный цикл, но развернутый цикл включает только 4 инструкции subleq. Вы можете спросить себя: что произойдет, если count не делится на 5 без остатка? В этом случае программисты часто реализуют цикл постобработки или оператор switch для обработки остатка. Реализация переключателя может выглядеть примерно так:

int remainder = count % 5;
switch (remainder)                
{
        case 4 : *to = *from++;      
        case 3 : *to = *from++;
        case 2 : *to = *from++;
        case 1 : *to = *from++;
        case 0 : ;
}

Этот код выполнит оставшееся количество копий регистра, не завершенных в развернутом цикле. Этот код компилируется до количества инструкций movw, равного remainder (плюс инструкции, необходимые для вычисления переключателя и перехода к правильной метке case). Важно понимать, что в C операторы switch не прерываются автоматически перед каждой меткой case. Это означает, что как только выполнение кода начинается с вычисленной метки case, он пропускает оставшиеся метки case, последовательно выполняя каждую строку кода. Это свойство языка C играет важную роль в реализации развертывания цикла Даффом.

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

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

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

Вот оно, Устройство Даффа, во всей красе:

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

примечание: для указателя to нет пост-инкремента, поскольку устройство предназначалось для последовательного копирования значений в регистр ввода-вывода. Устройство можно было бы использовать для общего копирования памяти, если бы постфикс ++ был включен.

Как это работает

Устройство Даффа включает петлю, размотанную 8 раз. Цикл встроен в оператор switch, так что переключатель вычисляет оставшиеся копии регистров, которые необходимо выполнить до входа в цикл. Выполнение переходит в цикл по вычисленной метке case, проходит через оставшиеся метки case, а затем попадает в ключевое слово while, которое переходит в начало цикла do-while и выполняет циклы из 8 копий регистров, пока n не достигнет 0.

Недостатки

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

Источники

Https://stackoverflow.com/questions/514118/how-does-duffs-device-work
http://www.lysator.liu.se/c/duffs-device.html пож
«Http://www.drdobbs.com/a-reusable-duff-device/184406208
https://en.wikipedia.org/wiki/Duff%27s_device#Performance