c++ - 为什么 linux 在分配动态内存时会占用一些额外的空间？

Question

我正在从事一个需要对大量字符串值集合进行快速字符串搜索的项目。我决定使用 Trie 进行搜索，这种方法很快。 这是与我的问题相关的项目的一部分:

class TTrieNode{
public:
    char c;
    bool data;
    TTrieNode *left, *mid, *right;  
    TTrieNode(){
        left = mid = right = NULL;
        c = data = 0;
    }
};

class TTrie{
private:
    TTrieNode *root;
    TTrieNode *insert(TTrieNode*n, char *s, int idx){
        char ch = s[idx];
        if(!n){
            n = new TTrieNode();
            n->c = ch;
        }
        if(ch < (n->c)){
            n->left = insert(n->left, s, idx);
        }else if(ch > (n->c)){
            n->right = insert(n->right, s, idx);
        }else if(idx+1 < strlen(s))
            n->mid = insert(n->mid, s, idx+1);
        else
            n->data = true;
        return n;
    }
public:
    TTrie() {
        root = NULL;
    }
    void insert(char *s) {
        root = insert(root, s, 0);
    }
};

在我们用真实数据测试我的 Trie 之前，一切都很好。根据我对节点数量和每个节点占用的空间量的计算，它应该占用大约 40GB 的 RAM，但令我惊讶的是它占用了大约 70GB。起初我认为这是因为每个节点的内存对齐(只是一个原始猜测!)，所以我使用 __attribute__((packed, aligned(1))) 和我的 TTrieNode定义! 使用它并没有太大的区别。经过大量测试后，我使用了一些手动内存分配。因此，我没有在每次想为新节点分配内存时调用 new，而是在程序开始时分配了约 50GB 的 RAM，并使用了以下自定义新函数:

TTrieNode *memLoc;
int memIdx;
void initMemory(){
    memLoc = (TTrieNode*) malloc(MAXNODES * sizeof(TTrieNode));
    memIdx = 0;
}
TTrieNode*myNew(){
    memLoc[memIdx].left =  memLoc[memIdx].right =  memLoc[memIdx].mid = NULL;
    memLoc[memIdx].c =  memLoc[memIdx].data = 0;
    return &memLoc[memIdx ++];
}

这非常令人惊讶，但这一次，程序占用的内存量完全符合我的预期!

现在我的问题是:

为什么每个 new (malloc) 都有一些额外的内存？每个内存分配在内核/用户级别是否有某种指针？我没有在 Windows(或任何其他操作系统)中测试我的代码，但想知道在这些操作系统上是否也有类似的行为。

Answer 1

分配的每个 block 有 8 到 16 字节的开销。在典型的 x86_64 分配器中，需要 8 字节的开销才能在释放内存块时正确组织它们。还有一个 16 字节对齐要求，这样一个已经是 16 字节倍数的 block 获得基本的 8 字节开销需要浪费另外 8 个字节。

典型的 64 位设计:每个 block 前面都有一个 8 字节的控制字。需要大部分控制字来给出该 block 的大小，因此它可以被释放。底部的几个位可用于其他目的，因为大小可以被 16 整除。这些目的中最重要的是知道前面的 block 是否空闲。当这个 block 被释放时，如果前一个 block 已经被释放，它就会被合并。如果可能的话，它还会与下一个 block 合并。但能够做到这一点并不需要额外的信息。

常见的最少信息令人惊讶(而且优雅)，尤其是每个 block 头都必须包含一个位来说明前一个 block 是否空闲，但不需要任何位来说明当前 block 是否空闲。对于合并，您可以找到下一个 block ，因为您知道该 block 的大小。但是用最少的信息你找不到前一个 block ，除非你已经知道它是免费的但你不需要找到它除非它是免费的。因此，在空闲 block 的末尾有一个指向其开头的指针(或等效大小)。因此，如果它是免费的，您可以从它的继任者导航到它。但是，如果它不是免费的，那么它就是已用数据的一部分，而不是开销。您可以通过转到继任者的继任者并查看其前任是否有空来了解继任者是否有空。这比使用更多的备用位更优雅，但不一定更好。