C++

Forum

 
std::bad_alloc

Fluffy Bunny (24)
Hi there,

I'm getting a strange error with a program I wrote to do some math. The program runs correctly for some short computations. But when it attempts a longer computation, it crashes after a few minutes with the error:

terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc

Any idea what could cause this error? I'm sort of at a loss because the point of the program where it crashes usually works correctly. I gather that this error has something to do with being unable to allocate memory, but the program is only using 3MB when it crashes, so I seem to have plenty of memory.
helios (17574)
The exception is thrown when new cannot allocate more memory.
I'd like to see the code. It could be that you're passing new an expression that evaluates to a really large number.
Fluffy Bunny (24)
Thanks for the reply helios. Unfortunately, the program is too long to post the whole thing. Here's the offending code, with an arrow pointing to the line where it crashes (sorry for posting a huge mess):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
 
#include "cone.h"

list<vector<bigrat> >::iterator last(list<vector<bigrat> >& L)
{
  list<vector<bigrat> >::iterator  i = L.end();
  i--;
  return i;
}

vector<bigrat> cross(const vector<bigrat> A, const vector<bigrat> B)
{
  vector<bigrat> C;
  C.push_back(A[1]*B[2] - A[2]*B[1]);
  C.push_back(A[2]*B[0]-A[0]*B[2]);
  C.push_back(A[0]*B[1]-A[1]*B[0]);
  return C;
}

bigrat dot(const vector<bigrat> V, const vector<bigrat> W)
{
  bigrat sum(0);
  for(unsigned int i = 0; i<V.size(); i++)
    sum += V[i]*W[i];
  return sum;
}

bool multiple(const vector<bigrat> V, const vector<bigrat> W)
{
  return zerovec(cross(V, W));
}

bigrat det(const vector<bigrat> U, const vector<bigrat> V, const vector<bigrat> W)
{
  return dot(cross(U, V), W);
}

bool in_fan(const vector<bigrat> U, const vector<bigrat> V, const vector<bigrat> W)
{
  return (sgn(dot(cross(U, V),cross(U, W))) >0) && ( sgn(dot(cross(W, V), cross(W, U))) > 0);
}

list<vector<bigrat> >::iterator circ_inc(list<vector<bigrat> >& L, list<vector<bigrat> >::iterator i)
{
  i++;
  if(i == L.end())
    i = L.begin();
  return i;
}

list<vector<bigrat> >::iterator circ_dec(list<vector<bigrat> >& L, list<vector<bigrat> >::iterator j)
{
  if(j == L.begin())
    j = L.end();
  j--;
  return j;
}

list<vector<bigrat> >::iterator circ_erase(list<vector<bigrat> >& L, list<vector<bigrat> >::iterator i)
{
  i = L.erase(i);
  if(i == L.end())
    i = L.begin();
  return i;
}

char Cone::add(vector<bigrat> newvec)
{
  if(multiple_in_hull(newvec))
    return 'b';
  switch(type)
    {
    case 'p':
      hull.push_back(newvec);
      type = 'f';
      return 'e';
    case 'f':
      switch(sgn(det(*(hull.begin()), *last(hull), newvec)))
	{
	case 0: //newvec in plane of cone
	  if(in_fan(*hull.begin(), newvec,*last(hull)))
	    return 'i';
	  else if(in_fan(newvec, *(hull.begin()), *last(hull)))
	    {
	      *(hull.begin()) = newvec;
	      return 'e';
	    }
	  else if(in_fan(*(hull.begin()), *last(hull), newvec))
	    {
	      *last(hull) = newvec;
	      return 'e';
	    }
	  else
	    {
	      type = 's';
	      return 'e';
	    }
	case 1:
	  hull.push_back(newvec);
	  type = 'c';
	  return 'e';
	case -1:
	  hull.insert(last(hull), newvec);
	  type = 'c';
	  return 'e';
	}
    case 's':
      switch(sgn(det(*(hull.begin()), *last(hull), newvec)))
	{
	case 0:
	  return 'i';
	case 1:
	  type = 'h';
	  return 'e';
	case -1:
	  hull.push_back(hull.front());
	  hull.erase(hull.begin());
	  type = 'h';
	  return 'e';
	}
    case 'h':
      switch(sgn(det(*(hull.begin()), *last(hull), newvec)))
	{
	case -1:
	  type = 'a';
	  hull.clear();
	  return 'e';
	case 0:
	  return 'b';
	case 1:
	  return 'i';
	}
    case 'a':
      return 'i';
    case 'c':
      list<vector<bigrat> >::iterator first_pos, first_neg;
      switch(extreme_pts(first_pos, first_neg, newvec))
	{
	case 'a':
	  type = 'a';
	  hull.clear();
	  return 'e';
	case 'i':
	  return 'i';
	case 'e':
	  first_neg = circ_inc(hull, first_neg);
	  while(first_neg != first_pos)
	    first_neg = circ_erase(hull, first_neg);
	  hull.insert(first_pos, newvec);
	  return 'e';
	case 'z':
	  list<vector<bigrat> >::iterator next = circ_inc(hull, first_pos);
	  
	  if(in_fan(*first_pos, newvec, *next))
	    return 'i';
	  else if(in_fan(newvec, *first_pos, *next))
	    {
	      first_pos = circ_erase(hull, first_pos);
	      first_pos = circ_dec(hull, first_pos);
 
		{
		  first_pos = circ_erase(hull, first_pos);
		  first_pos = circ_dec(hull, first_pos);
		}
	      hull.insert(next, newvec);
	      return 'e';
	    }
	  else if(in_fan(*first_pos, *next, newvec))
	    {
	      next = circ_erase(hull, next);
	      while(sgn(det(newvec, *next, *circ_inc(hull, next))) <= 0)
		next = circ_erase(hull, next);
	      hull.insert(next, newvec);
	      return 'e';
	    }
	  else
	    {
	      list<vector<bigrat> > newhull;
	      newhull.push_back(*first_pos);
	      newhull.push_back(*next);
	      hull = newhull;
	      type = 'h';
	      return 'e';
	    }
	}
    }
  return 'X'; //unreachable
}


If I go down the stack in gdb from the offending line, I see some mumbo-jumbo in stl_vector.h, then new_allocator.h, where it throws the exception:
1
2
3
4
5
6
7
 
 allocate(size_type __n, const void* = 0)
      { 
	if (__builtin_expect(__n > this->max_size(), false))
	  std::__throw_bad_alloc();

	return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
      }
Fluffy Bunny (24)
Update: it seems the program crashes during the copy constructor for a stl vector. I guess I probably somewhere messed up one of the vectors I am passing to the function det on line 159. Then when the copy constructor is called, the program crashes. Since I have some idea what's wrong now, I should be able to find the bug. Thanks again for your help.
jsmith (5804)
You really should be changing most of your functions to take the vector parameters by const reference rather than by value. As a result of your code, you are pushing entire copies of vectors onto the stack when you call your functions.
Fluffy Bunny (24)
Thanks jsmith, I will try that. The program is real slow so any optimization is useful.
jsmith (5804)
Also, I don't know how complex your "bigrat" type is. If it is expensive to copy,
then you might consider either not using vector or reserving enough space in
your vectors so that reallocations don't occur, because vector reallocations
require that the entire vector be copied, which can potentially be a lot of
copy constructor calls.

I suspect between my first comment and this one you should see at least an
order of magnitude speed increase.
Fluffy Bunny (24)
Surprisingly, changing those vector parameters to references had a negligible effect (.06seconds out of about 6). Maybe the compiler makes this optimization automatically?

bigrat is basically a pair of long int's (represents a rational number), and these vectors always have length 3, so it shouldn't be making reallocations. But maybe it would be faster to use arrays here.
exception (323)
std::bad_alloc *should* be thrown when you are out of memory. However, this part of the standard is usually not implemented for the free store/heap (indeed, cannot be implemented correctly by the runtime environment due to restrictions in the host OS). To understand why, google for "lazy memory allocation".
That being said, bad_alloc could be thrown "legally" due to a stack overflow. Otherwise, most likely undefined behavior is invoked somehow and the result "looks like" a std::bad_alloc is being thrown. Try increasing your stack size; avoid copies of big data structures; move very big data structures from the stack into the free store. If nothing helps, look for illegal access, iterator/pointer errors and other candidates for invoking undefined behavior.

And one last thing.
(sgn(dot(cross(U, V),cross(U, W)))

Er, you know, most people I know name "operator overloading" as one major reason to use C++ in the first place. It would really make your code nicer.
Fluffy Bunny (24)
I fixed it! Thanks for all your help.
aks (3)
hi all,

i am using a matrix (P) (of size n^2) whose each entry is a structure (pmNODE) of size 10 bytes. so for a input of n=15000, the matrix P has size n^2 * 10 = 15000^2 *10 = 2.25 GB (approx)

pmNODE has been defined as shown below:
1
2
3
4
5
6
7
 
typedef struct tag_pmNode {
int xIdx;
int yIdx;
int nIntIdx;
tag_pmNode(): xIdx(-1),yIdx(-1),nIntIdx(-1) {};
tag_pmNode(int x, int y, int nInt): xIdx(x),yIdx(y),nIntIdx(nInt) {};
}pmNODE;



Initially, i was initializing the matrix P (within some function) using the command:
-----------------------------------------------------------------------------------
 
 
vector<vector<pmNODE> > P(n+1, vector<pmNODE> (n+1, tag_pmNode()));



and i got the following error:
-----------------------------------------------------------------------------------
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc


I assumed that this amount of memory is too much to be assigned within the stack (since P in automatic variable) and changed it to the following:
-----------------------------------------------------------------------------------
1
2
3
4
5
6
 
/*** allocation ***/
pmNODE **P;
P = new pmNODE*[numOfElements+1];
for (int i =0; i<= numOfElements; i++) {
P[i] = new pmNODE[numOfElements+1];
}

....
....
1
2
3
 
/*** deallocation ***/
for (int i =0; i<= numOfElements; i++) {
delete[] P[i];hi all,


and i again get the following error:
-----------------------------------------------------------------------------------
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc


i tried this with machines having, 2GB, 4GB and 160 GB ot RAM. But it gives the same error in all of them. so i guess the problem must be elsewhere.

the code runs absolutely fine for small inputs but crashes for large inputs > 12000 or so.

could any one please comment/help ?

thanks.


Zaita (2770)
Aks: Make your own topic please.
aks (3)
ok.
done !!
Topic archived. No new replies allowed.