470,849 Members | 1,187 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,849 developers. It's quick & easy.

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

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

Jun 27 '08 #1
11 1581
br*************@hotmail.com wrote:
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
Jun 27 '08 #2
On 17 jun, 22:45, "Bo Persson" <b...@gmb.dkwrote:
brey_maastri...@hotmail.com wrote:
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
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.
Jun 27 '08 #3
On Jun 17, 3:18 pm, brey_maastri...@hotmail.com wrote:
>
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<intcoordinates;
};

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

I hope this helps, Brey.

-- Jean-Luc

Jun 27 '08 #4
On Jun 17, 2:30 pm, brey_maastri...@hotmail.com wrote:
>
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
Jun 27 '08 #5
Sam
br*************@hotmail.com writes:

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.
And the reason you to manually babysit this array's allocation/deallocation,
instead of making it a std::vector, is?

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEABECAAYFAkhYOn4ACgkQx9p3GYHlUOKY0ACfZ3ldJf/RARRhfXLrjU6ei8SQ
CQUAmQE3ZZ73O79JMHjToPGbJwb+rYOl
=Ryqm
-----END PGP SIGNATURE-----

Jun 27 '08 #6
br*************@hotmail.com wrote:
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.)
Jun 27 '08 #7
iu2
On Jun 17, 11:30*pm, brey_maastri...@hotmail.com wrote:
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)
Jun 27 '08 #8
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.

Jun 27 '08 #9
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<intcoordinates;
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
std::allocator<int::vector<int,class std::allocator<int>
>(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
std::allocator<int::operator=(class std::vector<int,class
std::allocator<int>
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::operator[](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
ndSystem2::trackPoint(class std::vector<int,class std::allocator<int>
>) (main.obj)
17,757 1,0 56,407 3,1 21132
hashTable2::codeer(class std::vector<int,class std::allocator<int>
>,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::push_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
std::ostreambuf_iterator<char,struct std::char_traits<char
>::do_put(class
std::ostreambuf_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
Jun 27 '08 #10
br*************@hotmail.com wrote:
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<intcoordinates;
double valueReal;
double valueImag;
long code;
nDimPoint2();
nDimPoint2(vector<int_coordinates, double
_valueReal, double _valueImag, int useless);
This is passing a vector<intby value. That is very unusual.
~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
Jun 27 '08 #11
br*************@hotmail.com kirjutas:
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<intcoordinates;
double valueReal;
double valueImag;
long code;
Public data!? Why?
nDimPoint2();
nDimPoint2(vector<int_coordinates, double
_valueReal, double _valueImag, int useless);
The vector should most probably be passed by reference. If you don't need
the initial vector and it is used for initialization only, you can pass
by non-const reference and swap the contents away:

nDimPoint2(vector<int>& _coordinates, double _valueReal,
double valueImag, int useless)
: valueReal(_valueReal), valueImag(_valueImag) {

coordinates.swap(_coordinates);
code = ...
}

If you write such things, then I dare to ask if you are sure you are
actually building and testing the optimized build?

Best regards
Paavo
Jun 27 '08 #12

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

6 posts views Thread by Ganesh | last post: by
11 posts views Thread by Rick | last post: by
34 posts views Thread by Ville Voipio | last post: by
5 posts views Thread by Bob lazarchik | last post: by
8 posts views Thread by mike2036 | last post: by
56 posts views Thread by Johnny E. Jensen | last post: by
reply views Thread by Mirco Wahab | last post: by
158 posts views Thread by pushpakulkar | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.