2014-04-24-01-本気で move について考える - 4

>> Site top >> weblog >> 月別アーカイブ >> 2014年04月のlog >> 2014-04-24-01-本気で move について考える - 4

最終更新日付：2014/04/24 01:00:00

本気で move について考える - 4

2014 年 04 月 24 日

考えなきゃならないことはまだまだある。というか、実際にソースファイルに手を加えずにここまで検討を続けたのって初めてかも。それだけ自信がないんだな。

　

さてさて、昨日は最後にこんなことを書いた。

1. C++ でのオブジェクト間ムーブの模倣だけでなく、nil <- obj タイプのムーブの一般的なルール策定。
2. ムーブコンストラクタのこと（上記にも関連する）。
3. range move アルゴリズムをちゃんと move で実現する（以前のはインチキ過ぎた）。

‥‥‥と、その前に、またもやコードをイジったので再掲しておこう。__move-2 は operator-move に名前を変え、__move-1 は move マクロの中に統合した。これに伴い、move マクロをかなり変えている（やっていることに変わりはない）。

(defclass remove-reference ()
  ((closure :type     :function
            :initarg  :closure
            :accessor __rm-ref-closure)))

(defgeneric operator-move (lhs rhs))
(defmethod  operator-move (lhs rhs)
  (declare (ignore lhs))
  (values rhs nil))

(defgeneric __move-3 (first last result))

(let ((g-get (gensym "GET")))
  (defmacro move (&rest args)
    (ecase (length args)
      (1 (multiple-value-bind (vars forms var set ref)
                              (get-setf-expansion (car args))
           `(let* (,@(mapcar #'list vars forms))
              (if (eq (type-of ,ref) 'remove-reference)
                  ,ref
                  (make-instance 'remove-reference
                                 :closure (lambda (&optional (,@var ',g-get))
                                            (if (eq ,@var ',g-get)
                                                ,ref
                                                ,set)))))))
      (3 `(__move-3 ,@args)))))

(defmethod operator= (a (b remove-reference))
  (multiple-value-bind (lhs rhs)
      (operator-move a (funcall (__rm-ref-closure b)))
    (funcall (__rm-ref-closure b) rhs)
    lhs))

　

では、これを前提として順番に。

　

move の一般的なルール

これは move のルールというよりは operator= のルールかな。C++ では、代入演算子というのはそもそも（特殊なオーバーロードを除いて）代入の元／先が同じオブジェクトだ。しかし、CL-STL ではそのような保証はないから、それ以外の状況でどう動くべきかを決めておかなければならない。それは operator= や operator-move がどのように実装されるかによるわけだが、一般的なルールがないとなんでもアリになってしまうだろう。

では、どのようなルールであるべきか。まず、同じオブジェクト同士であれば、それはそのタイプ独自の代入処理を勝手に決めれば良い。そして、代入先が nil であれば、それはオブジェクト参照先オブジェクトを共有するか、でなければ新しいオブジェクトを作成して内容をコピーするかだ。それ以外の場合、エラーにするか、特殊な代入として処理するかになる。

moveの場合も基本的な考え方は同じだ。ただし、前提は「所有権の移動」だということを忘れてはならない。

1. 移動先が nil の場合、オブジェクト参照自体が移動する。移動元には nil が設定される。
2. 移動先にも同じ型のオブジェクトがある場合、タイプ依存。一般には内容だけを移動するが、移動先が nil の場合と同じ動作をしても良い。デフォルト動作は 1 と同じ。
3. 移動先に異なる型のオブジェクトがある場合、タイプ依存。エラーにするか、特殊な変換処理を行うか、移動先が nilの場合と同じ動作をするか。デフォルト動作は 1 と同じ。

どうだろう、一般的にはこれで良いだろうし、remove-reference が作成された時点でその内容が何処かに移動してしまうことは覚悟しているはずだから、これで問題ないと思う。たとえば、内容だけを移動させる vector コンテナの operator-move は以下のようなものになる。実装詳細なので細かい説明はしないけれども、vector 内部で保有している『コア』オブジェクトだけを「移動」させている。

(defmethod  operator-move ((lhs vector-container)
                           (rhs vector-container))
  (setf (vector-core lhs) (vector-core rhs))
  (setf (vector-core rhs) nil)
  (values lhs rhs))

　

ムーブコンストラクタのこと

要するに、こういうことだ。

std::vector<int> v1 = { 0, 1, 2, 3, 4, 5 };
std::vector<int> v2 = std::move( v1 );
        :
        :

　

これに対応する CL-STL コードは、以下のようになる。

(let* ((v1 (stl:new :vector (#{0 1 2 3 4 5})))
       (v2 (stl:new :vector ((stl:move v1)))))
        :
        :

　

そういうわけなので、コンストラクタ関数が remove-reference を取ることができなければならない。ついでなので、initializer-list を取るコンストラクタがどうあるべきかも見ることにしよう。initializer-list は常にムーブして良いものとして扱うつもりでいるので、上記の v1 のコンストラクトは以下の総称関数メソッド呼び出しに辿りつく。これは実際のコードとは違うが、わかりやすさ優先でこうしてある。

(defmethod __new-vector-1 ((arg initializer-list))
  (let ((vec (new :vector ((size arg) nil))))
    (move (begin arg) (end arg) (begin vec))
    vec))

　

やっていることは、渡された initializer-list と同じ要素数の vectorを作成し、range move アルゴリズムを使用して「移動」させている。通常であれば、これが終わった時点で initializer-list の中身は空っぽになるだろう。

では、remove-reference を渡した場合のコンストラクタはどうなるだろうか。以下のようになる。

(defmethod __new-vector-1 ((arg remove-reference))
  (let ((rhs (funcall (__rm-ref-closure arg))))
    (check-type rhs vector-container)
    (let ((lhs (new :vector ())))
      (setf (vector-core lhs) (vector-core rhs))
      (setf (vector-core rhs) nil)
      lhs)))

　

最初にやっているのが、remove-reference から取り出した内容が vector-container かどうかをチェックすることだ。とんでもないモノを remove-reference にくるんで渡されるのを防ぐことはできないので、これは実行時エラーにするしかない。その後にやっているのは、空の vector を作成し、例の『コア』オブジェクトを「移動」させることだ。

　

range move アルゴリズム

最後は range move アルゴリズムだ。単純に考えると opr= と move の組み合わせを全ての要素に対して実行することになるが、それだと要素の個数分だけ remove-reference を make-instance しなければならないことになる。今はまだ検討段階なので、ものスゴく乱暴なことをしよう。opr= も move も remove-reference もすっとばして operator-move を直接コールするのだ。以下のようになる。

(defmethod __move-3 ((first input-iterator)
                     (last  input-iterator) (result output-iterator))
  (let ((dest (clone result)))
    (if (iter= first last)
        dest
        (do ((itr (clone first)))
            ((iter= itr last) dest)
          (multiple-value-bind (a b)
              (operator-move (iter* dest) (iter* itr))
            (setf (iter* dest) a)
            (setf (iter* itr)  b))
          (++iter itr)
          (++iter dest)))))

　

「ものスゴく乱暴」だと書いた理由は、状況によっては以下の本来的に正しい実装と同じ動きをしない可能性があるからだ。

(defmethod __move-3 ((first input-iterator)
                     (last  input-iterator) (result output-iterator))
  (let ((dest (clone result)))
    (if (iter= first last)
        dest
        (do ((itr (clone first)))
            ((iter= itr last) dest)
          (opr= (iter* dest) (move (iter* itr)))
          (++iter itr)
          (++iter dest)))))

　

上記の「正しい実装」では、opr= の展開によって、総称関数 operator= がコールされる。この第２パラメータは remove-reference になるが、第１パラメータがより特定的なメソッドが追加されている可能性があり、その実装によっては operator-move がコールすらされない可能性があるのだ。最初の実装が「ものスゴく乱暴」だと書いた理由はこれだ。

で、ここんところをどうするか。選択肢は、この乱暴狼藉を正当化するためのルールを作るか、そうでなければ常に「正しく」動作する範囲内での最適化を頑張るか、だ。これは今後も検討することになるだろう。

　

‥‥‥さて、随分長くなってしまった。まだ続くのか、と自分でも思うが、続きます。多分。

　

コメント

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

　

このページのタグ

Page tag : Common Lisp

Page tag : STLとその移植

　

　

---

Copyright(C) 2005-2020 project-enigma.
Generated by CL-PREFAB.