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

i wrote little program handle word searching other day , found that, when keep allocating memory bianry search tree store every 1 word tried analyse, using malloc(), 4g memory quickily consumed up.

there no memory leek in program, because allocate memory binary search tree. still, can allocate less 6000 binary search trees in program. structure of binary search tree is:

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

so pretty small. according have learned, every 1 of structure cost 80 bytes of memory(the data cost 20 bytes , others because of memory alignment) (right?)

so 6000 structure in memory cost 480mb in total.

however, program failed when try allocate memory 6000 structrue(it ok when allocate memory 5000 of that).and pc have 4 gb memory in total!! (with 1000mb cached,2100mb available , 1100mb free(according task manager on windows)).

why that?

my primary concerns be:

1. why that?

2. how gracefully manage memory allocation in program.

3. could provide more information?( citation , example , books,etc)

(by way, if want see code please left comment below. there many lines, cost time make 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 name of file wanna open here:");   char name[20] =   { '\0' };   scanf("%s", name);    file* fs = fopen(name, "r");   if (!fs)   {     perror("failed 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 single word, , put bst*/   int flag_1 = 0;   char buf = '\0';   char word[20] =   { '\0' };   node* ptrofnode = firstnode;   int numofword = 0;    while (1)   {     if (numofword < 2000)     {   //amend number determine how many word input       if (1 != fread(&buf, 1, 1, fs))       {         perror("failed read file or eof\n");       }       if (!isalpha(buf))         continue;       /*this while loop used picked out single word in text*/       while (flag_1 == 0)       {         strncat(word, &buf, 1);         if (1 != fread(&buf, 1, 1, fs))         {           perror("failed read char file");           exit(2);         }         if (isalpha(buf))           flag_1 = 0;         else           flag_1 = 1;    //now buf 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 2 reason:     *1.there have been identical word in tree;     *2.the child want insert word have not been allocated memory     */       if (stricmp(word, ptrofnode->data) == 0)       {         ++(ptrofnode->num);         memset(word, '\0', 20);         ptrofnode = firstnode;  //move pointer of node first         numofword+=1;         continue;       }       else       {         if (stricmp(word, ptrofnode->data) > 0)         {        //mean there no more right child           ptrofnode->rightchild = malloc(sizeof(node));           if (ptrofnode->rightchild == null )           {             perror("failed 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 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 program wrote can absolutely explained question. way long can't make readable of , post here.[1]https://github.com/walkerlala/searchtext

if don't think proper program question(the 1 in link absolutely be), please consider concerns above.

i wrote simple code simulate 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!     (int = 0; < factor; i++){         ptrarr[i] = new node[n];     }     //test 2, costs 348mb!     /*     (int = 0; < n*factor; i++){         node *temp = new node;     }*/     return 0; } 

we want allocate 5*10e5 * nodes, , in theory, costs 12bytes * 5 * 10e5 = 6mb.

i run code in vs2013, , test 1 costs 57mb while test 2costs 348mb!

so question, why that?

1. one reason fragment, reason reserved memory.

   • if open debug->windows->memory , @ address of ptrarr[i], find after memory used save node, there quite big area of unused memory.

   • for example, ptrarr[0] = 0x00b18040 , ptrarr[1] = 0x0169f040. 0x0169f040 - 0x00b18040 = 0xb87000 = 12087296 bytes ≈ 12*10e6 bytes

   • so, visual studio allocates 10 times memory need.

   • what test 2? smaller memory allocated @ single time, more memory fragments.

2. how gracefully manage memory allocation in program?

   • avoid frequent allocating small pieces of memory.(it's quite slow , costs more memory.)

3. more information.

   • do know how std::vector increase in visual studio?
   • std::vector<int> numbers; when push 1 number time, capacity of numbers change this:
   • 1->2->3->4->6->9->13->19->...->n->(n+n/2)->...
   • i think it's similar question: reserve space, avoid frequent reallocate operation, increase efficiency.(i'm not sure it.)
   • if want know more memory management in os, can read modern operation system (tanenbaum) chapter 3.