memory consumption lists

[jaapkroe]

Hi,

I created a program to handle large datafiles where I 'pipe' the data trough a list with pop_front and push_back.
However I noticed that the program is consuming more memory than I expected.
Looking at the memory consumption (with top for example), it seems that the elements of a (doubly linked) list each use 32 bytes.

Since I couldn't find anything on the web I hope you can explain to me how this memory is handled. In my case, I expected just 8 bytes for each double. Does the referencing (back and forth) in a doubly linked list perhaps take memory?

Below is a simple test program to fill up the memory with list<double>

Kind regards,
Jaap

#include <iostream>
#include <list>
using namespace std;

int main() {
  char buf;
  cout << "Program will now allocate doubles in a list." << endl
       << "sizeof(double) = " << sizeof(double) << " bytes" << endl
       << "(<enter> to continue)";
  cin.get(buf);

  list<double> l;
  for(int i=1; i<=10; i++) {
    for(int j=0; j<1024*1024; j++) {
      l.push_back(0);
    }
    cout << "Stop: pushed " << i << " x 1024^2 numbers (<enter> to continue) ";
    cin.get(buf);
  }

  return 0;
}

[helios]

Does the referencing (back and forth) in a doubly linked list perhaps take memory?

Of course. Each node needs at least two pointers and space to hold the templated member, which in you case is a double, which usually takes 64 bits. That's 16 or 24 bytes, depending on whether your system is 32- or 64-bits. Then you have to add some overhead from heap allocation, which is used to store the size of the allocated buffer.

This is why linked lists are not used to store very small objects. For example, a very common use of linked lists is to queue small buffers (4K-16K) in streaming applications, like audio players. This is because the data is much larger than the node that will hold it, so the overhead from using a linked list is negligible.

[jaapkroe]

Thank you for the response.
Perhaps I should use another container format for my purpose.
A deque seems to offer all the functionality I need and a similar test shows their items use only 8bytes.

However, I don't understand why...
Aren't they linked in the same way?

When I write:

deque<double> deq;
deque<double>::iterator it;
it = deq.begin()
it++;

I expected that to 'raise the iterator by one' it needs a pointer to the memory location of the next element.
Which would again require the same space for the pointers (the 16 or 24 bytes including the double), because also the deque allows me to go trough it both ways (using it++ or it--).
Is there any reason why these pointers are not needed in deques??
Is it perhaps because deques don't allow middle insertion and therefore the elements are stored like 0x00000000, 0x00000001, ... ??
If so, what if another program tries to allocate some space at the same time??

Sorry for the stupid questions.
Here is a test which shows the functionality I want to use.

#include <iostream>
#include <deque>
using namespace std;

int main() {
  char buf;
  cout << "Program will now allocate doubles in a double-ended queue." << endl
       << "sizeof(double) = " << sizeof(double) << " bytes" << endl
       << "(<enter> to continue)";
  cin.get(buf);

  deque<double> q;
  for(int i=1; i<=10; i++) {
    for(int j=0; j<10; j++) {
      q.push_back(j*i);
      if(q.size() > 15) q.pop_front();
      cout << "q = ";
      deque<double>::iterator it = q.begin();
      for(it=q.begin(); it!=q.end(); it++) {
        cout << *it << ',' ;
      } cout << endl;
    }
    cout << "Stop: pushed " << i*10 << " numbers (<enter> to continue) ";
    cin.get(buf);
  }

  return 0;
}

[jsmith]

std::deque is a linked list of arrays, essentially.

(std::deque does allow insertion in the middle).

[jaapkroe]

std::deque is a linked list of arrays, essentially.

But then why does it consume less memory??

Or is middle insertion here implemented as: shift all values after 'middle' by one memory position and write new value to 'middle'?

[jsmith]

(speaking gcc here; not sure how much of this is mandated)

Each element stored in a std::list is stored in a node, which contains, in addition to the data, a next and prev
pointer and a color (the underlying implementation used by STL is an r-b tree).

A deque stores as many elements as it can in an array of 512 bytes. Each array then has a couple of pointers
of overhead.

So with a deque, if your elements are small, you get less overhead. If you attempt to store an element that
is at least 512 bytes in size, then the memory efficiency of std::deque<>approaches that of std::list<>.

[jaapkroe]

Thank you for the explanation.
My gcc-version seems to have the same 512 bytes hard-coded.
It still seems a bit strange but apparently this is a useful magic number.
At least in my case it also seems like a useful value and if you want to store larger items one could use lists as you said.

Excerpt from my "stl_deque.h", which is now understandable with your explanation and some google.. :)
Thanks!

  /**  
   *  @brief This function controls the size of memory nodes.
   *  @param  size  The size of an element.
   *  @return   The number (not byte size) of elements per node.
   *
   *  This function started off as a compiler kludge from SGI, but seems to
   *  be a useful wrapper around a repeated constant expression.  The '512' is
   *  tunable (and no other code needs to change), but no investigation has
   *  been done since inheriting the SGI code.
  */
  inline size_t
  __deque_buf_size(size_t __size)
  { return __size < 512 ? size_t(512 / __size) : size_t(1); }

...

  /**
   *  Here's how a deque<Tp> manages memory.  Each deque has 4 members:
   *
   *  - Tp**        _M_map
   *  - size_t      _M_map_size
   *  - iterator    _M_start, _M_finish
  */