2011-12-30 16 views
5

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

+0

आप किस लिस्प कार्यान्वयन का उपयोग कर रहे हैं? – seh

+0

@seh: मैं सामान्य lisp – Mark

+0

कौन सी सीएल कार्यान्वयन का उपयोग कर रहा हूं? आरईपीएल में निम्नलिखित दो रूपों का मूल्यांकन करने का प्रयास करें: '(लिस्प-कार्यान्वयन-प्रकार) 'और' (लिस्प-कार्यान्वयन-संस्करण) '। – seh

उत्तर

2

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

+0

बिट में हेरफेर करना 64 बिट पूर्णांक के रूप में तेज़ वैक्टर? मैं कैसे lisp में 64 बिट पूर्णांक तक नहीं पहुंच सकता? क्या ऐसा इसलिए है क्योंकि यह कार्यान्वयन पर निर्भर करता है? – Mark

7

आप प्रकार (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 
+0

क्या आप थोड़ा और विस्तार कर सकते हैं? मैं सामान्य lisp 2.48 का उपयोग कर रहा हूं और जब मैंने टाइप किया (हस्ताक्षर-बाइट 64) मुझे – Mark

+0

'(हस्ताक्षरित-बाइट 64) त्रुटि मिली है, एक प्रकार का विनिर्देशक है, फ़ंक्शन नहीं। इसका उपयोग केवल तभी किया जा सकता है जहां एक प्रकार का विनिर्देशक कानूनी है। मैंने अपने जवाब में एक उदाहरण जोड़ा है। –

+0

क्या आप बिट्स सेट करने और बिट्स प्रदर्शित करने के लिए एक अच्छा तरीका जानते हैं? – Mark

6

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

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

प्रलेखन

5

उदाहरण बिट वैक्टर/सरणियों का उपयोग एक 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) से उदाहरण के लिए सरणी प्रकार को हर जगह बदलें)।

+0

बिट-वैक्टर के बजाय पूर्णांक का उपयोग करने के बारे में क्या? इस तरह का अंतर क्या है? कौन सा तेज़ है? – Mark

+0

समस्या यह है कि सीएल स्पेक आपको गारंटीकृत आकार के फ़िक्समम्स नहीं देता है - 64 बिट पर आपको आज अधिकांश कार्यान्वयन पर एक बिग्नम मिलेगा (32 बिट कार्यान्वयन - बहुत छोटा, जाहिर है, 64 बिट कार्यान्वयन - वे कुछ बिट्स का उपयोग करते हैं टैगिंग के लिए)। तो आप बिग्नम्स के साथ समाप्त हो जाते हैं, या आप 4 बिट बिट फिक्सम में 64 बिट फिक्सम को विभाजित कर सकते हैं और वहां से जा सकते हैं। 'तेज़' के लिए, यह कार्यान्वयन, अनुकूलन आदि पर निर्भर करता है। इसे मापें! व्यक्तिगत रूप से, मैं 'तेज़' और 'धीमी' के संदर्भ में नहीं सोचता, लेकिन 'पर्याप्त तेज़' और 'बहुत धीमा' - इससे मुझे 'किस के लिए' जवाब देने के लिए मजबूर किया जाता है? सवाल, जो अच्छा आईएमओ है। –

+1

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

संबंधित मुद्दे