Need help with std::bad_alloc

This is a discussion on Need help with std::bad_alloc within the C++ Programming forums, part of the General Programming Boards category; Hi, I have been working on c++ project. My project is big in size. I have added new algorithm to ...

  1. #1
    Registered User
    Join Date
    Jul 2009
    Posts
    7

    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.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  3. #3
    Registered User
    Join Date
    Apr 2006
    Posts
    2,023
    Sounds like you have a very bad memory leak.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Registered User
    Join Date
    Jul 2009
    Posts
    7
    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.
    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.

  6. #6
    Registered User
    Join Date
    Apr 2006
    Posts
    2,023
    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.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  7. #7
    Registered User
    Join Date
    Jun 2005
    Posts
    6,245
    Quote Originally Posted by King Mir View Post
    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?
    Right 98% of the time, and don't care about the other 3%.

  8. #8
    Registered User
    Join Date
    Apr 2006
    Posts
    2,023
    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.
    Last edited by King Mir; 10-07-2009 at 01:06 AM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,588
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21