4
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

LispAdvent Calendar 2015

Day 8

Triviaでlambda-list パターンを実装 したら destructuring-bind より早くなった話

Last updated at Posted at 2015-12-10

拙作 Trivia は、 m2ym氏作のOptimaを書き直したコピーライブラリです。

インターフェースはOptima完全互換、テストコードもほぼ同じでそのまま通ります。
なぜこうしたかというと、

  1. Optimaも元はfare-matcher の構文を採用。この構文ももとからよく出来たもの。
  2. 速度比較をするなら同じ構文にしたほうがやりやすい。
  3. もうすでにOptimaはlispの中でも有名ライブラリという形になっていて、移行コストがちょっとでもあったらユーザーは得られないだろうなと思ったから。タダでさえ狭いlispコミュニティで…。
  4. だいたいパターンマッチでそんなにいくつも構文があったらこまるでしょうに。

コピーとはいえ、改善点がいくつかあります。

  • optimaより速いです。Optimaで実験するとマッチ中になぜかConsingが発生しますが、Triviaでは発生しません。
  • lispがメインの自分と違って、m2ymさんは元はMLが中心の方。ライブラリの更新も最低限にされているようです。
  • Optimaには既存の構文を拡張するためのdefpatternがありますが、 defpatternだけでは基礎的なパターンを定義できません。

今回やったのは、このTriviaのなんでもパターンにできる特性を用いて、lambda-list パターンを定義した、というものです。

はじまり

はじまりは akssri 氏 (インド出身っぽい) からのpullreqでした。一部自分には読めない文字で書いてありましたが、とにかくこの人がlambda-list パターンの原型を作ってくれました。

lambda-list とは、 関数の引数とか、destructuring-bindに書けるあのあれです。

(lambda (a b c &optional (d "default" default-supplied-p))
  (format t "~a ~a ~a ~a should all die" a b c d))

(destructuring-bind (&rest rest &key key1
                                     (key2 :default)
                                     ((:key3 k3) :default key3-supplied-p)
                                &allow-other-keys)
   (print :アババババ))

(defmacro crap-macro (&whole whole a (&key b c) &aux (d "d"))
   `(,a ,b ,c ,d))

これを、Triviaのパターンマッチャで書けるようにしました。他の普通のパターンと混ぜてかけます:

(match '(1 #(1 2 3) 4)
  ((lambda-list a (vector 1 _ b) c
                &optional ((string #\d #\e #\f _ _ d _) "default"))
   (list a b c d)))

;; --> (1 3 4 #\l)

どうやら動くので、ロジックが正しいということはわかりましたから、単体テストまで書いてもらって、そのあとリファクタリングしました。

結果

destructuring-bind も同じようなことが出来ますので、速度比較を行ってみました。というか、akssri さんがやってくれました。

テストコード
(let ((lst '(1 :b 2)) (tmp 0))
     (time (dotimes (_ 1000)
         (match lst
           ((λlist a &key b) (incf tmp b)))))
     (time (dotimes (_ 1000)
         (destructuring-bind (a &key b) lst
           (incf tmp b)))))
結果
Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  11,484 processor cycles
  0 bytes consed

Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  58,386 processor cycles
  0 bytes consed

プロセッササイクルで考えると6倍ぐらい早くなりました。
めでたしめでたし。

4
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
4
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?