#:g1: Allegro CL: LLの紹介

Posted 2014-12-16 15:00:00 GMT

(LISP Library 365参加エントリ)
(Lisp Advent Calendar 2014参加エントリ)

 LISP Library 365 の351日目、Lisp Advent Calendar 2014の17日目です。

Allegro CL: LLとはなにか

 Allegro CL: LLは、Allegro CLで低レベルを記述する仕組みです。

パッケージ情報

パッケージ名Allegro CL: LL
ドキュメントILC 2007 Tutorial: Optimizing and Debugging Programs in Allegro CL - LL

インストール方法

 Allegro CL標準の機能です。compilerパッケージに定義されているようです。

試してみる

 LLというのは、何の略なのかというところですが、`attempt to perform low-level compiler-only :+ operation on NIL.'というエラーメッセージが出るところからすると、Low-Levelの略でしょうか。
Allegro CLにはLAPを直に書く機能もありますが、LLは、もう少しLispの世界と行ったり来たりがしやすくありつつ、インストラクションには大体1対1で対応した命令があるようです。なお、キャリーフラグ等の状態も取得できます。詳細は上記リンクの文献を参照してください。
ということで、簡単なコードでも書いてみます。

 以前、SBCLでVOPの実験をした時にfactの高速化を試みたことがありましたが、繰り返しでfactを書いてdisassembleしてみたところ、SBCLと同様に、繰り返し内でimulする度にfixnumと即値を変換していたので、これを出入口で一つにまとめてみたいと思います。

(defun fact-loop (n)
  (declare (optimize speed (safety 0) (debug 0)))
  (declare (fixnum n))
  (prog ((a 1))
        (declare (fixnum a))
     L0 (cond ((zerop n)
               (go L1 )))
        (setq a (* a n))
        (decf n)
        (go L0)
     L1 (return a)))

(fact-loop 30) ;=> 458793068007522304

;; code start: #x1002a140d8: 0: 49 c7 c5 08 00 movq r13,$8 ; 1 00 00 7: eb 0c jmp 21 9: 49 c1 fd 03 sar r13,$3 13: 4c 0f af ef imulq r13,rdi 17: 48 83 ef 08 sub rdi,$8 21: 48 83 ff 00 cmp rdi,$0 25: 75 ee jnz 9 27: 49 8b fd movq rdi,r13 30: f8 clc 31: 4c 8b 74 24 10 movq r14,[rsp+16] 36: c3 ret 37: 90 nop

 これをLLを使ってこんな感じに書いてみました。

(defun fact-loop/ (n)
  (declare (optimize speed (safety 0) (debug 0)))
  (declare (fixnum n))
  (prog ((a (comp::ll :fixnum-to-mi 1))
         (n (comp::ll :fixnum-to-mi n)))
     L0 (cond ((comp::ll := 0 n)
               (go L1 )))
        (setq a (comp::ll :* a n))
        (setq n (comp::ll :- n (comp::ll :fixnum-to-mi 1)))
        (go L0)
     L1 (return (comp::ll :mi-to-fixnum a))))

;; disassembly of #<Function FACT-LOOP/> ;; formals: N ;; code start: #x1001084a98: 0: 49 c7 c5 01 00 movq r13,$1 00 00 7: 48 c1 ff 03 sar rdi,$3 11: eb 08 jmp 21 13: 4c 0f af ef imulq r13,rdi 17: 48 83 ef 01 sub rdi,$1 21: 48 83 ff 00 cmp rdi,$0 25: 75 f2 jnz 13 27: 49 8b fd movq rdi,r13 30: 48 c1 e7 03 sal rdi,$3 34: f8 clc 35: 4c 8b 74 24 10 movq r14,[rsp+16] 40: c3 ret 41: 90 nop

 速度を比べてみます。

(dotimes (i (expt 10 8))
  (fact-loop 60))
;=> NIL
#|------------------------------------------------------------|
; cpu time (non-gc) 5.516000 sec user, 0.000000 sec system
; cpu time (gc)     0.000000 sec user, 0.000000 sec system
; cpu time (total)  5.516000 sec user, 0.000000 sec system
; real time  5.516957 sec
; space allocation:
;  54 cons cells, 5,232 other bytes, 0 static bytes
x86_64
 |------------------------------------------------------------|#

(dotimes (i (expt 10 8)) (fact-loop/ 60)) ;=> NIL #|------------------------------------------------------------| ; cpu time (non-gc) 3.640000 sec user, 0.000000 sec system ; cpu time (gc) 0.000000 sec user, 0.000000 sec system ; cpu time (total) 3.640000 sec user, 0.000000 sec system ; real time 3.640540 sec ; space allocation: ; 27 cons cells, 2,640 other bytes, 0 static bytes x86_64 |------------------------------------------------------------|#

少し速くなりました。

まとめ

 今回は、Allegro CL: LLを紹介してみました。
SBCL/CMUCLのVOPより手軽に使えて書き易い気がしました。通常の式と混ぜられるのが良いですね。
明日のLisp Advent Calendar 2014は、@y2q_actionmanさんです。お楽しみに。

comments powered by Disqus