OberonCore
https://forum.oberoncore.ru/

Duff's device vs Дейкстра
https://forum.oberoncore.ru/viewtopic.php?f=27&t=1563		 Страница 1 из 2
Автор:  Vlad [ Среда, 06 Май, 2009 08:15 ]
Заголовок сообщения:  Duff's device vs Дейкстра
Поскольку тема "правильных" циклов по-прежнему волнует участников данного форума, то предлагаю переписать "по Дейкстре" знаменитый Duff's device: http://en.wikipedia.org/wiki/Duff%27s_device
Код:
dsend(to, from, count)
char *to, *from;
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);
    }
}


Естественно с максимальной оптимизацией для неоптимизируещего компилятора (каковым является BB). Т.е. минимизировать количество проверок и переходов.

P.S. Не флейма ради :) Просто всегда считал, что "правильно" эту экзотику не перисать. Но может чего упустил (глядишь и сюда можно цикл Дейкстры приятнуть :)
Автор:  Валерий Лаптев [ Среда, 06 Май, 2009 08:23 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Vlad писал(а):
Поскольку тема "правильных" циклов по-прежнему волнует участников данного форума, то предлагаю переписать "по Дейкстре" знаменитый Duff's device: http://en.wikipedia.org/wiki/Duff%27s_device
Код:
dsend(to, from, count)
char *to, *from;
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);
    }
}


Естественно с максимальной оптимизацией для неоптимизируещего компилятора (каковым является BB). Т.е. минимизировать количество проверок и переходов.

P.S. Не флейма ради :) Просто всегда считал, что "правильно" эту экзотику не перисать. Но может чего упустил (глядишь и сюда можно цикл Дейкстры приятнуть :)


Я когда этот ужас у Страуструпа увидел, подумал - совсем сиплюсники с ума спрыгнули! Такой кошмар в проге писать... :)
Автор:  Александр Ильин [ Среда, 06 Май, 2009 08:40 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Код:
PROCEDURE UnwindedLoop (from, to, count);
VAR c: INTEGER;
BEGIN
   c := cound DIV 8;
   WHILE c > 0 DO
      to^ := from^; INC (from);
      to^ := from^; INC (from);
      to^ := from^; INC (from);
      to^ := from^; INC (from);
      to^ := from^; INC (from);
      to^ := from^; INC (from);
      to^ := from^; INC (from);
      to^ := from^; INC (from);
      DEC (c)
   END;
   c := count MOD 8;
   WHILE c > 0 DO
      to^ := from^; INC (from);
      DEC (c)
   END
END UnwindedLoop;
Прыжок в середину "развёрнутого" цикла заменён на дополнительный цикл по остатку от деления. По сравнению с Duff's device больше на 1..8 проверок.
Автор:  Vlad [ Среда, 06 Май, 2009 08:41 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Валерий Лаптев писал(а):
Я когда этот ужас у Страуструпа увидел, подумал - совсем сиплюсники с ума спрыгнули! Такой кошмар в проге писать... :)


Этот девайс придумали сишники, С++ в том году только появился на свет ;) Плюшники перепишут его на темплейтах, со всеми делами ;)
Автор:  Vlad [ Среда, 06 Май, 2009 08:45 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Александр Ильин писал(а):
Прыжок в середину "развёрнутого" цикла заменён на дополнительный цикл по остатку от деления. По сравнению с Duff's device больше на 1..8 проверок.


Принято. Но может быть можно как-нибудь "развернуть" эти 1..8 проверок? :)
Автор:  Александр Ильин [ Среда, 06 Май, 2009 08:51 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Vlad писал(а):
Принято. Но может быть можно как-нибудь "развернуть" эти 1..8 проверок? :)
Можно сделать и одну проверку, конечно, если уж очень сильно хочется:
Код:
PROCEDURE UnwindedLoop (from, to, count);
VAR c: INTEGER;
BEGIN
   c := cound DIV 8;
   WHILE c > 0 DO
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      DEC (c)
   END;
   CASE count MOD 8 OF
   | 7:
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^
   | 6:
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^
   | 5:
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^
   | 4:
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^
   | 3:
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^
   | 2:
      to^ := from^; INC (from);      to^ := from^
   | 1:
      to^ := from^
   | 0:
   END
END UnwindedLoop;
Автор:  Александр Ильин [ Среда, 06 Май, 2009 08:57 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Vlad писал(а):
Просто всегда считал, что "правильно" эту экзотику не перисать. Но может чего упустил (глядишь и сюда можно цикл Дейкстры приятнуть :)
Ну как, "правильно" получается?
Автор:  Vlad [ Среда, 06 Май, 2009 09:02 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Александр Ильин писал(а):
Можно сделать и одну проверку, конечно, если уж очень сильно хочется:


Я имел ввиду как-нибудь не в лоб :) Т.е. не "дублируя" присваивания в исходном тексте. Вот бы еще на ДРАКОНе кто-нибудь забабахал... Но я подозреваю, что там чуда тоже не будет (будет 7 отдельных веток).
Автор:  Vlad [ Среда, 06 Май, 2009 09:08 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Александр Ильин писал(а):
Vlad писал(а):
Просто всегда считал, что "правильно" эту экзотику не перисать. Но может чего упустил (глядишь и сюда можно цикл Дейкстры приятнуть :)
Ну как, "правильно" получается?


Да понятно, что можно переписать через нормальные циклы. Но изюминка теряется :) Вместо изюминки просто развернутый ручками код...
Автор:  Александр Ильин [ Среда, 06 Май, 2009 09:23 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Vlad писал(а):
не "дублируя" присваивания в исходном тексте.
Можно пойти на компромисс и вдвое сократить число дополнительных проверок (с 1..8 до 1..4), не так сильно увеличив объём исходника. В первом варианте было на 1 операцию присваивания больше, чем в сишном оригинале, во втором - на 28, здесь - на 7:
Код:
PROCEDURE UnwindedLoop (from, to, count);
VAR c: INTEGER;
BEGIN
   c := cound DIV 8;
   WHILE c > 0 DO
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      DEC (c)
   END;
   c := count MOD 8;
   IF c # 0 THEN
      IF c DIV 4 # 0  THEN
         to^ := from^; INC (from);      to^ := from^; INC (from);
         to^ := from^; INC (from);      to^ := from^; INC (from);
      END;
      c := c MOD 4;
      IF c DIV 2 # 0 THEN
         to^ := from^; INC (from);      to^ := from^; INC (from);
      END;
      IF ODD(c) THEN
         to^ := from^
      END
   END
END UnwindedLoop;
Автор:  Александр Ильин [ Среда, 06 Май, 2009 09:33 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Vlad писал(а):
Да понятно, что можно переписать через нормальные циклы. Но изюминка теряется :) Вместо изюминки просто развернутый ручками код...
Там изюминка в том, что организован цикл с 8 точками входа. На ассемблере такое допустимо, но стурктурные языки не должны такого допускать, насколько я понимаю. Что же вы подразумевали под "правильной" реализацией, если не "нормальные" структурные циклы? Вот вам решение "по Дейкстре", даже в нескольких вариантах.
Автор:  Рэйлвэй Каген [ Среда, 06 Май, 2009 10:00 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Vlad писал(а):
Вот бы еще на ДРАКОНе кто-нибудь забабахал... Но я подозреваю, что там чуда тоже не будет (будет 7 отдельных веток).
Почему отдельных? Думаю, лесенка видна явно.
Вложение:
2.png
2.png [ 7.21 КБ | Просмотров: 10242 ]
Автор:  Alexey Veselovsky [ Среда, 06 Май, 2009 10:09 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Если несколько точек входа... То быть может сопрограммы чем помогут?
В Модуле они вроде есть, сопрограммы эти.
Автор:  Valery Solovey [ Среда, 06 Май, 2009 12:04 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Там написано очень сложно, поэтому я не уверен, что понимаю правильно, но это похоже на вечный цикл.
Автор:  Александр Ильин [ Среда, 06 Май, 2009 13:46 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Valery Solovey писал(а):
Там написано очень сложно, поэтому я не уверен, что понимаю правильно, но это похоже на вечный цикл.
Где сложно написано? В сишном оригинале?
Автор:  Александр Ильин [ Среда, 06 Май, 2009 13:50 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Чуть более "регулярный" вариант концовки:
Код:
   c := count MOD 8;
   IF ODD(c) THEN
      to^ := from^; INC (from);
   END;
   c := c DIV 2;
   IF ODD(c) THEN
      to^ := from^; INC (from);      to^ := from^; INC (from);
   END;
   c := c DIV 2;
   IF ODD(c) THEN
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
   END
Число проверок ровно на 3 больше, чем в Duff's device.
Автор:  Valery Solovey [ Среда, 06 Май, 2009 15:29 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Да, я про сишный вариант. В нём count не меняется, значит n или равно нулю или не будет нулевым никогда.
Автор:  Александр Ильин [ Среда, 06 Май, 2009 15:38 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Valery Solovey писал(а):
Да, я про сишный вариант. В нём count не меняется, значит n или равно нулю или не будет нулевым никогда.
Инструкция "--n" внутри while уменьшает значение n на единицу. После входа в цикл count уже не при делах.
Автор:  Geniepro [ Среда, 06 Май, 2009 15:40 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Valery Solovey писал(а):
Да, я про сишный вариант. В нём count не меняется, значит n или равно нулю или не будет нулевым никогда.

Ну как же? n постоянно уменьшается же, значит этот цикл проработает конечное время...

Вообще же это из серии какой длины нужна верёвка, что бы выстрелить себе в голову с максимальным разрушительным эффектом...
Автор:  Valery Solovey [ Среда, 06 Май, 2009 15:43 ]
Заголовок сообщения:  Re: Duff's device vs Дейкстра
Только теперь заметил, оказывается n инициализируется вне цикла.
Страница 1 из 2 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/