nptclのブログ

Common Lisp処理系nptの開発メモです。https://github.com/nptcl/npt

formatterで高速化

Common Lisp

【追記】内容が間違っていたので何回か書き直しました。

Common Lispの、formatterマクロの使い方を紹介します。

このマクロは、formatの制御文字を受け取って関数を返却するものです。
とりあえず例をあげます。

下記のformat文を考えます。

(format t "Hello~%")

実行すると次のような出力をします。

Hello

それに対してformatterは、ただ関数を返却するだけです。
とりあえず実行してみます。

(formatter "Hello~%")
  -> #<FUNCTION>

関数が返却されました。
これを実行してみるとどうなるでしょう。

(funcall (formatter "Hello~%") *standard-output*)
Hello

ちなみにfuncallはnilを返却します。

これは一体なにが楽しいのでしょうか？

formatterはformat関数を高速化するためのものです。
大きく、下記の2つのアプローチから高速化を実現します。

まず「構文解析を事前に行う」とはどういう事でしょうか。

構文解析とは、例えば"Hello~%"という文字を見て、 ①Helloの出力と②terpriの出力に分けることです。
formatの制御文字は文字列によりゴチャゴチャと記載されているため、 一文字ずつ調べて行き、~文字が現れたら さあどうしようかと考える処理が必要になります。
制御文字を一つずつ読んで解析するのはそれなりに時間がかかる作業です。
この解析を行うのがformatterマクロの仕事になります。

もう一つの「コンパイルにより高速化を行う」というのはどういう事でしょうか。
それはformatterを用いることでformatの制御文字そのものを 機械語の変換してしまおうというものです。
nptはインタープリタなのでその恩恵は得られませんが、 compileを実装したLisp処理系だと、 format制御文字をLisp式にさえ変換できれば コンパイルで機械語に変換できるので、 かなり高速に実行できるようになります。

formatterによる高速化の作業は、実際にコードが実行する時点より 遥かに前で終わらせておくことができます。
例えば次のような文を考えます。

(dotimes (i 5)
  (format t "Hello: ~A~%" i))

難しいことは何もない文ですね。
実行結果を下記に示します。

Hello: 0
Hello: 1
Hello: 2
Hello: 3
Hello: 4

この文の問題点は、"Hello: ~A~%"という文字を 5回も構文解析している点にあります。
「先頭にHello:があってprincの次にterpriがある」という分析は、 何も律義に5回実行する必要なんてありません。

それに今回は5回で済んでいますが 何万回も出力するということは珍しくないと思います。
そういうときにformatterマクロの出番です。

(setq *format* (formatter "Hello: ~A~%"))
(dotimes (i 5)
  (funcall *format* *standard-output* i))

いいですね。
構文解析が1回で終わっています。
【変更】 さらに次のように書き直すことができます。

(dotimes (i 5)
  (format t #.(formatter "Hello: ~A~%") i))

formatterの結果を#.によりread時に実行するように変更しています。
すると全体では下記のような文になります。

(dotimes (i 5)
  (format t #<FUNCTION> i))

なぜformatの引数にformatterを指定しているのか疑問に思うかもしれません。
実はformat関数は、制御文字の引数に関数そのものを受け取ることができます。
ちょうどformatterの返却値を受け取るように考慮されているのです。

実際、やっていることは次の命令と変わりません。

(dotimes (i 5)
  (funcall #<FUNCTION> *standard-output* i))

以上でformat関数をより高速に実行する方法を覚えました。

では実際にやってみましょうということで、 速度を測定してみたりしても 全然変わらないじゃないかと思う人もいるかもしれません。

実際、全然変わっていない可能性が高いです。
なぜなら、Lisp処理系がeval時に勝手にformatterを実行しているからです。

つまり、

(format t "Hello~%")

と記載していたにも関わらず、 処理系はお節介にも

(format t (formatter "Hello~%"))

と変換して実行しているのです。

本当に？
調べる方法があります。

次の例文を考えましょう。

(format t "ERROR ~! ERROR")

見てわかるように、~!なんて命令は無いので不正な文です。
実行してみましょう。

(format t "ERROR ~! ERROR")
  →エラー、~!なんて知らない

そりゃそうです。
しかしlambdaで囲んだらどうなるでしょうか。

(lambda () (format t "ERROR ~! ERROR"))

普通に考えるならば、実行結果は何も問題が無いはずです。
では実際はどうなるでしょうか？
各処理系で実行した結果を示します。

  • sbcl

    • WARNING, ~!がおかしい
    • FUNCTION返却

  • clisp

    • FUNCTION返却

  • ccl

    • WARNING, ~!がおかしい
    • FUNCTION返却

clispは素直にlambdaで囲んだ分を返却しています。
しかしsbclとcclはWARNINGが出力されているため、 formatの制御文字を構文解析しようと試みたのが分かります。

この事前処理を行おうとしたのはevalの最適化です。
もしformat文の2番目の引数が文字列だったら、 先行してformatterを実行しておこうした結果です。

これはありがたい。
何も考えなくてもいいんですから。

しかし最適化が見てくれているとしても、 例えば実験データなんかを大量に出力するということが分かり切っている場合は、 format文の制御文字の代わりにformatterを使っておくのはいい考えだと思います。

ちなみにsbclだと、optimizeのspeedを0にすることで この機能を解除することができました。

(locally
  (declare (optimize (speed 0)))
  (lambda () (format t "ERROR ~! ERROR")))
  -> WARNINGは出ない
  -> FUNCTION返却

書き直しについて

最初は、#.をつけずに下記のように実行することを考えていました。

(dotimes (i 5)
  (format t (formatter "Hello: ~A~%") i))

しかしどの処理系を見てもformatterはlambda式を返却するため、 これだと構文解析は1回で終わるのですが、実行するたびに関数が生成されてしまいます。
つまり上記の例では、lambdaにより5個の無名関数が生成されてしまいます。

formatterが無いときに比べれば早くなるので悪くはないのですが、 メモリを無駄に使うのも良くはありません。
確実に#.を付けた方がいいでしょう。
しかし#.による仕組みは、見た目は綺麗ですが結構変なことをしていますので、 setqやletなんかでformatterの関数を 変数に束縛するのが一番素直で確実なのかもしれません。
つまりはこんな感じ。

(setq *format* (formatter "Hello: ~A~%"))
(dotimes (i 5)
  (format t *format* i))