GC のタイミングと処理時間 〜 コンパイルしたら遅くなる!? 〜

はじめに

一般に「コンパイルしたプログラムは、インタプリタより高速に実行できる」と言われています。

しかし、 Allegro CL 8.2 を処理系とした Lisp プログラムにおいて、 プログラムの書き方(構造)によっては、稀に、コンパイルすると遅くなる場合があります。

コンパイルすると遅くなるプログラム

以下が、コンパイルすると遅くなる現象を再現するプログラムです。

(defun strange-function ()
  (loop repeat 10
      do (let ((n-list (make-list 1000000))
               (1-list (list nil)))
           (and n-list 1-list))))
  • OS: CentOS 6.2
  • Allegro CL: Enterprise Edition 8.2

再現

実行してみます。

最初に、GC によるメモリ領域の拡張が起きないよう、 十分な領域を確保します。

CL-USER(2): (system:resize-areas :old 10000000 :new 100000000)
CL-USER(3): 

次に、関数を定義します。

CL-USER(3): (defun strange-function ()
              (loop repeat 10
                  do (let ((n-list (make-list 1000000))
                           (1-list (list nil)))
                       (and n-list 1-list))))
STRANGE-FUNCTION
CL-USER(4):

メモリ上のゴミを GC の強制実行によって削除してから、 strange-function をインタプリタで実行した場合の処理時間を計測します。

CL-USER(4): (progn (gc :tenure) (gc t))
CL-USER(5): (time (strange-function))
; cpu time (non-gc) 0.038994 sec user, 0.018997 sec system
; cpu time (gc)     0.007999 sec user, 0.000000 sec system
; cpu time (total)  0.046993 sec user, 0.018997 sec system
; real time  0.066760 sec
; space allocation:
;  10,000,455 cons cells, 8,496 other bytes, 0 static bytes
NIL
CL-USER(6):

0.067秒で実行できました。

次に、 strange-function をコンパイルした場合の処理時間を計測します。 公平に比較するために、Allegro CL を一度終了してから上記と同じ手順で CL-USER(3): までの操作を行いました。 それ以降の実行ログを以下に示します。

CL-USER(4): (compile 'strange-function)
STRANGE-FUNCTION
NIL
NIL
CL-USER(5): (progn (gc :tenure) (gc t))
CL-USER(6): (time (strange-function))
; cpu time (non-gc) 0.042993 sec user, 0.014998 sec system
; cpu time (gc)     0.028996 sec user, 0.000000 sec system
; cpu time (total)  0.071989 sec user, 0.014998 sec system
; real time  0.087266 sec
; space allocation:
;  10,000,010 cons cells, 0 other bytes, 0 static bytes
NIL
CL-USER(7): 

0.087秒かかっており、 コンパイルした方が遅いという結果になりました。

処理時間の内訳を比較してみると、コンパイルした方がインタプリタで実行した場合に比べて、 GC に 0.02 秒多く時間が使われていることがわかります。

なぜ GC の処理時間に違いがでたのか

Allegro CL では次のパラメタを設定すると GC のログを出力することができます。

(setf (sys:gsgc-switch :print) t
      (sys:gsgc-switch :verbose) t)

これを設定して、先程と同じ手順で strange-function を実行します。

インタプリタの場合:

CL-USER(5): (strange-function)
scavenging...done eff: 80%, new copy: 4260224 + tenure: 0 +  aclmalloc free: 0 = 4260224
  Page faults: non-gc = 0 major + 527 minor, gc = 0 major + 2 minor
NIL
CL-USER(6): 

コンパイルをした場合:

CL-USER(6): (strange-function)
scavenging...done eff: 51%, new copy: 20256736 + tenure: 0 +  aclmalloc free: 0 = 20256736
  Page faults: non-gc = 0 major + 521 minor, gc = 0 major + 10 minor
NIL
CL-USER(7): 

GC による scavenging は共に1回行なわれていますが、 コンパイルした場合の方が new 領域へのデータのコピー量 ("new copy:" の値) が多いことがわかります。

この結果から、コンパイルした場合の方が scavenging の効率が悪く、 new 領域へのコピー量が多くなったことによって処理時間が遅くなったことがわかりました。

なぜコンパイルした方が scavenging の効率が悪いのか

なぜ new 領域へのデータのコピー量に違いが出たのでしょうか。 strange-function を改めて見てみます。

1:  (defun strange-function ()
2:    (loop repeat 10
3:        do (let ((n-list (make-list 1000000))
4:                 (1-list (list nil)))
5:             (and n-list 1-list))))

この問題のポイントは、いつ変数が bind され、 いつその bind が解かれるのか、という点にあります。また、GC が動くタイミングは、 大きなデータを生成している make-list を実行している最中であることに留意ください。

インタプリタの場合

最初に、インタプリタによる実行の場合について説明します。

インタプリタは評価規則に従って式を順々に評価するものです。1

変数 n-list1-list は、 3 行目let 句を評価する際に bind されますが、 これらの binding を確保しておくための environment は、 loop 中 毎回 let 句に出合うたびに新たに設けられ、 let 句を拔ければ、破棄される。 つまり、 binding は、一旦 let 句を拔ければ、 すぐさま解放されると考える事ができます。

このため、 loop のN回目の make-list の実行によって GC が動いた時、一つ前 (N-1回目) の make-list で得られたデータの binding は既にどこにも存在しませんので、 一世代前のデータはゴミと判断されて new 領域にコピーされません。 新たに make-list が生成しているデータだけが new 領域にコピーされます。

よって、GC が動いた時に new 領域にコピーされるのは、 高々 make-list 1回分のデータ量となります。

コンパイルした場合

まずは、コンパイルを行った場合のレキシカル変数の bind 方法について説明します。

  • レキシカル変数には、一般にその値を保持するための領域がスタック上に確保されます。
  • レキシカル変数の値を保持するスタックフレームは、関数がエントリーされた時に確保されます。

このことから、 strange-function が呼出されたときには、 変数 n-list1-list の値を登録するための領域 (slot) がスタック上に確保されます。

loop が開始し、 3 行目make-list を呼び出して結果を得ると、 その結果は一旦 n-list の slot に登録されます。次に 4 行目list を呼び出し、 そこで得た結果と n-list の slot に登録されている値とを使用して 5 行目and 演算を行います。 これが loop によって繰返し行われます。

loop の2回目以降の実行で 3 行目make-list を呼び出すとき、 その結果が得られるまで、 n-list の slot には一つ前の loop で獲得した値 (本来ゴミとなるべき値) が未だ登録されたままになっています。 この状態のまま make-list が実行されることによって GC が動きます。

GC (tenure) は「データが生きているのかどうか」の判断を、その時のコールスタック上の変数に対し行って、 生きていると判断されたデータを new 領域にコピーします。 これに従うと、 loop の N回目の実行によって GC が動いた時、 関数 make-list が新たに生成しているデータと、 n-list の slot に登録されたままになっている、一つ前 (N-1回目) の loop で獲得したデータが、それぞれ new 領域にコピーされます。

つまり、GC が動いた時に new 領域にコピーされるのは、 高々 make-list 2回分のデータ量となり、 インタプリタによる実行の場合と比べると、 一つ前の loop で獲得した値の分だけ new 領域へのコピー量が多くなります。

コンパイルした結果を disassemble して、その動作を確認します。

CL-USER(8): (disassemble 'strange-function)
;; disassembly of #<Function STRANGE-FUNCTION>
;; formals: 
;; constant vector:
0: EXCL::INTERNAL-MAKE-LIST

;; code start: #x1000a781b8:
   0: 48 81 ec 88 00 subq       rsp,$136     ; 17
      00 00 
   7: 4c 89 74 24 08 movq       [rsp+8],r14
  12: 48 83 f8 00    cmp        rax,$0
  16: 74 01          jz 19
  18: 06             (push es)        ; SYS::TRAP-ARGERR
  19: 41 80 7f a7 00 cmpb       [r15-89],$0  ; SYS::C_INTERRUPT-PENDING
  24: 74 01          jz 27
  26: 17             (pop ss)         ; SYS::TRAP-SIGNAL-HIT
  27: 48 c7 c7 50 00 movq       rdi,$80      ; 10
      00 00 
  34: 48 c7 c6 08 00 movq       rsi,$8       ; 1
      00 00 
  41: 40 f6 c7 07    testb      dil,$7
  45: 75 34          jnz        99
  47: 4c 8b ef       movq       r13,rdi
  50: 4c 2b ee       subq       r13,rsi
  53: 70 2c          jo 99
  55: 4c 89 6c 24 78 movq       [rsp+120],r13        ; #:|g-7|
  60: 33 f6          xorl       esi,esi
  62: 41 f6 c5 07    testb      r13b,$7
  66: 75 2e          jnz        114
  68: 4c 3b ee       cmpq       r13,rsi
  71: 7d 3b          jnl        132
  73: 41 80 7f a7 00 cmpb       [r15-89],$0  ; SYS::C_INTERRUPT-PENDING
  78: 74 01          jz 81
  80: 17             (pop ss)         ; SYS::TRAP-SIGNAL-HIT
  81: 49 8b ff       movq       rdi,r15
  84: f8             clc
  85: 48 8d a4 24 88 leaq       rsp,[rsp+136]
      00 00 00 
  93: 4c 8b 74 24 10 movq       r14,[rsp+16]
  98: c3             ret
  99: 49 8b af cf fb movq       rbp,[r15-1073]       ; EXCL::-_2OP
      ff ff 
 106: ff 53 d0       call       *[rbx-48]    ; SYS::TRAMP-TWO
 109: 4c 8b ef       movq       r13,rdi
 112: eb c5          jmp        55
 114: 49 8b fd       movq       rdi,r13
 117: 49 8b af 4f fd movq       rbp,[r15-689]        ; EXCL::<_2OP
      ff ff 
 124: ff 53 d0       call       *[rbx-48]    ; SYS::TRAMP-TWO
 127: 4c 3b ff       cmpq       r15,rdi
 130: 75 c5          jnz        73
 132: 49 8b f7       movq       rsi,r15
 135: 49 8b 6e 36    movq       rbp,[r14+54] ; EXCL::INTERNAL-MAKE-LIST
 139: 48 c7 c7 00 12 movq       rdi,$8000000 ; 1000000
      7a 00 
 146: ff 53 d0       call       *[rbx-48]    ; SYS::TRAMP-TWO
 149: 48 89 7c 24 70 movq       [rsp+112],rdi        ; N-LIST
 154: 49 8b ff       movq       rdi,r15
 157: 49 8b f7       movq       rsi,r15
 160: 41 ff 57 07    call       *[r15+7]     ; SYS::QCONS
 164: 4c 3b 7c 24 70 cmpq       r15,[rsp+112]        ; N-LIST
 169: 75 00          jnz        171
 171: 41 80 7f a7 00 cmpb       [r15-89],$0  ; SYS::C_INTERRUPT-PENDING
 176: 74 01          jz 179
 178: 17             (pop ss)         ; SYS::TRAP-SIGNAL-HIT
 179: 48 8b 7c 24 78 movq       rdi,[rsp+120]        ; #:|g-7|
 184: e9 65 ff ff ff jmp        34
 189: 90             nop
CL-USER(9): 

code 132 から code 146make-list を呼び出しています。 次の code 149 で、 [rsp+112] にレジスタの値を movq することによって、 n-list の slot に make-list の結果を登録しています。 次に (list nil) の呼び出しを行い、 その結果が登録されたレジスタと [rsp+112] とを cmpq で比較することによって and 演算を行っています。

この結果を見ると、 n-list の slot である [rsp+112] に値を movq している箇所は、 code 149 の一箇所だけです。つまり、 n-list の slot に登録される値は make-list の結果だけであり、 これが登録された状態のまま次の loop が実行されることがわかります。 従って、次の make-list の結果で上書きされるまで、一つ前の loop で獲得した make-list の結果はゴミにならないことがわかります。

また、 1-list については、 (list nil) の結果を slot に登録していないことがわかります。 1-list は bind 直後の and 演算で使われるだけであるため、 slot には登録せずに、 (list nil) の結果が登録されたレジスタを直接参照して and 演算を行うようコンパイルされました。

どのようにして回避できるのか

では、インタプリタによる実行と同様に効率良く scavenging を行なうためには、プログラムをどのように変更すれば良いのでしょうか。

2つの方法が考えられます。

  • loop を実行するたびに変数の slot をクリアする。
  • レジスタを利用して、大きなデータは slot に登録されないようにする。

1つ目の方法は、 make-list を呼び出す前までに、 n-list の slot に nil をセットするよう変更します。

2つ目の方法は、先程 disassemble してわかった 1-list のように、 make-list の結果を slot に登録せずに直接レジスタを参照するよう変更します。

では、1つ目の方法で変更してみます。

1:  (defun strange-function ()
2:    (loop repeat 10
3:        do (let ((n-list nil)
4:                 (1-list nil))
5:             (setf n-list (make-list 1000000))
6:             (setf 1-list (list nil))
7:             (and n-list 1-list))))

n-list nil を代入 してから make-list を呼び出すよう変更しました。 これをコンパイルして、先程と同じ手順で実行した結果は次のとおりです。

CL-USER(6): (time (strange-function))
scavenging...done eff: 54%, new copy: 20181296 + tenure: 0 +  aclmalloc free: 0 = 20181296
  Page faults: non-gc = 0 major + 526 minor, gc = 0 major + 10 minor
; cpu time (non-gc) 0.044993 sec user, 0.016997 sec system
; cpu time (gc)     0.026996 sec user, 0.003000 sec system
; cpu time (total)  0.071989 sec user, 0.019997 sec system
; real time  0.093293 sec
; space allocation:
;  10,000,010 cons cells, 0 other bytes, 0 static bytes
NIL
CL-USER(7):

new 領域へのコピー量は減っておらず、この関数定義では回避できませんでした。

なぜ回避することができなかったのか、コンパイルした結果を disassemble して確認したところ、先程掲載した 再現プログラムの disassemble 結果 と全く同じコードにコンパイルされたことがわかりました。

全く同じコードにコンパイルされた理由は、次のとおりです。

変更後の関数の定義では、 n-list への代入を 3 行目5 行目 の二箇所で行っています。この間に n-list の値を変化させる処理関数の呼び出しがないために、 コンパイラは 一つ目の代入 を不要と判断して省き、 二つ目の代入 のみを採用してコンパイルしました。 その結果、再現プログラムと全く同じコードにコンパイルされました。

同様の理由により、次にあげる定義も再現プログラムと全く同じコードにコンパイルされます。

(defun strange-function ()
  (loop repeat 10
      as n-list = nil
      and 1-list = nil
      do (setf n-list (make-list 1000000))
         (setf 1-list (list nil))
         (and n-list 1-list)))

このように、我々プログラマが値をクリアするようプログラムをしても、コンパイラによってそれが無効にされてしまうことがあります。 このため、 loop を実行するたびに変数の slot をクリアするという回避方法については、そもそもそういうプログラムを書くこと自体が難しいことだと言えそうです。2

では、2つ目の方法で変更してみます。 変更したプログラムは次のとおりです。

(defun strange-function ()
  (loop repeat 10
      do (let ((1-list (list nil))
               (n-list (make-list 1000000)))
           (and n-list 1-list))))

let における変数の bind の順番を入れ替えました。 これをコンパイルして、先程と同じ手順で実行した結果は次のとおりです。

CL-USER(6): (time (strange-function))
scavenging...done eff: 82%, new copy: 4181392 + tenure: 0 +  aclmalloc free: 0 = 4181392
  Page faults: non-gc = 0 major + 527 minor, gc = 0 major + 2 minor
; cpu time (non-gc) 0.044993 sec user, 0.014998 sec system
; cpu time (gc)     0.005999 sec user, 0.001999 sec system
; cpu time (total)  0.050992 sec user, 0.016997 sec system
; real time  0.067760 sec
; space allocation:
;  10,000,010 cons cells, 0 other bytes, 0 static bytes
NIL
CL-USER(7):

new 領域へのコピー量が減り、回避できました。

n-list を bind した直後に and 演算を行ったことによって、 先程 disassemble した結果で見た 1-list に代わり、 make-list の結果を slot に登録せずに、レジスタを直接参照して実行できました。

まとめ

この事例は、あるアプリケーションを高速化するために行なった調査の過程で見付けたものでした。 同じ目的を持った C++ で書かれたアプリケーションと Common Lisp で書かれたアプリケーションとがあり、 処理時間を比較すると Common Lisp で書かれた方が2倍遅く、かつ、想定していた倍以上のメモリを消費していたことがわかりました。

そこで、 大きなデータを指す変数をできるだけレジスタに乗せるような工夫をし、加えて Allegro CL の Runtime analyzer を利用してプログラムを見直すことで、 最終的に C++ で書かれたアプリケーションの 0.8倍の処理時間で実行できるようなチューニングを行ないました。

アプリケーションが、 想定以上にメモリを消費している場合や処理に時間がかかっている場合には、 上に述べたようなことが原因にあるかもしれません。 変数の bind の順序を入れ替えるだけで解消される可能性もあるので、 試してみて頂けたらと思います。

Allegro CL Free Express Edition

Allegro CL 8.2 の Free Express Edition (無償体験版) は、 以下から download できます。

Allegro CL Free Express Edition

resize-areas で指定するサイズや n-list の個数を調整するなどして試してみてください。

Acknowledgments

  • Duane Rettig (Franz Inc.)
    • ここでレポートした現象の原因を教えて頂きました。

Reference

Footnotes:

1 Common Lisp の仕樣にインタプリタは規定されていませんので、 以下の議論は、極く素直にインタプリタが実装されている、 という仮定の元に進めます。

2 参考までに、 loop を実行するたびに強制的に変数の slot をクリアする workaround を紹介しておきます。

(defun dummy (a b)
  (declare (ignore a b)))
(defun strange-function ()
  (loop repeat 10
      do (let ((n-list nil)
               (1-list nil))
           (dummy n-list 1-list)
           (dummy n-list 1-list)
           (setf n-list (make-list 1000000))
           (setf 1-list (list nil))
           (and n-list 1-list))))

dummy 関数を呼び出している理由については、コンパイルした結果を disassemble して考えてみてください。 dummy 関数の呼び出し回数を順に減らして disassemble してみると、その理由がわかってくると思います。

Author: 数理システム知識工学部

Date: 2013-05-10T13:34+0900

Generated by Org version 7.9.2 with Emacs version 24

© Mathematical Systems Inc. 2013