6

完全にブランチ フリーのメモリ マネージャー (C++ で) を作成する方法を考えた人はいますか? プール、スタック、キュー、およびリンク リスト (プールから割り当てる) を作成しましたが、ブランチ フリーの汎用メモリ マネージャーを作成することがどれほど妥当か疑問に思っています。

これはすべて、確実な同時実行、順序付けされた CPU、およびキャッシュに適した開発を行うための、本当に再利用可能なフレームワークを作成するのに役立ちます。

編集:ブランチレスとは、直接または間接の関数呼び出しを行わず、ifs を使用しないことを意味します。私はおそらく、最初に要求されたサイズを false 呼び出しのゼロに変更する何かを実装できると考えていましたが、実際にはそれ以上のものはありませんでした。不可能ではないと思いますが、この演習のもう 1 つの側面は、前述の「友好的でない」プロセッサでプロファイリングして、分岐を回避するためにこれほど努力する価値があるかどうかを確認することです。

4

2 に答える 2

2

これは良い考えだとは思いませんが、1 つの解決策は、さまざまなログ2サイズのバケットを事前に割り当てておくことです。愚かな疑似コードです。

class Allocator {

    void* malloc(size_t size) {
        int bucket = log2(size + sizeof(int));
        int* pointer = reinterpret_cast<int*>(m_buckets[bucket].back());
        m_buckets[bucket].pop_back();
        *pointer = bucket; //Store which bucket this was allocated from
        return pointer + 1; //Dont overwrite header
    }

    void free(void* pointer) {
        int* temp = reinterpret_cast<int*>(pointer) - 1;
        m_buckets[*temp].push_back(temp);
    }

    vector< vector<void*> > m_buckets;
};

(もちろんstd::vector、 を単純な配列 + カウンターに置き換えることもできます)。

編集：これを堅牢にする（つまり、バケットが空の状況を処理する）には、何らかの形式の分岐を追加する必要があります。

EDIT2:これは小さなブランチレスlog2関数です:

//returns the smallest x such that value <= (1 << x)
int
log2(int value) {
    union Foo {
        int x;
        float y;
    } foo;
    foo.y = value - 1;
    return ((foo.x & (0xFF << 23)) >> 23) - 126; //Extract exponent (base 2) of floating point number
}

これにより、33554432 バイト未満の割り当てに対して正しい結果が得られます。より大きな割り当てが必要な場合は、double に切り替える必要があります。

これは、浮動小数点数がメモリ内でどのように表現されるかへのリンクです。

于 2010-03-22T11:13:03.437 に答える