Delphiの文字列並の効率を実現できるようにUnbounded_Stringを改造したい
何度も書いてますが、言語組み込みの文字列とライブラリ提供の文字列では効率に天と地の差があります。C++みたいになるべく自然に使えるように努力している言語ですら、その差は到底埋められていません。ましてやAdaのUnbounded_Stringなんて(略)ですよ。
Delphiの文字列のスゴイところと、どうすればおんなじ風にできるかなー、ってのをダラダラやってた話です。あ、ここでいうDelphiの文字列というのは2007以前のAnsiStringのことです。2009以降については正直静的言語なのにコードページを実行時に持つ必要は無いと……どうでもいい。
実はD言語の文字列のほうがもっとスゴイのですが、あのスゴさはGC前提なので省略。
Delphi2〜Delphi2007のAnsiStringの構造
「参照カウンタ、長さ、文字列本体、(C互換用のゼロ終端←以後省略)」というメモリブロックへの「ポインタ」です。
まあこの構造自体はstd::stringでも同じでしょう。0xでは参照カウンタでの共有は許されなくなったんでしたっけ？
で、早速Adaには難点が。Adaでは(C++で言う)デストラクタを実現するためには、Ada.Finalization.Controlledを継承しなければいけないのですが、そうすると当然VMTが必要になるわけです。つまりポインタ2つの組になってしまうわけです。若干メモリの無駄。
| Delphi | C++ | Ada |
| ○ | ○ | × |
レジスタに入る
AnsiStringの実体はポインタ1つだけです。ということはレジスタに入ります。
std::string(C++03以前)も、実体はポインタ1つだけにできますが、レジスタに入りません。メンバ関数にthis(ポインタを1個だけ持つクラスへの更にポインタ)を渡さないといけないからですね。*1
もちろん上記のようにAdaでは最低でもポインタ2つ必要になりますので、レジスタには入りません。
| Delphi | C++ | Ada |
| ○ | × | × |
文字列定数
AnsiStringの定数は、静的に確保されてます。参照カウンタには-1が入ってます。コンパイラが最初っから文字列の構造を把握してるからこそですね。
一方、std::stringもUnbounded_Stringも、コンストラクタ/To_Unbounded_Stringに定数文字列を渡されても、動的にメモリを確保して中身をコピーする必要があります。C/C++もAdaも文字列定数は単なる文字型の配列であり、参照カウンタも長さデータも持ってないからです。
そのため、ちょっと構造を変えましょう。
「参照カウンタ、長さ、文字列本体」→「参照カウンタ、長さ、文字列本体へのポインタ、(文字列本体)」
動的に確保する時は、「文字列本体」まで一緒に確保して、「文字列本体へのポインタ」メンバには「文字列本体」(要するにすぐ次のアドレス)を入れます。
静的に確保する時は、「文字列本体」は確保せずに、「文字列本体へのポインタ」メンバには実定数へのポインタをそのまま持たせます。
……実はこれだけだとダメです。
仮に引数の型をchar const *やaccess constant Stringにしたとしても、ローカル変数(定数)へのポインタを渡されたりすると、そのまま使うわけにいかないですよね。呼び出し元の関数を抜けると消えちゃいますから。
というわけで安全に文字列定数を作るためには、引数で渡された定数が本当に定数であることの保証が必要になります。D言語ならimmutableって便利なものがあるのですが、C++やAdaにはありません。
ただAdaのaccess型(ポインタ)はスコープに紐付けられた型ですので、ライブラリレベル(一番外)のaccess型を使えば、関数を抜けるなどで消えたりはしないことだけは保証できます。それでも、Adaのaccess constantはC++のconst *と同じで、実際に指しているものは変数かもしれません。中身が書き換わる恐れだけは無くせません。
| Delphi | C++ | Ada |
| ○ | × | × |
引数渡し
AnsiStringは参照カウンタで管理されていますが、引数渡しの時は参照カウンタが増減されません。
実引数は関数呼び出しよりも寿命が長いことが確実だからです。
C++やAdaでこれを避けるには参照渡しにするしかなくて、そうするとポインタのポインタになってしまって、無意味な逆参照が1段入ってしまいます。引数として渡ってくるわけですからどんなにコンパイラが賢くてもひとつの関数内だけの最適化では取り除けません。LTOなら話は別。
まあAdaは特に、継承を使っている型は明示しなくても問答無用で参照渡しになってしまうわけですが。
| Delphi | C++ | Ada |
| ○ | × | × |
世の中にはStringPieceなんかもありますが、折角の参照カウンタが活用されないため、あんまり意味無いかなあ。(リンク先の例だと中でCopyToStringするのも呼び出し元で一時的なstd::stringを作って中では参照カウンタを増やすだけってのも大して変わらないはず？out->append(dir);をout->assign(dir);に変えたら……と思って試してるのですが……続きは↓↓)
返値
返値も今までの話と似たようなものです。
AnsiStringはレジスタで返せて、その際参照カウントも増減しません。
std::stringはレジスタでは返せずに(暗黙の引数が必要になる)、コピーコンストラクタと一時変数のデストラクタも走ります。(0xならムーブコンストラクタと一時変数のデストラクタ)
Unbounded_Stringもレジスタでは返せずに(暗黙の略)、やっぱりAssignと一時変数のFinalizeが走ります。
もちろん定数を返すとわかっているなら参照返しにすればよいのですが、std::stringやUnbounded_Stringは上記のように定数であっても作成時点で中身全部コピーしたりしますので参照返しにして参照カウンタの操作を省略できたやったー、なんてやっても虚しいだけです。最終的に単なるポインタのレジスタ間コピーだけになるAnsiStringだからこそ活きる最適化ですよね。
| Delphi | C++ | Ada |
| ○ | × | × |
連結
文字列を一気に3つ連結したりする時も、AnsiStringならコンパイラが知ってますからまとめて連結してくれたりします。(ランタイムには_LStrCat3とかある)
std::stringやUnbounded_Stringの連結は、演算子オーバーロードで実現されいるわけですが、「A & B & Cを一括で処理するオーバーロード」は定義できませんので、ちまちま連結していくしかないです。
ただ少しだけあがくことは出来て、「A & B」の時点で領域を多めにとっておいて、「& C」がそこに入るなら再アロケート無し、みたいな頑張り方はできます。もちろん「& C」されなれば無駄な領域ですのでふつーの発想だとやらないと思います。後はRopeにするぐらいかなあ。
| Delphi | C++ | Ada |
| ○ | × | × |
というわけで結論
Unbounded_Stringをいろいろ弄ってたんですがあまり改善できそうにないです。
要は失敗談でした。
*1:ただしC++Builderには__declspec(delphireturn)なるものがありましてレジスタに入れることができます。
