2014-05-22-01-総称関数メソッドのパフォーマンス確認
>> Site top >> weblog >> 月別アーカイブ >> 2014年05月のlog >> 2014-05-22-01-総称関数メソッドのパフォーマンス確認
最終更新日付:2014/05/22 01:00:00
総称関数メソッドのパフォーマンス確認
2014 年 05 月 22 日
C++ でいうところの演算子オーバーロード、例えば operator< は CL-STL の世界では opr< となる。これは総称関数なので、その解決にかかるコストは実行時に負担しなければならない。ではそのコストは‥‥‥? というのが急に気になり始めた。というのも、このままいくとアルゴリズムに渡す比較子のデフォルトも opr< とかになるからだ。以前にも似たようなことをやった気がするが、今回改めて試してみる。
試したのは以下のコード。test-func1 は基準になるもので、比較関数を渡すかわりに < オペレータをハードコーディングしてある。test-func2 は比較関数を渡すもので、これに #'< やら #'stl:opr< を渡して時間を測ってみる。
(locally (declare (optimize speed)) (defun test-func1 (cnt) (declare (type fixnum cnt)) (let ((a 0) (b 0)) (declare (type fixnum a b)) (do ((i 0 (1+ i))) ((= i cnt) (values a b)) (declare (type fixnum i)) (if (< (random 100) (random 100)) (incf a) (incf b)))))) (locally (declare (optimize speed)) (defun test-func2 (cnt pred) (declare (type fixnum cnt)) (let ((a 0) (b 0)) (declare (type fixnum a b)) (do ((i 0 (1+ i))) ((= i cnt) (values a b)) (declare (type fixnum i)) (if (funcall pred (random 100) (random 100)) (incf a) (incf b))))))
総称関数を実装するメソッドが増えれば増えるほどパフォーマンスが落ちるのではないかと心配しているので確認しておこう。この時点で総称関数 cl-stl:opr< は以下のような状態になっている。19 個のメソッドが実装されている。
* (describe #'stl:opr<) #<STANDARD-GENERIC-FUNCTION CL-STL:OPR< (19)> [generic-function] Lambda-list: (OBJ1 OBJ2) Derived type: (FUNCTION (T T) *) Method-combination: STANDARD Methods: (opr< (stl:queue-container stl:queue-container)) (opr< (stl:stack-container stl:stack-container)) (opr< (stl:multimap-container stl:multimap-container)) (opr< (stl:map-container stl:map-container)) (opr< (stl:multiset-container stl:multiset-container)) (opr< (stl:set-container stl:set-container)) (opr< (stl:list-container stl:list-container)) (opr< (stl:deque-const-reverse-iterator stl:deque-const-reverse-iterator)) (opr< (stl:deque-const-iterator stl:deque-const-iterator)) (opr< (stl:deque-container stl:deque-container)) (opr< (stl:vector-container stl:vector-container)) (opr< (stl:array-container stl:array-container)) (opr< (stl:array-const-reverse-pointer stl:array-const-reverse-pointer)) (opr< (stl:array-const-pointer stl:array-const-pointer)) (opr< (stl:reverse-randomaccess-iterator stl:reverse-randomaccess-iterator)) (opr< (simple-vector simple-vector)) (opr< (cons cons)) (opr< (string string)) (opr< (t t))
で、これを実行した結果は以下の通りだった。
* (time (test-func1 10000000)) Evaluation took: 0.484 seconds of real time 0.483603 seconds of total run time (0.483603 user, 0.000000 system) 100.00% CPU 1,154,700,944 processor cycles 0 bytes consed 4949343 5050657 * (time (test-func2 10000000 #'<)) Evaluation took: 0.546 seconds of real time 0.546003 seconds of total run time (0.546003 user, 0.000000 system) 100.00% CPU 1,317,882,744 processor cycles 0 bytes consed 4950802 5049198 * (time (test-func2 10000000 #'stl:opr<)) Evaluation took: 0.655 seconds of real time 0.655205 seconds of total run time (0.655205 user, 0.000000 system) 100.00% CPU 1,542,710,128 processor cycles 0 bytes consed 4947180 5052820
まぁ、予想を大きく違えるということはなかったが、思ったよりは差がないように見える。あくまでアルゴリズムなどに渡す比較子が「普通の関数」だった場合と「多くのメソッドをもつ総称関数」だった場合のコストを比較するのが目的なので、コード内部に < を直書きした場合を比較対象とする気はない。なので、1.17 倍のコストということになる。これならば許容範囲内だろう。ひとまずのところ、自分が心配していたのは5倍遅いとかそういうレベルだったので。
コメント
このページのタグ
Page tag : Common Lisp
Page tag : STLとその移植
Copyright(C) 2005-2021 project-enigma.
Generated by CL-PREFAB.