我正在一个需要对大量字符串值进行快速字符串搜索的项目中。我决定使用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,而是在程序的beginnig中分配了约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(或任何其他操作系统)中测试我的代码,但想知道在这些操作系统上是否也有类似的行为。

最佳答案

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

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

常见的最小信息令人惊讶(优雅),特别是每个块头都必须包含一点以说明先前的块是否空闲,而无需花费一点以表明当前块是否可用的事实。对于合并,您可以找到下一个块,因为您知道该块的大小。但是只有很少的信息,您才能找到以前的块,除非您已经知道它是免费的,但是除非它是免费的,否则您不需要找到它。因此,在空闲块的末尾有一个指向其开始的指针(或等效大小)。因此,如果它是免费的,则可以从其后继产品导航到它。但是,如果不是免费的,那将成为使用数据的一部分,而不是开销。您可以通过转到继任者的继任者并查看其前任是否空闲来了解继任者是否自由。这比使用更多的备用位更为优雅,但不一定更好。

关于c++ - 为什么Linux在分配动态内存时会占用一些额外的空间?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/32759526/

10-15 02:19
查看更多