c++ - 无分支内存管理器？

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

这是一个 link float 在内存中的表示方式。