new/delete vs. vector implementing n-ary tree

[nandor.sieben]

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...ef3f22fdb90?lnk=gst&q=sieben#8d274ef3f22fdb90

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?

 

[Kai-Uwe Bux]

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...ef3f22fdb90?lnk=gst&q=sieben#8d274ef3f22fdb90

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

 

[nandor.sieben]

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.

 

[Ian Collins]

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

 

[Bo Persson]

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