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

...
Google Search
Forth-FAQ Spy Grafic

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




Ответить
Имя пользователя:
Заголовок:
Текст сообщения:
Введите текст вашего сообщения. Длина сообщения в символах не более: 60000

Размер шрифта:
Цвет шрифта
Настройки:
BBCode ВКЛЮЧЕН
[img] ВЫКЛЮЧЕН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЕН
Смайлики ВЫКЛЮЧЕНЫ
Отключить в этом сообщении BBCode
Не преобразовывать адреса URL в ссылки
Вопрос
Теперь гостю придется вводить здесь пароль. Не от своей учетной записи, а ПАРОЛЬ ДЛЯ ГОСТЯ, получить который можно после регистрации на форуме через ЛС.:
Этот вопрос предназначен для выявления и предотвращения автоматических регистраций.
   

Обзор темы - быстрый CASE
Автор Сообщение
  Заголовок сообщения:  Re: быстрый CASE  Ответить с цитатой
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 тиков на ветку в цикле

Так понятнее?
Сообщение Добавлено: Пн авг 08, 2011 09:50
  Заголовок сообщения:  Re: быстрый CASE  Ответить с цитатой
chess писал(а):
Сейчас аппаратура другая, если case работает в цикле там времена вообще практически не будут отличаться. Все в кэше будет и прогноз ветвлений даст свое. Сейчас эти оптимизации
уже не слишком актуальны(они делались давно, когда железо медленное было).

Если современный ЦП в цикле предсказывает ветвления линейного кейса, то он точно также предскажет их для дерева. А в проходе (достаточно большого и сбалансированного) дерева их будет логарифмически меньше, так что и время должно быть меньше.
Какие еще эффекты возможны?
Сообщение Добавлено: Вс авг 07, 2011 14:34
  Заголовок сообщения:  Re: быстрый CASE  Ответить с цитатой
chess писал(а):
При разовом исполнении разница в 3,5 раза выльется по отношению ко всей программе в тысячные доли процента, а при исполнении в цикле время исполнения будет не в 3,5 раза больше, а на 1-2% больше из-за современной аппаратуры

Всё не настолько хорошо в соверменной аппаратуре, кроме того, тут вот процессоростроители есть, не уверен, что у них там предсказание ветвлений, да и пример из темы про rorelf, если дать себе труд прочесть (хоть бы и не разбираясь) свидетельствует об обратном.
Сообщение Добавлено: Вс авг 07, 2011 11:51
  Заголовок сообщения:  Re: быстрый CASE  Ответить с цитатой
вопрос писал(а):
Ничего себе "всего" - люди ради 20% идут на нарушение всех стандартов, а тут разы!

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

При разовом исполнении разница в 3,5 раза выльется по отношению ко всей программе в тысячные доли процента, а при исполнении в цикле время исполнения будет не в 3,5 раза больше, а на 1-2% больше из-за современной аппаратуры.
Сообщение Добавлено: Вс авг 07, 2011 05:47
  Заголовок сообщения:  Re: быстрый CASE  Ответить с цитатой
_Harry писал(а):
chess писал(а):
по мере увеличения количества веток кратность ускорения будет возрастать,
Странно что первый от 213-го отличается всего в 3,5 раза. Получается что если case-ов штук 30 или меньше то нет особого смысла в оптимизации :?:
Ничего себе "всего" - люди ради 20% идут на нарушение всех стандартов, а тут разы!
Сообщение Добавлено: Сб авг 06, 2011 14:50
  Заголовок сообщения:  Re: быстрый CASE  Ответить с цитатой
_Harry писал(а):
Странно что первый от 213-го отличается всего в 3,5 раза. Получается что если case-ов штук 30 или меньше то нет особого смысла в оптимизации

Сейчас аппаратура другая, если case работает в цикле там времена вообще практически не будут отличаться. Все в кэше будет и прогноз ветвлений даст свое. Сейчас эти оптимизации
уже не слишком актуальны(они делались давно, когда железо медленное было).
Сообщение Добавлено: Пт авг 05, 2011 20:53
  Заголовок сообщения:  Re: быстрый CASE  Ответить с цитатой
chess писал(а):
по мере увеличения количества веток кратность ускорения будет возрастать,
Странно что первый от 213-го отличается всего в 3,5 раза. Получается что если case-ов штук 30 или меньше то нет особого смысла в оптимизации :?:
Сообщение Добавлено: Пт авг 05, 2011 18:24
  Заголовок сообщения:  Re: быстрый CASE  Ответить с цитатой
_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 от их числа.
Сообщение Добавлено: Пт авг 05, 2011 15:21
  Заголовок сообщения:  Re: быстрый CASE  Ответить с цитатой
chess писал(а):
Довольно серьезно все.
Как бы проверить насколько это ускоряет код по сравнению с "тупым" case-ом. :?:
Сообщение Добавлено: Пт авг 05, 2011 14:22
  Заголовок сообщения:  Re: быстрый CASE  Ответить с цитатой
Да, предварительная сортировка есть. А потом дихотомический поиск в коде и наконец перебор оставшихся 4-5 вариантов. Довольно серьезно все.
Сообщение Добавлено: Чт авг 04, 2011 19:53
  Заголовок сообщения:  Re: быстрый CASE  Ответить с цитатой
Код:
   ;       switch(U)
   ;   
?live1@16: ; EAX = U
   cmp       eax,1000
   jg        short @25
   je        @14
   cmp       eax,70
   jg        short @26
   je        @19
   cmp       eax,10
   jg        short @27
   je        @22
   sub       eax,1
   jb        @24
   sub       eax,4
   je        @23
   jmp       @2
@27:
   sub       eax,20
   je        @21
   sub       eax,5
   je        @20
   jmp       @2
@26:
   sub       eax,190
   je        @18
   sub       eax,20
   je        @17
   sub       eax,60
   je        @16
   sub       eax,220
   je        @15
   jmp       @2
@25:
   cmp       eax,100990
   jg        short @28
   je        @8
   cmp       eax,5000
   jg        short @29
   je        @11
   sub       eax,2190
   je        @13
   sub       eax,300
   je        @12
   jmp       @2
@29:
   sub       eax,21000
   je        short @10
   sub       eax,29002
   je        @9
   jmp       @2
@28:
   sub       eax,225000
   je        @7
   sub       eax,775000
   je        short @6
   sub       eax,1100990
   je        short @5
   sub       eax,18899010
   je        short @4
   jmp       @2
   ;   
   ;         {
   ;         
   ;         case(0):        A = 100; break;
   ;   
?live1@32: ;
@24:
   mov       eax,100
   jmp       @30
   ;   
   ;         case(21000000): A = 101; break;
   ;   
@4:
   mov       eax,101
   jmp       @30
   ;   
   ;         case(70):       A = 102; break;
   ;   
@19:
   mov       eax,102
   jmp       @30
   ;   
   ;         case(2100990):  A = 103; break;
   ;   
@5:
   mov       eax,103
   jmp       short @30
   ;   
   ;         case(10):       A = 104; break;
   ;   
@22:
   mov       eax,104
   jmp       short @30
   ;   
   ;         case(490):      A = 105; break;
   ;   
@15:
   mov       eax,105
   jmp       short @30
   ;   
   ;         case(21000):    A = 106; break;
   ;   
@10:
   mov       eax,106
   jmp       short @30
   ;   
   ;         case(190):      A = 107; break;
   ;   
@18:
   mov       eax,107
   jmp       short @30
   ;   
   ;         case(5000):     A = 108; break;
   ;   
@11:
   mov       eax,108
   jmp       short @30
   ;   
   ;         case(20):       A = 109; break;
   ;   
@21:
   mov       eax,109
   jmp       short @30
   ;   
   ;         case(100990):   A = 110; break;
   ;   
@8:
   mov       eax,110
   jmp       short @30
   ;   
   ;         case(1000):     A = 111; break;
   ;   
@14:
   mov       eax,111
   jmp       short @30
   ;   
   ;         case(1000000):  A = 112; break;
   ;   
@6:
   mov       eax,112
   jmp       short @30
   ;   
   ;         case(2190):     A = 113; break;
   ;   
@13:
   mov       eax,113
   jmp       short @30
   ;   
   ;         case(210):      A = 114; break;
   ;   
@17:
   mov       eax,114
   jmp       short @30
   ;   
   ;         case(2490):     A = 115; break;
   ;   
@12:
   mov       eax,115
   jmp       short @30
   ;   
   ;         case(270):      A = 116; break;
   ;   
@16:
   mov       eax,116
   jmp       short @30
   ;   
   ;         case(225000):   A = 117; break;
   ;   
@7:
   mov       eax,117
   jmp       short @30
   ;   
   ;         case(25):       A = 118; break;
   ;   
@20:
   mov       eax,118
   jmp       short @30
   ;   
   ;         case(5):        A = 119; break;
   ;   
@23:
   mov       eax,119
   jmp       short @30
   ;   
   ;         case(50002):    A = 120; break;
   ;   
@9:
   mov       eax,120
   jmp       short @30
   ;   
   ;         default: A = 0;
   ;   
@2:
   xor       eax,eax
   ;   
   ;         }
Сообщение Добавлено: Чт авг 04, 2011 16:47
  Заголовок сообщения:  Re: быстрый CASE  Ответить с цитатой
Что-то иерархии не видно, и все-таки непонятно насчет предварительной сортировки.

Сделайте вот так. Для прояснения картины:
Код:
      {
      case(0):        A = 100; break;
      case(21000000): A = 101; break;
      case(70):       A = 102; break;
      case(2100990):  A = 103; break;
      case(10):       A = 104; break;
      case(490):      A = 105; break;
      case(21000):    A = 106; break;
      case(190):      A = 107; break;
      case(5000):     A = 108; break;
      case(20):       A = 109; break;
      case(100990):   A = 110; break;
      case(1000):     A = 111; break;
      case(1000000):  A = 112; break;
      case(2190):     A = 113; break;
      case(210):      A = 114; break;
      case(2490):     A = 115; break;
      case(270):      A = 116; break;
      case(225000):   A = 117; break;
      case(25):       A = 118; break;
      case(5):        A = 119; break;
      case(50002):    A = 120; break;
      default: A = 0;
      }
Сообщение Добавлено: Чт авг 04, 2011 16:41
  Заголовок сообщения:  Re: быстрый CASE  Ответить с цитатой
Код:
    switch(U)
      {
      case(0): A = 100; break;
      case(10): A = 101; break;
      case(70): A = 102; break;
      case(190): A = 103; break;
      case(490): A = 104; break;
      case(1000): A = 105; break;
      case(5000): A = 106; break;
      case(100990): A = 107; break;
      case(1000000): A = 108; break;
      case(20): A = 100; break;
      case(210): A = 101; break;
      case(270): A = 102; break;
      case(2190): A = 103; break;
      case(2490): A = 104; break;
      case(21000): A = 105; break;
      case(25000): A = 106; break;
      case(2100990): A = 107; break;
      case(21000000): A = 108; break;
      default: A = 0;
      }

Код:
?live1@16: ; EAX = U
@1:
   cmp       eax,2190
   jg        short @22
   je        @12
   cmp       eax,190
   jg        short @23
   je        @17
   sub       eax,1
   jb        @21
   sub       eax,9
   je        @20
   sub       eax,10
   je        @19
   sub       eax,50
   je        @18
   jmp       @2
@23:
   sub       eax,210
   je        @16
   sub       eax,60
   je        @15
   sub       eax,220
   je        short @14
   sub       eax,510
   je        short @13
   jmp       @2
@22:
   cmp       eax,100990
   jg        short @24
   je        short @7
   sub       eax,2490
   je        @11
   sub       eax,2510
   je        short @10
   sub       eax,16000
   je        @9
   sub       eax,4000
   je        @8
   jmp       @2
@24:
   sub       eax,1000000
   je        short @6
   sub       eax,1100990
   je        short @5
   sub       eax,18899010
   je        short @4
   jmp       short @2
   ;   
   ;         {
   ;         case(0): A = 100; break;
   ;   
?live1@32: ;
@21:
   mov       eax,100
   jmp       short @25
   ;   
   ;         case(10): A = 101; break;
   ;   
@20:
   mov       eax,101
   jmp       short @25
   ;   
   ;         case(70): A = 102; break;
   ;   
@18:
   mov       eax,102
   jmp       short @25
   ;   
   ;         case(190): A = 103; break;
   ;   
@17:
   mov       eax,103
   jmp       short @25
   ;   
   ;         case(490): A = 104; break;
   ;   
@14:
   mov       eax,104
   jmp       short @25
   ;   
   ;         case(1000): A = 105; break;
   ;   
@13:
   mov       eax,105
   jmp       short @25
   ;   
   ;         case(5000): A = 106; break;
   ;   
@10:
   mov       eax,106
   jmp       short @25
   ;   
   ;         case(100990): A = 107; break;
   ;   
@7:
   mov       eax,107
   jmp       short @25
   ;   
   ;         case(1000000): A = 108; break;
   ;   
@6:
   mov       eax,108
   jmp       short @25
   ;   
   ;         case(20): A = 100; break;
   ;   
@19:
   mov       eax,100
   jmp       short @25
   ;   
   ;         case(210): A = 101; break;
   ;   
@16:
   mov       eax,101
   jmp       short @25
   ;   
   ;         case(270): A = 102; break;
   ;   
@15:
   mov       eax,102
   jmp       short @25
   ;   
   ;         case(2190): A = 103; break;
   ;   
@12:
   mov       eax,103
   jmp       short @25
   ;   
   ;         case(2490): A = 104; break;
   ;   
@11:
   mov       eax,104
   jmp       short @25
   ;   
   ;         case(21000): A = 105; break;
   ;   
@9:
   mov       eax,105
   jmp       short @25
   ;   
   ;         case(25000): A = 106; break;
   ;   
@8:
   mov       eax,106
   jmp       short @25
   ;   
   ;         case(2100990): A = 107; break;
   ;   
@5:
   mov       eax,107
   jmp       short @25
   ;   
   ;         case(21000000): A = 108; break;
   ;   
@4:
   mov       eax,108
   jmp       short @25
   ;   
   ;         default: A = 0;
   ;   
@2:
   xor       eax,eax
   ;   
   ;         }
Сообщение Добавлено: Чт авг 04, 2011 16:22
  Заголовок сообщения:  Re: быстрый CASE  Ответить с цитатой
вопрос писал(а):
можно посмотреть

Всего было 9 значений в CASE,
разделили диапазон значений на 5-ки,
получилось два поддиапазона 5 и 4, проанализировали в какой диапазон идти,
в каждом из поддиапазонов сделали последовательный перебор.
Критерий деления - 5 штук значений.
Значит если значений меньше пяти делить диапазон не надо.
Ну в маш. коде может и так, а в форт-коде, будет не так.
Правда при таком подходе при стандартной структуре CASE в форте наверно
надо будет делить где-то от 12 до 16 штук.
Никакой 'крутой' оптимизации тут нет.
Можно с натяжкой это назвать формированием кода дихотомического поиска с ограничением интервала поиска снизу(до 5),

1. Вот если расположить параметры CASE не в отсортированном виде, а в произвольном,
интересно проведет сортировку или нет?
2. И если число параметров в CASE превысит 5-ть хотя-бы в 4 раза, то произойдет-ли формирование иерархии или будет
последовательный просмотр кусков по 5-ть параметров?
Сообщение Добавлено: Чт авг 04, 2011 14:52
  Заголовок сообщения:  Re: быстрый CASE  Ответить с цитатой
chess писал(а):
А если выходит, то что.

тогда DEFAULT
chess писал(а):
А если все пары значений друг от друга сильно отличаются, из-за чего таблицу переходов нельзя применить из-за ее огромного размера

можно посмотреть
Код:
#include <stdio.h>


int main(void)
    {
    int A,U;
   
    switch(U)
      {
      case(0): A = 100; break;
      case(10): A = 101; break;
      case(70): A = 102; break;
      case(190): A = 103; break;
      case(490): A = 104; break;
      case(1000): A = 105; break;
      case(5000): A = 106; break;
      case(100990): A = 107; break;
      case(1000000): A = 108; break;
      default: A = 0;
      }
    printf("%d",A);
    }

ассемблерный выход
Код:
   ;   int main(void)
   ;   
   push      ebp
   mov       ebp,esp
   ;   
   ;       {
   ;       int A,U;
   ;      
   ;       switch(U)
   ;   
?live1@16: ; EAX = U
@1:
   cmp       eax,490
   jg        short @13
   je        short @8
   sub       eax,1
   jb        short @12
   sub       eax,9
   je        short @11
   sub       eax,60
   je        short @10
   sub       eax,120
   je        short @9
   jmp       short @2
@13:
   sub       eax,1000
   je        short @7
   sub       eax,4000
   je        short @6
   sub       eax,95990
   je        short @5
   sub       eax,899010
   je        short @4
   jmp       short @2
   ;   
   ;         {
   ;         case(0): A = 100; break;
   ;   
?live1@32: ;
@12:
   mov       eax,100
   jmp       short @14
   ;   
   ;         case(10): A = 101; break;
   ;   
@11:
   mov       eax,101
   jmp       short @14
   ;   
   ;         case(70): A = 102; break;
   ;   
@10:
   mov       eax,102
   jmp       short @14
   ;   
   ;         case(190): A = 103; break;
   ;   
@9:
   mov       eax,103
   jmp       short @14
   ;   
   ;         case(490): A = 104; break;
   ;   
@8:
   mov       eax,104
   jmp       short @14
   ;   
   ;         case(1000): A = 105; break;
   ;   
@7:
   mov       eax,105
   jmp       short @14
   ;   
   ;         case(5000): A = 106; break;
   ;   
@6:
   mov       eax,106
   jmp       short @14
   ;   
   ;         case(100990): A = 107; break;
   ;   
@5:
   mov       eax,107
   jmp       short @14
   ;   
   ;         case(1000000): A = 108; break;
   ;   
@4:
   mov       eax,108
   jmp       short @14
   ;   
   ;         default: A = 0;
   ;   
@2:
   xor       eax,eax
   ;   
   ;         }
   ;       printf("%d",A);
   ;   
Сообщение Добавлено: Чт авг 04, 2011 13:20

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


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