Автор |
Сообщение |
|
|
Заголовок сообщения: |
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 тиков на ветку в цикле Так понятнее?
[quote="dynamic-wind"]Если современный ЦП в цикле предсказывает ветвления линейного кейса, то он точно также предскажет их для дерева. А в проходе (достаточно большого и сбалансированного) дерева их будет логарифмически меньше, так что и время должно быть меньше. Какие еще эффекты возможны?[/quote] Я ж с этим и не спорю. Я хотел только сказать, что когда CASE используется в цикле, то время на исполнение ветки CASE никаким образом не оптимизированного CASE становится меньше и добавка быстродействия от оптимизации становится гораздо меньше по абсолютной величине для каждой ветки и ощутимый эффект от оптимизации CASE в программе появится только при очень большом количестве веток. [code]: 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 тиков на ветку в цикле [/code] Так понятнее?
|
|
|
|
Добавлено: Пн авг 08, 2011 09:50 |
|
|
|
|
|
Заголовок сообщения: |
Re: быстрый CASE |
|
|
chess писал(а): Сейчас аппаратура другая, если case работает в цикле там времена вообще практически не будут отличаться. Все в кэше будет и прогноз ветвлений даст свое. Сейчас эти оптимизации уже не слишком актуальны(они делались давно, когда железо медленное было). Если современный ЦП в цикле предсказывает ветвления линейного кейса, то он точно также предскажет их для дерева. А в проходе (достаточно большого и сбалансированного) дерева их будет логарифмически меньше, так что и время должно быть меньше. Какие еще эффекты возможны?
[quote="chess"]Сейчас аппаратура другая, если case работает в цикле там времена вообще практически не будут отличаться. Все в кэше будет и прогноз ветвлений даст свое. Сейчас эти оптимизации уже не слишком актуальны(они делались давно, когда железо медленное было).[/quote] Если современный ЦП в цикле предсказывает ветвления линейного кейса, то он точно также предскажет их для дерева. А в проходе (достаточно большого и сбалансированного) дерева их будет логарифмически меньше, так что и время[i] должно быть [/i] меньше. Какие еще эффекты возможны?
|
|
|
|
Добавлено: Вс авг 07, 2011 14:34 |
|
|
|
|
|
Заголовок сообщения: |
Re: быстрый CASE |
|
|
chess писал(а): При разовом исполнении разница в 3,5 раза выльется по отношению ко всей программе в тысячные доли процента, а при исполнении в цикле время исполнения будет не в 3,5 раза больше, а на 1-2% больше из-за современной аппаратуры Всё не настолько хорошо в соверменной аппаратуре, кроме того, тут вот процессоростроители есть, не уверен, что у них там предсказание ветвлений, да и пример из темы про rorelf, если дать себе труд прочесть (хоть бы и не разбираясь) свидетельствует об обратном.
[quote="chess"]При разовом исполнении разница в 3,5 раза выльется по отношению ко всей программе в тысячные доли процента, а при исполнении в цикле время исполнения будет не в 3,5 раза больше, а на 1-2% больше из-за современной аппаратуры[/quote] Всё не настолько хорошо в соверменной аппаратуре, кроме того, тут вот процессоростроители есть, не уверен, что у них там предсказание ветвлений, да и пример из темы про rorelf, если дать себе труд прочесть (хоть бы и не разбираясь) свидетельствует об обратном.
|
|
|
|
Добавлено: Вс авг 07, 2011 11:51 |
|
|
|
|
|
Заголовок сообщения: |
Re: быстрый CASE |
|
|
вопрос писал(а): Ничего себе "всего" - люди ради 20% идут на нарушение всех стандартов, а тут разы! Вы не поняли следующее chess писал(а): Сейчас эти оптимизации уже не слишком актуальны(они делались давно, когда железо медленное было). При разовом исполнении разница в 3,5 раза выльется по отношению ко всей программе в тысячные доли процента, а при исполнении в цикле время исполнения будет не в 3,5 раза больше, а на 1-2% больше из-за современной аппаратуры.
[quote="вопрос"]Ничего себе "всего" - люди ради 20% идут на нарушение всех стандартов, а тут разы![/quote] Вы не поняли следующее[quote="chess"]Сейчас эти оптимизации уже не слишком актуальны(они делались давно, когда железо медленное было).[/quote] При разовом исполнении разница в 3,5 раза выльется по отношению ко всей программе в тысячные доли процента, а при исполнении в цикле время исполнения будет не в 3,5 раза больше, а на 1-2% больше из-за современной аппаратуры.
|
|
|
|
Добавлено: Вс авг 07, 2011 05:47 |
|
|
|
|
|
Заголовок сообщения: |
Re: быстрый CASE |
|
|
_Harry писал(а): chess писал(а): по мере увеличения количества веток кратность ускорения будет возрастать, Странно что первый от 213-го отличается всего в 3,5 раза. Получается что если case-ов штук 30 или меньше то нет особого смысла в оптимизации Ничего себе "всего" - люди ради 20% идут на нарушение всех стандартов, а тут разы!
[quote="_Harry"][quote="chess"]по мере увеличения количества веток кратность ускорения будет возрастать,[/quote]Странно что первый от 213-го отличается всего в 3,5 раза. Получается что если case-ов штук 30 или меньше то нет особого смысла в оптимизации :?:[/quote]Ничего себе "всего" - люди ради 20% идут на нарушение всех стандартов, а тут разы!
|
|
|
|
Добавлено: Сб авг 06, 2011 14:50 |
|
|
|
|
|
Заголовок сообщения: |
Re: быстрый CASE |
|
|
_Harry писал(а): Странно что первый от 213-го отличается всего в 3,5 раза. Получается что если case-ов штук 30 или меньше то нет особого смысла в оптимизации Сейчас аппаратура другая, если case работает в цикле там времена вообще практически не будут отличаться. Все в кэше будет и прогноз ветвлений даст свое. Сейчас эти оптимизации уже не слишком актуальны(они делались давно, когда железо медленное было).
[quote="_Harry"]Странно что первый от 213-го отличается всего в 3,5 раза. Получается что если case-ов штук 30 или меньше то нет особого смысла в оптимизации [/quote] Сейчас аппаратура другая, если case работает в цикле там времена вообще практически не будут отличаться. Все в кэше будет и прогноз ветвлений даст свое. Сейчас эти оптимизации уже не слишком актуальны(они делались давно, когда железо медленное было).
|
|
|
|
Добавлено: Пт авг 05, 2011 20:53 |
|
|
|
|
|
Заголовок сообщения: |
Re: быстрый CASE |
|
|
chess писал(а): по мере увеличения количества веток кратность ускорения будет возрастать, Странно что первый от 213-го отличается всего в 3,5 раза. Получается что если case-ов штук 30 или меньше то нет особого смысла в оптимизации
[quote="chess"]по мере увеличения количества веток кратность ускорения будет возрастать,[/quote]Странно что первый от 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 от их числа.
[quote="_Harry"]Как бы проверить насколько это ускоряет код по сравнению с "тупым" case-ом.[/quote] Можно сравнить с SPF. [code]: 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 )[/code] там будет разброс меньше даже если принять, что самое малое время будет такое-же как в SPF ( 207 ) ( 300 ) по мере увеличения количества веток кратность ускорения будет возрастать, так как время там будет расти не линейно от числа веток как в SPF, а по логарифму по основанию 2 от их числа.
|
|
|
|
Добавлено: Пт авг 05, 2011 15:21 |
|
|
|
|
|
Заголовок сообщения: |
Re: быстрый CASE |
|
|
chess писал(а): Довольно серьезно все.
Как бы проверить насколько это ускоряет код по сравнению с "тупым" case-ом.
[quote="chess"]Довольно серьезно все. [/quote]Как бы проверить насколько это ускоряет код по сравнению с "тупым" case-ом. :?:
|
|
|
|
Добавлено: Пт авг 05, 2011 14:22 |
|
|
|
|
|
Заголовок сообщения: |
Re: быстрый CASE |
|
|
Да, предварительная сортировка есть. А потом дихотомический поиск в коде и наконец перебор оставшихся 4-5 вариантов. Довольно серьезно все.
Да, предварительная сортировка есть. А потом дихотомический поиск в коде и наконец перебор оставшихся 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 ; ; }
[code] ; 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 ; ; } [/code]
|
|
|
|
Добавлено: Чт авг 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; }
Что-то иерархии не видно, и все-таки непонятно насчет предварительной сортировки.
Сделайте вот так. Для прояснения картины: [code] { 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; }[/code]
|
|
|
|
Добавлено: Чт авг 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 ; ; }
[code] 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; }[/code] [code]?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 ; ; } [/code]
|
|
|
|
Добавлено: Чт авг 04, 2011 16:22 |
|
|
|
|
|
Заголовок сообщения: |
Re: быстрый CASE |
|
|
вопрос писал(а): можно посмотреть Всего было 9 значений в CASE, разделили диапазон значений на 5-ки, получилось два поддиапазона 5 и 4, проанализировали в какой диапазон идти, в каждом из поддиапазонов сделали последовательный перебор. Критерий деления - 5 штук значений. Значит если значений меньше пяти делить диапазон не надо. Ну в маш. коде может и так, а в форт-коде, будет не так. Правда при таком подходе при стандартной структуре CASE в форте наверно надо будет делить где-то от 12 до 16 штук. Никакой 'крутой' оптимизации тут нет. Можно с натяжкой это назвать формированием кода дихотомического поиска с ограничением интервала поиска снизу(до 5), 1. Вот если расположить параметры CASE не в отсортированном виде, а в произвольном, интересно проведет сортировку или нет? 2. И если число параметров в CASE превысит 5-ть хотя-бы в 4 раза, то произойдет-ли формирование иерархии или будет последовательный просмотр кусков по 5-ть параметров?
[quote="вопрос"]можно посмотреть[/quote] Всего было 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); ;
[quote="chess"]А если выходит, то что.[/quote] тогда DEFAULT [quote="chess"]А если все пары значений друг от друга сильно отличаются, из-за чего таблицу переходов нельзя применить из-за ее огромного размера[/quote] можно посмотреть [code]#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); } [/code] ассемблерный выход [code] ; 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); ; [/code]
|
|
|
|
Добавлено: Чт авг 04, 2011 13:20 |
|
|
|
|