Asp Forum - Pool question

a_linux_user

10/12/2008 7:42:00 PM

I am creating a large graph object in which I add nodes whenever I
need them, and I create them by 'new node' individually. I know this
is slow if I am going to allocate thousands of nodes individually. I
want to replace this allocation by an allocation from a pool. One
simple method I can think of is a manual allocation of a large array
of nodes (since I have an estimate of how many nodes there will be),
and use pointers to array elements, and then of course keep track of
used nodes. I think I can do this easily because in my current version
there is no freeing of nodes (until the end, when everything is
freed), so it is manageable without writing a complicated pool
mechanism. But potentially such a simplistic method will be
inadequate. Moreover I am trying to make a transition to C++ from
another language, so I want to know how it is done in C++ style. So I
would like to know if there is some pool facility in the library. I
have seen that there is a Boost pool library but I don't know if it is
the simplest choice.

18 Answers

Kai-Uwe Bux

10/12/2008 8:01:00 PM

a_linux_user wrote:

> I am creating a large graph object in which I add nodes whenever I
> need them, and I create them by 'new node' individually. I know this
> is slow if I am going to allocate thousands of nodes individually. I
> want to replace this allocation by an allocation from a pool. One
> simple method I can think of is a manual allocation of a large array
> of nodes (since I have an estimate of how many nodes there will be),
> and use pointers to array elements, and then of course keep track of
> used nodes. I think I can do this easily because in my current version
> there is no freeing of nodes (until the end, when everything is
> freed), so it is manageable without writing a complicated pool
> mechanism. But potentially such a simplistic method will be
> inadequate. Moreover I am trying to make a transition to C++ from
> another language, so I want to know how it is done in C++ style. So I
> would like to know if there is some pool facility in the library. I
> have seen that there is a Boost pool library but I don't know if it is
> the simplest choice.

First, I would change the code so that is uses an allocator instead of using
new and delete directly. You can test the code using the standard
allocator.

Then I would replace that allocator with a pool allocator. You can check out
various alternatives and also write your own. In the end, you can choose
the fastest.

Best

Kai-Uwe Bux

Adem

10/12/2008 8:20:00 PM

"a_linux_user" <bdthatte@gmail.com> wrote:
>
> I am creating a large graph object in which I add nodes whenever I
> need them, and I create them by 'new node' individually. I know this
> is slow if I am going to allocate thousands of nodes individually. I
> want to replace this allocation by an allocation from a pool. One
> simple method I can think of is a manual allocation of a large array
> of nodes (since I have an estimate of how many nodes there will be),
> and use pointers to array elements, and then of course keep track of
> used nodes. I think I can do this easily because in my current version
> there is no freeing of nodes (until the end, when everything is
> freed), so it is manageable without writing a complicated pool
> mechanism. But potentially such a simplistic method will be
> inadequate. Moreover I am trying to make a transition to C++ from
> another language, so I want to know how it is done in C++ style. So I
> would like to know if there is some pool facility in the library. I
> have seen that there is a Boost pool library but I don't know if it is
> the simplest choice.

Look for "operator new()" in your C++ manual(s) and on the net.
By this mechanism you can have your own allocator.

Juha Nieminen

10/12/2008 8:45:00 PM

Stephen Horne

10/13/2008 4:40:00 AM

On Sun, 12 Oct 2008 12:42:13 -0700 (PDT), a_linux_user
<bdthatte@gmail.com> wrote:

>I am creating a large graph object in which I add nodes whenever I
>need them, and I create them by 'new node' individually. I know this
>is slow if I am going to allocate thousands of nodes individually. I
>want to replace this allocation by an allocation from a pool.

Why not hold all your nodes in an std::vector, and refer to them by
subscript?

I've rarely felt the need for custom allocators. I usually just choose
data structures that don't need single-item allocation.

a_linux_user

10/13/2008 7:50:00 AM

Thanks to all of you who responded. To begin with I am going to look
into using the standard allocator. Trying to read section 19.4 from
Stroustrup, but so far haven't figured how to use it. Later I will try
to post here little pieces of code to get your comments. Thank you
once again.

Juha Nieminen

10/13/2008 4:31:00 PM

a_linux_user wrote:
> Thanks to all of you who responded. To begin with I am going to look
> into using the standard allocator.

I don't really understand what is it that you are going to gain from
that. The standard allocator does 'new' and 'delete' in the way you are
already doing.

Jeff Schwab

10/13/2008 4:45:00 PM

a_linux_user wrote:
> Thanks to all of you who responded. To begin with I am going to look
> into using the standard allocator. Trying to read section 19.4 from
> Stroustrup, but so far haven't figured how to use it. Later I will try
> to post here little pieces of code to get your comments. Thank you
> once again.

That may be an interesting learning exercise, but be forewarned that
standard allocators are not used consistently by different standard
library implementations. They're not anywhere near as useful as they
seem at first, unless you stick with a particular STL implementation.

Furthermore, it is often a waste of time to start optimizing constant
factors before you even have a working program. Since you're working
with graphs, the best places to improve performance (once your program
functions) will probably be in your search and traversal algorithms.
It's hard to optimize without profiling, and it's hard to profile
without working code. Make it right before you worry about making it fast.

My recommendation is to begin with create_node and destroy_node
functions that just use new and delete, and typedef'd pointers that are
either raw (e.g. typedef node* node_pointer; typedef node const*
node_const_pointer;) or reference-counted (e.g. typedef
std::tr1::shared_ptr<node> node_pointer). If you really find that new
and delete are your performance bottleneck down the road, you can always
replace the use of new and delete with something fancier, without
breaking the syntax used in the rest of your program.

a_linux_user

10/13/2008 8:20:00 PM

On Oct 13, 5:30 pm, Juha Nieminen <nos...@thanks.invalid> wrote:
> a_linux_user wrote:
> > Thanks to all of you who responded. To begin with I am going to look
> > into using the standard allocator.
>
> I don't really understand what is it that you are going to gain from
> that. The standard allocator does 'new' and 'delete' in the way you are
> already doing.

Thanks for pointing this out. I didn't realize that. I was always
under the impression that doing 'new' for each node was somehow bad.

Stephen Horne

10/14/2008 3:20:00 AM

On Mon, 13 Oct 2008 13:20:09 -0700 (PDT), a_linux_user
<bdthatte@gmail.com> wrote:

>On Oct 13, 5:30 pm, Juha Nieminen <nos...@thanks.invalid> wrote:
>> a_linux_user wrote:
>> > Thanks to all of you who responded. To begin with I am going to look
>> > into using the standard allocator.
>>
>> I don't really understand what is it that you are going to gain from
>> that. The standard allocator does 'new' and 'delete' in the way you are
>> already doing.
>
>Thanks for pointing this out. I didn't realize that. I was always
>under the impression that doing 'new' for each node was somehow bad.

I think this is a language issue.

You need to look up custom allocators. The standard allocator *is* bad
(for some requirements), which is why it can be overridden using
custom allocators.

Both standard and custom allocators are accessed through the new
operator. This is because the new operator is responsible for calling
the constructor - not just allocating the memory.

Containers have defaulted template parameters that give a kind of
allocation policy ("policy" being a kind of template design pattern) -
it may be more appropriate to target this than the new operator.

Stephen Horne

10/14/2008 3:30:00 AM

On Mon, 13 Oct 2008 12:45:12 -0400, Jeff Schwab
<jeff@schwabcenter.com> wrote:

>Furthermore, it is often a waste of time to start optimizing constant
>factors before you even have a working program.

Very good point. Another reason for it is that you can end up
overcommitted to poor algorithm/data structure choices simply because
you've put so much time into developing and optimising them. A
variation on the KISS principle, basically.

comp.lang.c++

Pool question

a_linux_user

Kai-Uwe Bux

Adem

Juha Nieminen

Stephen Horne

a_linux_user

Juha Nieminen

Jeff Schwab

a_linux_user

Stephen Horne

Stephen Horne

x Login to ForumsZone