làm thế nào để có được số nguyên 64 bit trong lisp chung?

Question

Tôi muốn viết một bitboard trong lisp phổ biến, vì vậy tôi cần một số nguyên 64 bit. Làm thế nào để có được một số nguyên 64 bit trong lisp chung? Ngoài ra, có bất kỳ thư viện có thể giúp tôi thực hiện điều này mà không cần viết tất cả mọi thứ từ đầu?

Answer 1

Bạn muốn sử dụng các bit bit, là các mảng bit có kích thước tùy ý, chứ không phải là số nguyên như số nguyên 64 bit. Việc thực hiện sẽ đối phó với các đại diện nội bộ cho bạn.

Answer 2

Bạn có thể khai báo các biến của bạn sẽ được loại (signed-byte 64) hoặc (unsigned-byte 64):

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

Nó phụ thuộc vào việc thực hiện của bạn nếu nó thực sự là đủ thông minh để thực sự cụ này trong 8 byte liên tiếp hoặc nếu nó sẽ sử dụng một bignum cho điều này. Thích hợp optimize - các tuyên bố có thể hữu ích.

Dưới đây là một (rất đơn giản) ví dụ về khai báo kiểu như vậy, và xử lý các số nguyên trong hệ nhị phân:

(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 

Dưới đây là một định nghĩa setf-giãn nở để có được một setter đơn giản cho bit trong số nguyên, và một getter tương ứng:

(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)) 

đây có thể được sử dụng như thế này:

(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 

Answer 3

Trong di động Phổ biến Lisp 'số nguyên' là lớn như bạn muốn. Có một tập hợp con hiệu quả hơn các số nguyên được gọi là 'fixnums'. Phạm vi chính xác của fixnums được thực hiện phụ thuộc. Nhưng nó thường không phải là 64 bit đầy đủ (trên một kiến ​​trúc 64bit) có thể được sử dụng, vì hầu hết các triển khai thường gặp của Lisp cần bit thẻ loại. Đối với người dùng không có nhiều sự khác biệt. Fixnums là một tập hợp con của các số nguyên và một có thể thêm hai fixnums và nhận được một kết quả số nguyên không cố định. Sự khác biệt duy nhất có thể quan sát được là việc tính toán với số nguyên không cố định chậm hơn, cần lưu trữ nhiều hơn, ... Nói chung, nếu bạn muốn tính toán với số nguyên, bạn không cần khai báo rằng bạn muốn tính toán với 64 bit . Bạn chỉ cần sử dụng số nguyên và các hoạt động bình thường cho những người.

Nếu bạn muốn các số nguyên 64 bit thực (chỉ có 64 bit, không có thẻ, vv) và tính toán với những số đó, bạn sẽ để lại khả năng ANSI CL di động. Nếu và cách CLISP hỗ trợ điều đó, được yêu cầu tốt nhất trên danh sách gửi thư của CLISP.

Documentation

• Loại FIXNUM
• Loại INTEGER

Answer 4

Ví dụ sử dụng các vectơ bit/mảng để thực hiện một 8x8 chút-board (bắt đầu với mã tối ưu hóa cách tàn bạo và sớm chỉ để hiển thị a cách lấy mã lắp ráp chặt chẽ):

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

MAKE-BITBOARD sẽ tạo bitboard 8x8 làm mảng bit. Khi sử dụng SBCL, điều này được biểu diễn nội bộ dưới dạng 1 bit cho mỗi phần tử (vì vậy, bạn có 64 bit + mảng trên không). Nếu bạn yêu cầu tối ưu hóa khi truy cập bảng, bạn sẽ nhận được mã nhanh.

(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)) 

Các DECLAIM s đang có để cho phép địa phương inlining requests cho GET-BITBOARD.

Một ví dụ của việc sử dụng 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)) 

Vì không có SET-BITBOARD nào, một ví dụ của việc sử dụng USE-BITBOARD là:

(use-bitboard (make-bitboard)) 

Tháo USE-BITBOARD (SBCL một lần nữa, Linux x64) cho thấy trình biên dịch được inline 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 

Không chắc chắn tại sao trình biên dịch đưa vào tất cả các số NOP s đó (để lại không gian cho thiết bị đo đạc sau này? sắp xếp?) nhưng nếu bạn nhìn vào mã số ở cuối nó khá nhỏ gọn (không nhỏ gọn như bộ chế tạo thủ công, trong số khóa học).

Đây là trường hợp rõ ràng về tối ưu hóa sớm. Cách đúng để bắt đầu ở đây sẽ chỉ đơn giản là viết:

(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)) 

... và sau đó sử dụng một hồ sơ khi chạy mã trò chơi có sử dụng các bit-board để xem nơi tắc nghẽn CPU đang có. SBCL bao gồm một số đẹp statistical profiler.

Bắt đầu với mã đơn giản hơn và chậm hơn, không có khai báo cho tốc độ , là tốt nhất. Chỉ cần so sánh kích thước của mã - Tôi bắt đầu với mã với nhiều khai báo để làm cho mã đơn giản ở cuối trông đơn giản hơn bằng cách so sánh :-). Lợi thế ở đây là bạn có thể coi Common Lisp là một ngôn ngữ kịch bản/tạo mẫu khi thử các ý tưởng , sau đó ép hiệu suất ra khỏi mã mà trình biên dịch gợi ý.

Mã lắp ráp rõ ràng là không chặt chẽ khi tải toàn bộ bảng trong một thanh ghi 64 bit và sau đó truy cập các bit riêng lẻ. Nhưng nếu bạn quyết định rằng bạn muốn nhiều hơn 1 bit trên mỗi hình vuông, thì việc thay đổi mã CL nhiều hơn là thay đổi mã CL (chỉ cần thay đổi loại mảng ở mọi nơi từ '(mod 2) thành '(mod 16), ví dụ ).