- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在从事一个需要对大量字符串值集合进行快速字符串搜索的项目。我决定使用 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(或任何其他操作系统)中测试我的代码,但想知道在这些操作系统上是否也有类似的行为。
最佳答案
分配的每个 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 的末尾有一个指向其开头的指针(或等效大小)。因此,如果它是免费的,您可以从它的继任者导航到它。但是,如果它不是免费的,那么它就是已用数据的一部分,而不是开销。您可以通过转到继任者的继任者并查看其前任是否有空来了解继任者是否有空。这比使用更多的备用位更优雅,但不一定更好。
关于c++ - 为什么 linux 在分配动态内存时会占用一些额外的空间?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32759526/
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 要求我们推荐或查找工具、库或最喜欢的场外资源的问题对于 Stack Overflow 来说是偏离主题的,
Linux 管道可以缓冲多少数据?这是可配置的吗? 如果管道的两端在同一个进程中,但线程不同,这会有什么不同吗? 请注意:这个“同一个进程,两个线程”的问题是理论上的边栏,真正的问题是关于缓冲的。 最
我找到了here [最后一页] 一种有趣的通过 Linux 启动 Linux 的方法。不幸的是,它只是被提及,我在网上找不到任何有用的链接。那么有人听说过一种避免引导加载程序而使用 Linux 的方法
很难说出这里要问什么。这个问题模棱两可、含糊不清、不完整、过于宽泛或夸夸其谈,无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开,visit the help center . 关闭 1
我试图了解 ld-linux.so 如何在 Linux 上解析对版本化符号的引用。我有以下文件: 测试.c: void f(); int main() { f(); } a.c 和 b.c:
与 RetroPie 的工作原理类似,我可以使用 Linux 应用程序作为我的桌面环境吗?我实际上并不需要像实际桌面和安装应用程序这样的东西。我只需要一种干净简单的方法来在 RaspberryPi 上
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 这个问题似乎不是关于 a specific programming problem, a softwar
关闭。这个问题是off-topic .它目前不接受答案。 想改进这个问题吗? Update the question所以它是on-topic用于堆栈溢出。 关闭 10 年前。 Improve thi
有什么方法可以覆盖现有的源代码,我应该用 PyQt、PyGTK、Java 等从头开始构建吗? 最佳答案 如果您指的是软件本身而不是它所连接的存储库,那么自定义应用程序的方法就是 fork 项目。据我所
我的情况是:我在一个磁盘上安装了两个 linux。我将第一个安装在/dev/sda1 中,然后在/dev/sda2 中安装第二个然后我运行第一个系统,我写了一个脚本来在第一个系统运行时更新它。
我在 i2c-0 总线上使用地址为 0x3f 的系统监视器设备。该设备在设备树中配置有 pmbus 驱动程序。 问题是,加载 linux 内核时,这个“Sysmon”设备没有供电。因此,当我在总线 0
关闭。这个问题是off-topic .它目前不接受答案。 想改进这个问题吗? Update the question所以它是on-topic用于堆栈溢出。 关闭 11 年前。 Improve thi
我正试图在 linux 模块中分配一大块内存,而 kalloc 做不到。 我知道唯一的方法是使用 alloc_bootmem(unsigned long size) 但我只能从 linux 内核而不是
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 这个问题似乎不是关于 a specific programming problem, a softwar
我有 .sh 文件来运行应用程序。在该文件中,我想动态设置服务器名称,而不是每次都配置。 我尝试了以下方法,它在 CentOS 中运行良好。 nohup /voip/java/jdk1.8.0_71/
我是在 Linux 上开发嵌入式 C++ 程序的新手。我有我的 Debian 操作系统,我在其中开发和编译了我的 C++ 项目(一个简单的控制台进程)。 我想将我的应用程序放到另一个 Debian 操
关闭。这个问题需要多问focused 。目前不接受答案。 想要改进此问题吗?更新问题,使其仅关注一个问题 editing this post . 已关闭 4 年前。 Improve this ques
我使用4.19.78版本的稳定内核,我想找到带有企鹅二进制数据的C数组。系统启动时显示。我需要在哪里搜索该内容? 我在 include/linux/linux_logo.h 文件中只找到了一些 Log
我知道可以使用 gdb 的服务器模式远程调试代码,我知道可以调试针对另一种架构交叉编译的代码,但是是否可以更进一步,从远程调试 Linux 应用程序OS X 使用 gdbserver? 最佳答案 当然
是否有任何可能的方法来运行在另一个 Linux 上编译的二进制文件?我知道当然最简单的是在另一台机器上重建它,但假设我们唯一能得到的是一个二进制文件,那么这可能与否? (我知道这可能并不容易,但我只是
我是一名优秀的程序员,十分优秀!