2018-07-11-01-「値コピー原則」の破棄‥‥‥で悩む - project-enigma

2018-07-11-01-「値コピー原則」の破棄‥‥‥で悩む

>> Site top >> weblog >> 月別アーカイブ >> 2018年07月のlog >> 2018-07-11-01-「値コピー原則」の破棄‥‥‥で悩む

最終更新日付:2018/07/11 19:13:13


「値コピー原則」の破棄‥‥‥で悩む

2018 年 07 月 11 日

cl-stl について、ずっと悩んでいることがある。それは、「値コピーの原則」だ。cl-stl を可能な限り STL に寄せるために、Common Lisp の感覚からすれば少々不自然なことをやっていた。それを今になって、捨ててしまおうかと考えている‥‥‥というか、悩んでいる。

 

STL に慣れていれば当たり前のことではあるが、STL コンテナは要素の出し入れにはコピーを用いる。std::vector<Foo> に対して手元の Foo 型オブジェクト foopush_back すると、foo のコピーがコンテナに追加される。手元にある foo と、コンテナに追加されたオブジェクト。両者は「同値」だが別のオブジェクトだ。当然ながら、このコピーにはオブジェクトのサイズに応じたコストがかかる。

大きなオブジェクトのコピーをしたくない場合、ポインタのコンテナを使うことができる。これならオブジェクトがコピーされることはない。しかし、STL はポインタを特別扱いしているわけではない。先程の Foo で言えば、そのポインタを格納するコンテナは std::vector<Foo*> になるため、このコンテナは「格納すべき値の型であるポインタをコピー」しているだけ、というわけだ。整数型を格納するコンテナとやることは対して変わらない。そしてこのコピーを用いるという原則は、pairtuple などでも同様だ。

で、cl-stl だ。開発当初は、自分でもそこまで寄せることは考えていなかった。値の設定ならば setf でよかろうというわけだ。しかし、作り込むほどに不自然さが気になるようになっていき、ムーブセマンティクスでとうとう「無理」と判断した。setf とは別の「代入」がないと、「ムーブ代入」ができない、となったわけだ。結構昔のことなので順序や細部には自信がないが、まぁ大体そんな経緯だったと思う。

雑な説明だけど、これで現在に至っているわけだ。しかし、今更ながら「そうまでして寄せなくてもよかったのでは?」と思うようになってしまった。理由は主にパフォーマンスだ。自分のやり方がマズかったのかもしれないが、現在コピーセマンティクスの実現には総称関数が関わっている。たとえば、単純な代入も以下のようにマクロ展開される(改めて見るともっと短くできるけどそれはまぁ置いとく)。

 (_= foo bar)
   
 ;=> (LET* ()
 ;     (LET ((#:NEW1 (OPERATOR_= FOO BAR)))
 ;       (SETQ FOO #:NEW1)
 ;       #:NEW1))

 

代入オペレータ _= はマクロだ。そして展開フォームに含まれる OPERATOR_= は総称関数である。なぜこんな面倒な仕組みになっているのか? 理由はいくつかあって、何よりも「コピーの具体的な処理をユーザー定義できるようにしたい」ことがひとつ。これは C++ でいうところの operator= のオーバーロードに相当する。しかし、総称関数だけで片がついたらどれだけ簡単だったか。理由の2つめは、実際に代入がおこなわれたところの foo に最終的な代入結果が設定されなければならないからだ。これは 関数でも総称関数でもできない。マクロが必要なのだ。そしてこのマクロと連携するために、総称関数 OPERATOR_= はその実装に対する要求事項として、代入の結果として代入先に setf されるべきオブジェクトを返すことになっている。

‥‥‥えーと、なんの話だっけ? そうだ、値コピー原則だ。この原則を守るために、「代入」の度に総称関数呼び出しが発生するのだ。そして、その総称関数を実装するメソッド数がまた問題になる。数えてみたら、cl-stl をロードしただけで OPERATOR_= のメソッドは 58個にもなることがわかった。そのほとんどが反復子やコンテナのコピーだ。メソッド呼び出しの解決の仕組みやコストについて詳しくは知らないが、そこで行なわれるであろうことを想像するに、定数時間とはいかないと思う。

大体こんな感じで、考えれば考えるほど「値コピーの原則」を捨てた方が良い気がしてくる。では、捨てた場合には何がどうなるだろう? あまり時間がないので、続きは次回に。

 

コメント

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

 

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

 

 


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