这段代码的实际内存使用量为什么与预计的

以下一段代码，执行时发现实际的内存用量与预计的相差2－3倍，经过处略调试，问题可能出在函数
int insertVNode(char *str, RGraph *g, int location)里面。但具体什么原因，恳请各位大神指正一下。

先说说这段代码的逻辑吧。
该程序从文件中读取记录，其中第一行是一个数值，代表文件里有多少条记录，第二行开始存放记录。即文件内容的格式为：

记录数目
记录编号，姓名1，姓名2，姓名3
记录编号，姓名4，姓名5，姓名6
......
记录编号，姓名X，姓名Y，姓名Z

程序会用文件中的全部姓名作为结点来构建一个无向图。该无向图采用邻接表方式来存储，即用一个数组把所有不重复的结点存放起来（最坏的情况是文件里的每个姓名可能都不一样，所以该数组长度最大为3*文件记录数），这样数组元素下标就成了该结点的编号了；每个数组元素各自包含一个链表指针，链表元素则是与该结点相邻的其他结点的编号。
具体C语言程序如下：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<fstream>

#include<Windows.h>
#include<time.h>

#define MAX_REC_LENGTH 80
#define MAX_NAME_LENGTH 20
#define ROLE_COUNT_IN_ONE_REC 3

#define SUCC 0
#define FAIL -1

#pragma pack(1)

struct ANode
{
	int toVNodeIndex;
	ANode *next;
};

typedef ANode* ArcList;

//定义结点 
struct VNode
{
	bool isVisited;//结点是否已被访问 
	char *name;//结点的实际数据
	ArcList arcList;//链表，用于存放与该结点相邻的其他结点的编号 
};

typedef VNode** AdjList;

//定义图 
struct RGraph
{
	AdjList adjList;//邻接表 
	int adjListLength;//邻接表长度（即结点个数） 
};

using namespace std;

/*
	返回文件第一行的内容（该行记录了文件里除第一行外有多少行记录） 
*/
int readRecordCount(char *strCount)
{
	int len = strlen(strCount);

	for(int i=0;i<len;i++)
		if(strCount[i]<'0' || strCount[i] > '9')
			strCount[i] = '0';

	return atoi(strCount);
}

/*
	用二分查找法在一个升序序列的邻接表中定位字符串string所在的结点的编号。
	如果查找成功，则返回0，并且该编号由指针location返回。 
	如果查找失败，则返回-1，并且指针location会返回该string结点在升序邻接表中应该对应的编号（以便后面的插入操作的定位）。 
*/
int locateInAdjList(char *string, RGraph *g, int* location)
{
	int low = 0;
	int high = g->adjListLength -1;
	int mid;
	int result;

	while(low <= high)
	{
		mid = (low + high) / 2;
		result = strcmp(string, (*(g->adjList + mid))->name);
		if(0 == result)
		{
			*location = mid;// 字符串string对应的顶点在邻接表中的编号 
			return SUCC;// 查找成功 
		}
		else if(result < 0)
			high = mid - 1;
		else
			low = mid + 1;
	}

	*location = low;// 字符串结点将要插入的位置
	return FAIL;// 查找失败 
}

/*
	为字符串str创建一个VNode结点, 并在指定的location位置将其插入到图的邻接表中.
	（内存使用量的问题应该出在这个函数里？？？） 
*/
int insertVNode(char *str, RGraph *g, int location)
{
	VNode *pVNode;

	// 为str创建VNode结点 
	pVNode = (VNode*)malloc(sizeof(VNode));
	pVNode->name = (char *)malloc(sizeof(char) * MAX_NAME_LENGTH);
	strcpy(pVNode->name, str);
	pVNode->arcList = NULL;
	pVNode->isVisited = false;

	// 邻接表中location打后的结点全部后移一位 
	for(int i=g->adjListLength; i>location; i--)
		*(g->adjList + i) = *(g->adjList + (i-1));

	// 插入新建的VNode结点 
	*(g->adjList + location) = pVNode;
	g->adjListLength ++;

	return SUCC;
}

/* 
	从文件的每一行读取3个姓名，每一个都作为图的结点，并插进该图的邻接表中 
*/
int buildVNode(char* fileName, RGraph *g)
{
	char fisBuffer[MAX_REC_LENGTH];
	char *pName[ROLE_COUNT_IN_ONE_REC];

	ifstream fis1(fileName);
	if(!fis1)
		return FAIL;

	// 图的初始化
	fis1.getline(fisBuffer,MAX_REC_LENGTH);//读取文件中的第一行内容，它记录了文件有多少行记录 
	g->adjListLength = 0;
	g->adjList = (VNode**) malloc(sizeof(VNode*) * readRecordCount(fisBuffer) * ROLE_COUNT_IN_ONE_REC);

	// 将每一个姓名作为一个结点，插入到图的邻接表中 
	while(!fis1.eof())
	{
		fis1.getline(fisBuffer,MAX_REC_LENGTH);
		strtok(fisBuffer, ",");//将文件每一行中的第一个字段跳过，不对其作任何处理 
		for(int i=0;i<ROLE_COUNT_IN_ONE_REC;i++)
			pName[i] = strtok(NULL,",");

		int location;
		//该行记录的第一个姓名结点不在邻接表中，则插入之  
		if(FAIL == locateInAdjList(pName[0],g, &location))
			insertVNode(pName[0],g,location);

		//该行记录的第二个姓名结点与第一个姓名结点不同，且不在邻接表中，则插入之 
		if(strcmp(pName[1],pName[0]) !=0 && FAIL == locateInAdjList(pName[1],g, &location))
			insertVNode(pName[1],g,location);

		//该行记录的第二个姓名结点与前两个姓名结点不同，且不在邻接表中，则插入之 
		if(strcmp(pName[2],pName[0]) !=0 && 
			strcmp(pName[2],pName[1]) !=0 && 
			FAIL == locateInAdjList(pName[2],g, &location))
			insertVNode(pName[2],g,location);
	}

	fis1.close();

	return SUCC;
}

int main(int argc,char* argv[])
{
	RGraph g;

	//构建图的顶点 
	buildVNode(argv[1], &g); 

	cout<<"VNode Count: "<<g.adjListLength<<endl;
	cout<<"Total run time: "<<clock()<<endl;

	free(g.adjList);

	return SUCC;
}

现在有测试数据为100万条记录，且每个姓名都不一样。这种情况下，以上代码的内存使用预计如下：
1. 邻接表g->adjList的内存使用量 ＝ sizeof(VNode*) * 100万 * 3 = 4 Byte * 100万 * 3 = 11.444MB
2. 所有VNode结点的内存使用量 = sizeof(VNode) * 100万 * 3 = 9 Byte * 100万 * 3 = 25.749MB
(9 Byte = sizeof(bool) + sizeof(char*) + sizeof(ArcList) = 1 Byte + 4 Byte + 4 Byte)
3. 每个VNode结点中的字符指针name会指向20个字符的姓名字符串，因此所有VNode包含字符串总量为
20Byte * 100万 * 3 = 57.22MB
因此预计程序总共需要分配的内存数是11.444+25.749+57.22＝94.413MB

但实际运行后，发现程序需要占用264.19MB的内存，足足相差将近3倍！！
请问大神们能帮忙分析一下这个差异的原因吗？

谢谢！

11 个解决方案

#1

建议LZ分别试一下10万、1万、1000、100、10、1条记录的情况，然后对比找规律
这个算黑盒吧，白盒的由楼下补充

#2

引用 1 楼 *mill 的回复:

建议LZ分别试一下10万、1万、1000、100、10、1条记录的情况，然后对比找规律
这个算黑盒吧，白盒的由楼下补充

我也曾经打算用1条、10条记录来调试，只是这样的内存量太少了，我在Win7的任务管理器->进程->内存一栏看不出内存的变化(那里的单位都是KB级别的......)。
或者您有什么好的工具推荐一下吗？

#3

1. 没算name的20个字节
2. 没算栈

#4

我的意思是，程序需要占用264.19MB的内存是不是都由这个无向图占用的。比如，如果10万条记录要用30M，那就是；如果10万条记录占用150M，那就不是。

#5

引用 3 楼 ma100 的回复:

1. 没算name的20个字节
2. 没算栈

name的20个字节已经包含了（见估算过程的第3点），共占用20Byte * 100万 * 3 = 57.22MB。
至于栈的空间，这应该怎么算呢？会造成2-3倍的内存空间差异吗？

#6

一般会有两种浪费。
1. 这种大规模小size的内存分配正常都不会给你正好分配这个size的内存的。你得去看你的C运行库代码，看看比如是不是会对9字节的malloc请求给你实际分配了16字节。我印象里的glibc把小size内存的malloc给向上取整到2幂次，那么9字节就实际分配16字节，20字节就实际分配32字节，直接就多出来(7+12)*300w=57MB了。当然具体数字因情况而异，但是正常情况下这类浪费肯定有。大块malloc这类浪费忽略不计，但是小的肯定不行。
2. 每一块malloc的内存，在那个指针的前面，allocator会存储一些关于这块内存是如何分配的这种信息，以便它free的时候使用。具体也是要看allocator怎么写，不过正常都在8~16字节左右。每块malloc的空间都会有。这也是为什么越界经常会导致崩溃……因为这块数据被破坏了allocator就不知道该怎么free这块内存了。如果算它8字节，这里就有8*300w*3=72MB了。

所以即使通用allocator再厉害，自己做内存池的理由还是有很多的，这就是其中一个。

#7

VMMap 是进程虚拟和物理内存分析实用工具。 http://technet.microsoft.com/zh-cn/sysinternals/dd535533

#8

那么多malloc却只有一个free.  内存占用高也很正常, 最后也会有一大堆的内存泄漏 

#9

引用 6 楼 FancyMouse 的回复:

一般会有两种浪费。
1. 这种大规模小size的内存分配正常都不会给你正好分配这个size的内存的。你得去看你的C运行库代码，看看比如是不是会对9字节的malloc请求给你实际分配了16字节。我印象里的glibc把小size内存的malloc给向上取整到2幂次，那么9字节就实际分配16字节，20字节就实际分配32字节，直接就多出来(7+12)*300w=57MB了。当然具体数字因情况而异，但是正常情况下这类浪费肯定有。大块malloc这类浪费忽略不计，但是小的肯定不行。
2. 每一块malloc的内存，在那个指针的前面，allocator会存储一些关于这块内存是如何分配的这种信息，以便它free的时候使用。具体也是要看allocator怎么写，不过正常都在8~16字节左右。每块malloc的空间都会有。这也是为什么越界经常会导致崩溃……因为这块数据被破坏了allocator就不知道该怎么free这块内存了。如果算它8字节，这里就有8*300w*3=72MB了。

所以即使通用allocator再厉害，自己做内存池的理由还是有很多的，这就是其中一个。

刚刚试用VS2010和DevCPP编译同一份代码，发现编译出来的程序在运行时使用的内存量貌似真的有很大的差异呢。

请问有没有什么编译器推介一下，可以让生成的程序占用较小的内存？
谢谢！

#10

几个建议：
1、编译器换最新的VS 2013 或者 gcc 4.9.x
2、把malloc内存的操作全部替换掉，改成C++ 0x11的 vector 和 tuple 组合
3、算法似乎可以优化，但不知道你的具体需求。

#11

终于知道问题所在了。

正如6楼提到的第二点，malloc分配出来的实际空间会比参数指定的size还要多出一点点。如果malloc的次数少还发现不到这问题，可一旦malloc的次数十分巨大时，那些多出来的“碎片”加起来就变得十分可观了。

最后我采用的方法是预先malloc出一大片空间池，以后每次需要申请内存保存数据的话，就把指针指向那片空间池对应的位置把数据保存到里面。这样程序运行时实际使用的内存量就和之前估算的差不多了。