はじめに
組み込みやゲームなど特殊な環境では, 独自のメモリ割り当てが必要になることがあります. ひとつの選択肢として, "Buddy memory allocation"を考えてみます.
良いメモリ割り当ての理想は次になります. 特殊環境で自前に実装する理由は, 3つ目を捨てて, その環境で1と2を追求するということです.
- 確保・解放が高速に動作する
- 内部・外部断片化が最小である
- 環境に応じて最適に動作する
記載するコードは一部を抜き出しています.
Buddy system
オブジェクトの相方（buddy)を決めて, 処理の効率化を測るシステムになります. "Buddy memory allocation"では, メモリブロックを2分木で管理して, 兄弟の節を相方と考えます. 実装が2分木であるかではなく, 考え方が2分木です. メモリ割り当ての効率化とは, コンパクションの効率化になります.
前の図の例で, 8KB以下のメモリを2つ確保すると次のようになります.
それから, 確保順に解放したとすると, 次のようになります. 相方が空きなら親を遡って空きにすることで, コンパクションを実現します.
欠点は, 2分木ですので割り当てサイズの自由度が狭く, 内部断片化が大きくなることです.
Bitmap表現による"Buddy system"の実装
N分木は配列で表現できるため, "Buddy system"も配列で表現可能です.
前項を見ると"Buddy system"を実現するために, "空き", "割り当て済", "一部割り当て済"の3値が必要になります. ここでは単純に, 一部割り当て済かを表すfillと, そのブロックが割り当て済かを表すuseを使用します.
template<class T=u64>
class BitTree
{
typedef T value_type;
value_type fill_;
value_type use_;
};
割り当て
入力は割り当てたい木のレベルです. 64KBのブロックから32KBが欲しいなら, レベル1を要求してください. 出力は, 割り当ての成否と木の配列インデックスです. APIの設計の話ですので, お好きにしていただきたいです.
未使用の節の子供を探索して, 該当のレベルの節が空なら割り当て成功です. 割り当てに成功した場合, 親を遡って一部割り当て済（fill）のフラグをセットします.
余談ですが, スタックが8固定なのは64bitのbitmapまでしか考えていないからです.
template<class T>
bool BitTree<T>::set(u8& index, u32 level)
{
assert(level <= MaxLevel);
Node stack[8];
u8 top = 1;
stack[top] = {0, 0};
while(0 < top) {
Node node = stack[top];
--top;
value_type flag = One << node.index_;
if(level <= node.level_) {
bool empty = 0 == (fill_ & flag);
if(empty) {
use_ |= flag;
fill_ |= flag;
backtrackSet(node.index_);
index = node.index_;
return true;
}
} else if(0 == (use_ & flag)){
assert(node.level_<=MaxLevel);
u8 nextLevel = node.level_ + 1;
u8 child0 = (node.index_ << 1) + 1;
u8 child1 = child0 + 1;
++top;
stack[top] = {child1, nextLevel};
++top;
stack[top] = {child0, nextLevel};
}
}
return false;
}
親を遡って一部割り当て済のフラグをセットします.
template<class T>
void BitTree<T>::backtrackSet(u8 index)
{
while(0 < index) {
index = (index-1) >> 1;
fill_ |= (One << index);
}
}
解放
入力は, 木の配列インデックスです, 管理は外側に任せる方針です.
template<class T>
void BitTree<T>::reset(u8 index)
{
assert(0 != (use_ & (One << index)));
assert(0 != (fill_ & (One << index)));
value_type flag = ~(One << index);
use_ &= flag;
fill_ &= flag;
backtrackReset(index);
}
親に遡りながら相方が空きなら, その親を空きにセットします. コンパクションがこのように単純なことが, このシステムの利点です.
template<class T>
void BitTree<T>::backtrackReset(u8 index)
{
while(0 < index) {
u8 sibling = 0 == (index & 0x01U) ? index - 1 : index + 1;
value_type flag = One << sibling;
if(0 != (fill_ & flag)) {
return;
}
index = (index - 1) >> 1;
fill_ &= ~(One << index);
}
}
テスト
BitTree<> bitTree;
u8 index[3];
bitTree.set(index[1], BitTree<>::MaxLevel);
bitTree.set(index[0], 3);
bitTree.print();
bitTree.set(index[2], BitTree<>::MaxLevel);
bitTree.print();
bitTree.reset(index[0]);
bitTree.print();
bitTree.reset(index[1]);
bitTree.print();
bitTree.reset(index[2]);
bitTree.print();
結果は次のようになります, 'f'は一部割り当て済, 'u'は割り当て済, '-'は空きになります. 正しい（おそらく）.
f
f-
f---
fu------
f---------------
u-------------------------------
f
f-
f---
fu------
f---------------
uu------------------------------
f
f-
f---
f-------
f---------------
uu------------------------------
f
f-
f---
f-------
f---------------
-u------------------------------
-
--
----
--------
----------------
--------------------------------
まとめ
何に使うの？というのは後日書くかもしれません.