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

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 42 ]  На страницу Пред.  1, 2, 3
Автор Сообщение
 Заголовок сообщения:
СообщениеДобавлено: Вт окт 16, 2007 20:03 
Не в сети

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 380
Благодарил (а): 1 раз.
Поблагодарили: 10 раз.
Давайте попробуем на, скажем, 0х2FFF3
SEAforth 0x2FFF3 считает 150 наносекунд.
Вот дамп программы:
Код:
: bc
000 8TSS 048B2 @p+ push . .
001 LAL8 3FFFF
: loop
002 O6A4 25304 dup if 4
003 HL5S 3607A 2* and next 2
004 NNPS 3A29A drop drop pop .
005 J0SS 335B2 not ;
006 83AK 05600 @p+ call 0  bc
007 TAKO 2FFF3


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср окт 17, 2007 09:46 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
in4 писал(а):
Время выполнения этого алгоритма зависит от входных данных, а они не приведены.
Хорошо бы показать и способ получения временных параметров... я бы хотел проверить на своем компе


Число конечно же 0xFFFFFFFF - максимальное по задаче
Способ измерения времени выполнения:
Код:
\ на моем ассме
: @TSC-LO  DUP DA=TSC ;

\ тоже самое на Ассм СПФ
\ CODE @TSC-LO
\ LEA EBP, -4 [EBP]
\ MOV [EBP], EAX
\ RDTSC
\ RET
\ END-CODE

VECT MEASURE

: ns.
  CR ." dT(" DUP WordByAddr TYPE ." ) = " TO MEASURE
  @TSC-LO >R MEASURE @TSC-LO R> - @TSC-LO >R @TSC-LO R> - - 2/ . ." ns  " CR
;
\ @TSC-LO >R @TSC-LO R> - - это учет времени выполнения команды >R в конечном результате
\ 2/ - учет тактовой частоты процессора (у меня она 2000 мгц - один тик 0.5 нсек, чтобы получилось в нсек делим результат на 2)

Измерение производим так:

Код:
0xFFFFFFFF ' maxlen-bits  ns.
\ результат
dT(maxlen-bits) = 275 ns

За счет кэша время плавает - беру наиболее часто повторяющееся значение.
forther писал(а):
Вот дамп программы:

Быстро и компактно - не хуже P4.
Правда у P4 есть команды работы с битами - на них будет быстрее. Время будет - покажу.
Кстати в форт на IA-32 можно несколько примитивов для работы с битами добавить.

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


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

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

Для Форта

Код:
REQUIRE ASSEMBLER lib\ext\spf-asm.f

CODE @TSC-LO
LEA EBP, -4 [EBP]
MOV [EBP], EAX
RDTSC
RET
END-CODE

0 VALUE par
0 VALUE rep

: ns.
TO par TO rep
0  \ счетчик времени
rep 0
DO
    par @TSC-LO >R BITS_COUNT @TSC-LO R> -
        @TSC-LO >R            @TSC-LO R> - -
        2/ NIP +
LOOP
rep / .
;

\ EOF
STARTLOG
   1 0xFFFFFFFF ns. CR
   1 0xFFFF     ns. CR CR
1000 0xFFFFFFFF ns. CR
1000 0xFFFF     ns.
ENDLOG

лог
617
151

112
60


Для Ассма

Код:
L: maxlen-bits
$ 0 bB=b#      \ MOV  BL, # 0
L1: A|A        \ @@1: OR EAX, EAX
L2  JE         \      JE SHORT @@2
    C=A        \ MOV  ECX, EAX
    $ 1 #C>>   \ SHR  ECX, # 1
    A&C        \ AND  EAX, ECX
    bB++       \ INC  BL
L1  JMP        \      JMP SHORT @@1
L2: bA=bB      \ @@2: MOV AL, BL
L;             \ RET

: @TSC-LO  DUP DA=TSC ;

0 VALUE par
0 VALUE rep

: ns.
TO par TO rep
0  \ счетчик времени
rep 0
DO
    par @TSC-LO >R maxlen-bits @TSC-LO R> -
        @TSC-LO >R             @TSC-LO R> - -
        2/ NIP +
LOOP
rep / .
;

\ EOF
STARTLOG
   1 0xFFFFFFFF ns. CR
   1 0xFFFF     ns. CR CR
1000 0xFFFFFFFF ns. CR
1000 0xFFFF     ns.
ENDLOG

лог
264
119

73
41
Вторые два числа в обоих вариантах для случая, когда исполняемый код находится полностью в кэше.

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


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

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 380
Благодарил (а): 1 раз.
Поблагодарили: 10 раз.
Тут мне старшие товарищи подсказали, как синтаксически улучьшить код и вот что получилось в результате:
Код:
: bc ( u -- c )
  -1 push
  begin dup while
    2* and next
  then
  drop drop pop
  not ;


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

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
forther писал(а):
Тут мне старшие товарищи подсказали, как синтаксически улучьшить код и вот что получилось в результате:

Код:: bc ( u -- c )
  -1 push
  begin dup while
    2* and next
  then
  drop drop pop
  not ;


а дамп можно показать. А то мой компилятор данный код не хочет понимать.
ему не нравится next

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


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

Зарегистрирован: Вт ноя 06, 2007 21:23
Сообщения: 227
Откуда: Екатеринбург
Благодарил (а): 4 раз.
Поблагодарили: 7 раз.
Идея держать два счетчика единиц. Код может и не оптимальный, но работоспособный при любых значениях.
Код:
1  CONSTANT ONE

: ?MSB ( # - pos )
   DUP IF
   0 31 DO DUP  ONE I LSHIFT  AND IF  DROP I 1+ UNLOOP EXIT THEN  -1 +LOOP THEN ;

: PREPARE ( # -- n1 .. nk k)
   DEPTH >R  BEGIN DUP ?MSB  ?DUP NOT IF  R>DROP EXIT  THEN
   TUCK 1- ONE SWAP LSHIFT -  ?DUP 0= UNTIL  DEPTH R> - 1+ ;

DEFER BC:  VARIABLE BC1   VARIABLE BC2
: BC1:  ['] BC1 IS BC: ;   : BC2:   ['] BC2 IS BC: ;
: BCVALUE   BC1: BC: @  BC2: BC: @  MAX ;
: CHANGEBC  BCVALUE BC: !  0  BC: BC1 = IF BC2: ELSE BC1: THEN  BC: ! ;

: BITCOUNT ( # -  # )
   PREPARE  DUP IF  ONE BC1: BC: !  ONE BC2: BC: !
   ONE ?DO  OVER 1- <> IF CHANGEBC THEN  ONE BC: +! LOOP DROP  BCVALUE  THEN  ;

%110011100011110011111 bitcount . 5
-1 bitcount . 32
$FC7F BITCOUNT . 7


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

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 380
Благодарил (а): 1 раз.
Поблагодарили: 10 раз.
Ужасно. Или был объявлен конкурс на худшее решение, а я просто не заметил?


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

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
Alexander писал(а):
Идея держать два счетчика единиц. Код может и не оптимальный, но работоспособный при любых значениях.


Хм... и не знал, что есть любители ездить из Питера в Москву через Владивосток
с обязательным заплывом на пароме до Бразилии...

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


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

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
forther писал(а):
Ужасно. Или был объявлен конкурс на худшее решение, а я просто не заметил?

плохое решение, это тоже решение 8) особенно, если оно работает!
к тому же, человек, наверное сначала ТЗ прочел, потом написал код(который смог придумать),
а лишь потом стал смотреть на чужие решения. А это есть ГУТ. Не все и не сразу учатся находить оптимальные решения.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт ноя 29, 2007 23:40 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
А после написания своего, что мешало заглянуть в другие решения и самостоятельно же сравнить?
А то выглядит как явление паровоза на соревнование легковушек,
да еще и после того, как все остальные пересекли финиш...

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн дек 03, 2007 10:22 
Не в сети
Аватара пользователя

Зарегистрирован: Вт ноя 06, 2007 21:23
Сообщения: 227
Откуда: Екатеринбург
Благодарил (а): 4 раз.
Поблагодарили: 7 раз.
Всем спасибо за комментарии... 8) мне понравилось реакция сообщества
Я смотрю появилась тема "Как не надо программировать на Форте" вот мой пример туда и запишите :P
Просто не хотелось повторяться или выдумывать ориганальный алгоритм, просто хотелось как можно больше использовать уже ранее определенные в моем словарике слова :D после небольшого обдумывания критики получилось вот что:
Код:
1 CONSTANT ONE
ICODE ?MSB ( n - n ) \ старший значащий бит
\ функция BSR возращает 0 при 0 или 1 на  входе и соответсвующее значение флага нуля
   EBX EBX TEST  0<> IF  EBX EBX BSR   EBX INC  THEN  RET
END-CODE

: PREPARE ( n -- 0 | n1 .. nk k) \ позиции единичных бит, начиная с 1
   0 >R BEGIN ?DUP WHILE  DUP ?MSB TUCK 1- ONE SWAP LSHIFT - R++  REPEAT R> ;

VARIABLE BC0   VARIABLE BC1
: BITCOUNT ( n -  n )
   DUP IF
      ONE BC0 ! ONE BC1 !  PREPARE
      ONE ?DO  OVER 1- <> IF  BC0 @ BC1 @ MAX BC1 ! 0  BC0 !  THEN  ONE BC0 +!  LOOP
      BC0 @ BC1 @ MAX NIP
   THEN ;

Конечно в Swifte есть R++, не знаю есть ли это в СПФ.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт дек 04, 2007 05:56 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Alexander писал(а):
Я смотрю появилась тема "Как не надо программировать на Форте" вот мой пример туда и запишите

8) ЭЭ на самом деле тут не в фоте дело, а в нерациональности решения.
Причем наиболее удачное решение, которое уже похоже не превзойти, уже опубликовано и даже обжевано многократно 8)
Поэтому его стоит посмотреть 8)

Alexander писал(а):
после небольшого обдумывания критики получилось вот что:

и всеравно это на много хуже варианта WingLion-a (очень рекомендую его разобрать).

Alexander писал(а):
Конечно в Swifte есть R++

в СПФе пока не видел.
У меня есть R+ в либе.

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


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

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


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

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


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

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