470,588 Members | 2,188 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

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

new/delete vs. vector implementing n-ary tree

I am using a small set of functions that implements an n-ary tree. The
library is disscusses here:

http://groups.google.com/group/comp....274ef3f22fdb90

The nodes of the tree are cretaed and erased by new and delete. I just
read in Modern C++ Design that new/delete can be very inefficient. I
am using this library to search in game trees so I do create and erase
a lot of nodes. Would I be better of by creating a large vector
containing nodes and use this vector to store my tree nodes. Instead
of pointers I could use indices. The unused nodes would be linked
together for easy access and used only when a new node is needed. This
would avoid the use of new/delete. The only drawback is that the
memory is allocated even when it's not used, but this is not really an
issue for my application.

Should I expect a significant gain in performance from this?
Jun 27 '08 #1
5 3005
na***********@gmail.com wrote:
I am using a small set of functions that implements an n-ary tree. The
library is disscusses here:

http://groups.google.com/group/comp....274ef3f22fdb90
>
The nodes of the tree are cretaed and erased by new and delete. I just
read in Modern C++ Design that new/delete can be very inefficient. I
am using this library to search in game trees so I do create and erase
a lot of nodes. Would I be better of by creating a large vector
containing nodes and use this vector to store my tree nodes. Instead
of pointers I could use indices. The unused nodes would be linked
together for easy access and used only when a new node is needed. This
would avoid the use of new/delete.
This amounts essentially to implementing your own dynamic memory management
scheme. You should be able to achieve very similar effects my overloading
new and delete for your node class so that a pooled allocation scheme is
used transparently in the background.
The only drawback is that the
memory is allocated even when it's not used, but this is not really an
issue for my application.

Should I expect a significant gain in performance from this?
You will have to try. Adjusting the memory allocation scheme used for
certain classes can yield significant performance gains. Whether it will do
so in a particular case can only be decided by testing.
Best

Kai-Uwe Bux
Jun 27 '08 #2
On Sun, 13 Apr 2008 16:47:32 -0700 (PDT), na***********@gmail.com
wrote:
>The nodes of the tree are cretaed and erased by new and delete
My gosh! What an abomination. Haven't you heard that a C++ program
never use the keyword "new" and "delete"?
Jun 27 '08 #3
My gosh! What an abomination. Haven't you heard that a C++ program
never use the keyword "new" and "delete"?
I do feel a certain amount of shame but what can I do. There is no
ntree<Tcontainer in the STL so I need to write my own. I am sure
someone more familiar with the insights of the STL allocators could do
a much better job. I am trying to do my best, that is why I am asking
what the best way is to do the allocation.
Jun 27 '08 #4
na***********@gmail.com wrote:
>My gosh! What an abomination. Haven't you heard that a C++ program
never use the keyword "new" and "delete"?

I do feel a certain amount of shame but what can I do. There is no
ntree<Tcontainer in the STL so I need to write my own. I am sure
someone more familiar with the insights of the STL allocators could do
a much better job. I am trying to do my best, that is why I am asking
what the best way is to do the allocation.
The overloaded new and delete for your Node class as suggested by
Kai-Uwe Bux is probably your best option. You can experiment until you
get acceptable performance for your application. Start by just calling
global new and delete from your overloads as a baseline.

You should also learn to ignore plonkers on Usenet :)

--
Ian Collins.
Jun 27 '08 #5
na***********@gmail.com wrote:
>My gosh! What an abomination. Haven't you heard that a C++ program
never use the keyword "new" and "delete"?

I do feel a certain amount of shame but what can I do. There is no
ntree<Tcontainer in the STL so I need to write my own. I am sure
someone more familiar with the insights of the STL allocators could
do a much better job. I am trying to do my best, that is why I am
asking what the best way is to do the allocation.
No, that's just a joke from another thread.

There Razii amuses himself by calling new 10 million, or 100 million,
times in a row. When that doesn't run fast enough, he has just
'proven' that Java code is always faster than C++. Don't bother.

There is a this line between 'never used' and 'rarely used'.
Bo Persson
Jun 27 '08 #6

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

4 posts views Thread by Dmitri Zhukov | last post: by
9 posts views Thread by Gunnar G | last post: by
16 posts views Thread by cppaddict | last post: by
2 posts views Thread by Stijn Oude Brunink | last post: by
9 posts views Thread by david wolf | last post: by
35 posts views Thread by Jon Slaughter | last post: by
10 posts views Thread by ypjofficial | last post: by
7 posts views Thread by JH Programmer | last post: by
13 posts views Thread by Tristan Wibberley | last post: by
19 posts views Thread by Daniel Pitts | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.