Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > new/delete vs. vector implementing n-ary tree

Reply
Thread Tools

new/delete vs. vector implementing n-ary tree

 
 
nandor.sieben@gmail.com
Guest
Posts: n/a
 
      04-13-2008
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?
 
Reply With Quote
 
 
 
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      04-14-2008
http://www.velocityreviews.com/forums/(E-Mail Removed) 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
 
Reply With Quote
 
 
 
 
nandor.sieben@gmail.com
Guest
Posts: n/a
 
      04-14-2008
> 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<T> container 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.
 
Reply With Quote
 
Ian Collins
Guest
Posts: n/a
 
      04-14-2008
(E-Mail Removed) 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<T> container 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.
 
Reply With Quote
 
Bo Persson
Guest
Posts: n/a
 
      04-14-2008
(E-Mail Removed) 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<T> container 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


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
const vector<A> vs vector<const A> vs const vector<const A> Javier C++ 2 09-04-2007 08:46 PM
Initializing vector<vector<int> > and other vector questions... pmatos C++ 6 04-26-2007 05:39 PM
Free memory allocate by a STL vector, vector of vector, map of vector Allerdyce.John@gmail.com C++ 8 02-18-2006 12:48 AM
how the vector is created, how to pass vector to webservices method apachesoap:Vector Rushikesh Joshi Perl Misc 0 07-10-2004 01:04 PM
B tree, B+ tree and B* tree Stub C Programming 3 11-12-2003 01:51 PM



Advertisments