Printable View
I have a program that throws a std::bad_alloc exception, even though there is clearly plenty of free memory left on my computer (see attached picture of page file usage history in Task Manager). Prior to program execution, memory usage was about 600 MB, during program execution it went up to ~1.3 GB, at which point a bad_alloc was thrown. I'm wondering, why would my program run out of memory so soon?
p.s. my OS in WinXP SP2
How big is the allocation? If a sufficiently large allocation is attempted on a sufficiently fragmented heap, an allocation can fail despite there appearing to be enough free memory. It's not a matter of how much memory is free, but of whether or not there is a contiguous region of free memory large enough for the allocation.
My situation is quite the opposite. I have a large number of small memory allocations. The objects that I am allocating are only 30-40 bytes in size each, but I have ~13 million of them. So, I don't think that the fragmentation is the problem.Quote:
Originally Posted by Hermit
It does sound like a memory fragmentation problem to me. It occurs because of objects of different size are being created and destroyed. You can write a customize allocator that allocate and deallocate from a specific memory pool to minimize fragmentation.
<edit>
Sorry, I mean it sound like memory fragmentation problem. :P
you should be aware that the default allocator adds extra bytes of memory for each allocation with new you make (I don't know the exact number, something between 4 and 32 bytes) so, instead of 35 bytes being your average allocation, it is in reality 60 bytes. then 13 million of these is about 7 MB which is consistent with your memory usage of 1.3 GB.
You should consider using a small object allocator. The loki library has one and it is free. You can't use it with
VC++ 6.0, but it works with 2005 etc.
You may want to look at this as well http://www.ddj.com/cpp/184402039
As to your problem. You have probably corrupted memory somewhere. Are you sure you don't have any first chance access violations before the bad_alloc is thrown?
Thanks, I'll look into Loki's allocator.Quote:
Originally Posted by souldog
I'm not sure what you mean by 'first chance access violation'. How do I know if one has occurred before the bad_alloc is thrown?Quote:
As to your problem. You have probably corrupted memory somewhere. Are you sure you don't have any first chance access violations before the bad_alloc is thrown?
sorry, I was not clear. You may get a bad_alloc, not because you have run out of memory, but because you have corrupted the heap. If you are lucky this may show up in the debug window as an access violation somewhere before the bad_alloc is thrown. If you are not lucky , then ...
I'm still not entirely clear on what you mean... do you mean that, given that I still had memory available, the bad_alloc was thrown necessarily because the heap was corrupted? Or could there be some other reason for the bad_alloc being thrown?Quote:
Originally Posted by souldog
I believe he means that it's one of several possibilities. Although, if a bad_alloc were to be thrown as a result of a corrupted heap, it would only be by chance, and not because that's the defined behavior if a corruption in the heap is somehow detected. More likely is that you'll get an assertion failure in the debug CRT, if you're lucky enough to not just get random behavior and crashing.Quote:
Originally Posted by HighCommander4
All I was saying is that bad_alloc is thrown when an allocation attempt fails. This could be due to running out of memory, or memory fragmentation, or hardware failure, or a bug in your program that corrupts the free store, or .... Could even be that something other than new is throwing the bad_alloc (like some objects constructor)
I only mentioned this, because you should look over your program and make sure you do not have a bug, instead of just focusing on the size/fragmentation issue
I took a look at Loki's small object allocator, but I can't quite figure out how to use it. I was expecting an allocator class like std::allocator that I could use instead of std::allocator in instantiating the vectors and other containers that contain my small objects. However, I see nothing of the sort. The only documentation that I could find is rather vague and technical.Quote:
Originally Posted by souldog
Could someone point me in the right direction? A piece of example code using the small object allocator would be really helpful.
Thanks, souldog, those links were very helpful. :thumb:Quote:
Originally Posted by souldog
The book preview had some key pages missing, but I think I got the gist of how the small object allocator works.
From what I've read, it seems to me that the small object allocator is designed to allocate small objects one-by-one, i.e. the way you would if you used operator new.
My problem is that my small objects are not allocated one-by-one, but are rather stored in small vectors (the vectors store a small number of small objects, ranging from 1 to 15 small objects).
I noticed that the class SmallObject, while overriding operators new and delete, does not override operators new[] and delete[]. Does this mean that if I make my small object class derive from Loki::SmallObject and use these in a vector (which uses new[] for allocation), then the default operator new[] will be invoked?
If that's the case, should I instead use the Loki SmallObjAllocator class directly, as in vector<MyType, SmallObjAllocator>? I read that the SmallObjAllocaotr will use a different memory pool for each object size, so this method may end up using 15 different memory pools, one for single objects, one for arrays of two objects, and so on... does that sound reasonable?
Or is there, perhaps, a different allocator class (perhaps something from boost) that would suit my needs (millions of vectors, each with 1 to 15 small objects, each 3 bytes in size) better?
OK, it turns out I was wrong about that. vector does not, after all, use operator new[] for allocation. It uses (by default) std::allocator, which always calls the non-array version of operator new (this was a little counterintuitive for me - seeing as vector manages an array of elements, I thought for sure I'd use the array version, but apparently not). So there is no problem with using a SmallObject-derived class in vector (other than the fact that, in my case, the SmallObjAllocator is likely to be using as many as 15 FixedAllocator-s behind the scenes).Quote:
Originally Posted by HighCommander4
Anyways, so I tried using the SmallObjAllocator, and it was certainly an improvement: now my program gets to ~1.6 GB memory usage (of which about 1.1 GB is my program's) before getting an out of memory error. This still seems a little low for me (I have 2 GB RAM + 1.6 GB pagefile, and each process under Windows should be able to address 2 GB of virtual memory), I guess the problem is still memory fragmentation, which is difficult to avoid when you have allocations in the hundreds of megabytes. (I should mention that using the SmallObjAllocator also resulted in a slight (maybe 10-20%) improvement in speed, in spite of using 15 different FixedAllocators behind the scenes).
In any case, I can estimate now that my program will require ~4 GB of memory to run to completion, which is simply not possible under 32-bit Windows (again, 2 GB virtual memory limit), so I'll need more than a good allocator to get it to work (I'll probably have to manually "page" some of my data to the hard drive, or something similar).
In any case, I thank you for all your help, and I will be back if I encounter any other problems.
:wave:
Just wondering, but what are you trying to do? Why do you need to simultaneously create 13 million entries?
I'm writing a "timetable generator" program for a faculty at a university.Quote:
Originally Posted by PredicateNormative
The program takes, as input, the courses a student wishes to take. Typically, a student will take 5 courses at a time, and each course can have a lecture component, a tutorial component and a practical component. There are typically multiple timeslots to choose from for each component of a course, so that a student can assemble a working timetable.
Thus, for any given set of courses, a certain number of timetables are possible, given by
TOTAL_POSSIBLE = n_lecture(1) * n_tutorial(1) * n_practical(1) * n_lecture(2) * n_tutorial(2) * ...
where n_lecture(1) is the number of possible timeslots for the lecture component of course 1, n_tutorial(1) is the number of possible timeslots for the tutorial component, and so on.
Of course, not all possible timetables are valid, because some timeslots conflict with each other. The purpose of the program is to "weed out" the ones that conflict, and display to the user the ones that are valid.
For most sets of courses, this process takes at most a few seconds. However, the occasional set of courses will come up where every course has all three of the components, and every course has 5-10 possible timeslots for each of the components. In situations like this, TOTAL_POSSIBLE can takes values in the hundreds of billions. Of the hundreds of billions of possible timetables, I estimate that between 10 and 100 million are valid.
Now the "weeding" algorithm is very efficient: it does NOT, as a naive solution might, generate all the possible timetables, then check each one, and remove the invalid ones - this would be ridiculous in a case like the onoe above, where there are hundreds of billions of possible timetables. In fact, the algorithm barely uses any additional memory other than the memory required to store the valid timetables.
But if we have, say, 80 million valid timetables, that's still 80 million timetables x 45 bytes per timetable = 3.6 GB of memory I need.
Using the standard allocator, the algorithm gets around to generating 8 million before throwing bad_alloc. Using Loki::SmallObjAlloc, I can now reach 16 million - a definite improvement. But I've still got a long way to go to 80 million, and as I said, it seems that under 32-bit Windows, my only option will be to somehow manually "page" the timetables to the hard drive, which will be a pain in the behind, because it will slow sorting the timetables (already a time-consuming operation with 80 million of them) to a crawl (and sorting becomes especially necessary with 80 million timetables - after all, what student will look through all 80 million of them to find the one that works best!)
Is there a reason why all of the valid timetables must persist in memory? Perhaps there is some way to restructure the program such that you can dump timetables to a database or flat-file while minimizing (or even eliminating) the odds that a given timetable will need to be read back into memory. I can't put forward a specific technique, though, without a better understanding of how your program works.
Well that's exactly what I was thinking when I said "paging" my data - keeping most of it on the hard drive, and only keeping a reasonable amount (say one million) in memory.Quote:
Originally Posted by Hermit
This is fine for the algorithm that generates them - once generated, a timetable can be stored in a file etc. since it's not relevant to the remainder of the generating algorithm.
Once all the valid timetables are generated, however, they need to be sorted, by various criteria specified by the user at run-time (these criteria will help the student choose the "best" timetable out of the millions). It is for this sorting process that it would be nice to have all the valid timetables in memory at once. Because of the multiple-pass nature of sorting, I'd have to read and write the timetables to and from the hard drive multiple times, which would be very time-consuming.
Merge sort.Quote:
Originally Posted by HighCommander4
http://en.wikipedia.org/wiki/Merge_s...ng_tape_drives
Did you actually time this, or are you making presumptions?Quote:
Because of the multiple-pass nature of sorting, I'd have to read and write the timetables to and from the hard drive multiple times, which would be very time-consuming.
Regards,
Paul McKenzie
Yeah, I was thinking of merge sort too. I will definitely give that a try.Quote:
Originally Posted by Paul McKenzie
And yes, I'm making presumptions - I assume that reading 3.6 GB of data from the hard drive and then writing it again log(80,000,000) = 27 times will be more time-consuming that sorting it in memory - but I could be wrong ;). I'll post back here once I've actually tried it (got a few more components to write before then).