如何优化malloc()以充分利用你的记忆？

Question

我前几天编写了一个小程序来处理单词搜索,并发现,当我为bianry搜索树分配内存时,我存储了我试图分析的每个单词,使用时malloc(),我的4G内存将被快速消耗掉.

我的程序中没有内存韭菜,因为我只为该二进制搜索树分配内存.但是,我仍然可以在程序中分配少于6000个二叉搜索树.二叉搜索树的结构是:

typedef struct BSTnode{
    char data[20];
    struct BSTnode* leftchild;    
    struct BSTnode* rightchild;   
    int num;
}BSTnode;

所以它很小.根据我所学到的,每个结构都需要80个字节的内存(data成本为20个字节,其他因为内存对齐)(对吧？)

因此,内存中的6000个结构总共需要480MB.

但是,当我尝试为6000个结构分配内存时,我的程序失败了(当我为5000分配内存时可以.)我的PC总共有4 GB的内存!(与约1000MB cached,2100MB available和1100MB free(根据Windows上的任务经理)).

这是为什么？

我主要担心的是:

1. 这是为什么？

2. 如何在我的程序中优雅地管理内存分配.

3. 你能提供更多信息吗？(引用,例子和书籍等)

(顺便说一句,如果你想查看我的代码,请在下面留下评论.行数太多,花费一些时间让它更具可读性.抱歉)

################################################## ################## 3

码:

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>

typedef struct Node
{
  struct Node* leftChild;
  struct Node* rightChild;
  char data[20];
  int num;
} Node;

int inputWord(FILE*, Node*);

int main(int argc, char** argv)
{
  printf("Enter the name of file you wanna open here:");
  char name[20] =
  { '\0' };
  scanf("%s", name);

  FILE* fs = fopen(name, "r");
  if (!fs)
  {
    perror("Failed to open file!");
    exit(EXIT_FAILURE);
  }

  Node* firstNode = malloc(sizeof(Node));
  if (firstNode == NULL )
  {
    perror("ALLOCATION FAILED!");
    exit(1);
  }

  firstNode->leftChild = firstNode->rightChild = NULL;
  firstNode->num = 1;
  strcpy(firstNode->data, "a");

  inputWord(fs, firstNode);
  fclose(fs);

  printf("Done!!");
  return 0;
}

int inputWord(FILE* fs, Node* firstNode)
{
  rewind(fs);
  /*first figure out a single word, and then put it into to BST*/
  int flag_1 = 0;
  char buf = '\0';
  char word[20] =
  { '\0' };
  Node* ptrOfNode = firstNode;
  int numOfWord = 0;

  while (1)
  {
    if (numOfWord < 2000)
    {   //amend this number to determine how many word to be input
      if (1 != fread(&buf, 1, 1, fs))
      {
        perror("failed to read file or eof\n");
      }
      if (!isalpha(buf))
        continue;
      /*this while loop is used to picked out a single word in the text*/
      while (flag_1 == 0)
      {
        strncat(word, &buf, 1);
        if (1 != fread(&buf, 1, 1, fs))
        {
          perror("Failed to read char from the file");
          exit(2);
        }
        if (isalpha(buf))
          flag_1 = 0;
        else
          flag_1 = 1;    //now buf is not alpha
      }

      flag_1 = 0;

      while (1)
      {
        if (stricmp(word, ptrOfNode->data) > 0&& ptrOfNode->rightChild!=NULL)
          ptrOfNode = ptrOfNode->rightChild;
        else if (stricmp(word, ptrOfNode->data) < 0 && ptrOfNode->leftChild!=NULL)               
          ptrOfNode = ptrOfNode->leftChild;
        else
          break;
      }
   /*the while loop above break for only two reason:
    *1.there have been an identical word in the tree;
    *2.the child where I want to insert the word have not been allocated memory
    */
      if (stricmp(word, ptrOfNode->data) == 0)
      {
        ++(ptrOfNode->num);
        memset(word, '\0', 20);
        ptrOfNode = firstNode;  //move the pointer of Node to the very first
        numOfWord+=1;
        continue;
      }
      else
      {
        if (stricmp(word, ptrOfNode->data) > 0)
        {        //mean that there is no more right child
          ptrOfNode->rightChild = malloc(sizeof(Node));
          if (ptrOfNode->rightChild == NULL )
          {
            perror("FAILED TO ALLOCATED MEMORY!!");
            exit(1);
          }
          ptrOfNode = ptrOfNode->rightChild;
          ptrOfNode->leftChild = ptrOfNode->rightChild = NULL;
          ptrOfNode->num = 1;
          strcpy(ptrOfNode->data, word);

          memset(word, '\0', 20);
          ptrOfNode = firstNode;
          numOfWord += 1;
          continue;
        }
        else
        {
          ptrOfNode->leftChild = malloc(sizeof(Node));
          if (ptrOfNode->leftChild == NULL )
          {
            perror("FAILED TO ALLOCATE MEMORY!");
            exit(1);
          }
          ptrOfNode = ptrOfNode->leftChild;
          ptrOfNode->leftChild = ptrOfNode->rightChild = NULL;
          ptrOfNode->num = 1;
          strcpy(ptrOfNode->data, word);

          memset(word, '\0', 20);
          ptrOfNode = firstNode;
          numOfWord += 1;
          continue;
        }
      }
    }
    else
      break;
  }

  return 0;
}

我写的另一个程序可以绝对解释我的问题.但这太长了以至于我无法让所有人都阅读并在此发布.[1] https://github.com/walkerlala/searchText

如果你不认为这是一个适合这个问题的程序(我链接中的那个绝对是),请考虑我上面的问题.

Answer 1

我写了一些简单的代码来模拟你的问题。

\n\n

struct Node{\n    int val;\n    Node *left;\n    Node *right;\n    Node() :val(1){}\n};\n\nint main(){\n    int size = sizeof(Node);//size = 12Bytes\n    const int N = 10e5;\n    const int factor = 5;//12B*5*10^5 = 6MB\n    Node* ptrArr[factor];\n    //Test 1, costs 57MB!\n    for (int i = 0; i < factor; i++){\n        ptrArr[i] = new Node[N];\n    }\n    //Test 2, costs 348MB!\n    /*\n    for (int i = 0; i < N*factor; i++){\n        Node *temp = new Node;\n    }*/\n    return 0;\n}\n

\n\n

我们想要分配5*10e5* Nodes，理论上，它会花费12Bytes * 5 * 10e5 = 6MB。

\n\n

我运行这段代码VS2013，Test 1成本57MB很高！Test 2348MB

\n\n

回到你的问题，这是为什么？

\n\n

\n

1. 一个原因是碎片，另一个原因是保留内存。

   \n\n
   \n

   • 如果你打开DEBUG->WINDOWS->MEMORY查看地址ptrArr[i]，你会发现在那些用来保存的内存之后Node，还有相当大的一块区域没有使用。

   \n

   • 例如，ptrArr[0] = 0x00b18040和ptrArr[1] = 0x0169f040。0x0169f040 - 0x00b18040 = 0xb87000 = 12087296 Bytes \xe2\x89\x88 12*10e6 Bytes

   \n

   • 因此，Visual Studio 分配的内存是我们需要的 10 倍。

   \n

   • 关于什么Test 2？一次性分配的内存越小，内存碎片越多。

   \n
\n

2. 如何优雅地管理程序中的内存分配？

   \n\n
   \n
   • 避免频繁分配小块内存。（它非常慢并且消耗更多内存。）
   \n
\n

3. 更多信息。

   \n\n
   \n
   • 你知道std::vectorVisual Studio中如何增加吗？
   \n
   • std::vector<int> numbers;当我们一次按下一个数字时， 的容量numbers将发生如下变化：
   \n
   • 1->2->3->4->6->9->13->19->...->n->(n+n/2)->...
   \n
   • 我认为这类似于这个问题：保留额外的空间，避免频繁的重新分配操作，提高效率。（我对此不太确定。）
   \n
   • 如果你想了解更多关于操作系统内存管理的知识，可以阅读Modern Operating System (Tanenbaum) Chapter 3。
   \n
\n

\n