सामान्य लिस्प में 64 बिट पूर्णांक कैसे प्राप्त करें?

Question

मैं सामान्य लिस्प में एक बिटबोर्ड लिखना चाहता हूं, इसलिए मुझे 64 बिट पूर्णांक की आवश्यकता है। मैं सामान्य लिस्प में 64 बिट पूर्णांक कैसे प्राप्त करूं? साथ ही, क्या कोई पुस्तकालय है जो मुझे सबकुछ लिखने के बिना इसे पूरा करने में मदद कर सकता है?

Answer 1

आप बिट वैक्टर का उपयोग करना चाहते हैं, जो 64 बिट पूर्णांक की तरह बिट्स के मनमानी आकार के सरणी हैं। कार्यान्वयन आपके लिए आंतरिक प्रतिनिधित्व से निपटेंगे।

Answer 2

आप प्रकार (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-विस्तारक परिभाषा, और एक इसी गेटर है:

(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 

Answer 3

पोर्टेबल में सामान्य लिस्प 'इंटेगर्स' जितना बड़ा हो उतना बड़ा होता है। 'फिक्समम्स' नामक पूर्णांक का एक अधिक कुशल सबसेट है। फिक्समम्स की सटीक सीमा कार्यान्वयन निर्भर है। लेकिन यह आमतौर पर पूर्ण 64 बिट (64 बिट आर्किटेक्चर पर) नहीं है जिसका उपयोग किया जा सकता है, क्योंकि अधिकांश सामान्य लिस्प कार्यान्वयनों को टाइप टैग बिट्स की आवश्यकता होती है। उपयोगकर्ता के लिए बहुत अंतर नहीं है। Fixnums पूर्णांक का एक सबसेट है और कोई दो फिक्समम्स जोड़ सकता है और एक फिक्सनम पूर्णांक परिणाम प्राप्त कर सकता है। केवल अंतर ही देखे जा सकते हैं कि गैर-फिक्सम पूर्णांक के साथ गणना धीमी है, अधिक संग्रहण की आवश्यकता है ... आम तौर पर, यदि आप पूर्णांक के साथ गणना करना चाहते हैं, तो आपको यह घोषणा करने की आवश्यकता नहीं है कि आप 64 बिट के साथ गणना करना चाहते हैं । आप केवल उन लोगों के लिए इंटीग्रर्स और सामान्य संचालन का उपयोग करते हैं।

यदि आप असली 64 बिट बड़े पूर्णांक (केवल 64 बिट्स में, बिना टैग के इत्यादि) में प्रतिनिधित्व करते हैं और उनके साथ गणना करते हैं, तो आप पोर्टेबल एएनएसआई सीएल क्षमताओं को छोड़ देंगे। यदि और कैसे सीएलआईएसपी इसका समर्थन करता है, तो सीएलआईएसपी मेलिंग सूची पर सबसे अच्छा पूछा जाता है।

प्रलेखन

• प्रकार FIXNUM
• प्रकार INTEGER

Answer 4

उदाहरण बिट वैक्टर/सरणियों का उपयोग एक 8x8 सा बोर्ड (लागू करने के लिए बेरहमी से और समय से पहले ही अनुकूलित कोड के साथ शुरू बस पता चलता है एक तंग असेंबलर कोड प्राप्त करने का तरीका):

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

MAKE-BITBOARD बिट्स की सरणी के रूप में 8x8 बिटबोर्ड बनाएगा। जब एसबीसीएल का उपयोग करते हुए, यह आंतरिक रूप से 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 रों वहाँ GET-BITBOARD के लिए अनुमति देने के लिए स्थानीय inlining requests हैं।

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 फिर, लिनक्स 64) से पता चलता है कि कंपाइलर 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)) 

... और फिर एक प्रोफाइलर का उपयोग करते हैं सा बोर्ड का उपयोग करता है, जहां सीपीयू बाधाओं को देखने के लिए खेल कोड चल रहा है। एसबीसीएल में एक अच्छा statistical profiler शामिल है।

सरल और धीमे कोड से शुरू, गति के लिए कोई घोषणा नहीं है, सबसे अच्छा है। बस कोड के आकार की तुलना करें - मैंने कोड के साथ शुरू किया है जिसमें पर सरल कोड बनाने के लिए बहुत सी घोषणाओं के साथ तुलना की गई है :-)। यहां लाभ यह है कि विचारों को बाहर करने की कोशिश करते समय सामान्य लिस्प को स्क्रिप्टिंग/प्रोटोटाइप भाषा के रूप में देख सकते हैं, फिर प्रोफाइलर सुझाव के कोड से अधिक प्रदर्शन निचोड़ें।

असेंबली कोड स्पष्ट रूप से में एक 64 बिट रजिस्टर में पूरे बोर्ड को लोड करने और फिर व्यक्तिगत बिट्स तक पहुंचने के रूप में तंग नहीं है। लेकिन अगर आप अचानक निर्णय लेते हैं कि आप प्रति वर्ग 1 से अधिक बिट चाहते हैं, तो एंबलर कोड बदलने के लिए सीएल कोड को बदलने में आसान है ( '(mod 2) से '(mod 16) से उदाहरण के लिए सरणी प्रकार को हर जगह बदलें)।