Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 15:30

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 25 ]  На страницу Пред.  1, 2
Автор Сообщение
 Заголовок сообщения: Re: быстрый CASE
СообщениеДобавлено: Чт авг 04, 2011 19:53 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Да, предварительная сортировка есть. А потом дихотомический поиск в коде и наконец перебор оставшихся 4-5 вариантов. Довольно серьезно все.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: быстрый CASE
СообщениеДобавлено: Пт авг 05, 2011 14:22 
Не в сети
Аватара пользователя

Зарегистрирован: Пт дек 26, 2008 21:16
Сообщения: 412
Откуда: Великий Новгород
Благодарил (а): 9 раз.
Поблагодарили: 4 раз.
chess писал(а):
Довольно серьезно все.
Как бы проверить насколько это ускоряет код по сравнению с "тупым" case-ом. :?:


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: быстрый CASE
СообщениеДобавлено: Пт авг 05, 2011 15:21 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
_Harry писал(а):
Как бы проверить насколько это ускоряет код по сравнению с "тупым" case-ом.

Можно сравнить с SPF.
Код:
: case
CASE
1     OF 1     ENDOF
2     OF 2     ENDOF
3     OF 3     ENDOF
4     OF 4     ENDOF
5     OF 5     ENDOF
6     OF 6     ENDOF
7     OF 7     ENDOF
8     OF 8     ENDOF
9     OF 9     ENDOF
10    OF 10    ENDOF
11    OF 11    ENDOF
12    OF 12    ENDOF
13    OF 13    ENDOF
14    OF 14    ENDOF
15    OF 15    ENDOF
16    OF 16    ENDOF
17    OF 17    ENDOF
18    OF 18    ENDOF
19    OF 19    ENDOF
20    OF 20    ENDOF
21    OF 21    ENDOF
12    OF 1     ENDOF
22    OF 2     ENDOF
32    OF 3     ENDOF
42    OF 4     ENDOF
52    OF 5     ENDOF
62    OF 6     ENDOF
72    OF 7     ENDOF
82    OF 8     ENDOF
92    OF 9     ENDOF
102   OF 10    ENDOF
112   OF 11    ENDOF
122   OF 12    ENDOF
132   OF 13    ENDOF
142   OF 14    ENDOF
152   OF 15    ENDOF
162   OF 16    ENDOF
172   OF 17    ENDOF
182   OF 18    ENDOF
192   OF 19    ENDOF
202   OF 20    ENDOF
212   OF 21    ENDOF
ENDCASE ;

: tst1   1 case ; METER tst1   ( 207 )
: tst2 212 case ; METER tst2   ( 711 )

там будет разброс меньше даже если принять, что самое малое время будет такое-же как в SPF
( 207 )
( 300 )
по мере увеличения количества веток кратность ускорения будет возрастать, так как время там будет
расти не линейно от числа веток как в SPF, а по логарифму по основанию 2 от их числа.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: быстрый CASE
СообщениеДобавлено: Пт авг 05, 2011 18:24 
Не в сети
Аватара пользователя

Зарегистрирован: Пт дек 26, 2008 21:16
Сообщения: 412
Откуда: Великий Новгород
Благодарил (а): 9 раз.
Поблагодарили: 4 раз.
chess писал(а):
по мере увеличения количества веток кратность ускорения будет возрастать,
Странно что первый от 213-го отличается всего в 3,5 раза. Получается что если case-ов штук 30 или меньше то нет особого смысла в оптимизации :?:


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: быстрый CASE
СообщениеДобавлено: Пт авг 05, 2011 20:53 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
_Harry писал(а):
Странно что первый от 213-го отличается всего в 3,5 раза. Получается что если case-ов штук 30 или меньше то нет особого смысла в оптимизации

Сейчас аппаратура другая, если case работает в цикле там времена вообще практически не будут отличаться. Все в кэше будет и прогноз ветвлений даст свое. Сейчас эти оптимизации
уже не слишком актуальны(они делались давно, когда железо медленное было).

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: быстрый CASE
СообщениеДобавлено: Сб авг 06, 2011 14:50 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
_Harry писал(а):
chess писал(а):
по мере увеличения количества веток кратность ускорения будет возрастать,
Странно что первый от 213-го отличается всего в 3,5 раза. Получается что если case-ов штук 30 или меньше то нет особого смысла в оптимизации :?:
Ничего себе "всего" - люди ради 20% идут на нарушение всех стандартов, а тут разы!


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: быстрый CASE
СообщениеДобавлено: Вс авг 07, 2011 05:47 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
вопрос писал(а):
Ничего себе "всего" - люди ради 20% идут на нарушение всех стандартов, а тут разы!

Вы не поняли следующее
chess писал(а):
Сейчас эти оптимизации
уже не слишком актуальны(они делались давно, когда железо медленное было).

При разовом исполнении разница в 3,5 раза выльется по отношению ко всей программе в тысячные доли процента, а при исполнении в цикле время исполнения будет не в 3,5 раза больше, а на 1-2% больше из-за современной аппаратуры.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: быстрый CASE
СообщениеДобавлено: Вс авг 07, 2011 11:51 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
chess писал(а):
При разовом исполнении разница в 3,5 раза выльется по отношению ко всей программе в тысячные доли процента, а при исполнении в цикле время исполнения будет не в 3,5 раза больше, а на 1-2% больше из-за современной аппаратуры

Всё не настолько хорошо в соверменной аппаратуре, кроме того, тут вот процессоростроители есть, не уверен, что у них там предсказание ветвлений, да и пример из темы про rorelf, если дать себе труд прочесть (хоть бы и не разбираясь) свидетельствует об обратном.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: быстрый CASE
СообщениеДобавлено: Вс авг 07, 2011 14:34 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июн 25, 2009 11:12
Сообщения: 412
Благодарил (а): 41 раз.
Поблагодарили: 8 раз.
chess писал(а):
Сейчас аппаратура другая, если case работает в цикле там времена вообще практически не будут отличаться. Все в кэше будет и прогноз ветвлений даст свое. Сейчас эти оптимизации
уже не слишком актуальны(они делались давно, когда железо медленное было).

Если современный ЦП в цикле предсказывает ветвления линейного кейса, то он точно также предскажет их для дерева. А в проходе (достаточно большого и сбалансированного) дерева их будет логарифмически меньше, так что и время должно быть меньше.
Какие еще эффекты возможны?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: быстрый CASE
СообщениеДобавлено: Пн авг 08, 2011 09:50 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
dynamic-wind писал(а):
Если современный ЦП в цикле предсказывает ветвления линейного кейса, то он точно также предскажет их для дерева. А в проходе (достаточно большого и сбалансированного) дерева их будет логарифмически меньше, так что и время должно быть меньше.
Какие еще эффекты возможны?

Я ж с этим и не спорю. Я хотел только сказать, что когда CASE используется в цикле, то время на исполнение ветки CASE никаким образом не оптимизированного CASE становится меньше и добавка быстродействия от оптимизации становится гораздо меньше
по абсолютной величине для каждой ветки и ощутимый эффект от оптимизации CASE в программе появится только при очень большом количестве веток.
Код:
: case
CASE
1  OF 1  ENDOF
2  OF 2  ENDOF
3  OF 3  ENDOF
4  OF 4  ENDOF
5  OF 5  ENDOF
6  OF 6  ENDOF
7  OF 7  ENDOF
8  OF 8  ENDOF
9  OF 9  ENDOF
10 OF 10 ENDOF
11 OF 11 ENDOF
12 OF 12 ENDOF
13 OF 13 ENDOF
14 OF 14 ENDOF
15 OF 15 ENDOF
16 OF 16 ENDOF
17 OF 17 ENDOF
18 OF 18 ENDOF
19 OF 19 ENDOF
20 OF 20 ENDOF
21 OF 21 ENDOF
12 OF 12 ENDOF
22 OF 22 ENDOF
23 OF 23 ENDOF
24 OF 24 ENDOF
25 OF 25 ENDOF
26 OF 26 ENDOF
27 OF 27 ENDOF
28 OF 28 ENDOF
29 OF 29 ENDOF
30 OF 30 ENDOF
31 OF 31 ENDOF
32 OF 32 ENDOF
33 OF 33 ENDOF
34 OF 34 ENDOF
35 OF 35 ENDOF
36 OF 36 ENDOF
37 OF 37 ENDOF
38 OF 38 ENDOF
39 OF 39 ENDOF
40 OF 40 ENDOF
41 OF 41 ENDOF
42 OF 42 ENDOF
43 OF 43 ENDOF
44 OF 44 ENDOF
45 OF 45 ENDOF
46 OF 46 ENDOF
47 OF 47 ENDOF
48 OF 48 ENDOF
49 OF 49 ENDOF
50 OF 50 ENDOF
ENDCASE ;

: tst1   1 case ; METER tst1  ( 153 18  ) (837-153)/50 = 14 тиков на ветку при разовом исполнении
: tst2  50 case ; METER tst2  ( 837 99  ) ( 99 - 18 )/50 = 1,6 тиков на ветку в цикле

Так понятнее?

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 25 ]  На страницу Пред.  1, 2

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 20


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB