2014-05-22-01-総称関数メソッドのパフォーマンス確認

>> Site top >> weblog >> 月別アーカイブ >> 2014年05月のlog >> 2014-05-22-01-総称関数メソッドのパフォーマンス確認

最終更新日付：2014/05/22 01:00:00

≪ 2014-05-15-01-Emacs24 で困っていたこと

2014-05-31-01-Emacs24 にお引越し ≫

総称関数メソッドのパフォーマンス確認

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 倍のコストということになる。これならば許容範囲内だろう。ひとまずのところ、自分が心配していたのは５倍遅いとかそういうレベルだったので。

このページにコメントする