はじめてのにき

_ bump allocator

について考えてた。コンパイラとかは最初にガーと alloc して、作ったデータ構造は解放せず、解析の中に解析用のデータ構造を alloc/free する、というパターンになる。これは割と GC 泣かせなアクセスパターンであることが知られている……らしい。なんか世代別があれば良いような気がするけど

やろうと思えば一瞬で作れるからだろうけど、案外実装が転がってないような気がする。昔からあるものとして、 libiberty の obstack や、 apache だと apr_pool だっけ、そんなのがある。まあ GNU とかいかにもコンパイラぽい最初にガーと alloc パターン多そうなのと、 apache もリクエストごとに確保した領域を途中で捨てる必要がないのはよくわかるので、まあそういうところにあるのはとてもよくわかる

bump allocator には地味に良い特徴があると思っていて、アドレスが昇順になるように実装が簡単にできる。これは結構おいしくない？というのは、なんか僕は気楽に `std::set<Value*>` みたいなのを作って、それだけならいいんだけど iteration してしまって、すぐプログラムを非決定論的にしてしまう癖があって。。。根本的に解決するいい方法ないかなあ、とあれこれ考えてて、 bump allocator は割と一石二鳥な感じで良いんじゃないかと……

昇順になってることを保証しようと思うと、 mmap を一回だけ行なうか、あふれた時にもっと先のアドレスを取りに行くように MAP_FIXED で指定しないといけない。まあ、なんか巨大な領域を一回だけ alloc すれば良いように思う

あと、 C++ フレンドリーにするとデストラクタを持たないといけない。単純に考えるとアロケートしたものに対して std::vector<std::pair<void*, std::function<void(void*)>>> みたいな感じで、アロケートしたオブジェクトと、デストラクタの組を管理領域に持っておけば良くて、これだと allocation ごとにオーバヘッドが 16B か。サイズ 4G は越えないっしょと int で持って、デストラクタなんて 4G 種類もないでしょと配列に入れたデストラクタを index で取ってくるような感じにすれば 8B には簡単になりそう。サイズが 65535 以下でデストラクタが 32767 種類以下の時だけ短く持つとかすれば 4B になるが、誰もそこをケチってくれとは言っていないのであった

元の話に戻ると、決定論的にするには、単に使いやすい ruby/python の Hash/dict 的な挿入順序覚えてくれるやつがあれば解決なんだよな。 torch に OrderedDict はあるけど……

なんというか、普段書いてるコードが多すぎて食傷気味で、こういうやつにぱっと手を動かすのがダルくなってる感じがある

(18:03)

_ ちなみに

map に入れたいオブジェクトに通し番号振っておいて、 std::less をそれ使うようにする、てのを最初にやってみて、まあそれで動くのだけど、 forward declaration してあるとダメというのがなあ……となっている

(18:09)

_ ordered map/set

https://github.com/shinh/test/blob/master/ordered.h

https://github.com/shinh/test/blob/master/ordered_test.cc

あと emplace operator[] の口用意するのと、 erase 2 種類くらいあれば実用できるくらいなのかな。。

(18:52)