Как получить 64-битное целое число в общем LISP? - PullRequest
Новая
       13

Как получить 64-битное целое число в общем LISP?

5 голосов
/ 30 декабря 2011

Я хочу написать битборд в общем lisp, поэтому мне нужно 64-битное целое число.Как я могу получить 64-битное целое число в общем lisp?Кроме того, есть ли библиотеки, которые могли бы помочь мне сделать это, не написав все с нуля?

Ответы [ 4 ]

7 голосов
/ 30 декабря 2011

Вы можете объявить, что ваши переменные имеют тип (signed-byte 64) или (unsigned-byte 64): 

CL-USER> (typexpand '(unsigned-byte 64))
(INTEGER 0 18446744073709551615)
T
CL-USER> (typexpand '(signed-byte 64))
(INTEGER -9223372036854775808 9223372036854775807)
T

Это зависит от вашей реализации, насколько она достаточно умна, чтобы действительно заполнить ее 8 последовательными байтами или еслидля этого он будет использовать bignum.Могут помочь соответствующие optimize -декларации.

Вот (очень простой) пример таких объявлений типов и обработки целых чисел в двоичном виде: 

(let* ((x #b01)
       (y #b10)
       (z (logior x y)))
  (declare ((signed-byte 64) x y z))
  (format t "~a~%" (logbitp 1 x))
  (format t "~a~%" (logbitp 1 (logior x (ash 1 1))))
  (format t "~b~%" z))

Output:
NIL
T
11

Вот определение setf-expander для полученияпростой установщик для битов в целых числах и соответствующий получатель: 

(define-setf-expander logbit (index place &environment env)
  (multiple-value-bind (temps vals stores store-form access-form)
      (get-setf-expansion place env)
    (let ((i (gensym))
          (store (gensym))
          (stemp (first stores)))
      (values `(,i ,@temps)
              `(,index ,@vals)
              `(,store)
              `(let ((,stemp (dpb ,store (byte 1 ,i) ,access-form))
                     ,@(cdr stores))
                 ,store-form
                 ,store)
              `(logbit ,i ,access-form)))))

(defun logbit (index integer)
  (ldb (byte 1 index) integer))

Они могут использоваться следующим образом: 

(let ((x 1))
  (setf (logbit 3 x) 1)
  x)
==> 9
(let ((x 9))
  (setf (logbit 3 x) 0)
  x)
==> 1

(logbit 3 1)
==> 0
(logbit 3 9)
==> 1
6 голосов
/ 31 декабря 2011

В переносимом Common Lisp «целые числа» настолько большие, насколько вам нужно. Существует более эффективное подмножество целых чисел, называемое «fixnums». Точный диапазон фикснумов зависит от реализации. Но обычно это не полные 64-битные (на 64-битной архитектуре), которые могут использоваться, так как большинству реализаций Common Lisp нужны биты тегов типа. Для пользователя нет особой разницы. Фиксированные числа - это подмножество целых чисел, и можно добавить два фиксных числа и получить целочисленный результат, не являющийся фиксированным. Единственными различиями, которые могут быть заметны, является то, что вычисления с целыми числами, не являющимися фиксированными, выполняются медленнее, требуют больше памяти, ... Как правило, если вы хотите выполнять вычисления с целыми числами, вам не нужно объявлять, что вы хотите вычислять с помощью 64-битных , Вы просто используете целые числа и обычные операции для них.

Если вам нужны настоящие 64-битные большие целые числа (представленные только в 64-битах, без тегов и т. Д.) И вычисления с ними, вы оставите возможности переносимого ANSI CL. Если и как CLISP поддерживает это, лучше всего спрашивать в списке рассылки CLISP.

Документация

5 голосов
/ 02 января 2012

Пример использования битовых векторов / массивов для реализации битовой платы 8x8 (начиная с грубо и преждевременно оптимизированного кода, чтобы показать способ получить жесткий ассемблерный код): 

(defun make-bitboard ()
  (make-array '(8 8) :element-type '(mod 2) :initial-element 0))

MAKE-BITBOARD создаст битовую доску 8x8 в виде массива битов. когда используя SBCL, это внутренне представляется как 1 бит на элемент (так у вас есть 64 бита + издержки экземпляра массива). Если вы попросите оптимизации при доступе к плате, вы получите быстрый код. 

(declaim (inline get-bitboard))
(defun get-bitboard (bit-board x y)
       (declare (optimize speed (safety 0) (debug 0))
                (type (simple-array (mod 2) (8 8)) bit-board)
                (type fixnum x y))
       (aref bit-board x y))
(declaim (notinline get-bitboard))

DECLAIM s, чтобы разрешить местный запросов на встраивание для GET-BITBOARD.

Пример использования GET-BITBOARD: 

(defun use-bitboard (bit-board)
  (declare (optimize speed (safety 0) (debug 0))
           (type (simple-array (mod 2) (8 8)) bit-board)
           (inline get-bitboard))
  (let ((sum 0))
    (declare (type fixnum sum))
    (dotimes (i 8)
      (declare (type fixnum i))
      (dotimes (j 8)
        (declare (type fixnum j))
        (incf sum (the (mod 2) (get-bitboard bit-board i j)))))
    sum))

Поскольку SET-BITBOARD еще нет, пример использования USE-BITBOARD: 

(use-bitboard (make-bitboard))

Разборка USE-BITBOARD (снова SBCL, Linux x64) показывает, что встроенный компилятор GET-BITBOARD: 

; disassembly for USE-BITBOARD
; 030F96A2:       31F6             XOR ESI, ESI               ; no-arg-parsing entry point
;      6A4:       31D2             XOR EDX, EDX
;      6A6:       EB54             JMP L3
;      6A8:       90               NOP
;      6A9:       90               NOP
;      6AA:       90               NOP
;      6AB:       90               NOP
;      6AC:       90               NOP
;      6AD:       90               NOP
;      6AE:       90               NOP
;      6AF:       90               NOP
;      6B0: L0:   31DB             XOR EBX, EBX
;      6B2:       EB3E             JMP L2
;      6B4:       90               NOP
;      6B5:       90               NOP
;      6B6:       90               NOP
;      6B7:       90               NOP
;      6B8:       90               NOP
;      6B9:       90               NOP
;      6BA:       90               NOP
;      6BB:       90               NOP
;      6BC:       90               NOP
;      6BD:       90               NOP
;      6BE:       90               NOP
;      6BF:       90               NOP
;      6C0: L1:   488D04D500000000 LEA RAX, [RDX*8]
;      6C8:       4801D8           ADD RAX, RBX
;      6CB:       4C8B4711         MOV R8, [RDI+17]
;      6CF:       48D1F8           SAR RAX, 1
;      6D2:       488BC8           MOV RCX, RAX
;      6D5:       48C1E906         SHR RCX, 6
;      6D9:       4D8B44C801       MOV R8, [R8+RCX*8+1]
;      6DE:       488BC8           MOV RCX, RAX
;      6E1:       49D3E8           SHR R8, CL
;      6E4:       4983E001         AND R8, 1
;      6E8:       49D1E0           SHL R8, 1
;      6EB:       4C01C6           ADD RSI, R8
;      6EE:       4883C302         ADD RBX, 2
;      6F2: L2:   4883FB10         CMP RBX, 16
;      6F6:       7CC8             JL L1
;      6F8:       4883C202         ADD RDX, 2
;      6FC: L3:   4883FA10         CMP RDX, 16
;      700:       7CAE             JL L0
;      702:       488BD6           MOV RDX, RSI
;      705:       488BE5           MOV RSP, RBP
;      708:       F8               CLC
;      709:       5D               POP RBP
;      70A:       C3               RET

Не уверен, почему компилятор вставил все эти NOP с (оставляя место для приборы позже? выравнивания?) но если вы посмотрите на код на В конце концов, он довольно компактный (не такой компактный, как ручной сборщик, Конечно).

Теперь это очевидный случай преждевременной оптимизации. Правильный путь для начала здесь было бы просто написать: 

(defun get-bitboard (bit-board x y)
  (aref bit-board x y))

(defun use-bitboard (bit-board)
  (let ((sum 0))
    (dotimes (i 8)
      (dotimes (j 8)
        (incf sum (get-bitboard bit-board i j))))
    sum))

... и затем использовать профилировщик при запуске игрового кода, который использует плата, чтобы увидеть узкие места процессора. SBCL включает в себя хороший статистический профилировщик .

Начиная с более простого и медленного кода, без объявлений для скорость, лучше. Просто сравните размер кода - я начал с код с множеством объявлений, чтобы сделать простой код в конце Выглядит еще проще в сравнении :-). Преимущество здесь в том, что вы может рассматривать Common Lisp как язык сценариев и прототипов при попытке идеи, а затем выжать больше производительности из кода, что Профилировщик предлагает.

Код сборки явно не такой жесткий, как загрузка всей платы в один 64-битный регистр, а затем доступ к отдельным битам. Но если ты вдруг решить, что вы хотите больше, чем 1 бит на квадрат, это очень проще изменить код CL, чем изменить код ассемблера (просто везде изменить тип массива с '(mod 2) на '(mod 16), для экземпляр).

2 голосов
/ 30 декабря 2011

Вы хотите использовать битовые векторы, которые представляют собой массивы битов произвольного размера, а не что-то вроде 64-битного целого числа. Реализация будет иметь дело с внутренними представлениями для вас.

...