ビット加算器であそぶ

一本目

はい

(defun bit-add (a b)
  (let* ((base-length (max (length a) (length b)))
         (base-length-1 (1- base-length))
         (tmp    (make-array base-length :element-type 'bit :initial-element 0))
         (tmp2   (make-array base-length :element-type 'bit :initial-element 0))
         (cin    (make-array base-length :element-type 'bit :initial-element 0))
         (cout   (make-array base-length :element-type 'bit :initial-element 0))
         (sum    (make-array base-length :element-type 'bit :initial-element 0)))
    (bit-xor a b tmp)
    (bit-and a b tmp2)
    (dotimes (i base-length)
      (bit-ior tmp2 (bit-and tmp cin) cout)
      (replace cin cout
               :start1 1 :end1 base-length
               :start2 0 :end2 base-length-1))
    (bit-xor tmp cin sum)
    (values sum (aref cout base-length-1)))) ; carry-up

動く。

TO-SAS.3690427216> (bit-add #*1000000000000000000000000000000000000000000000000000000000000000 
                            #*1111111111111111111111111111111111111111111111111111111111111111)
#*0000000000000000000000000000000000000000000000000000000000000000
1

TO-SAS.3690427216> (time
                    (dotimes (i 1000000)
                      (bit-add #*0000000000000000000000000000000000000000000000000000000000000000
                               #*0000000000000000000000000000000000000000000000000000000000000000)))


Evaluation took:
  2.341 seconds of real time
  2.352000 seconds of total run time (2.352000 user, 0.000000 system)
  [ Run times consist of 0.084 seconds GC time, and 2.268 seconds non-GC time. ]
  100.47% CPU
  7,035,187,988 processor cycles
  2,207,997,056 bytes consed

; disassembly for BIT-ADD
; Size: 1789 bytes. Origin: #x1004D880D4

コンスしまくり。

二本目 --- 型宣言追加

  (declare (simple-bit-vector a b))
  (declare (optimize (speed 3) (safety 0)))
; disassembly for BIT-ADD
; Size: 1279 bytes. Origin: #x10052B5872

Evaluation took:
  2.028 seconds of real time
  2.036000 seconds of total run time (2.028000 user, 0.008000 system)
  [ Run times consist of 0.100 seconds GC time, and 1.936 seconds non-GC time. ]
  100.39% CPU
  6,097,897,182 processor cycles
  2,208,012,800 bytes consed

まだコンスしまくり。

3本目 dynamic-extent

メモリをスタックアロケートしてみよう。

    (declare (dynamic-extent tmp tmp2 cin cout sum))

Evaluation took:
  1.980 seconds of real time
  1.992000 seconds of total run time (1.988000 user, 0.004000 system)
  [ Run times consist of 0.088 seconds GC time, and 1.904 seconds non-GC time. ]
  100.61% CPU
  5,951,275,610 processor cycles
  2,048,000,448 bytes consed

; disassembly for BIT-ADD
; Size: 1151 bytes. Origin: #x10066F4502

スタックアロケート出来てるのにコンスし過ぎじゃない?

4本目

置き場所に書き込むようにしてみた。ビット数も固定。

(defun bit-add (a b &optional (sum
                               (make-array 64 :element-type 'bit :initial-element 0)))
  (declare ((simple-bit-vector 64) a b sum))
  (declare (optimize (speed 3) (safety 0)))
  (let* ((tmp    (make-array 64 :element-type 'bit :initial-element 0))
         (tmp2   (make-array 64 :element-type 'bit :initial-element 0))
         (cin    (make-array 64 :element-type 'bit :initial-element 0))
         (cout   (make-array 64 :element-type 'bit :initial-element 0)))
    (declare (dynamic-extent tmp tmp2 cin cout))
    (declare ((simple-bit-vector 64) tmp tmp2 cin cout))
    (bit-xor a b tmp)
    (bit-and a b tmp2)
    (dotimes (i 64)
      (bit-ior tmp2 (bit-and tmp cin) cout)
      (replace cin cout
               :start1 1 :end1 64
               :start2 0 :end2 63))
    (bit-xor tmp cin sum)
    (values sum (aref cout 63))))


(time
                    (let ((a #*0000000000000000000000000000000000000000000000000000000000000000)
                          (b #*0000000000000000000000000000000000000000000000000000000000000000)
                          (c #*0000000000000000000000000000000000000000000000000000000000000000))
                      (dotimes (i 1000000)
                        (bit-add a b c))))

Evaluation took:
  1.905 seconds of real time
  1.912000 seconds of total run time (1.908000 user, 0.004000 system)
  [ Run times consist of 0.088 seconds GC time, and 1.824 seconds non-GC time. ]
  100.37% CPU
  5,727,066,306 processor cycles
  2,047,999,856 bytes consed

だめだな。なんでだろう。

5 凡ミスだった

-     (bit-ior tmp2 (bit-and tmp cin) cout)
+     (bit-and tmp carry carry)
+     (bit-ior tmp2 carry carry)

0 bytes consed.

6 time がcons している

5時間前

@guicho271828 憶測ですが、timeのボディの中のアロケートも拾ってしまうことがあるようなので、できるだけtimeの外に出せば良いのかもしれません |実験 => https://gist.github.com/g000001/f28186c8e9262c98a78f68d8ad77fbed

当たってた。

(defun test ()
  (let ((a #*0000000000000000000000000000000000000000000000000000000000000000)
        (b #*0000000000000000000000000000000000000000000000000000000000000000)
        (c #*0000000000000000000000000000000000000000000000000000000000000000))
    (declare (inline bit-add))
    (dotimes (i 1000000)
      (bit-add a b c))))

(time (test))

Evaluation took:
  1.044 seconds of real time
  1.044000 seconds of total run time (1.044000 user, 0.000000 system)
  100.00% CPU
  3,137,843,573 processor cycles
  0 bytes consed