Memory allocation of std::list

[Victor]

struct Item
{
int *pPtr;
std::list<int*> intList;
};

Item *pItem = new Item[1700000];

I expected the memory usage would be (sizeof(Item) * 1700000) + (the head
pointer of list * 1700000), ie. (28+12)*1700000 = ~64MB, but the outcome is
about 170MB. Would you tell me why is it so?

I asked this question in the MSDN forums and someone answered me "You should
not only account for the array itself (28 x 1700000 = 47.6M) but also for the
size of each constructed std::list object. That's two nodes, 2 x 36 bytes in
your case. That adds up to 47.6M + 2 x 36 x 1700000 = 170M."

But according to my understanding

list()
: _Mybase(), _Myhead(_Buynode()), _Mysize(0)
{ // construct empty list
}

The default contructor will only allocate memory for _Myhead using "_Nodeptr
_Pnode = this->_Alnod.allocate(1);" which allocates only 12 bytes (_Nodeptr
size). Could you let me know which two nodes will be allocated in the
contructor of std::list?

Also, is there any method to reduce the memory usage of a std::list or I
need to write my own link list?

Thanks a lot.

[Bo Persson]

Victor wrote:
> struct Item
> {
> int *pPtr;
> std::list<int*> intList;
> };
>
> Item *pItem = new Item[1700000];
>
> I expected the memory usage would be (sizeof(Item) * 1700000) +
> (the head pointer of list * 1700000), ie. (28+12)*1700000 = ~64MB,
> but the outcome is about 170MB. Would you tell me why is it so?

No, not really. Do you run in debug mode? Using _SECURE_STL to trace
the iterators?

The std::list implementation might also allocate a head node, which
also requires memory.

Also, an allocation of 12 bytes might actually become 16 bytes on some
systems - to reduce heap fragmentation.

>
> I asked this question in the MSDN forums and someone answered me
> "You should not only account for the array itself (28 x 1700000 =
> 47.6M) but also for the size of each constructed std::list object.
> That's two nodes, 2 x 36 bytes in your case. That adds up to 47.6M
> + 2 x 36 x 1700000 = 170M."

Don't know how they came up with that.

>
> But according to my understanding
>
> list()
> : _Mybase(), _Myhead(_Buynode()), _Mysize(0)
> { // construct empty list
> }
>
> The default contructor will only allocate memory for _Myhead using
> "_Nodeptr _Pnode = this->_Alnod.allocate(1);" which allocates only
> 12 bytes (_Nodeptr size). Could you let me know which two nodes
> will be allocated in the contructor of std::list?
>
> Also, is there any method to reduce the memory usage of a std::list
> or I need to write my own link list?
>

One obvious way of reducing memory usage is to NOT have a std::list of
int pointers. The overhead is pretty big, compared to the pointers
themselves. Would a std::vector or a std::deque do the job better?

Bo Persson

[Stephan T. Lavavej [MSFT]]

_SECURE_SCL in release mode and _HAS_ITERATOR_DEBUGGING in debug mode are
*very* different things.

A default-constructed std::list *must* allocate a sentinel node - this is
because it has to support bidirectional iterators and O(1) nofail
non-iterator-invalidating swap(). Additionally, VC9 under _SECURE_SCL makes
Standard containers (even default-constructed ones) allocate an "aux
object", which is the size of a pointer, because otherwise _SECURE_SCL would
be incompatible with O(1) nofail non-iterator-invalidating swap(), as was
the case in VC8.

Owning raw pointers are leaktrocity, especially STL containers of owning raw
pointers. Outside of the implementation of fundamental data structures
(like trees), every "new" in your program should be given to a smart pointer
(I suggest shared_ptr), and every "delete" should vanish.

Stephan T. Lavavej
Visual C++ Libraries Developer

"Bo Persson" <b...@gmb.dk> wrote in message
news:7d59goF...@mid.individual.net...

[Victor]

Yes, I am running in debug mode, but I haven't explicitly define _SECURE_STL.
The size parameter passed to "new" is 28*1700000, after pressing F11, it
went to contruct the object and finally I read ~170MB from Process Explorer's
Private bytes.

[Bo Persson]

Victor wrote:
> Yes, I am running in debug mode, but I haven't explicitly define
> _SECURE_STL. The size parameter passed to "new" is 28*1700000,
> after pressing F11, it went to contruct the object and finally I
> read ~170MB from Process Explorer's Private bytes.

It's actually _SECURE_SCL (I misspelled it) and is on by default. Like
Stephan wrote earlier, you also have some iterator debugging code that
might add to the object sizes.

Generally, any performance measures in debug mode is highly unreliable
(unless you intend to deliver you programs in debug mode).

Bo Persson

[Victor]

The same situration occurred when I test the program in release mode.