am I running out of memory?

[Rich S]

Or just loosing it?

I have a small c++ app which generates millions combinations of bitset
class objects and adds them to a STL map.

(on a side thanks to all who responded to my earlier posting about
increasing the programs speed)

Anyway, I calculate my bitset class object size to be 8 bytes and when
I run this in debug mode I can generate 19,675,656 objects before an
exception is thrown from AfxMem.cpp line 341.

What I don't understand is why I only get that many and not a whole lot
more. 19,675,656 million times 8 is 157,405,208 which is significantly
less than the 1 gig of memory I have running on this machine. I
understand that I don't get the whole gig and thanks to virtual memory
I have 2 gig available but I don't understand why I'm not even getting
close to that mark.

Do you think its truly out of memory or am I trampling on on memory I
shouldn't be. I don't think I am.

One other thing is that I have exception handlers in place but they are
not catching the exception so I'm not sure whats going on there.

Thanks for any help.
Regards

[Victor Bazarov]

Rich S wrote:

Or just loosing it?

I have a small c++ app which generates millions combinations of bitset
class objects and adds them to a STL map.

(on a side thanks to all who responded to my earlier posting about
increasing the programs speed)

Anyway, I calculate my bitset class object size to be 8 bytes and when
I run this in debug mode I can generate 19,675,656 objects before an
exception is thrown from AfxMem.cpp line 341.
I have no idea what 'AfxMem.cpp' is or what is in its like 341. Did
you mean to post it and forgot?
What I don't understand is why I only get that many and not a whole
lot more. 19,675,656 million times 8 is 157,405,208 which is
significantly less than the 1 gig of memory I have running on this
machine. I understand that I don't get the whole gig and thanks to
virtual memory I have 2 gig available but I don't understand why I'm
not even getting close to that mark.
How much overhead does your system produce on top of every object
created in the free store? Perhaps you should try a custom allocator
or something... 19 million objects of the same size are just begging
to be pre-allocated in an array or something.
Do you think its truly out of memory or am I trampling on on memory I
shouldn't be. I don't think I am.
Then who am I to contradict you?
One other thing is that I have exception handlers in place but they
are not catching the exception so I'm not sure whats going on there.

What exception handers? What exception is thrown?

V

[Kai-Uwe Bux]

Rich S wrote:

Or just loosing it?

I have a small c++ app which generates millions combinations of bitset
class objects and adds them to a STL map.

(on a side thanks to all who responded to my earlier posting about
increasing the programs speed)

Anyway, I calculate my bitset class object size to be 8 bytes and when
I run this in debug mode I can generate 19,675,656 objects before an
exception is thrown from AfxMem.cpp line 341.

What I don't understand is why I only get that many and not a whole lot
more. 19,675,656 million times 8 is 157,405,208 which is significantly
less than the 1 gig of memory I have running on this machine. I
understand that I don't get the whole gig and thanks to virtual memory
I have 2 gig available but I don't understand why I'm not even getting
close to that mark.
Hm, your std::set< T > class very likely is implemented as some kind of
balanced tree, i.e., your objects will be stored as nodes that look
somewhat like this:

struct node {
T data_field;
node* right;
node* left;
node* parent;
some_type balancing_info;
}

Also, keep in mind that the new/delete mechanism is likely to add another
word of memory to keep track of how much memory can be reclaimed at delete.
Thus, depending on how balancing information is handled, you might get
slightly above 32 bytes per node. In that case, a call to new might
actually reserve something like 48 or 64 bytes per node, which would be 6
to 8 times more than you calculated.
Do you think its truly out of memory or am I trampling on on memory I
shouldn't be. I don't think I am.

One other thing is that I have exception handlers in place but they are
not catching the exception so I'm not sure whats going on there.

Thanks for any help.
Regards

[Pete Becker]

Kai-Uwe Bux wrote:

Also, keep in mind that the new/delete mechanism is likely to add another
word of memory to keep track of how much memory can be reclaimed at delete.
Thus, depending on how balancing information is handled, you might get
slightly above 32 bytes per node. In that case, a call to new might
actually reserve something like 48 or 64 bytes per node, which would be 6
to 8 times more than you calculated.

Yup, map and set use far more memory than one might expect, especially
for small data objects. A vector or a deque would make much better use
of available memory when you need to manage such a large number of objects.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[Rich S]

Thanks for replying.

I'm never sure how many objects I'll need, it depends on the data. I
could have up to 300 million but it's doubtful. I understand that I
could never actually hold that many but I was hoping for a higher
number than 19 million.

I'm trying to catch std::exception bad_alloc and I don't have the file
handy so I'm not sure what is being thrown. I'll check it out next
crash.

Thanks

[Rich S]

ok thanks. I was going to try vector but I calculated the bytes to be
higher than that of the map so I figured why bother, but I'll give it a
try.

[Rich S]

I'm trying the vector class now but it's running really really slow, I
don't think it'll get to 19 million any time soon and this is in
release mode.

Since I was trying to emulate the map class what I did was create the
bitset object, do a find on the vector class and if it finds it, it
updates an internal counter otherwise it adds the object to the vector.

It must be the find call that's slowing it down drastically.

Any other thoughts?

Thanks again

[Gianni Mariani]

Rich S wrote:

I'm trying the vector class now but it's running really really slow, I
don't think it'll get to 19 million any time soon and this is in
release mode.

Since I was trying to emulate the map class what I did was create the
bitset object, do a find on the vector class and if it finds it, it
updates an internal counter otherwise it adds the object to the vector.

It must be the find call that's slowing it down drastically.

Any other thoughts?

searching a map is O(lnN), searching a vector is O(N).

G

[David White]

Rich S wrote:

I'm trying the vector class now but it's running really really slow, I
don't think it'll get to 19 million any time soon and this is in
release mode.

Since I was trying to emulate the map class what I did was create the
bitset object, do a find on the vector class and if it finds it, it
updates an internal counter otherwise it adds the object to the
vector.

It must be the find call that's slowing it down drastically.

Any other thoughts?

You could try a map that uses a more memory efficient algorithm. A hash
table would probably be better. I have a similar problem with a program that
likes to store as many small objects as it can in a std::set object.
Depending on the exact object size it can store maybe 15 million before it
runs out of memory. The std::set also uses nodes with three pointers, so I'm
going to try a hash-table instead.

Are you deleting objects from the map as well as adding them? If not you can
use a memory allocator that has zero overhead per allocated block and save a
few more bytes per allocation. Such an allocator can only free all the
memory it's allocated at once and not individually allocated blocks, but
that's all you need if you aren't deleting objects except when the map is
destroyed. I use that kind of allocator with my std::set of small objects.

DW

[ravinderthakur]

if you are running your application on windows and are not sure what
type of exceptions are being thrown then u can look up the structured
exception handling in windows (SEH)
to see if those exceptions are being thrown.

windows throws these exceptions in certain cases (eg. when no more
stack space could be allocated).
thanks
rt