CFFI vs UFFI
risupu - notes on Lisp and programming
http://risupu.blogspot.com/2009/05/cffi-vs-uffi-performance.htmlの訳
Common LispからCの関数を呼び出すための機構は、基本的に各処理系に依存する。例えばCMUCLやSBCLは相互に互換性のあるFFI (foreign function interface)を持っている。しかしながら、これだとCのライブラリを利用する、処理系に依存しない可搬性を備えたソフトウェアを書くことはできない。
そこで、処理系非依存のFFIを実装したパッケージがある。それがCFFIとUFFIである。UFFIはCFFIより若干古い。CFFIにはUFFIを仮定して書かれたコードをCFFIで処理するための互換レイヤーを持っており、CFFI-UFFI-COMPATと呼ばれる。ASDFのシステム定義でUFFIのところをCFFI-UFFI-COMPATで置き換えることによって、CFFIひとつで全て用足りるようになる。
さらに、UFFIよりもCFFIの方がパフォーマンスの点で優れている。
例えば、CのグラフィックライブラリGDのラッパーであるCL-GDはUFFIを使用する。二つの画像間の各画素のRGB値の差分をとる関数を以下のように定義する。
(defun square (x) (the fixnum (* (the fixnum x) (the fixnum x)))) (defun compare-images (image1 image2) "Compare two images -- uses API exported by CL-GD" (declare (optimize (debug 0) (speed 3)(safety 0))) (let ((err 0) (height (cl-gd:image-height image1)) (width (cl-gd:image-width image1))) (declare (fixnum err height width)) (loop for y fixnum from 0 below height do (loop for x fixnum from 0 below width do (let ((img-color (cl-gd:get-pixel y x :image image2)) (target-color (cl-gd:get-pixel y x :image image1))) (incf err (square (- (the fixnum (cl-gd:color-component :red img-color :image image2)) (the fixnum (cl-gd:color-component :red target-color :image image1))))) (incf err (square (- (the fixnum (cl-gd:color-component :blue img-color :image image2)) (the fixnum (cl-gd:color-component :blue target-color :image image1))))) (incf err (square (- (the fixnum (cl-gd:color-component :green img-color :image image2)) (the fixnum (cl-gd:color-component :green target-color :image image1)))))))) err))
まず、標準的なCL-GDで実行時間を測る(SBCL 1.0.28, CL-GD 0.5.6, UFFI-1.6.1, 3GHz Intel Core2 Duo, Linux)。
EVO-LISA> (progn (defparameter *image1* (cl-gd:create-image-from-file "023.JPG")) (defparameter *image2* (cl-gd:create-image-from-file "023.JPG")) (time (compare-images *image1* *image2*))) height1=1024, height2=768 Evaluation took: 1.684 seconds of real time 1.688105 seconds of total run time (1.688105 user, 0.000000 system) 100.24% CPU 5,061,067,326 processor cycles 141,296 bytes consed 0
1024x768の画像を比較するのに1.68秒かかるのは極端に遅い。Common Lispで1024x768の配列の差分を計算するのに1.7秒もかからないから、これはFFIがボトルネックになっていそうである。
多くのアプリケーションではFFIのオーバーヘッドはあまり問題にならない。というのも、FFIを使う目的はLispでの再実装なしに他言語で書かれたライブラリを使用することだからである(外部の機能を呼ぶ頻度は少ないのでFFIのオーバーヘッドは大して問題にならない)。ところで、外部のライブラリを使うもう一つの理由は、Cで書かれた高速なライブラリを使うことである。CFFIはIOLibなどの低レベルなライブラリのために使われるため、ここではパフォーマンスが問題になる(外部の機能を頻繁に呼ぶ必要があるのでFFIのオーバーヘッドが問題になる)。
試しに、CFFIのUFFI互換レイヤーを使ってみようと思う。
やったことは、cl-gd.asd を編集し、UFFIに依存している部分をCFFI-UFFI-COMPATで置き換えただけである(CL-GDは処理系がCLISP及びOpenMCLのときはデフォルトでCFFI-UFFI-COMPATを使うが、SBCLのときはUFFIがデフォルト)。CFFI-UFFI-COMPATを使うことで、UFFIで1.68秒かかっていたところが0.336秒でいける。つまり約5倍は速くなる。
EVO-LISA> (progn (defparameter *image1* (cl-gd:create-image-from-file "023.JPG")) (defparameter *image2* (cl-gd:create-image-from-file "023.JPG")) (time (compare-images *image1* *image2*))) height1=1024, height2=768 Evaluation took: 0.336 seconds of real time 0.336021 seconds of total run time (0.336021 user, 0.000000 system) 100.00% CPU 1,010,111,976 processor cycles 21,712 bytes consed
もちろん、CL-GDのAPIを通してピクセル情報にアクセスすることによる大きなオーバーヘッドが依然としてある。
それは部分的にはFFIレイヤーのせいか、GDのせいか、CL-GDのせいであるだろう。
このオーバーヘッドはどれだけ大きいのか?
ここに純粋なCommon Lispで書かれた2つの色の配列を比較する単純な関数がある(これは最適化すらしていない。すなわち、画像の型宣言をしていない)
(defstruct color (red 0 :type fixnum) (blue 0 :type fixnum) (green 0 :type fixnum)) (defun compare-2darrays (image1 image2 height width) "Compare two images -- uses API exported by CL-GD" (declare (fixnum height width)) (declare (optimize (debug 0) (speed 3)(safety 0))) (let ((err 0)) (declare (fixnum err height width)) (loop for y fixnum from 0 below height do (loop for x fixnum from 0 below width do (let ((color1 (aref image1 y x)) (color2 (aref image2 y x))) (incf err (square (- (color-red color1) (color-red color2)))) (incf err (square (- (color-blue color1) (color-blue color2)))) (incf err (square (- (color-green color1) (color-green color2)))))))))
結果は、
CL-USER> (let ((img1 (make-array '(1024 768) :initial-element (make-color))) (img2 (make-array '(1024 768) :initial-element (make-color)))) (time (compare-2darrays img1 img2 1024 768))) Evaluation took: 0.048 seconds of real time 0.048003 seconds of total run time (0.048003 user, 0.000000 system) 100.00% CPU 143,562,681 processor cycles 0 bytes consed
CFFI経由でCL-GDからCのライブラリにアクセスしたときには0.336秒かかったが、基本的に同じ操作(二つの配列について、差分の二乗を取って比較する)をCommon Lispで実行するのには0.048秒しかかからない。
これはCFFI/UFFIのオーバーヘッドと思われるが、それとはまた別に非効率の元がある。CL-GDのバインディング部分のコードだ。
ドキュメントに明確に記載されているように、CL-GDは良いAPIを提供するのが目的であって、速くなるように設計されているわけではない。バインディング部分のコードには、いくらかのオーバーヘッドがある。GDは画像生成ライブラリであって画像処理のためのものではないので、CL-GDをピクセル単位での反復的なアクセスに使うのは誤用といえる。しかし、私はいくつかのGIFファイルを読み込んでそこから新しい画像を作る必要があった。そこで最初に駆け込んだライブラリがCL-GDであったというわけだ。
ここで、CL-GDベースの別のバージョンを載せる。
これはexportで公開されたCL-GDのAPIといくつかの非exportの内部関数をバイパスしている(これを人々が好まないことは知っているが、::でパッケージ内部のシンボルにアクセスできることはCommon Lispの大きな利点であると私は思う)。
(defun compare-images-raw (image1 image2) "Compare two images -- use internal functions to eliminate overhead added by CL-GD API" (declare (optimize (debug 0) (speed 3)(safety 0))) (let ((err 0) (height (cl-gd:image-height image1)) (width (cl-gd:image-width image1)) (img1 (cl-gd::img image1)) (img2 (cl-gd::img image2))) (declare (fixnum err height width)) (loop for y fixnum from 0 below height do (loop for x fixnum from 0 below width do (let ((img2-color (cl-gd:get-pixel y x :image image2)) (img1-color (cl-gd:get-pixel y x :image image1))) (incf err (square (- (the fixnum(cl-gd::gd-image-get-red img2 img2-color)) (the fixnum(cl-gd::gd-image-get-red img1 img1-color))))) (incf err (square (- (the fixnum(cl-gd::gd-image-get-green img2 img2-color)) (the fixnum(cl-gd::gd-image-get-green img1 img1-color))))) (incf err (square (- (the fixnum(cl-gd::gd-image-get-blue img2 img2-color)) (the fixnum(cl-gd::gd-image-get-blue img1 img1-color)))))))) err))
結果は、
EVO-LISA> (progn (defparameter *image1* (cl-gd:create-image-from-file "023.JPG")) (defparameter *image2* (cl-gd:create-image-from-file "023.JPG")) (time (compare-images-raw *image1* *image2*))) height1=1024, height2=768 Evaluation took: 0.282 seconds of real time 0.284018 seconds of total run time (0.284018 user, 0.000000 system) 100.71% CPU 845,516,097 processor cycles 21,936 bytes consed
0.336秒から0.282秒に短縮されたが、CLの生のコードよりは遥かに遅い。
もしこれが本当に重要な例であれば(そうではないが)、Cのライブラリ側のGDのAPI周りを掘り起こして、ピクセルごとの処理の代わりに画像全体をまとめて処理するように実装してからFFIで呼び出すことで、FFIのオーバーヘッドを除去しようとしただろう。
この例においてなぜCFFIがUFFIより5倍速いのか、中身まで見ているわけではないが、得られる教訓は変わらない。