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

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 30 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: *определить количество значащих байт в числе
СообщениеДобавлено: Чт мар 20, 2008 14:24 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Как можно определить наиболее быстрым образом текущую разрядность числа, проще говоря, сколько значащих байт в числе 1-2-3-4 ?8)

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Последний раз редактировалось mOleg Вс мар 23, 2008 22:01, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 15:56 
Не в сети

Зарегистрирован: Вс дек 02, 2007 17:31
Сообщения: 442
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
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
;


Последний раз редактировалось Forthware Чт мар 20, 2008 16:09, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 16:03 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
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 ..

конечно, не факт, что будет быстрее, зато без ветвлений

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 18:52 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
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 ;

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 19:08 
Не в сети

Зарегистрирован: Вс дек 02, 2007 17:31
Сообщения: 442
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
chess писал(а):
Cочетание форт+assm дает более простое и быстрое решение
А вы знаете что BSR может выполняться вплоть до 70 тактов на пентиуме? :?
И /MOD это тоже быстро??? :shock:
И без ветвления не обошлось. :)
Нет, этот код даже на новых процах больше полсотни тактов на выполнение плюс риск одного ветвления...
У меня было 2 ветвления но всего около десятка тактов на все остальное. У Олега никакого риска вообще.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 19:47 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Forthware писал(а):
А вы знаете что BSR может выполняться вплоть до 70 тактов на пентиуме?

Я уже начал забывать про Пентиумы. У меня Core DUO. Сколько там я не знаю пока - посмотрю где нибудь. А так - знаю. Вообщем надо убрать про быстродействие. Код более компактный это да.
А вообще-то я говорил, что СП-Форт поставлен на IA-32 с точки зрения быстродействия не совсем
правильно. Структуры данных смешаны с исполняемым кодом.
Пространство данных (переменных, массивов и т.д.) должно быть подальше от кода(от словаря).
Тут много тонких моментов. :(
Тут проигрыш в 10-ки раз получиться может. В это же время делается выравнивание, от которого в данной ситуации на фоне замедления от смешивания данных и кода толку никакого. Так что не знаю
ваш или mОlega или мой вариант быстрее будет. Замеры быстродействия в данной ситуации дело
ненадежное. Попробовать сравнить конечно можно через RDTSC - но за результат ручаться нельзя.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 20:21 
Не в сети

Зарегистрирован: Вс дек 02, 2007 17:31
Сообщения: 442
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
mOleg писал(а):
 .. DUP 4 LSHIFT OR  DUP 2 LSHIFT OR DUP 1 LSHIFT OR  0xFEFEFEFE AND
    16 RSHIFT + 8 RSHIFT + 7 AND ..
Шото оно не работает... Можно рабочую версию? :shuffle;

_________________
Am I evil? I'm man - yes I am! © James Hatefield


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 20:24 
Не в сети

Зарегистрирован: Вс дек 02, 2007 17:31
Сообщения: 442
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
chess писал(а):
Я уже начал забывать про Пентиумы.
Ну да, конечно. :lol: У меня просто еще с тех пор к BSR "особое" отношение. :dmad; На Атлоне 10 тактов.
chess писал(а):
Замеры быстродействия в данной ситуации дело ненадежное.
Замерил ваш и мой. Олега пока не рабочий. Получилось что мой в среднем, около 5 раз быстрее. Однако, опять же, гадание на ветвлениях штука не надежная. ;)

_________________
Am I evil? I'm man - yes I am! © James Hatefield


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт мар 21, 2008 16:41 
Не в сети

Зарегистрирован: Вс дек 02, 2007 17:31
Сообщения: 442
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
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+ ;
Или нет? :?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт мар 21, 2008 18:47 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Forthware писал(а):
Я вот думал, думал, так и не понял зачем все эти сложности. Ведь можно было так сделать:
Код:
REQUIRE IDN ~chess\assm\sp-assm.f
: SB ( u -- +n )
A=H\A 3 RSHIFT 1+ ;
Или нет?

Ну лучшие-то решения всегда приходят после некоторых раздумий. :D
Я-то когда код писал - не думал вообще, точнее вспомнил, что BSR дает номер старшего бита в числе
на 1-цу меньший, а дальше все на автомате - какие сложности.
А тут получилось как раз то что надо - деление на степень двойки с округлением результата в большую сторону - красиво однако. 8)
То есть из числа надо сначала отнять 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.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт мар 21, 2008 20:16 
Не в сети

Зарегистрирован: Вс дек 02, 2007 17:31
Сообщения: 442
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
chess писал(а):
Ну лучшие-то решения всегда приходят после некоторых раздумий.
:D
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 ) 
DUP 0xFFFF0000 AND 
IF 0xFF000000 AND IF 4 EXIT ELSE 3 EXIT THEN
ELSE 0xFF00 AND IF 2 EXIT ELSE 1 EXIT THEN
THEN
;
Все еще где-то в 1.5-2 раза быстрее за:
Код:
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

_________________
Am I evil? I'm man - yes I am! © James Hatefield


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб мар 22, 2008 13:27 
Не в сети

Зарегистрирован: Чт май 04, 2006 18:18
Сообщения: 456
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
chess писал(а):
А вообще-то я говорил, что СП-Форт поставлен на IA-32 с точки зрения быстродействия не совсем
правильно. Структуры данных смешаны с исполняемым кодом.
Пространство данных (переменных, массивов и т.д.) должно быть подальше от кода(от словаря).
Тут много тонких моментов. :(
Тут проигрыш в 10-ки раз получиться может. В это же время делается выравнивание, от которого в данной ситуации на фоне замедления от смешивания данных и кода толку никакого.


Если вы уверены что есть такой эффект и для вас это важно, то почему бы это не исправить (если есть желание)?

_________________
http://forth.org.ru/~ygrek


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб мар 22, 2008 19:40 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
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(


_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб мар 22, 2008 21:33 
Не в сети

Зарегистрирован: Вс дек 02, 2007 17:31
Сообщения: 442
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
mOleg писал(а):
а вот что получается, если без ветвлений:
По грубым прикидкам, получается гдето на 20-25% медленнее за
Код:
REQUIRE IDN ~chess\assm\sp-assm.f
: SB ( u -- +n )
  A=H\A 3 RSHIFT 1+ ;
И где-то в 2.5 раза медленнее за:
Код:
: 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
;

_________________
Am I evil? I'm man - yes I am! © James Hatefield


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

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Ради интереса сравнил быстродействие
Код:
REQUIRE IDN ~chess\assm\sp-assm.f
: 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
;
на CORE 2 DUO.
получилось абсолютно одинаково,
потом на ATHLON 64
получилось SB быстрее чем SB1 на 25%.

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


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

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


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

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


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

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