How to optimize malloc() to get full use of your memory?

Question

I wrote a little program to handle word searching the other day and found that, when keep allocating memory for the bianry search tree where I store every one word I tried to analyse, using malloc(), my 4G memory would be quickily consumed up.

There is no memory leek in my program, because I only allocate memory for that binary search tree. But still, I can only allocate less than 6000 binary search trees in my program. The structure of that binary search tree is:

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

So it is pretty small. According to what I have learned, every one of that structure cost 80 bytes of memory(the data cost 20 bytes and so is the others because of memory alignment) (right?)

So 6000 that structure in memory would cost 480MB in total.

However, my program failed when I try to allocate memory for that 6000 structrue(It is ok when I allocate memory for 5000 of that).And my PC have 4 GB memory in total!! (with about 1000MB cached,2100MB available and 1100MB free(according to the task manager on Windows)).

Why is that?

My primary concerns would be:

1. Why is that?

2. How to gracefully manage memory allocation in my program.

3. Could you provide more information?( citation and example and books,etc)

(By the way, if you want to see my code please left a comment below. There is too many lines, it cost some time to make it more readable. sorry)

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

code:

#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;
}

And there is another program I wrote which can absolutely explained my question. But it is way too long that I can't make it readable for all of you and post it here.[1]https://github.com/walkerlala/searchText

If you don't think this is a proper program for this question(the one in my link would absolutely be), please consider about my concerns above.

Answer 1

I wrote some simple code to simulate your problem.

struct Node{
    int val;
    Node *left;
    Node *right;
    Node() :val(1){}
};

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

We want to allocate 5*10e5 * Nodes, and in theory, it will costs 12Bytes * 5 * 10e5 = 6MB.

I run this code in VS2013, and Test 1 costs 57MB while Test 2costs 348MB!

So back to your question, why is that?

1. One reason is fragment, another reason is reserved memory.

   • If you open DEBUG->WINDOWS->MEMORY and look at the address of ptrArr[i], you will find that after those memory used to save Node, there is quite a big area of unused memory.

   • For example, ptrArr[0] = 0x00b18040 and ptrArr[1] = 0x0169f040. 0x0169f040 - 0x00b18040 = 0xb87000 = 12087296 Bytes ≈ 12*10e6 Bytes

   • So, Visual Studio allocates 10 times memory than we need.

   • What about Test 2? Smaller memory allocated at a single time, more memory fragments.

2. How to gracefully manage memory allocation in my program?

   • Avoid frequent allocating small pieces of memory.(It's quite slow and costs more memory.)

3. More information.

   • Do you know how std::vector increase in Visual Studio?
   • std::vector<int> numbers; When we push one number a time, the capacity of numbers will change like this:
   • 1->2->3->4->6->9->13->19->...->n->(n+n/2)->...
   • I think it's similar to this question: reserve extra space, avoid frequent reallocate operation, increase efficiency.(I'm not very sure about it.)
   • If you want to know more about memory management in OS, you can read Modern Operation System (Tanenbaum) Chapter 3.