2014-04-18-01-代入から move へ

>> Site top >> weblog >> 月別アーカイブ >> 2014年04月のlog >> 2014-04-18-01-代入から move へ

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

代入から move へ

2014 年 04 月 18 日

前回の最後で、今検討している「代入」の方式では出力反復子から「値を取得」できなければならないことが判明した。今回はこの「代入」の問題から展開（右往左往？）した思考の結果、入力反復子に「値を設定」できなければならないことがわかったところまでを書いておきたい。

検討中の opr= による「代入」は、なんやかやでパフォーマンスは良くない。マクロ展開はコンパイル時点で済むとはいえ、そのマクロ展開コードは総称関数を呼び出し、その結果を受け取って値の設定を行うのだ。「代入の真のコスト」は総称関数を実装するメソッド次第ではあるのだが。

この代入問題について考え始めるまで、例えば copy アルゴリズムが実行する「コピー（代入）」は、単純に setf だった。これは STL で言えばポインタのコンテナをコピーするのと同じだから、一番速い部類に入る。もちろん、コピー元とコピー先は対応する位置同士で要素を共有することになるから、これはちとマズい。それがそもそも「代入についてちゃんと考えましょう」の始まりではあった。

たとえば、例の initializer_list、あれは内部的には配列で実現されているが、それでもってコンテナを初期化するとき、何が起きるだろうか。ここで、heavy はコピーに非常にコストのかかる重量級オブジェクトの生成関数としておこう。

(stl:new :array (5 #{(heavy 0)
                     (heavy 1)
                     (heavy 2)
                     (heavy 3)
                     (heavy 4)}))

リードマクロによって initializer-list が生成される際、５つのオブジェクトが作成される。それは array の初期化に使われているが、opr= 以前の CL-STL では単純な setf だったから、initializer-list が保有していた５つのオブジェクトがそのまま使われた。しかし、「代入」をちゃんとやることになると、list を new する際にこの５つのオブジェクトのコピーが作成されるのだ。そして initializer-list が破棄される際、最初に作成された５つの要素オブジェクトも破棄される（実際のタイミングは GC 任せということになるが）。

どうだろう、無駄だと思わないだろうか？　実際無駄なのだ。上記のコードに関して言えば、initializer-list でコンテナを初期化する場合、その initializer-list は使い捨てなのでいちいちコピーする必要はない。initializer-list から新規コンテナに要素を移動してくれればいいのに‥‥‥と、ここで気付いた。move だ。

STL のアルゴリズムには、move と move-backward がある。それぞれ copy と copy-backward に似ているが、コピーせずに move を行う。move semantics は C++ の比較的新しい概念で、自分はまだ理解しきれていないため、move アルゴリズムには手をつけていなかった。しかし、move が setf のイメージで要素を「移動」してくれるなら、これはそのものズバリの解決策になるのではないだろうか。そう思って書いてみたのが以下のコード。比較のために copy のコードと御一緒に。

(defmethod copy ((first input-iterator)
                 (last  input-iterator) (result output-iterator))
  (let ((dest (clone result)))
    (if (opr== first last)
        dest
        (do ((itr (clone first)))
            ((opr== itr last) dest)
          (opr= (opr* dest) (opr* itr))    ; assignment.
          (++opr itr)
          (++opr dest))))))

(defmethod move ((first input-iterator)
                 (last  input-iterator) (result output-iterator))
  (let ((dest (clone result)))
    (if (opr== first last)
        dest
        (do ((itr (clone first)))
            ((opr== itr last) dest)
          (setf (opr* dest) (opr* itr))    ; move
          (setf (opr* itr) nil)            ; move
          (++opr itr)
          (++opr dest))))))

問題は、というか自分がまだ理解できていないのは、move アルゴリズムが「移動元」のシーケンスとして input-iterator の組みを取るということだ。コピーでなく移動である以上、それは値が変更されなければならない。ということは、input-iterator なのに(setf (opr* itr) nil) としなければならないのだ。これは、「前回の出力反復子から『値を取得』できなければならない」という問題の丁度逆である（というか、上記の copy アルゴリズムの opr= 呼び出し部分でまさにこれが起きているね）。

無論、input-iterator にも (setf opr*) のデフォルトの動作として「指定値を無視する」という動作をつけ加えてやればひとまず動作はする。しかし、これらの『回避策』的なデフォルト動作は、当然ながら間違った局面でも動作してしまうのだ。そう考えると、安直にそのような対処で終わりにはしたくないというのが正直なところだ。

‥‥‥まだ続く。でも、考え抜かないとな。

コメント

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

このページのタグ

Page tag : Common Lisp

Page tag : STLとその移植

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