无分区内存管理器？

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

这都是为了帮助构建一个真正可重用的框架，用于实现可靠的并发，有序CPU和缓存友好的开发。

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

来源

2010-03-22 Richard Fabian

你是什么意思的“分支”？ – 2010-03-22 10:23:08

@Neil，我想，这是分裂控制流的东西（例如'if'运算符）。 – 2010-03-22 10:30:48

如果分支意味着“如果”，那么答案是否定的。 @OP：请你澄清一下，如果这确实是你的意思？ – 2010-03-22 11:10:52

虽然我不认为这是一个好主意，一个解决办法是有各种日志的预分配桶大小，愚蠢的伪代码：

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字节正确的结果。如果你需要更大的分配，你将不得不切换到双打。

这里是一个link浮点数如何表示在内存中。

来源

2010-03-22 11:13:03

Log2可能需要依赖于平台的实现才能无分支。在x86上，您可能需要对参数进行BSR指令。 – 2010-03-22 11:33:19

@Jasper：这里有一些代码声称是无分区clz - 我假设没有测试它的工作原理：http://stackoverflow.com/questions/2255177/finding-the-exponent-of-n-2x-using-按位操作 - 对数 - 在基-2-的/ 2255282＃2255282。从简单的浏览，它似乎返回0输入0，所以你可能想要一个分支覆盖0情况，或大于一半的范围的情况。正如你所说，虽然，实现可能提供更快的CPU操作。 – 2010-03-22 11:44:45

@Jasper @Steve看我的编辑。 – 2010-03-22 12:24:38

我知道创建一个真正的无分配分配器的唯一方法是预先保存所有可能使用的内存。否则总是会有一些隐藏的代码在某处，以查看我们是否超出了某个当前容量，无论它是否处于向量中的隐藏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; 
};

因为它是完全的无网点，它只是如果你尝试分配更多的内存比最初保留出现segfaults。它也有试图释放空指针的未定义行为。为了更简单的例子，我也避免了对齐。

来源

2015-05-01 09:09:30

无分区内存管理器？

回答

相关问题