2015-09-30-01-STL書籍の掲載コードをCL-STLで書いてみよう-5 - project-enigma

2015-09-30-01-STL書籍の掲載コードをCL-STLで書いてみよう-5

>> Site top >> weblog >> 月別アーカイブ >> 2015年09月のlog >> 2015-09-30-01-STL書籍の掲載コードをCL-STLで書いてみよう-5

最終更新日付:2015/09/30 08:17:38


STL書籍の掲載コードをCL-STLで書いてみよう-5

2015 年 09 月 30 日

今回は、「Effective STL」の第14項、「reserve を使って不必要な割り当てを避けよう」のコードを CL-STL で書いてみる。コード量も少ないし、今回は力を抜いていこう。

そうそう、以前連想コンテナがバグっていると書いたが、実はいまだに直っていない。実装に使用している赤黒木の構造についてもういっぺん頭に叩き込み直そうとしているのだけれど、一方でこの weblog に逃避しているような気もする。というわけで逃避行為開始。

話は簡単だ。以下のようなコードでは、おそらくループが終了するまでの間に数回(10回を超えることはないだろうが)のメモリ再割り当てと要素のコピーが発生するだろう。実際の回数は、vector の実装が初期状態でどれだけのバッファを確保するかによる。

vector<int> v;
for( int i = 1; i <= 1000; ++i )
    v.push_back( i );

 

これを CL-STL でできるだけ似せて書くと以下のようになる。何回かの再割り当てとコピーが発生するのも同じだ。

(let ((v (new stl:vector)))
  (stl:for (((i 1)) (<= i 1000) (incf i))
    (stl:push-back v i)))

 

で、これに対して、「最終的な要素数がわかっているなら reserve をしなさい」というワケだ。reserve で予めバッファを確保しておけば、それを超えない限りメモリの再割り当て(とコピー)が発生することはない。

vector<int> v;
v.reserve( 1000 );
for( int i = 1; i <= 1000; ++i )
    v.push_back( i );

 

reserve の使用もそのまま CL-STL でできる。今回はコードが本当に簡単でいいなぁ。

(let ((v (new stl:vector)))
  (stl:reserve v 1000)
  (stl:for (((i 1)) (<= i 1000) (incf i))
    (stl:push-back v i)))

 

この話の重要なところは、メモリの再割り当て(とコピー)にかかるコストもそうなのだけれど、反復子が無効化される点だろう。反復子が無効化されるポイントを予期できないなら、反復子を握りっぱなしにするようなプログラミングはリスキーな話ということになる。実際、自分が STL で std::vector を使う場合、要素数に増減がある局面を跨ぐようなかたちで反復子を握ることはない。あまり意識はしていないけど、ほぼ習性のレベルでそうしていると思う。

CL-STL ではどうだろう。反復子を握っている状態で、本体である stl:vector のバッファが再割り当てされた場合、反復子はどうなるだろう。もちろん仕様としては無効化される。だからそれをデリファレンスした場合の挙動は未定義だ。では、実際はどうなるだろう。

以下のコードで試してみた。まずは、メモリの再割り当てが発生しないパターンだ。

* (let* ((obj (new stl:vector 8 :org))
         (itr (stl:begin obj)))
    (stl:fill (stl:begin obj) (stl:end obj) :new)
    (values (stl:data obj)
            (_* itr)))

=> #(:NEW :NEW :NEW :NEW :NEW :NEW :NEW :NEW) 
   :NEW

 

予想通り。itr は同じ場所を指し続け、最初 :org だったものが stl:fill の実施後には :new を指している。では、反復子を握った後でstl:resize をしてみよう。

* (let* ((obj (new stl:vector 8 :org))
         (itr (stl:begin obj)))
    (stl:resize obj 16)
    (stl:fill (stl:begin obj) (stl:end obj) :new)
    (values (stl:data obj)
            (_* itr)))

=> #(:NEW :NEW :NEW :NEW :NEW :NEW :NEW :NEW :NEW :NEW :NEW :NEW :NEW :NEW :NEW :NEW) 
   NIL

 

stl:resize の実施により、バッファの再割り当てが発生した。そして、itr をデリファレンスした結果は、nil になっている。もちろん未定義の領域なのだから何が起きても文句は言えないのだけれど、実際に起きていることはなんだろう。

まず重要なことは、バッファの再割り当てが処理された stl:vector が古い方のバッファを手放したとしても、それで古いバッファが消えてなくなるわけではないという点だ。C/C++ なら free/delete でメモリを開放するだろうが、Lisp ではガベージコレクタに任せる他ない。そして、プログラムのどこかでその古いバッファを参照しているなら、ガベージコレクタはそのバッファに手をつけたりはしない。そしてまさに、反復子 itr がその「どこか」なのだ。反復子が古いバッファのどこかの要素を参照しているがゆえに、古いバッファは消えてくれないのだ。

そして、CL-STL では、上記のようなバッファの再割り当て(とコピー)において、実際にはコピーではなく move のイメージで処理を行なっている。その結果として古いバッファの内容は全て nil になる。_* オペレータによってデリファレンスした結果が nil だった理由というのは、大体こんなところだ。

個人的には、無効化された反復子をデリファレンスしてクラッシュしたりするよりも、何くわぬ顔で nil を返したり処理を続行させたりする方がタチが悪いと思っている。だから反復子を操作する際にそれが既に無効化されているかどうかをチェックする機構が必要だとは感じているのだが、それは今後の取り組みになるだろう。

 

コメント

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

 

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

 

 


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