* Variable Array ライブラリを作って失敗した話
-(by [[K]], 2017.10.24)

** (1) 起
-[[K]]はC言語が好きです。C++も好きだけど結局C言語が好きです。

-さてそのC言語ですが、不便なところが一つあります。それは配列の長さを容易には変更できないということです。
-いやreallocを使えば変更はできます。reallocはすごいです。でもreallocするとポインタが変わってしまいます（変わらないこともあるけど）。まあそりゃそうですよね、後ろに伸ばせなかったら別の場所に再確保するしかないです。それは当然です。
-当然なんだけど、でもオブジェクトの場所が変わっちゃうって、結構困るのです。この可変長配列上のある要素を指し示すポインタを作るとしたらどうしたらいいの？reallocするたびにポインタを全部更新する？えー、さすがにそれは大変すぎる・・・。

-ということでこんなのを作りました。
 typedef struct VA_ {
     void *p;
     int elementSize, n, n1; // n1はreallocしたサイズ（つまりマージン込みのサイズ）, nは現在利用中のサイズ.
     const char *nam;
 } VA;
-このVA型のオブジェクトvaを作ってメモリのどこかにおいておきます。これで&vaの値さえわかれば、配列がどこにあるか確実にわかります。配列の何番目かを指し示したいのなら、何番目の要素なのかも持っておけばいいわけです。つまり、ポインタ一つと整数一つあれば、可変長配列上の任意の要素を示すことができるようになったのです。ここでは便宜上、VA型オブジェクトのポインタをpvaと呼ぶことにします。

-pvaに対して、サイズを変更せよというのはとても簡単です。
 VA_size(pva, n);
-みたいにすればいいのです。これでサイズが更新されます。n1を超えるようなら適当なマージンを付けてreallocもされます（それでrealloc回数を減らすようにしている）。
-もしreallocに失敗したらstderrにエラーを出力してexit(1)してくれるので、もはやサイズ変更が失敗するケースを想定する必要がありません。
-さらにマージン付きの可変長をやめる関数も付けました。適切なサイズが確定したら呼び出して、マージン部分を解放させます。
 VA_sizeFix(pva, n);
-関数に配列を渡すときは、pを渡さずにpvaを渡すようにするのです。

** (2) 承
-この可変長配列ライブラリ（VA）は大成功で、すごく便利になりました。・・・今までの[[K]]のプログラミングスタイルは、とりあえず大きめの固定サイズでmallocして、それを超えたらエラー終了、というものがほとんどでした。これなら何も面倒なことはないわけです。でもメモリ効率は良くないです。・・・そのせいでメモリが少ない環境ではうまく動かなかったり、想定以上の入力が来てエラー終了してしまったりと、柔軟性には難がありました。
-それがVAを使うことで、すごくメモリ効率が良くなりました。プログラムでは、上限を超えていないかのチェック箇所をVA_sizeに置き換えている程度なので、大して複雑さは変わっていません。それでこんなによくなるなんて・・・。
-VAライブラリでは、vaを初期化するときに VA_init(pva, elementSize, "array-name"); みたいにするのですが、これによって可変長配列に名前がつきます（つけたくなければ""でもいい）。なんで名前を付けるのかというと、init時に内部テーブルに登録されて管理しており、それはデバッグ用のdump関数があって、それを実行するとfreeされていないVAをすべて表示してくれる機能があるからです（p, n, n1を表示してくれる）。その時に名前も出るのです。
-このデバッグ機能が最高で、メモリリークとかも簡単に見つけられます。名前があるから、ああこいつがまだメモリに残っていたか、なんてわかっちゃうわけです。・・・[[K]]はもはや生のmalloc/reallocを全く使わなくなって、全部VAで管理するようになってしまいました。可変長ではなくてもVAで管理できるので。

-VAはただの可変長配列です。線形リストでも木構造でもないです。だから配列の途中への高速な挿入・削除などの凝ったことはできません。でも配列ってちょっとしたことなら一通りできるので、よほど大規模なことをやらない限り、十分使用に耐えます。・・・今までデータ構造のライブラリはいくつか作って使っていましたが、「ああ、自分に必要なのはこういうシンプルなやつだったんだー」とつくづく思いました。

** (3) 転
-ところが・・・問題が発覚します。
-VAの中にVAを置いておくことができないのです。いや、おいてもいいのですが、サイズが変更されてポインタが変わってしまうと、pvaの値が変わってしまいます。これでは「pvaとiがあれば、VA上の任意の要素を指し示せる」が崩れてしまいます。何かの拍子にpvaが変わって有効じゃなくなるかもしれないからです。

-さあ困った。どうしましょう。・・・ということで、VAはあちこちに分散させても管理がうまくいかなくなるだけなので、どこか一ヶ所で管理すべきだと考えました。vaTable[]みたいなのを作って、そこにVA型のオブジェクトを置くわけです。でもvaTable[]が移動したらどうしましょう。まあ移動させないという解もありなのですが、ここは移動も想定して（その代わりvaTable[]は分散せずに一ヶ所にまとめる）、vaTable[]の要素へのポインタを持つのはやめて、vaTable[]の何番目の要素なのかを持つことにします。
-つまりこの新しいルールでは、ポインタは2つの整数の組で表現されるのです。vaTable[]の何番目なのか、そしてその配列の何番目なのか。

** (4) 結
-これはOSASKでやっていたslot番号の仕組みにかなり似ています。あの時slotは固定長でしたが、vaTableは可変長です（だから移動もありうる）。
-そしてこの方式では、VA型のオブジェクトはポインタ型の変数を持っているのでCPUのアドレスサイズに依存しますが、アプリ側のポインタは整数を2つ持っているだけなので、「アプリ全体でポインタをいくつ扱うのか＆配列の要素数の上限」だけで必要なintのビット数が決まり、CPUに依存しなくなります。つまり移植性も向上するのです。

-ということで、これからslotライブラリを作ります。

-それにしても、整数2つでポインタを表現するって、まさにセグメンテーションですよねー。

-ちなみにこの方式ではアプリは生のポインタを長期には保存しないので（ループの中でサイズを変更しない間に一時的に持つとかは十分ありうるし、そうしないとスピードが出ない）、それを利用して、オブジェクトの再配置などを行うことができる。つまりメモリのデフラグみたいなもの。・・・その間はアプリを止めておかなければいけないかもしれないけど、それをもって一概にダメだということはできない。なぜなら従来の方式では、アプリを止めても再配置などできなかったのだから。選択肢が増えただけ、ずっとマシである。
-ちなみにこの方式ではアプリは生のポインタを長期には保存しないので（ループの中で配列長を変更しない間に一時的に持つとかは十分ありうるし、そうしないとスピードが出ない）、それを利用して、オブジェクトの再配置などを行うことができる。つまりメモリのデフラグみたいなもの。・・・その間はアプリを止めておかなければいけないかもしれないけど、それをもって一概にダメだということはできない。なぜなら従来の方式では、アプリを止めても再配置などできなかったのだから。選択肢が増えただけ、ずっとマシである。

* こめんと欄
#comment
トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS