C++ memory allocation errors without use of new

Question

I am having issues with my program throwing a large number of memory allocation exceptions and I am having a very hard time diagnosing the problem...I would post code, but my program is very large and I have proprietary information concerns, so I am hoping to get some help without posting the code. If you plan on responding with some form of SSCCE comment, just stop reading now and save both of us some time. This is a case where I cannot post succinct code - I will try to be as clear and concise as possible with my problem description and some specific questions.

Program Background - my program is basically a data cruncher. It takes a bunch of data tables as inputs, performs calculations on them, and spits out new data tables based on the calculation results. All of my data structures are user-defined classes (consisting of int, double and string types with vector containers for arrays). In all cases, I initiate instances of class variables without the use of new and delete.

Problem Description - my program compiles without warnings, and runs fine on smaller datasets. However, once I increase the dataset (from a 20x80 array to 400x80), I start throwing bad_alloc exceptions (once I've processed the first 35 entries or so). The large datasets runs fine in 17 of my 18 modules - I have isolated one function where the errors are occurring. The calculations needed for this function would result in about 30,000 rows of data being created, whereas other functions in my code generate 800,000+ rows without incident.
The only real unique attribute in this module is that I am using resize a lot (about 100 times per function call), and that the function uses recursive loops during the resize operation (the function is allocating square feet out of a building one tenant at a time, and then updating the remaining feet to be allocated after each tenant lease size and duration is simulated, until all square feet are allocated). Also, the error is happening at nearly the same place each time (but not the exact same location because I have a random number generator that is throwing in some variation to the outcomes). What really confounds me is that the first ~34 calls to this function work fine, and the ~35 call does not require more memory than the previous 34, yet I am having these bad_alloc exceptions on the 35th call nonetheless...

I know it's difficult to help without code. Please just try to give me some direction. My specific questions are as follows:

1. If I am not using "new" and "delete", and all of my variables are being initialized INSIDE of local functions, is it possible to have memory leaks / allocation problems through repeated function calls? Is there anything I can or should do to manage memory when initializing variables include of local function using "vector Instance;" to declare my variables?

2. Is there any chance I am running low on stack memory, if I am doing the whole program through the stack? Is it possible I need to load some of my big lookup tables (maps, etc.) on the heap and then just use the stack for my iterations where speed is important?

3. Is there a problem with using resize a lot related to memory? Could this be an instance where I should use "new" and "delete" (I've been warned in many instances not to use those unless there is a very strong, specific reason to do so)?

4. [Related to 3] Within the problem function, I am creating a class variable, then writing over that variable about 20 times (once for each "iteration" of my model). I don't need the data from the previous iteration when I do this...so I could ostensibly create a new instance of the variable for each iteration, but I don't understand how this would help necessarily (since clearly I am able to do all 20 iterations on one instance on the first ~34 data slices)

Any thoughts would be appreciated. I can try to post some code, but I already tried that once and everyone seemed to get distracted by the fact that it wasn't compilable. I can post the function in question but it doesn't compile by itself.

Here is the class that is causing the problem:

// Class definition
class SpaceBlockRentRoll
{
public:
    double RBA;
    string Tenant;
    int TenantNumber;
    double DefaultTenantPD;
    int StartMonth;
    int EndMonth;
    int RentPSF;
    vector<double> OccupancyVector;
    vector<double> RentVector;
};

// Class variable declaration (occuring inside function)
vector<SpaceBlockRentRoll> RentRoll;

Also, here is a snippet from the function where the recursion occurs

for (int s=1; s<=NumofPaths; ++s) {
    TenantCounter = 0;
    RemainingTenantSF = t1SF;
    if (RemainingTenantSF > 0) {
        while (RemainingTenantSF > 0) {
            TenantCounter = TenantCounter + 1;

            // Resize relevant RentRoll vectors
            ResizeRentRoll(TenantCounter, NumofPaths, NumofPeriods, RentRoll);

            // Assign values for current tenant
            RentRoll[TenantCounter] = AssignRentRollValues(MP, RR)  
            // Update the square feet yet to be allocated
            RemainingTenantSF = RemainingTenantSF - RentRoll[TenantCounter].RBA;
        }
    }
}

Answer 1

bad_alloc comes from heap problems of some kind, and can be thrown by any code that indirectly allocates or frees heap memory, which includes all the standard library collections (std::vector, std::map, etc) as well as std::string.

If your programs do not use a lot of heap memory (so they're not running out of heap), bad_allocs are likely caused by heap corruption, which is generally caused by using dangling pointers into the heap.

You mention that your code does a lot of resize operations -- resize on most collections will invalidate all iterators on the collection, so if you reuse any iterator after a resize, that may cause heap corruption that manifests bad_alloc exceptions. If you use unchecked vector element accesses (std::vector::operator[]), and your indexes are out of range, that can cause heap corruption as well.

The best way to track down heap corruption and memory errors in general is to use a heap debugger such as valgrind

Answer 2

Classes like std::vector and std::string are allowed to throw bad_alloc or other exceptions. After all, they have to use some memory that comes from somewhere, and any computer only has so much memory to go around.

Standard 17.6.5.12/4:

Destructor operations defined in the C++ standard library shall not throw exceptions. Every destructor in the C++ standard library shall behave as if it had a non-throwing exception specification. Any other functions defined in the C++ standard library that do not have an exception-specification may throw implementation-defined exceptions unless otherwise specified. [Footnote 1] An implementation may strengthen this implicit exception-specification by adding an explicit one.

Footnote 1: In particular, they can report a failure to allocate storage by throwing an exception of type bad_alloc, or a class derived from bad_alloc (18.6.2.1). Library implementations should report errors by throwing exceptions of or derived from the standard exception classes (18.6.2.1, 18.8, 19.2).

Answer 3

If I am not using "new" and "delete", and all of my variables are being initialized INSIDE of local functions, is it possible to have memory leaks / allocation problems through repeated function calls?

Unclear. If all the variables you refer to are local, no. If you're using malloc(), calloc(), and free(), yes.

Is there any chance I am running low on stack memory, if I am doing the whole program through the stack?

Not if you get bad_alloc. If you got a 'stack overflow' error, yes.

Is it possible I need to load some of my big lookup tables (maps, etc.) on the heap and then just use the stack for my iterations where speed is important?

Well, it's hard to believe that you need a local copy of a lookup table in every stack frame of a recursive method.

Is there a problem with using resize a lot related to memory?

Of course. You can run out.

Could this be an instance where I should use "new" and "delete"

Impossible today without knowing more about your data structures.

(I've been warned in many instances not to use those unless there is a very strong, specific reason to do so)?

By whom? Why?

Within the problem function, I am creating a class variable,

You are creating an instance of the class on the stack. I think. Please clarify.

then writing over that variable about 20 times (once for each "iteration" of my model).

With an assignment? Does the class have an assignment operator? Is it correct? Does the class itself use heap memory? Is it correctly allocated and deleted on construction, destruction, and assignment?

Answer 4

Since, as you said, you are using std::vector with default allocator, problem occurs when you use a lot of std::vector::resize(...) and it occurs after some iterations, my guess is that you run into heap fragmentation problem.