6

任何人都想过如何编写一个完全无分支的内存管理器（在 C++ 中）？我已经编写了一个池、一个堆栈、一个队列和一个链表（从池中分配），但我想知道编写一个无分支的通用内存管理器有多合理。

这一切都是为了帮助创建一个真正可重用的框架，以进行可靠的并发、有序 CPU 和缓存友好的开发。

编辑：无分支是指不进行直接或间接函数调用，也不使用 ifs。我一直在想我可能可以实现一些东西，首先将请求的大小更改为零以进行错误调用，但实际上并没有更多。我觉得这不是不可能的，但是这个练习的另一个方面是在所说的“不友好”处理器上对其进行分析，看看是否值得像这样努力避免分支。

4

2 回答 2

2

虽然我认为这不是一个好主意，但一种解决方案是预先分配各种日志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 字节的正确结果。如果您需要更大的分配，您将不得不切换到双打。

这是浮点数在内存中表示方式的链接。

于 2010-03-22T11:13:03.437 回答
0

我知道创建一个真正的无分支分配器的唯一方法是提前保留它可能使用的所有内存。否则总会有一些隐藏的代码在某处查看我们是否超过了当前容量，无论它是否隐藏push_back在向量中，检查大小是否超过用于实现它的容量或类似的东西。

这是一个固定分配的粗略示例，它具有完全无分支的malloc和free方法。

class FixedAlloc
{
public:
    FixedAlloc(int element_size, int num_reserve)
    {
        element_size = max(element_size, sizeof(Chunk));
        mem = new char[num_reserve * element_size];

        char* ptr = mem;
        free_chunk = reinterpret_cast<Chunk*>(ptr);
        free_chunk->next = 0;

        Chunk* last_chunk = free_chunk;
        for (int j=1; j < num_reserve; ++j)
        {
            ptr += element_size;
            Chunk* chunk = reinterpret_cast<Chunk*>(ptr);
            chunk->next = 0;
            last_chunk->next = chunk;
            last_chunk = chunk;
        }
    }

    ~FixedAlloc()
    {
        delete[] mem;
    }

    void* malloc()
    {
        assert(free_chunk && free_chunk->next && "Reserve memory exhausted!");
        Chunk* chunk = free_chunk;
        free_chunk = free_chunk->next;
        return chunk->mem;
    }

    void free(void* mem)
    {
        Chunk* chunk = static_cast<Chunk*>(mem);
        chunk->next = free_chunk;
        free_chunk = chunk;
    }

private:
    union Chunk
    {
        Chunk* next;
        char mem[1];
    };
    char* mem;
    Chunk* free_chunk;
};

由于它完全是无分支的，因此如果您尝试分配比最初保留更多的内存，它只会出现段错误。它还具有未定义的尝试释放空指针的行为。为了一个更简单的例子，我也避免处理对齐。

于 2015-05-01T09:09:30.483 回答