By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,144 Members | 1,250 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,144 IT Pros & Developers. It's quick & easy.

Pool question

P: n/a
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.
Oct 12 '08 #1
Share this Question
Share on Google+
17 Replies


P: n/a
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
Oct 12 '08 #2

P: n/a
"a_linux_user" <bd******@gmail.comwrote:
>
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.

Oct 12 '08 #3

P: n/a
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.
If all the nodes have the same size, you can use this:

http://warp.povusers.org/FSBAllocator/
Oct 12 '08 #4

P: n/a
On Sun, 12 Oct 2008 12:42:13 -0700 (PDT), a_linux_user
<bd******@gmail.comwrote:
>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.

Oct 13 '08 #5

P: n/a
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.
Oct 13 '08 #6

P: n/a
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.
Oct 13 '08 #7

P: n/a
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<nodenode_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.
Oct 13 '08 #8

P: n/a
On Oct 13, 5:30*pm, Juha Nieminen <nos...@thanks.invalidwrote:
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.
Oct 13 '08 #9

P: n/a
On Mon, 13 Oct 2008 13:20:09 -0700 (PDT), a_linux_user
<bd******@gmail.comwrote:
>On Oct 13, 5:30*pm, Juha Nieminen <nos...@thanks.invalidwrote:
>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.

Oct 14 '08 #10

P: n/a
On Mon, 13 Oct 2008 12:45:12 -0400, Jeff Schwab
<je**@schwabcenter.comwrote:
>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.

Oct 14 '08 #11

P: n/a
On Tue, 14 Oct 2008 04:20:20 +0100, Stephen Horne
<sh********@blueyonder.co.ukwrote:
>I think this is a language issue.
That wasn't clear - I meant English language rather than C++. I got
the impression that a_linux_user was getting a tad confused.

Oct 14 '08 #12

P: n/a
On Oct 13, 10:20 pm, a_linux_user <bdtha...@gmail.comwrote:
On Oct 13, 5:30 pm, Juha Nieminen <nos...@thanks.invalidwrote:
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.
The standard allocators are required to use the global operator
new() and operator delete() functions to acquire memory. They
do NOT use new or delete expressions, however, as they are
required to separate allocation an initialization.
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.
What's wrong with it? It's the obvious solution, and is only
"bad" if it causes the program to fail to meet some requirement.

Also, the standard requires the standard allocator to use
::operator new() and ::operator delete() to acquire and free
memory. However, it also explicitly states that "it is
unspecified when or how often this function [::operator new()]
is called."

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Oct 14 '08 #13

P: n/a
James Kanze wrote:
What's wrong with it? It's the obvious solution, and is only
"bad" if it causes the program to fail to meet some requirement.
In many systems with many compilers the default allocator can be quite
slow in some situations (for example when allocating and freeing
enormous amounts of small objects). Using a faster allocator can speed
up the allocation by a large factor. If your program is very allocation
(and deallocation) heavy, your entire program can speed up by a large
factor.

(The most common solution to this problem is to use large arrays
rather than allocating each object individually, as arrays do not suffer
from the speed issues of 'new' and 'delete'. However, arrays cannot
always be used in every possible such situation.)
Oct 14 '08 #14

P: n/a
On 14 Oct, 13:05, Juha Nieminen <nos...@thanks.invalidwrote:
James Kanze wrote:
What's wrong with it? It's the obvious solution, and is only
"bad" if it causes the program to fail to meet some requirement.

In many systems with many compilers the default allocator can be quite
slow in some situations (for example when allocating and freeing
enormous amounts of small objects). Using a faster allocator can speed
up the allocation by a large factor. If your program is very allocation
(and deallocation) heavy, your entire program can speed up by a large
factor.

(The most common solution to this problem is to use large arrays
rather than allocating each object individually, as arrays do not suffer
from the speed issues of 'new' and 'delete'. However, arrays cannot
always be used in every possible such situation.)
I tested two versions:
1. new and delete a node structure a billion times (took about 52
seconds)
2. calloc an array of million nodes, set the id of each node, then
free the array (and repeat this 1000 times) (took 22 seconds)
so clearly the second alternative does run much faster, but in my
graph program, where I allocate only 10 million nodes, this is not a
significant difference given that I am doing other computations (35
seconds vs 28 seconds).
This is what I expected, and that is what I wanted to ask about in the
first post. But I have to do a bit learning about various allocation
mechanisms available in C++ to fully understand all comments that have
been made above, and I want to thank you all.
Oct 14 '08 #15

P: n/a
On Oct 14, 2:05*pm, Juha Nieminen <nos...@thanks.invalidwrote:
James Kanze wrote:
What's wrong with it? *It's the obvious solution, and is only
"bad" if it causes the program to fail to meet some requirement.
In many systems with many compilers the default allocator can
be quite slow in some situations (for example when allocating
and freeing enormous amounts of small objects).
I know that used to be the case (over ten years ago), but I've
not found it to be true recently. Most implementations of
operator new just call malloc, and most modern implementations
of malloc have special optimizations for small allocations,
handling them basically just as you would in your custom
allocator which chopped the big block.
Using a faster allocator can speed up the allocation by a
large factor. If your program is very allocation (and
deallocation) heavy, your entire program can speed up by a
large factor.
Been there, done that. It's only relevant IF you have a
performance problem. And even then, you might consider just
replacing ::operator new and ::operator delete with something
more intelligent.
(The most common solution to this problem is to use large
arrays rather than allocating each object individually, as
arrays do not suffer from the speed issues of 'new' and
'delete'. However, arrays cannot always be used in every
possible such situation.)
That's typically what the standard allocator will do, on
platforms where there is a problem. As I said, however, I've
not found it to be a problem on modern systems---the last time I
had to tune allocation was something like 15 years ago.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Oct 14 '08 #16

P: n/a
On Oct 14, 7:16*pm, a_linux_user <bdtha...@gmail.comwrote:
On 14 Oct, 13:05, Juha Nieminen <nos...@thanks.invalidwrote:
I tested two versions:
1. new and delete a node structure a billion times (took about 52
seconds)
2. calloc an array of million nodes, set the id of each node, then
free the array (and repeat this 1000 times) (took 22 seconds)
so clearly the second alternative does run much faster, but in my
graph program, where I allocate only 10 million nodes, this is not a
significant difference given that I am doing other computations (35
seconds vs 28 seconds).
A custom fixed length allocator would have to do a little bit
more than that (since you have to consider the case where some
of the elements are freed and then have to be reused). It's
possible to get it down to less than about ten machine
instructions. Which is two or three less than a well written
standard allocator would need; the typical difference shouldn't
be more than about 25%, however. Of the time spent strictly
allocating. If you're spending less than 90% of your time in
the allocator, then it's definitely not worth it. (I have had
code where the profiler showed 99.98% of the time in the
allocator. In that particular case, the solution was to
allocate a lot less, however, not to optimize the allocator.)

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Oct 14 '08 #17

P: n/a
On Wed, 15 Oct 2008 14:48:12 GMT, Juha Nieminen
<no****@thanks.invalidwrote:
An allocator which is able to optimize the list of free memory blocks
in such way that it's able to traverse it linearly in memory can be much
faster than the default allocator, even if it has to do much more work
(in terms of machine code) to keep the list optimized.
Yes, but I tend to deal with that issue other ways.

The standard library associative containers are binary trees, which
can be problematic. Multiway trees were designed to be far better in
terms of locality from the start.

There are overheads in terms of item copying on inserts, deletes, node
splits etc - but the locality advantage normally outweighs that.
Particularly for sequential access, since the trees I use are more B+
tree than B tree, so a sequential traversal is just a
linked-list-of-small-arrays traversal.

Using a different kind of container means that custom allocators are
much less of an issues - though obviously they're not suitable for
everything.

Oct 16 '08 #18

This discussion thread is closed

Replies have been disabled for this discussion.