Slow manual 'garbage collection' in C++ ??

[brey_maastricht]

Hello guys,

I really need your help. I'm a Java programmer and right now I'm
experiencing a huge problem with C++.

In a scientific computation I need to store a lot of Point objects
(which have an array of doubles and 2 ints as fields).
To quickly search among all these points I have designed a Hashtable
to store them; a bucket/vector of buckets/vectors.
The hashtable is filled with Points objects in a while loop.

This whole procedure again is repeated a lot of times in a for loop.
At the end of every run of this for loop the Hashtable has to be
emptied in order to prevent for memroy leaks: this means looping
through every vector in the main vector of the hashtable and delete
every Point object manually.
Later on, this C++ computation will be compiled under Matlab to use it
over there.

But now the problem is:

My C++ programm is very fast without emptying the hashtable. But then
I have a huge memory leak; and my swapfile grows enormouly.
With emptying the hashtable my C++ programm becomes dramatically
slow.....even slower than my Java programm.

So the question is: What to do now ?? It cannot be the case that
preventing a memory leak, slows down the computations ??

Kind regards,
Brey

 

[Mirco Wahab]

In a scientific computation I need to store a lot of Point objects
(which have an array of doubles and 2 ints as fields).
To quickly search among all these points I have designed a Hashtable
to store them; a bucket/vector of buckets/vectors.
The hashtable is filled with Points objects in a while loop.
...
My C++ programm is very fast without emptying the hashtable. But then
I have a huge memory leak; and my swapfile grows enormouly.
With emptying the hashtable my C++ programm becomes dramatically
slow.....even slower than my Java programm.
So the question is: What to do now ?? It cannot be the case that
preventing a memory leak, slows down the computations ??

You could redesign the stuff for speed by using
e.g. continous vectors - and hash separate
integer indexes which point into these:

// [PSEUDO]

vector<int>indexarray; // <= 0 .. NUMPOINTS-1

struct coordinates {
vector<double>x; // <= 0 .. NUMPOINTS-1
vector<double>y; //
vector<double>z; //
vector<int>data1;
vector<int>data2;
};

or use the more traditional approach
with the same index array:

vector<int>indexarray; // <= 0 .. NUMPOINTS-1

struct coordinates { double x,y,z; int data1,data2; };
vector<coordinates>v; // <= 0 .. NUMPOINTS-1

Why did you design a hash algorithm instead
using a std::map<whatever, whatelse> (whats wrong with it?).
What exactly is hashed, what has to be looked up fast?

Regards

Mirco

 

[iu2]

Hello guys,

I really need your help. I'm a Java programmer and right now I'm
experiencing a huge problem with C++.

In a scientific computation I need to store a lot of Point objects
(which have an array of doubles and 2 ints as fields).
To quickly search among all these points I have designed a Hashtable
to store them; a bucket/vector of buckets/vectors.
The hashtable is filled with Points objects in a while loop.

This whole procedure again is repeated a lot of times in a for loop.
At the end of every run of this for loop the Hashtable has to be
emptied in order to prevent for memroy leaks: this means looping
through every vector in the main vector of the hashtable and delete
every Point object manually.
Later on, this C++ computation will be compiled under Matlab to use it
over there.

But now the problem is:

My C++ programm is very fast without emptying the hashtable. But then
I have a huge memory leak; and my swapfile grows enormouly.
With emptying the hashtable my C++ programm becomes dramatically
slow.....even slower than my Java programm.

So the question is: What to do now ?? It cannot be the case that
preventing a memory leak, slows down the computations ??

Kind regards,
Brey

You don't need to write your own hash.
Try using STL. I think an STL 'multiset' can store objects in an RB-
tree fashion. When the multiset goes out of scope it automatically
frees all the memory.
You will need to overload the '<' operator to allow the multiset
comare the nodes in the RB tree.

Here is an example:

#include <set>
#include <iostream>

using namespace std;

// define the Point struct
struct Point {
double ar[10];
int a, b;

Point(int x, int y) {
a = x;
b = y;
}
};

// define the '<' operator, this definition relates to the 'a' field
bool operator < (const Point &p1, const Point &p2) {
return p1.a < p2.a;
}


int main()
{
multiset<Point> points;

// insert some points
for (int i = 0; i < 10; i++) {
cout << "Inserting point with a = " << 10 - i << endl;
points.insert(Point(10 - i, 0));
points.insert(Point(10 - i, 0)); // add each item twice..., just to
see this works
}

cout << endl;

// now scan the set
multiset<Point>::iterator it;
for (it = points.begin(); it != points.end(); it++) {
cout << "Reading point: a = " << it->a << ", b = " << it->b << endl;
}

return 0;
}


The output is:

Inserting point with a = 10
Inserting point with a = 9
Inserting point with a = 8
Inserting point with a = 7
Inserting point with a = 6
Inserting point with a = 5
Inserting point with a = 4
Inserting point with a = 3
Inserting point with a = 2
Inserting point with a = 1

Reading point: a = 1, b = 0
Reading point: a = 1, b = 0
Reading point: a = 2, b = 0
Reading point: a = 2, b = 0
Reading point: a = 3, b = 0
Reading point: a = 3, b = 0
Reading point: a = 4, b = 0
Reading point: a = 4, b = 0
Reading point: a = 5, b = 0
Reading point: a = 5, b = 0
Reading point: a = 6, b = 0
Reading point: a = 6, b = 0
Reading point: a = 7, b = 0
Reading point: a = 7, b = 0
Reading point: a = 8, b = 0
Reading point: a = 8, b = 0
Reading point: a = 9, b = 0
Reading point: a = 9, b = 0
Reading point: a = 10, b = 0
Reading point: a = 10, b = 0

See how the numbers are ordered from least to most, although inserted
from most to least.

 

[Erik Wikström]

Hello guys,

I really need your help. I'm a Java programmer and right now I'm
experiencing a huge problem with C++.

In a scientific computation I need to store a lot of Point objects
(which have an array of doubles and 2 ints as fields).
To quickly search among all these points I have designed a Hashtable
to store them; a bucket/vector of buckets/vectors.
The hashtable is filled with Points objects in a while loop.

This whole procedure again is repeated a lot of times in a for loop.
At the end of every run of this for loop the Hashtable has to be
emptied in order to prevent for memroy leaks: this means looping
through every vector in the main vector of the hashtable and delete
every Point object manually.
Later on, this C++ computation will be compiled under Matlab to use it
over there.

But now the problem is:

My C++ programm is very fast without emptying the hashtable. But then
I have a huge memory leak; and my swapfile grows enormouly.
With emptying the hashtable my C++ programm becomes dramatically
slow.....even slower than my Java programm.

So the question is: What to do now ?? It cannot be the case that
preventing a memory leak, slows down the computations ??

Since you are allocating/deallocating a lot of objects of the same type
a specialised allocator such as a pool allocator might be useful.

You could also put all the point objects in a pre-resized vector and
store pointers to them in the hash-table. This will get rid of the high
number of deallocations since the vector manages the memory for the points.

 

[jl_post]

This whole procedure again is repeated a lot of times in a for loop.
At the end of every run of this for loop the Hashtable has to be
emptied in order to prevent for memroy leaks: this means looping
through every vector in the main vector of the hashtable and delete
every Point object manually.

Dear Brey,

Maybe I misunderstood something in your post, but it sounds like
you are using a vector of vectors of Point pointers (that is,
vector<vector<Point *> >).

If that's the case, why are you using pointers? If you just use
Point objects (as opposed to Point pointers), there would be no need
to free/delete the memory; the vectors and Points would just clean
themselves up when they go out of scope.

I find that a lot of C and Java programmers who move to C++ have a
habit of thinking in pointers; for some reason, they like to allocate
memory and free/delete it even when there's no advantage to doing so.

However, C++ eliminates the need to use pointers in many, many
places. For example, do you need a function to modify a parameter
itself, instead of a copy of the parameter? Use a C++ reference (no
pointer needed). Do you need a variable-length array? Use a
std::vector (again, no pointers needed). Do you need a variable-
length string? Use a std::string. Do you need to create an object
that outlasts its scope? Have the caller function declare it, and
pass it in as a reference.

In my experience about 90% of crashes in C++ programs are due to
pointer errors. Thus, if a programmer were to write pointer-free
code, 9 out 10 potential crashes could be avoided.

But some programmers have a hard time wrapping their heads around
pointer-free code. They can't conceive how it's possible to write
good code without pointers, and will sometimes argue that fact with
someone who can show them that it is in fact possible (I'm speaking
from experience here).

I'm not saying that it's necessarily bad to program with pointers;
what I'm trying to say is that most uses of pointers are unnecessary,
and that by using self-cleaning code (which C++ affords the use of),
programmers can use and manipulate objects without ever having to
worry about memory allocation & deletion. Avoid pointers, and avoid
most crashes and memory leaks.

(Memory allocation and deletion are also rarely ever mentioned in
pseudo-code (probably because it's too environment-specific), so if
you believe that written code should map to well-written pseudo-code
(like I do), it would do you well to avoid malloc/new and free/delete
calls wherever possible.)

I apologize if I misunderstood your post, but I still recommend
avoid using pointers wherever possible.

Have a great day!

-- Jean-Luc

 

[brey_maastricht]

Thank you all for your replys !

Indeed I am using a vector<vector<nDimensionalPoint *> > as Hashtable.
My requirement is to lookup the value of a point of n dimensions very
fast for given coordinates.

I'm going to try an STL Map or Multiset. Maybe that works faster and
more memory efficient.
I have never heard before of a pool allocator but will Google for it.

But when I dont use pointers in my vector of vectors but only
vector<vector<nDimensionalPoint> >, the destructor of the objects
nDimensionalPoint are called, I suppose ?

Best regards !
Brey
The Netherlands

 

[Bo Persson]

Thank you all for your replys !

Indeed I am using a vector<vector<nDimensionalPoint *> > as
Hashtable. My requirement is to lookup the value of a point of n
dimensions very fast for given coordinates.

I'm going to try an STL Map or Multiset. Maybe that works faster and
more memory efficient.
I have never heard before of a pool allocator but will Google for
it.

But when I dont use pointers in my vector of vectors but only
vector<vector<nDimensionalPoint> >, the destructor of the objects
nDimensionalPoint are called, I suppose ?

Yes, but if the objects just contain doubles and ints, the destructor
doesn't have to do anything. Can't be much faster than that!


Bo Persson

 

[brey_maastricht]

Yes, but if the objects just contain doubles and ints, the destructor
doesn't have to do anything. Can't be much faster than that!

Bo Persson

Well, the objects contain 2 values and one array:
its real value, its imaginary value and the coordinates in an integer
array (because the number of coordinates have to be variable, can be 2
dimensional up till 12 dimensional).
So I need a real destructor which delete[] the int array.

 

[jl_post]

Well, the objects contain 2 values and one array:
its real value, its imaginary value and the coordinates in an integer
array (because the number of coordinates have to be variable, can be 2
dimensional up till 12 dimensional).
So I need a real destructor which delete[] the int array.

I think I said this in my previous post, but I'll say it again: If
you ever need to use a variable-length array, just use a vector, like
this:

class nDimensionalPoint
{
public:
double realValue;
double imaginaryValue;
std::vector<int> coordinates;
};

This way there's no need do define a destructor, since there was no
memory allocated!

I hope this helps, Brey.

-- Jean-Luc

 

[jl_post]

But when I dont use pointers in my vector of vectors but only
vector<vector<nDimensionalPoint> >, the destructor of the objects
nDimensionalPoint are called, I suppose ?

Yes. When an object is declared "on the stack" (as opposed to "on
the heap" as pointer memory usually is), its destructor automatically
gets called when the object goes out of scope. Therefore, there is no
need to "garbage collect" it.

Take a look at this class:

class A
{
A() { std::cout << "In A's constructor.\n"; }
~A() { std::cout << "In A's destructor.\n"; }
};

Both of the following lines will call A's constructor:

A a; // calls A::A()
A *aPtr = new A; // also calls A::A()

But when do the destructors get called? Well, for aPtr, it gets
called when you delete() it, like this:

delete(aPtr); // invokes A::~A()

As for the object/variable named "a", its destructor gets called as
soon as it goes out of scope. If you return or break out of the scope
prematurely, its destructor still gets called! In other words, a's
destructor is guaranteed to get called once (and exactly once),
whereas aPtr's destructor gets called only when the "delete(aPtr);"
line is encountered. (If it's never encountered, aPtr's destructor
never gets called, and if it gets encountered more than once, a double-
delete() will happen, likely causing your program to crash.)

So you have to make sure that if you call new() on a pointer to
call delete() on it once and exactly once. But if you just declare it
on the stack (that is, as a non-pointer), you don't have to remember
to call anything for it -- it will clean itself up as soon as it goes
out of scope!

This aspect of C++ (that allows out-of-scope objects to clean
themselves up by calling their destructor) is one of the reasons C++
doesn't have a garbage collector. There is just no need for one if
you write your objects to be self-cleaning. (And you don't need to
define a destructor for a class if all the objects that class are
already self-cleaning.)

In fact, C++'s approach in cleaning objects when they go out of
scope is often much faster than many other languages' approach --
namely, to use a garbage collector that activates only when a system
process decides to.

So my advice is to avoid using pointers as well as calls to malloc/
new and free/delete. Doing so will prevent many memory leaks and
crashes, and in many cases make your code easier to read.

I hope this helps, Brey.

-- Jean-Luc

 

[Juha Nieminen]

I have never heard before of a pool allocator but will Google for it.

One unfortunate side-effect of the C++ memory allocation scheme is
that most allocator implementations tend to be quite slow compared to
many other languages. 'news' and 'deletes' should often be avoided in
C++ not only because of the inherent memory leaking problems, but also
because of efficiency.

That being said, if all the objects you are allocating have the same
size, a pool/block allocator can speed up things considerably. For
example check this one:

http://warp.povusers.org/FSBAllocator/

(That library can even be modified so that if you are going to free
*all* the allocated objects anyways, and those objects do not have
destructors, it could just free them all in a single step so deleting
individual objects in a loop can be skipped completely. This makes
freeing all the objects an extremely fast operation. OTOH it would have
to be done very carefully, ie. you have to make sure that none of the
freed objects aren't referred to anymore anywhere.)

 

[iu2]

Thank you all for your replys !

Indeed I am using a vector<vector<nDimensionalPoint *> > as Hashtable.
My requirement is to lookup the value of a point of n dimensions very
fast for given coordinates.

I'm going to try an STL Map or Multiset. Maybe that works faster and
more memory efficient.
I have never heard before of a pool allocator but will Google for it.

But when I dont use pointers in my vector of vectors but only
vector<vector<nDimensionalPoint> >, the destructor of the objects
nDimensionalPoint are called, I suppose ?

Best regards !
Brey
The Netherlands

If you need looking for a point based on its coordinates, I can tell
you I did exactly the same thing in a project I worked on. I needed a
data structure represeneting a 3d box containing many cells at
different coordinates. Now, a 3d array could be fine if the size of
the box remained constant among different boxes, but it didn't.
So instead of trying dealing with a 3d array of varying dimensions for
each such a box I used a map of the kind:
map<Coord, Cell>
where Coord is a structure containing three coordinates, and Cell
contains all the required data of the cell. I overloaded the '<'
operator to compare between Cord structures, and that was all.
Cells could be removed from the box, and doing that was merely
removing them from the map.
Finding a cell in a given coordinate was as simple as
my_map.find(Cell(10, 0, 5))

The boxes I dealt with contained about 2000 cells, and in the
beginning I was insecure about the speed of that map with all those
cells, and each time we had speed problems I would go to that code and
measure the time the algorithm of removing cells from the box lasted.
Again and again I realized that the time was negligible (10 ms and
less) compared to the entire application cycle (100 ms).
Eventually I stopped measuring it. That was on a PC 1.2 GHz, running
windows.

(but to tell the truth I measured the time of only the data structure
manipulation. Its destruction time wasn't a part of this)

 

[brey_maastricht]

Well,

I forgot to say one thing:

I implemented the Hashtable myself because in every iteration I'm
filling the Hasthable with the same Points (same coordinates) and I am
searching the same Points. Therefore in the first iteration I store
the horizontal and vertical buckets in which the points are found as
ints in a vector. In that way I only have to search in the Hashtable
in the first iteration.
In my own implementation this provides me a speed up.

But because this was something not possible in a Map or Multiset, I
decided to implement it myself.

 

[brey_maastricht]

Well, after some hours of programming I changed my implementation
but.....it is even slower right now !!

What did I do:
1) All the Point objects in my Hashtable now have 4 fields and the
coordinates are now Vectors instead of int* coordinates. Moreover de
destructor is empty now:

using namespace std;
class nDimPoint2
{ public:
vector<int> coordinates;
double valueReal;
double valueImag;
long code;
nDimPoint2();
nDimPoint2(vector<int> _coordinates, double
_valueReal, double _valueImag, int useless);
~nDimPoint2();
};

2) My Hasttable before was structured as:
vector<vector<nDimPoint2*> > myHashTable2;
but now it is a vector<vector<nDimPoint2> > myHashTable2;
There are no NEW or DELETE statements anymore in my programm.

But now my program is even slower than before. Again calling clear()
on all the vectors of the vector of my Hashtable takes a lot of time.
Some timings:

old implementation with clearing the Hashtable: 15 seconds,
old implementation without clearing the Hashtable: 8 seconds (memory
leak!!),
new implementation with clearing the Hashtable: 46 seconds,
new implementation without clearing the Hashtable: 14 seconds (memory
leak!!) for each 1000 iterations.

Horrible ! I'm asking myself why does it get even slowwer now !?!?
I'm was not such a bad programmer before !

I made a profile report of the function calls and timings with my
Visual C++ 6.0 and most of the time is spent in function that are not
mine:

Func Func+Child Hit
Time % Time % Count Function
---------------------------------------------------------
179,137 9,7 179,137 9,7 463149 operator delete(void *)
(delop.obj)
143,360 7,8 143,360 7,8 332055 std::_Allocate(int,int
*) (main.obj)
116,819 6,3 160,788 8,7 821015 std::_Construct(int
*,int const &) (main.obj)
85,135 4,6 144,643 7,9 821015
std::allocator<int>::destroy(int *) (main.obj)
84,776 4,6 245,563 13,3 821015
std::allocator<int>::construct(int *,int const &) (main.obj)
67,266 3,7 67,266 3,7 728284 std::vector<int,class
std::allocator<int> >::size(void) (main.obj)
66,493 3,6 274,364 14,9 477501 std::vector<int,class
std::allocator<int> >::_Ucopy(int const *,int const *,int *)
59,765 3,2 204,408 11,1 471928 std::vector<int,class
std::allocator<int> >::_Destroy(int *,int *) (main.obj)
59,508 3,2 59,508 3,2 821015 std::_Destroy(int *)
(main.obj)
58,582 3,2 413,719 22,5 237988 std::vector<int,class

(class

std::vector<int,class std::allocator<int> > const &) (main.obj)
54,782 3,0 326,831 17,7 144218 std::vector<int,class
std::allocator<int> >::insert(int *,unsigned int,int const &)
48,033 2,6 48,033 2,6 915739 operator new(unsigned
int,void *) (main.obj)
47,647 2,6 47,647 2,6 587227 std::vector<int,class
std::allocator<int> >::begin(void) (main.obj)
42,473 2,3 137,866 7,5 85141 std::vector<int,class

const &) (main.obj)

41,345 2,2 383,897 20,8 144218 std::vector<int,class
std::allocator<int> >::insert(int *,int const &) (main.obj)
38,279 2,1 345,354 18,7 312125 std::vector<int,class
std::allocator<int> >::~vector<int,class std::allocator<int>
37,020 2,0 180,380 9,8 332055
std::allocator<int>::allocate(unsigned int,void const *) (main.obj)
36,508 2,0 36,508 2,0 323129 std::vector<int,class
std::allocator<int> >::end(void) (main.obj)
35,878 1,9 66,832 3,6 284784 std::vector<int,class
std::allocator<int> >:perator[](unsigned int) (main.obj)
28,804 1,6 188,081 10,2 406192
std::allocator<int>::deallocate(void *,unsigned int) (main.obj)
24,556 1,3 24,556 1,3 324357 std::vector<int,class
std::allocator<int> >::begin(void) (main.obj)
21,678 1,2 21,695 1,2 2
std::_Locinfo::_Locinfo(char const *) (locale.obj)
21,069 1,1 58,762 3,2 144218 std::vector<int,class
std::allocator<int> >::_Ufill(int *,unsigned int,int const &)
18,090 1,0 1129,281 61,3 2673

) (main.obj)

17,757 1,0 56,407 3,1 21132

,int) (main.obj)

16,593 0,9 476,780 25,9 15777
hashTable2::searchValueOfPoint(class std::vector<int,class
std::allocator<int> >,int)
15,675 0,9 407,218 22,1 144218 std::vector<int,class
std::allocator<int> >:ush_back(int const &) (main.obj)
13,974 0,8 13,974 0,8 108697 std::vector<class
std::vector<int,class std::allocator<int> >,class
std::allocator<class

std::vector<int,class std::allocator<int> > > >::size(void) (main.obj)
13,728 0,7 13,822 0,8 1 std::num_put<char,class

>::do_put(class

std:streambuf_iterator<char,struct std::char_traits<char> >,class
std::ios_base
&,char,double) (main.obj)
13,401 0,7 13,401 0,7 28674
std::_Allocate(int,class nDimPoint2 *) (main.obj)
etc etc.

I would almost think that the whole design of my implementation is
bad.....
Any suggestions ??

Best regards,
Brey

 

[Bo Persson]

Well, after some hours of programming I changed my implementation
but.....it is even slower right now !!

What did I do:
1) All the Point objects in my Hashtable now have 4 fields and the
coordinates are now Vectors instead of int* coordinates. Moreover de
destructor is empty now:

using namespace std;
class nDimPoint2
{ public:
vector<int> coordinates;
double valueReal;
double valueImag;
long code;
nDimPoint2();
nDimPoint2(vector<int> _coordinates, double
_valueReal, double _valueImag, int useless);

~nDimPoint2();
};

2) My Hasttable before was structured as:
vector<vector<nDimPoint2*> > myHashTable2;
but now it is a vector<vector<nDimPoint2> > myHashTable2;
There are no NEW or DELETE statements anymore in my programm.

But now my program is even slower than before. Again calling clear()
on all the vectors of the vector of my Hashtable takes a lot of
time. Some timings:

old implementation with clearing the Hashtable: 15 seconds,
old implementation without clearing the Hashtable: 8 seconds
(memory leak!!),
new implementation with clearing the Hashtable: 46 seconds,
new implementation without clearing the Hashtable: 14 seconds
(memory leak!!) for each 1000 iterations.

Horrible ! I'm asking myself why does it get even slowwer now !?!?
I'm was not such a bad programmer before !

I made a profile report of the function calls and timings with my
Visual C++ 6.0

Oh dear!

This is a compiler from the previous millennium. Not what I would use
for high performance code.

I would almost think that the whole design of my implementation is
bad.....
Any suggestions ??

http://www.microsoft.com/express/download/



Bo Persson




Bo Persson