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); Прыжок в середину "развёрнутого" цикла заменён на дополнительный цикл по остатку от деления. По сравнению с Duff's device больше на 1..8 проверок.
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; |
Автор: | 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 [ 7.21 КБ | Просмотров: 10320 ] |
Автор: | 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; Число проверок ровно на 3 больше, чем в Duff's device.
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 |
Автор: | 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/ |