- データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
915 ： ◆tAo.kQ2STk [sage]：2016/05/03(火) 15:46:52.15 ID:CPxVolRD - ちょっとOS書いてるんだけど
可変長かつ連続したメモリ領域が本当に必要になるケースはOSレベルではそんなに無いって事を仮定して
・メモリ全体を1つ16バイトのチャンクに分ける
・各チャンクのアドレスの下4ビットが常に0になるので、普段はアドレスを4ビット右シフトした値を識別子として保持する
としてアロケータを組んでみてます。
32ビットの識別子で36ビット(64GiB)の空間を扱えるって利点の他に
x86_64のglibc mallocが1確保に対し管理領域として追加で8 Bytes消費するのと比較して、
こちらは16バイトの確保に対して管理領域として1ビット必要なので
glibc mallocで1024バイトの連続した領域を確保するのと同じ利用効率になり、かつ
「ポインタ」の保存に必要な領域が半減するという利点があります。
アドレスの算出にシフト演算が必要な点と、
基本的なデータ構造(list, set, map, hash, ...)を
1個16バイトのチャンクの組み合わせとして表現するのがちょっと手間である事
連続したメモリ領域の確保に別なアロケータが必要である事が主な欠点です。
実際には、4KiB単位の連続したメモリ領域をアロケータが面白みもない方法で確保して、
その中身をチャンクとして分割し、先頭2チャンクを管理領域にして確保/開放を行うという実装にしています。
連続したメモリ領域が本当に必要でも、4KiBあれば十分と今は仮定しています。
こういう方法ってこのスレ的には既出？
|