通りすがりです (2014/02/13 01:52:06):

メリットの３つめとして挙げられている点についてですが、 通常の配列を使った文字列ならアクセス時間はO(1)なのでは？

shiro (2014/02/13 04:58:52):

まあ、Cのchar*に渡す時にどうせ変換が必要ならコードポイント配列に切り替えてもいい、という議論はできますが、フラグメントをマルチバイトで持ってると表示の時などはフラグメントをただ流すだけで良いのでマルチバイトの優位性がまるきり失われるというわけでもないかなと。

shiro (2014/02/13 05:09:14):

あ、ちなみになんでもともと文字の配列じゃなくてマルチバイト文字列なのかってのはscheme関係のMLやらニュースグループやらで何度も議論してるのでここでは繰りかえしません。

Kei (2014/02/13 16:21:47):

Clojureのコレクション(?)に近いイメージに思えますね。(Cに渡す部分はないですけど) JavaのStringはリーク以外にもメモリ使用量が減るというメリットもあったはず。オフセットとカウントが減るから系8バイト(?intのサイズ不明)。フラグメントにして管理すると多少メモリ効率が悪くなる気もしないでもないですが、どうなんでしょう？

shiro (2014/02/14 06:21:36):

どういうケースを想定するかですが、ポインタに8バイト使うのにフラグメントが数バイトとか数十バイトじゃ割が合わないでしょうから、現実的には大部分の短い文字列はこれまでどおりの表現になるだろうと思います(文字列接合でも閾値以下のものはコピーする)。おそらく影響を受けるのは数KB以上の長い文字列で、そういうのを大量に扱いかつsubstringを取りまくるというケースに当たってみないとはっきりした挙動はわからんですね。

ただBoehm GCはnon copyingなので巨大な連続するメモリをがんがんアロケートしたりCGしたりするとフリーメモリのフラグメンテーションが起きるってのはあって、OSのページくらいを基準に分割して持つくらいならツリー分の空間オーバヘッドはそれほどでもないでしょうし、GCの負担軽減分が勝るかもしれません。そういう長い文字列はだいたいScmDString (JavaのStringBuilderみたいなやつ) で作られるんですがScmDString自体はチャンクに貯めてって最後に連続領域にコピー、ってしてるんで、生成時のコピーも省ける可能性があります。

(しかし、Cに渡すところで連続領域をアロケートするなら結局元の木阿弥かもしれず…)