シンプルで高速なアロケータ(3)

program C++

過去ログ

メモリの配置方法ですが、以下のような配置にしようと思います。

[32bit]{[32bit]...[32bit]}({[32bit]...[32bit]}...{[32bit]...[32bit]}).........[MB][MB][MB][MB]...
[深さ0][      深さ1      ][                   深さ2                 ][深さD-1]

[32bit] は 32bit のメモリ領域
{} の中には [] が 32 個ある
() の中には {} が 32 個ある

[MB] はメモリブロック
D は深さの最大数

[32bit]というのは int１個分で、これが最小単位なので、int１個をチャンクと呼ぶことにします。


例えば深さの最大数が 3 で、ブロックを一つ確保して使用しているというフラグを立てるためには、以下のような手順になります。

  • （[深さnの先頭の位置のチャンク] → [Dn] と書いています）
  1. [D0] から、空いているビットを求める → この値を A とする
  2. [D1 + A] から、空いているビットを求める → この値を B とする
  3. [D2 + A * 32 + B] から、空いているビットを求める → この値を C とする
  4. メモリブロックの C 番目の値が空いている領域なので、そのポインタを保持しておく。
  5. [D2 + A * 32 + B] の、C 番目のビットを 1 にする
  6. もし 5. によって [D2 + A * 32 + B] が全て 1 になっている場合は、[D1 + A] の B 番目のビットを 1 にする
  7. もし 6. によって [D1 + A] が全て 1 になっている場合は、[D0] の A 番目のビットを 1 にする
  8. 4. で保持しておいたポインタを返す

これが Use() メソッドの処理です。


なぜ [D2 + A * 32 + B] といった計算式で空いているブロックの位置が求められるかというと、シンプルで高速なアロケータで書いた通り 32 分木になっているからです。


1 個のルートから 32 個のノードが出て、32 個のノードそれぞれから 32 個のノードが出ているので、

                         [Root]
                           ↓
        [Node00] [Node01] .... [Node30] [Node31] [] の中は１個のチャンク
           ↓                              ↓
([Node00] .... [Node31]) .... ([Node00] .... [Node31]) () の中は３２個のチャンク

このように、深さ 2 の場所では () １つ分を移動するために A * 32 の値ずつ移動し、[] １つ分を移動するために B を足す必要があり、つまり上記の式になるわけです。


次はこれをプログラムで考えてみます。