Need help with std::bad_alloc

Hi,

I have been working on c++ project. My project is big in size. I have added new algorithm to it. The program goes upto few clock cycles and after that it cannot dispatch more instruction and so it goes into timeout(defined in program) or it gives me strange error that says "terminate called after throwing an instance of 'std::bad_alloc' what(): ".

I am using c++ vector here. My program works fine without the added new algorithm but with the added part, I am not sure if has memory allocation problem or not. However I think my algorithm is correct. I also tried the program by removing some portion of that algorithm and it goes upto more instructions than before and then goes in timeout. I really think it is a memory allocation problem, but I am not sure how to solve it as I am still learning C++. I use g++ compiler on linux.

If anybody has any idea, Please let know. Any help is greatly appreciated.

Thank You.

So, bad_alloc is thrown by the standard containers (like vector) when you are out of memory. What that means for your code I can't say.

Sounds like you have a very bad memory leak.

Could it be that your algorithm tries to allocate more memory than a vector can hold (more that max_size is for the given vector type), perhaps by accidentally passing a negative value to a function like resize(), or doubling uncontrollably the size of a vector because of incorrect loop conditions, etc.

Hi,

I understood that I my algorithm is trying to allocate more memory. I tried to reduce the input and it works fine. But my project is really big and I am not sure how to solve this part. Do I need more memory or is there any better way to allocate lesser memory. I a really lost here. My code is really big but I can show a part of my algorithm here.

Quote:

---

Code:

---

odescnd_index[disp_context_id] = (scnd_index[disp_context_id] + (contexts[disp_context_id].ROB.size()-1)) % contexts[disp_context_id].ROB.size();
                        //for(scnd_index[disp_context_id]=(contexts[disp_context_id].ROB_head); scnd_index[disp_context_id]!= contexts[disp_context_id].ROB_tail; scnd_index[disp_context_id]=(scnd_index[disp_context_id]+1))
                        unsigned int num_searched = 0, prev_index = 0;
                                        while(num_searched<contexts[disp_context_id].ROB_num)
                                                        {
                                                                ROB_entry *prev_inst;
                                                            is = &contexts[disp_context_id].ROB[scnd_index[disp_context_id]];
                                                          if(is->dispatched == 0){
                                                            if(rs->src_physreg[0] == is->physreg){
                                                                    contexts[disp_context_id].ROB[contexts[disp_context_id].ROB_tail].prev_depend_ctr.push_back(&contexts[disp_context_id].ROB[scnd_index[disp_context_id]]);
                                                                    contexts[disp_context_id].ROB[scnd_index[disp_context_id]].depend_ctr.push_back(&contexts[disp_context_id].ROB[contexts[disp_context_id].ROB_tail]);
                                                                    if(is->depend_flag != 0){
                                                                            prev_inst = is;
                                                                            while(!prev_inst->prev_depend_ctr.empty()){
                                                                                    prev_inst = prev_inst->prev_depend_ctr[0];
                                                                                    prev_inst->depend_ctr.push_back(&contexts[disp_context_id].ROB[contexts[disp_context_id].ROB_tail]);
                                                                                    rs->depend_flag++;
                                                                            }
                                                                    }
                                                                    rs->depend_flag++;
                                                            }
                                                            else if(rs->src_physreg[1] == is->physreg){
                                                                    contexts[disp_context_id].ROB[contexts[disp_context_id].ROB_tail].prev_depend_ctr.push_back(&contexts[disp_context_id].ROB[scnd_index[disp_context_id]]);
                                                                contexts[disp_context_id].ROB[scnd_index[disp_context_id]].depend_ctr.push_back(&contexts[disp_context_id].ROB[contexts[disp_context_id].ROB_tail]);
                                                                if(is->depend_flag != 0){
                                                                        prev_inst = is;
                                                                        while(!prev_inst->prev_depend_ctr.empty()){
                                                                                prev_inst = prev_inst->prev_depend_ctr[0];
                                                                                prev_inst->depend_ctr.push_back(&contexts[disp_context_id].ROB[contexts[disp_context_id].ROB_tail]);
                                                                                rs->depend_flag++;
                                                                        }
                                                                }
                                                                rs->depend_flag++;
                                                            }
                                                          }
                                                            num_searched++;
                                                            scnd_index[disp_context_id] = (scnd_index[disp_context_id] + (contexts[disp_context_id].ROB.size()-1)) % contexts[disp_context_id].ROB.size();
                                                        }

---

---

In above algorithm, I have "depend_ctr" and "prev_depend_ctr" are two vectors that I have declared to the Class "ROB_entry". ROB is a vector of "ROB_entry"ies and each ROB_entry has one "depend_ctr" and "prev_depend_ctr" and they hold pointer to other ROB_entries. I am not sure if I can add index of that entry instead of pointer. But this works with small input upto arround 1000 instructions but I really need it for much more instructions.

If anybody knows better solution to it, please let me know. I really appreciate any help, as I need to finish this week.

Thank You.

I haven't looked at that code too much, but assuming there are no leaks:

Try changing vector to deque if you can, as it can hold more elements.

Quote:

---

Originally Posted by King Mir

Try changing vector to deque if you can, as it can hold more elements.

---

That's news to me. Where is that stated? Or how did you draw that conclusion?

It's because vector has to use a single continuous memory segment. Deque is allowed to use multiple segments; it can request several smaller segments, instead of one large one. Relaxing the continuity requirement allows the OS to allocate more memory.

It's stated in Josuttis's The C++ Standard Librairy.

Quote:

---

Originally Posted by grumpy

That's news to me. Where is that stated? Or how did you draw that conclusion?

---

My guess is that King Mir reasoned that since a vector must have contiguous internal storage, it may be the case where requested memory cannot be allocated despite the total available memory exceeding the memory required. Since a deque's internal storage is likely to consist of smaller blocks, there is less chance of this happening, thus in practice the maximum capacity of a deque would tend to be larger than that of an otherwise equivalent vector.