new/delete vs. vector implementing n-ary tree

Discussion in 'C++' started by nandor.sieben@gmail.com, Apr 14, 2008.

  1. Guest

    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?
    , Apr 14, 2008
    #1
    1. Advertising

  2. Kai-Uwe Bux Guest

    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...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
    Kai-Uwe Bux, Apr 14, 2008
    #2
    1. Advertising

  3. Guest

    > 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.
    , Apr 14, 2008
    #3
  4. Ian Collins Guest

    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.
    Ian Collins, Apr 14, 2008
    #4
  5. Bo Persson Guest

    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
    Bo Persson, Apr 14, 2008
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Wynan James

    Depth of n-ary tree

    Wynan James, Sep 29, 2003, in forum: Java
    Replies:
    10
    Views:
    11,147
    Stefan Poehn
    Sep 30, 2003
  2. Stevey

    N-ary tree code?

    Stevey, Apr 9, 2005, in forum: Java
    Replies:
    1
    Views:
    3,730
    Abhijat Vatsyayan
    Apr 10, 2005
  3. n-ary tree

    , Oct 22, 2006, in forum: C++
    Replies:
    1
    Views:
    971
    Daniel T.
    Oct 22, 2006
  4. Guilfoy9898

    M-ary Tree

    Guilfoy9898, Jul 25, 2008, in forum: C Programming
    Replies:
    0
    Views:
    426
    Guilfoy9898
    Jul 25, 2008
  5. cgirl
    Replies:
    1
    Views:
    336
    red floyd
    Jun 26, 2009
Loading...

Share This Page