无网点内存管理器？

Question

有人想过如何编写一个完全没有分支的内存管理器(用C++编写)吗？我写了一个池,一个堆栈,一个队列和一个链表(从池中分配),但我想知道编写一个免费的通用内存管理器是多么合理.

这有助于构建一个真正可重用的框架,用于执行可靠的并发,有序CPU和缓存友好的开发.

编辑:无分支我的意思是不进行直接或间接的函数调用,也不使用ifs.我一直在想我可能会实现一些事情,首先将请求的大小更改为零,以便进行错误的调用,但实际上并没有更多的东西.我觉得这不是不可能的,但是这个练习的另一个方面就是在所说的"不友好"的处理器上进行分析,看看是否值得尽可能地努力避免分支.

Answer 1

虽然我认为这不是一个好主意，但一种解决方案是预先分配各种 log ₂大小的存储桶，这是愚蠢的伪代码：

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 字节的分配，这给出了正确的结果。如果您需要更大的分配，则必须切换到双打。

这是有关如何在内存中表示浮点数的链接。