Forth http://fforum.winglion.ru/ |
|
*определить количество значащих байт в числе http://fforum.winglion.ru/viewtopic.php?f=19&t=1213 |
Страница 1 из 2 |
Автор: | mOleg [ Чт мар 20, 2008 14:24 ] |
Заголовок сообщения: | *определить количество значащих байт в числе |
Как можно определить наиболее быстрым образом текущую разрядность числа, проще говоря, сколько значащих байт в числе 1-2-3-4 ?8) |
Автор: | Forthware [ Чт мар 20, 2008 15:56 ] |
Заголовок сообщения: | |
mOleg писал(а): как можно определить наиболее быстрым образом текущую разрядность числа, проще говоря, сколько значащих байт в числе 1-2-3-4 ? Вот два варианта. В зависимости от реализации Форта, более быстрым может оказаться либо первый либо второй. В первом меньше ветвлений, во втором код легче оптимизируется.
Код: : SB1 ( u -- +n )
DUP 0xFFFF0000 AND IF 0xFF000000 AND IF 4 ELSE 3 THEN ELSE 0xFF00 AND IF 2 ELSE 1 THEN THEN ; : SB2 ( U -- +N ) DUP 0xFF000000 AND IF DROP 4 EXIT THEN DUP 0xFF0000 AND IF DROP 3 EXIT THEN 0xFF00 AND IF 2 EXIT THEN 1 ; |
Автор: | mOleg [ Чт мар 20, 2008 16:03 ] |
Заголовок сообщения: | |
Forthware писал(а): mOleg писал(а):как можно определить наиболее быстрым образом текущую разрядность числа, проще говоря, сколько значащих байт в числе 1-2-3-4 ?Вот два варианта.
а вот мой: Код: .. DUP 4 LSHIFT OR DUP 2 LSHIFT OR DUP 1 LSHIFT OR 0xFEFEFEFE AND
16 RSHIFT + 8 RSHIFT + 7 AND .. конечно, не факт, что будет быстрее, зато без ветвлений |
Автор: | chess [ Чт мар 20, 2008 18:52 ] |
Заголовок сообщения: | |
mOleg писал(а): кстати, попутно интересная задачка, как можно определить наиболее быстрым образом текущую разрядность числа, проще говоря, сколько значащих байт в числе 1-2-3-4 ?
Cочетание форт+assm дает более простое и быстрое решение Код: REQUIRE IDN ~chess\assm\sp-assm.f
: SB ( u -- +n ) A=H\A 1+ 8 /MOD SWAP IF 1+ THEN ; |
Автор: | Forthware [ Чт мар 20, 2008 19:08 ] |
Заголовок сообщения: | |
chess писал(а): Cочетание форт+assm дает более простое и быстрое решение А вы знаете что BSR может выполняться вплоть до 70 тактов на пентиуме?
И /MOD это тоже быстро??? И без ветвления не обошлось. Нет, этот код даже на новых процах больше полсотни тактов на выполнение плюс риск одного ветвления... У меня было 2 ветвления но всего около десятка тактов на все остальное. У Олега никакого риска вообще. |
Автор: | chess [ Чт мар 20, 2008 19:47 ] |
Заголовок сообщения: | |
Forthware писал(а): А вы знаете что BSR может выполняться вплоть до 70 тактов на пентиуме?
Я уже начал забывать про Пентиумы. У меня Core DUO. Сколько там я не знаю пока - посмотрю где нибудь. А так - знаю. Вообщем надо убрать про быстродействие. Код более компактный это да. А вообще-то я говорил, что СП-Форт поставлен на IA-32 с точки зрения быстродействия не совсем правильно. Структуры данных смешаны с исполняемым кодом. Пространство данных (переменных, массивов и т.д.) должно быть подальше от кода(от словаря). Тут много тонких моментов. Тут проигрыш в 10-ки раз получиться может. В это же время делается выравнивание, от которого в данной ситуации на фоне замедления от смешивания данных и кода толку никакого. Так что не знаю ваш или mОlega или мой вариант быстрее будет. Замеры быстродействия в данной ситуации дело ненадежное. Попробовать сравнить конечно можно через RDTSC - но за результат ручаться нельзя. |
Автор: | Forthware [ Чт мар 20, 2008 20:21 ] |
Заголовок сообщения: | |
mOleg писал(а): .. DUP 4 LSHIFT OR DUP 2 LSHIFT OR DUP 1 LSHIFT OR 0xFEFEFEFE AND Шото оно не работает... Можно рабочую версию?
16 RSHIFT + 8 RSHIFT + 7 AND .. |
Автор: | Forthware [ Чт мар 20, 2008 20:24 ] |
Заголовок сообщения: | |
chess писал(а): Я уже начал забывать про Пентиумы. Ну да, конечно. У меня просто еще с тех пор к BSR "особое" отношение. На Атлоне 10 тактов.chess писал(а): Замеры быстродействия в данной ситуации дело ненадежное. Замерил ваш и мой. Олега пока не рабочий. Получилось что мой в среднем, около 5 раз быстрее. Однако, опять же, гадание на ветвлениях штука не надежная.
|
Автор: | Forthware [ Пт мар 21, 2008 16:41 ] |
Заголовок сообщения: | |
chess писал(а): Код: REQUIRE IDN ~chess\assm\sp-assm.f : SB ( u -- +n ) A=H\A 1+ 8 /MOD SWAP IF 1+ THEN ; Я вот думал, думал, так и не понял зачем все эти сложности. Ведь можно было так сделать: Код: REQUIRE IDN ~chess\assm\sp-assm.f Или нет?
: SB ( u -- +n ) A=H\A 3 RSHIFT 1+ ; |
Автор: | chess [ Пт мар 21, 2008 18:47 ] |
Заголовок сообщения: | |
Forthware писал(а): Я вот думал, думал, так и не понял зачем все эти сложности. Ведь можно было так сделать:
Код: REQUIRE IDN ~chess\assm\sp-assm.f : SB ( u -- +n ) A=H\A 3 RSHIFT 1+ ; Или нет? Ну лучшие-то решения всегда приходят после некоторых раздумий. Я-то когда код писал - не думал вообще, точнее вспомнил, что BSR дает номер старшего бита в числе на 1-цу меньший, а дальше все на автомате - какие сложности. А тут получилось как раз то что надо - деление на степень двойки с округлением результата в большую сторону - красиво однако. То есть из числа надо сначала отнять 1-цу (а BSR как раз это и делает). Только один нюанс - если значащих бит нет вообще - будет все равно 1 байт - ну это впрочем так и надо по задаче. А насчет скорости может так еще чуть быстрее будет: Код: : SB ( u -- +n ) A=H\A 2/ 2/ 2/ 1+ ; Да забыл. Код первого варианта в СПФ: Код: 5A6057 0FBDC0 BSR EAX , EAX
5A605A C1E803 SHR EAX , 3 5A605D 8D4001 LEA EAX , 1 [EAX] 5A6060 C3 RET NEAR Интересно было-бы узнать, что по этому поводу "скажет" VFX. |
Автор: | Forthware [ Пт мар 21, 2008 20:16 ] |
Заголовок сообщения: | |
chess писал(а): Ну лучшие-то решения всегда приходят после некоторых раздумий. chess писал(а): А насчет скорости может так еще чуть быстрее будет: Врядли:Код:: SB ( u -- +n ) A=H\A 2/ 2/ 2/ 1+ ; Код: >see sb 5BB6C0 0FBDC0 BSR EAX , EAX 5BB6C3 D1F8 SAR EAX , 1 5BB6C5 D1F8 SAR EAX , 1 5BB6C7 D1F8 SAR EAX , 1 5BB6C9 8D4001 LEA EAX , 1 [EAX] 5BB6CC C3 RET NEAR Насчет скорости, мой старый вариант: Код: : SB1 ( u -- +n ) Все еще где-то в 1.5-2 раза быстрее за:DUP 0xFFFF0000 AND IF 0xFF000000 AND IF 4 EXIT ELSE 3 EXIT THEN ELSE 0xFF00 AND IF 2 EXIT ELSE 1 EXIT THEN THEN ; Код: REQUIRE IDN ~chess\assm\sp-assm.f Правда, я почти уверен что в моем тестировании он слишком удачно предсказывает ветвления. : SB ( u -- +n ) A=H\A 3 RSHIFT 1+ ; chess писал(а): Интересно было-бы узнать, что по этому поводу "скажет" VFX. Ну, по поводу "REQUIRE IDN ~chess\assm\sp-assm.f" скажет что-то нехорошее, "A=H\A", если хорошо попросить думаю даст BSR EBX, EBX. Остальное:Код: : test 3 RSHIFT 1+ ; ok
see test TEST ( 004ABBE0 C1EB03 ) SHR EBX, 03 ( 004ABBE3 43 ) INC EBX ( 004ABBE4 C3 ) NEXT, ( 5 bytes, 3 instructions ) ok |
Автор: | ygrek [ Сб мар 22, 2008 13:27 ] |
Заголовок сообщения: | |
chess писал(а): А вообще-то я говорил, что СП-Форт поставлен на IA-32 с точки зрения быстродействия не совсем
правильно. Структуры данных смешаны с исполняемым кодом. Пространство данных (переменных, массивов и т.д.) должно быть подальше от кода(от словаря). Тут много тонких моментов. Тут проигрыш в 10-ки раз получиться может. В это же время делается выравнивание, от которого в данной ситуации на фоне замедления от смешивания данных и кода толку никакого. Если вы уверены что есть такой эффект и для вас это важно, то почему бы это не исправить (если есть желание)? |
Автор: | mOleg [ Сб мар 22, 2008 19:40 ] |
Заголовок сообщения: | |
Forthware писал(а): mOleg писал(а):
.. DUP 4 LSHIFT OR DUP 2 LSHIFT OR DUP 1 LSHIFT OR 0xFEFEFEFE AND 16 RSHIFT + 8 RSHIFT + 7 AND .. Шото оно не работает... Можно рабочую версию? оно и не должно работать 8( я не то посчитал. у мя получился подсчет количества ненулевых байт в слове, и то я забыл поставить по DUPу перед каждым RSHIFT ом 8( Рабочие варианты подсчета количества ненулевых байт слова вот: Код: \ подсчет количества ненулевых байт в слове : bytes# ( n --> ) DUP 4 RSHIFT OR DUP 2 RSHIFT OR DUP 1 RSHIFT OR 0x01010101 AND DUP 16 RSHIFT + DUP 8 RSHIFT + 7 AND ; \ это ассемблерный вариант (правда со сдвигом влево, а не вправо как в примере выше). \ подсчет количества ненулевых байт в числе n CODE bytes# ( n --> # ) LEA EDX , [EAX*8] \ решение с LEA интересно тем, LEA EDX , [EDX*2] \ что отсутсвует предварительный MOV OR EAX , EDX \ то есть это замена последовательности: LEA temp , [EAX*4] \ MOV EDX, EAX SHL EAX, # 16 OR EAX , EDX \ понятно, что команда: OR EAX, EDX LEA temp , [EAX*2] \ остается в обоих случаях OR EAX , EDX AND EAX , # 0x80808080 SHR EAX , # 7 MOV EDX , EAX SHR EAX , # 16 ADD EAX , EDX MOV EDX , EAX SHR EAX , # 8 ADD EAX , EDX AND EAX , # 7 RET END-CODE но, как я уже заметил, это не совсем то 8( а вот что получается, если без ветвлений: Код: CREATE bref 0 B, 1 B, 3 B, 3 B,
2 B, 2 B, 3 B, 3 B, 4 B, 4 B, 4 B, 4 B, 4 B, 4 B, 4 B, 4 B, : bytes ( n --> # ) DUP 4 RSHIFT OR DUP 2 RSHIFT OR DUP 1 RSHIFT OR 0x01010101 AND DUP 15 RSHIFT OR DUP 6 RSHIFT OR 0x0F AND bref + B@ ; ассемблерный вариант приводить не буду - всеравно получается громоздко 8( |
Автор: | Forthware [ Сб мар 22, 2008 21:33 ] |
Заголовок сообщения: | |
mOleg писал(а): а вот что получается, если без ветвлений: По грубым прикидкам, получается гдето на 20-25% медленнее за
Код: REQUIRE IDN ~chess\assm\sp-assm.f И где-то в 2.5 раза медленнее за:: SB ( u -- +n ) A=H\A 3 RSHIFT 1+ ; Код: : SB1 ( u -- +n )
DUP 0xFFFF0000 AND IF 0xFF000000 AND IF 4 EXIT ELSE 3 EXIT THEN ELSE 0xFF00 AND IF 2 EXIT ELSE 1 EXIT THEN THEN ; |
Автор: | chess [ Пн мар 24, 2008 19:18 ] |
Заголовок сообщения: | |
Ради интереса сравнил быстродействие Код: REQUIRE IDN ~chess\assm\sp-assm.f и : SB ( u -- +n ) A=H\A 3 RSHIFT 1+ ; Код: : SB1 ( u -- +n ) на CORE 2 DUO.
DUP 0xFFFF0000 AND IF 0xFF000000 AND IF 4 EXIT ELSE 3 EXIT THEN ELSE 0xFF00 AND IF 2 EXIT ELSE 1 EXIT THEN THEN ; получилось абсолютно одинаково, потом на ATHLON 64 получилось SB быстрее чем SB1 на 25%. |
Страница 1 из 2 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |