linux x64 c++ allocates way too much memory for a linked list; why?

Question

i will be using linked list example code seen here on stackoverflow to illustrate the problem.

my c++ written progam (x64) contains this linked list code :

old code snippets deleted; im sorry if comments doesnot make sense anymore.

added fully working code to show what my problem is. compile : g++ linkedlist.cpp -o linked-list

#include <cstdlib>
#include <iostream>

using namespace std;


 struct node
{
    public :
          unsigned int part1; // 4 bytes
          unsigned int part2; // 4 bytes
          node *next;         //pointer, 8 bytes on 64 bit system
      unsigned int read_part1();
 };


struct LinkedList
 {
     public:
     LinkedList();
          void insert(unsigned int data[], unsigned int data1);
          bool isEmpty() const;
          node* head;
 };

unsigned int node::read_part1() {
return part1;
}
 LinkedList::LinkedList():
 head(NULL)
{
}

bool LinkedList::isEmpty() const
{
  return (head == NULL);
}

  void LinkedList::insert(unsigned int data[], unsigned int data1)
 {



    node* oldHead = head;
    node* newHead = new node();
    newHead->part1 = data[0];
    newHead->part2 = data1;
    newHead->next = oldHead;
    head = newHead;

  }

unsigned int allocations = 300000000;
unsigned int index_size = 430000000;//index of lists, 430m,.
                    //will be creatad on heap
    LinkedList *list = NULL;





int main(int argc, char *argv[])

{
LinkedList list_instance;

cout << "1 LinkedList instance takes [" << sizeof(list_instance) << "] bytes in memory!"<< endl;

node node_instance;

cout << "1 node instance takes [" << sizeof(node_instance) <<"] bytes in memory !"<< endl;


    try{
    list = new LinkedList[index_size];
    }

     catch(std::bad_alloc) {
    cout << "Error allocating memory" << endl;
     return 0;
    //reboot code
    }

unsigned int some_data[] = {00, 01};
unsigned int index;

LinkedList *list_instance2 = NULL;



cout << "Allocating ..." << endl;

for (int i=0; i<allocations; i++)
{

index = rand();
unsigned short inde = (unsigned short)index;
list_instance2 = &list[inde];

list_instance2->insert(some_data, some_data[1]);


}

unsigned long sk = ((allocations * sizeof(node_instance) + index_size*sizeof(list_instance))) / (1024*1024*1024);

cout << "This process *should* consume around " << sk <<" GBytes of memory, but does it ?"<< endl;

cout << "Allocating done, *check the process size* and press any number key + ENTER to exit ..." << endl;

int u=0;
cin >> u;


return 0;
}

compile it, run it and see if your process size even remotely matches whats expected. if not - where is the problem ?

oh, and i run it on 64 bit slackware 13.37 with a unmodified default kernel.

Answer 1

On my box, with slightly modified source (see below with notes)

• it uses 1243 MiB rather than the 'expected' 785 MiB using the standard library heap routines
• it uses 791 MiB when using Google's tcmalloc
• it uses 840 MiB when using Boost Object Pool to allocate nodes (with standard library heap or tcmalloc)

The overhead is very clearly in the implementation of the heap routines.

Here's the code:

• Note the use of new (nothrow) there.
• Also, the baseline measurement at the start (I used pmap $(pgrep test) | tail on linux)

• Note the choice in insert:

  void LinkedList::insert(unsigned int data[], unsigned int data1)
  {
  #if 1
      head = new node { data[0], data1, head };
  #else
      static boost::object_pool<node> node_pool;
  
      node* add = node_pool.malloc();
      *add = node { data[0], data1, head };
      head = add;
  #endif
  }
  

  Change #if 1 to #if 0 to use the Boost Object Pool

• There was a strangeness in the node allocation loop

  index = rand();
  unsigned short inde = (unsigned short)index;
  list_instance2 = &list[inde];
  list_instance2->insert(some_data, some_data[1]);
  

  I changed it to what you probably intended:

  list[rand() % index_size].insert(some_data, some_data[1]);
  

#include <stdlib.h>
#include <iostream>
#include <boost/pool/object_pool.hpp>

using namespace std;

struct node
{
    unsigned int part1; // 4 bytes
    unsigned int part2; // 4 bytes
    node *next;         //pointer, 8 bytes on 64 bit system
};

struct LinkedList
{
public:
    LinkedList();
    void insert(unsigned int data[], unsigned int data1);
    bool isEmpty() const;
    node* head;
};

LinkedList::LinkedList():
    head(NULL)
{
}

bool LinkedList::isEmpty() const
{
    return (head == NULL);
}

void LinkedList::insert(unsigned int data[], unsigned int data1)
{
#if 1
    head = new node { data[0], data1, head };
#else
    static boost::object_pool<node> node_pool;

    node* add = node_pool.malloc();
    *add = node { data[0], data1, head };
    head = add;
#endif
}

const unsigned int allocations = 30000000;
const unsigned int index_size = 43000000;//index of lists
//will be creatad on heap
LinkedList *list = NULL;

int main(int argc, char *argv[])
{
    LinkedList list_instance;
    cout << "1 LinkedList instance takes [" << sizeof(list_instance) << "] bytes in memory!"<< endl;
    node node_instance;
    cout << "1 node instance takes [" << sizeof(node_instance) <<"] bytes in memory !"<< endl;
    cout << "Before dynamic allocations: *check the baseline process size* and press ENTER to start allocating ..." << endl;
    std::string s;
    std::getline(std::cin, s);
    list = new (nothrow) LinkedList[index_size];
    if (!list)
    {
        cout << "Error allocating memory" << endl;
        return 1;
    }
    unsigned int some_data[] = {00, 01};
    cout << "Allocating nodes ..." << endl;
    for (unsigned int i=0; i<allocations; i++)
    {
        list[rand() % index_size].insert(some_data, some_data[1]);
    }
    unsigned long sk = ((allocations * sizeof(node_instance) + index_size*sizeof(list_instance))) >> 20;
    cout << "This process *should* consume around " << sk <<" MiB of memory, but does it ?"<< endl;
    cout << "Allocating done, *check the process size* and press ENTER to exit ..." << endl;
    std::getline(std::cin, s);
    return 0;
}