Подсчет кол-ва битов в слове

mOleg

быстрее я думаю не получится Ж8)
разве что еще и внешний цикл на асме написать, но без этого уже можно и обойтись

Код:

CODE ?bits ( N --> # )
           XOR EBX, EBX
      @@1: OR EAX, EAX
          JZ @@2
           MOV EDX, EAX
           AND EDX, # 1
           ADD EBX, EDX
           SHR EAX, # 1
          JMP @@1
      @@2: MOV EAX, EBX
         RET
      END-CODE

forther

mOleg писал(а):

быстрее я думаю не получится ЖCool
разве что еще и внешний цикл на асме написать, но без этого уже можно и обойтись

Ну и как быстро этот кашмар работает? (в наносекундах). Сам проверить немогу,
т.к. на gforth оно не компилируется. Но вам на слово поверю.

mOleg

forther писал(а):

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

Ну и как быстро этот кашмар работает? (в наносекундах). Сам проверить немогу,
т.к. на gforth оно не компилируется. Но вам на слово поверю.

Гм, а надо для GFORTH ?
там другой асм, наверное 8(

forther

mOleg писал(а):

Гм, а надо для GFORTH ?
там другой асм, наверное 8(

Не надо, просто интересно знать, насколько этот код быстрый.

chess

Для таблицы - число бит в слове быстродействие 3-го метода стало выше других.

Код:

\ Подключение преобразование системы счисления

: countBitsInBytes ( i byte -- i )
  SWAP OVER     1 AND IF 1+ THEN
       OVER     2 AND IF 1+ THEN
       OVER     4 AND IF 1+ THEN
       OVER     8 AND IF 1+ THEN
       OVER    16 AND IF 1+ THEN
       OVER    32 AND IF 1+ THEN
       OVER    64 AND IF 1+ THEN
       OVER   128 AND IF 1+ THEN
  NIP
;

\ Case2 --------------------------------------------------
: countBitsInCell ( i cell -- i )
   DUP 0x55555555 AND SWAP 0xAAAAAAAA AND 1 RSHIFT +
   DUP 0x33333333 AND SWAP 0xCCCCCCCC AND 2 RSHIFT +
   DUP 0x0F0F0F0F AND SWAP 0xF0F0F0F0 AND 4 RSHIFT +
   DUP 0x00FF00FF AND SWAP 0xFF00FF00 AND 8 RSHIFT +
   DUP 0x0000FFFF AND SWAP 0xFFFF0000 AND 16 RSHIFT +
 +
;

\ Case3 --------------------------------------------------
: BITS-WORD \ word --> i
DUP 0x5555 AND SWAP 0xAAAA AND 1 RSHIFT +
DUP 0x3333 AND SWAP 0xCCCC AND 2 RSHIFT +
DUP 0x0F0F AND SWAP 0xF0F0 AND 4 RSHIFT +
DUP 0x00FF AND SWAP 0xFF00 AND 8 RSHIFT +
;

CREATE [BITS-WORD] 65536 ALLOT

: GEN-TBL-WORD
[BITS-WORD] 65536 + [BITS-WORD]
DO
  I [BITS-WORD] - BITS-WORD I C!
LOOP
;

GEN-TBL-WORD

: BitsInWord ( i word -- i )
   [BITS-WORD] + C@
   +
;

\ ----- Testing ------
    1024 CONSTANT KB
 KB KB * CONSTANT MB

100 MB * CONSTANT BytesInArray

\ Выделние тестового масиива
USER Array
  BytesInArray ALLOCATE THROW Array !

\ Заполнение массива
: FillArray
  BytesInArray 0 DO
    I 256 MOD I Array @ + C!
  LOOP
; FillArray

\ Гоняем на тестовом массиве первый метод
: Case1
  0
  BytesInArray 0 DO
     Array @ I + C@ countBitsInBytes
  LOOP
;

\ Гоняем на тестовом массиве второй метод
: Case2
  0
  BytesInArray 4 / 0 DO
     Array @ I + @ countBitsInCell
  LOOP
;

\ Гоняем на тестовом массиве третий метод
: Case3
  0
  BytesInArray 2/ 0 DO
     Array @ I + W@  BitsInWord
  LOOP
;

\ Засекаем на время, что быстрее
REQUIRE time-reset d:/spf/devel/~af/lib/elapse.f
REQUIRE .elapsed   d:/spf/devel/~af/lib/elapse.f

 time-reset Case1 .elapsed CR
 time-reset Case2 .elapsed CR
 time-reset Case3 .elapsed CR

Код:

Elapsed time: 00:00:02:016  
Elapsed time: 00:00:00:578
Elapsed time: 00:00:00:453

У меня комп ATHLON-64-3200, поэтому абсолютные значения времен другие

AlexF

Добавил. Результат -- корректно реализован расчет, не самый быстрый.

ЗЫ. Если не сложно, пожалуйста, описывайте аргументы. Мне не очевидно было, что n -- это 32-х разрядное слово. К примеру, в других вариантах реализации, в качестве аргументво использовались байты.

AlexF

mOleg писал(а):

быстрее я думаю не получится Ж8)
разве что еще и внешний цикл на асме написать, но без этого уже можно и обойтись

увы, не самый быстрый, см. результат:

Код:

Method 1 419430400 1-bits Elapsed time: 00:00:02:172
Method 2 419430400 1-bits Elapsed time: 00:00:00:391
Method 3 419430400 1-bits Elapsed time: 00:00:00:453
Method 4 419430400 1-bits Elapsed time: 00:00:02:265
Method 5 419430400 1-bits Elapsed time: 00:00:01:266

Ваш код -- Method 5.
Тестирование на машинке: P4 3,4GHz, 2GB RAM, WinXP (SP2)

chess

Метод 1 - это ваш
Метод 2 - это Михаила
Метод 3 - это мой
Метод 5 - это Олега

Метод 4 - а это чей?
Почему-то мой метод на моем компе быстрее(с таблицей битов для слов), чем у Михаила, а на вашем нет.

AlexF

Метод 1 - это мой
Метод 2 - это Михаила
Метод 3 - это Chess (уж извините, не знаю как по батюшке :( )
Метод 5 - это Олега
Метод 4 - forther ( слово bc )

Цитата:

Почему-то мой метод на моем компе быстрее (с таблицей битов для слов), чем у Михаила, а на вашем нет.

у нас процы разные, как вариант. Может настройки самого Форта. Я использую сборку yGrek-а, 4.18 (прямо из коробки).

Mihail

AlexF писал(а):

у нас процы разные, как вариант. Может настройки самого Форта. Я

Ради этого примера я добавил пару правил http://fpauk.narod.ru/macroopt.f
Можно еще чуть ускорить.

chess

.

AlexF писал(а):

Может настройки самого Форта. Я использую сборку yGrek-а, 4.18 (прямо из коробки).

Попробовал на SP-Forth 4.18 Build 001 at 01.Dec.2006 (у меня был SP-Forth 4.00 Build 018 at 24.Nov.2006 )
Цифры другие получаются.

Код:

Elapsed time: 00:00:04:781 - ваш
Elapsed time: 00:00:00:594 - Михаила
Elapsed time: 00:00:00:437 - мой

Все-таки если не трудно приведите весь текст программы

Mihail

\ Гоняем на тестовом массиве первый метод
: Case1
0
BytesInArray 0 DO
Array @ I + C@ countBitsInBytes
LOOP
;

\ быстрее будет

REQUIRE [IFNDEF] ~nn\lib\ifdef.f
[IFNDEF] BOUNDS : BOUNDS OVER + SWAP ;
[THEN]

: Case1
0
Array @ BytesInArray BOUNDS DO
I C@ countBitsInBytes
LOOP
;

AlexF

chess писал(а):

Все-таки если не трудно приведите весь текст программы

Угу. Только не смог подключить оптимизатор, подскажите как? Скачал его в отдельную папку. INCLUDED ругается на слово [UNDEFINED] что не так?

Код:

\ Тестирвоание на про-сть различных вариантов реализации
\ подсчета кол-ва единичных бит в битовом массиве

: countBitsInBytes ( i byte -- i )
  SWAP OVER     1 AND IF 1+ THEN
       OVER     2 AND IF 1+ THEN
       OVER     4 AND IF 1+ THEN
       OVER     8 AND IF 1+ THEN
       OVER    16 AND IF 1+ THEN
       OVER    32 AND IF 1+ THEN
       OVER    64 AND IF 1+ THEN
       OVER   128 AND IF 1+ THEN
  NIP
;

\ Case2 --------------------------------------------------
: countBitsInCell ( i cell -- i )
   DUP 0x55555555 AND SWAP 0xAAAAAAAA AND 1 RSHIFT +
   DUP 0x33333333 AND SWAP 0xCCCCCCCC AND 2 RSHIFT +
   DUP 0x0F0F0F0F AND SWAP 0xF0F0F0F0 AND 4 RSHIFT +
   DUP 0x00FF00FF AND SWAP 0xFF00FF00 AND 8 RSHIFT +
   DUP 0x0000FFFF AND SWAP 0xFFFF0000 AND 16 RSHIFT +
 +
;

\ Case3 --------------------------------------------------
: BITS-BYTE \ byte -- i
DUP 0x55 AND SWAP 0xAA AND 1 RSHIFT +
DUP 0x33 AND SWAP 0xCC AND 2 RSHIFT +
DUP 0x0F AND SWAP 0xF0 AND 4 RSHIFT +
;

CREATE [BITS-BYTE] 256 ALLOT

: GEN-TBL-BYTE
[BITS-BYTE] 256 + [BITS-BYTE]
DO
  I [BITS-BYTE] - BITS-BYTE I C!
LOOP
;

GEN-TBL-BYTE

: BitsInByte ( i byte -- i )
   [BITS-BYTE] + C@
   +
;

\ Case4 --------------------------------------------------
: bc ( i cell -- i )
    -1 0 DO
        ?DUP 0= IF I UNLOOP + EXIT THEN
        DUP 1- AND
    LOOP
  +
; 

\ Case5 --------------------------------------------------
REQUIRE CODE lib\ext\spf-asm-tmp.f

CODE ?bits ( N --> # )
           XOR EBX, EBX
      @@1: OR EAX, EAX
          JZ @@2
           MOV EDX, EAX
           AND EDX, # 1
           ADD EBX, EDX
           SHR EAX, # 1
          JMP @@1
      @@2: MOV EAX, EBX
         RET
END-CODE 

\ ----------- Testing ---------------------
    1024 CONSTANT KB
 KB KB * CONSTANT MB
100 MB * CONSTANT BytesInArray

\ Выделние тестового масиива
USER Array
  BytesInArray ALLOCATE THROW Array !

\ Заполнение массива
: FillArray
  BytesInArray 0 DO
    I 256 MOD I Array @ + C!
  LOOP
; FillArray

\ --------- Проход по массиву --------------
: Case1
  0
  BytesInArray 0 DO
     Array @ I + C@ countBitsInBytes
  LOOP ;

: Case2
  0
  BytesInArray 4 / 0 DO
     Array @ I + @ countBitsInCell
  LOOP ;

: Case3
  0
  BytesInArray 0 DO
     Array @ I + C@  BitsInByte
  LOOP ;

: Case4
  0
  BytesInArray 4 / 0 DO
     Array @ I + @ bc
  LOOP ;

: Case5
  0
  BytesInArray 4 / 0 DO
     Array @ I + @ ?bits +
  LOOP  ;

\ Засекаем на время, что быстрее
REQUIRE time-reset d:/spf/devel/~af/lib/elapse.f
REQUIRE .elapsed   d:/spf/devel/~af/lib/elapse.f
: t
 ."   AlexF method " time-reset Case1 . ." 1-bits " .elapsed CR
 ."  Mihail method " time-reset Case2 . ." 1-bits " .elapsed CR
 ."   chess method " time-reset Case3 . ." 1-bits " .elapsed CR
 ." forther method " time-reset Case4 . ." 1-bits " .elapsed CR
 ."   mOleg method " time-reset Case5 . ." 1-bits " .elapsed CR
; t

Результаты работы:

Код:

SP-FORTH - ANS FORTH 94 for Win95/98/ME/NT/2000/XP
Open source project at http://spf.sf.net
Russian FIG at http://www.forth.org.ru ; Started by A.Cherezov
Version 4.18 Build 001 at 01.Dec.2006

CODE isn't unique
  AlexF method 419430400 1-bits Elapsed time: 00:00:02:172
 Mihail method 419430400 1-bits Elapsed time: 00:00:00:406
  chess method 419430400 1-bits Elapsed time: 00:00:00:453
forther method 419430400 1-bits Elapsed time: 00:00:02:281
  mOleg method 419430400 1-bits Elapsed time: 00:00:01:266

chess

AlexF писал(а):

Угу. Только не смог подключить оптимизатор, подскажите как? Скачал его в отдельную папку. INCLUDED ругается на слово [UNDEFINED] что не так?

Новую версию оптимизатора (macroopt.f) я подключаю так:
старый macroopt.f переименовываю, чтобы не мешал, новый вставляю в каталог SPF, затем запускаю
на исполнение файл install.bat (находится в этой же папке SPF).

Свой вариант получения количества 1-х битов в массиве переделал:

Код:

: BITS-WORD \ word --> i
DUP 0x5555 AND SWAP 0xAAAA AND 1 RSHIFT +
DUP 0x3333 AND SWAP 0xCCCC AND 2 RSHIFT +
DUP 0x0F0F AND SWAP 0xF0F0 AND 4 RSHIFT +
DUP 0x00FF AND SWAP 0xFF00 AND 8 RSHIFT +
;
CREATE [BITS-WORD] 0xFFFF ALLOT

: GEN-TBL-WORD
[BITS-WORD] 0xFFFF + [BITS-WORD]
DO
  I [BITS-WORD] - BITS-WORD I C!
LOOP
;
GEN-TBL-WORD

: Case3
  0
  BytesInArray 4 / 0 DO
  Array @ I      + W@ [BITS-WORD] + C@ + \ BitsInWord
  Array @ I  2+  + W@ [BITS-WORD] + C@ + \ BitsInWord
  LOOP
;

Если нужно еще быстрей, то можно за один проход по циклу обрабатывать не 2 слова, а 4 или 8 и т.д.
Например для 4 слов:

Код:

: Case3
  0
  BytesInArray 8 / 0 DO
  Array @ I      + W@ [BITS-WORD] + C@ + \ BitsInWord
  Array @ I  2+  + W@ [BITS-WORD] + C@ + \ BitsInWord
  Array @ I  4 +  + W@ [BITS-WORD] + C@ + \ BitsInWord
  Array @ I  6 +  + W@ [BITS-WORD] + C@ + \ BitsInWord
LOOP
;

А если уж совсем быстро надо, то нужно сгенерить предварительно таблицу на 0хFFFFFFFF значения
для числа битов в cell. Памяти хватит.

Mihail

chess писал(а):

Новую версию оптимизатора (macroopt.f) я подключаю так:
старый macroopt.f переименовываю, чтобы не мешал, новый вставляю в каталог SPF, затем запускаю
на исполнение файл install.bat (находится в этой же папке SPF).

Что за каталог SPF ? Нужно записать в католог \src и там запустить compile.bat

Цитата:

Свой вариант получения количества 1-х битов в массиве переделал:

Код:

: BITS-WORD \ word --> i
DUP 0x5555 AND SWAP 0xAAAA AND 1 RSHIFT +
DUP 0x3333 AND SWAP 0xCCCC AND 2 RSHIFT +
DUP 0x0F0F AND SWAP 0xF0F0 AND 4 RSHIFT +
DUP 0x00FF AND SWAP 0xFF00 AND 8 RSHIFT +
;

CREATE [BITS-WORD] 0xFFFF ALLOT

CREATE [BITS-WORD] 0x10000 ALLOT

Код:

: Case3
  0
  BytesInArray 4 / 0 DO
  Array @ I      + W@ [BITS-WORD] + C@ + \ BitsInWord
  Array @ I  2+  + W@ [BITS-WORD] + C@ + \ BitsInWord
  LOOP
;

для инлайн подстановки
: BitsInWord ( i word -- i )
[BITS-WORD] + C@ + ;

Нужно добавить строчку в определение DUP7B? оптимизатора

Код:

: DUP7B?      ( N -- N FLAG )
\ XX00.0101 0000.0100 1000.10X1
  DUP  3FFFFD AND 050489 =    \  MOV   X [EAX*_] , EAX  | MOV EAX , X [EAX*_]
\ XX00.0101 0000.0100 1000.1X01
  OVER 3FFFFB AND 050489 = OR \  MOV   X [EAX*_] , EAX  | LEA EAX , X [EAX*_]
  OVER 80B60F = OR \ MOVZX EAX, BYTE PTR [EAX]
;

Подсчет кол-ва битов в слове

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