Discussion:
Node free lists for STL containers
(too old to reply)
Scott Meyers
2003-11-06 16:44:52 UTC
Permalink
For the node-based containers, one thing has always nagged at the back of
my mind. To increase the performance of node allocation, one can keep a
free list of nodes that have been freed. But who keeps this free list, the
container or the allocator? The allocator seems like the logical place to
do it, but I can also imagine a container doing it. I've never bothered to
check STL implementations to see if any containers keep their own node free
lists, but I'm thinking that somebody reading this probably has. Is there
any reason why a container *can't* keep its own free list of nodes? Does
anybody know of any container implementation that actually does?

All enlightenment appreciated,

Scott


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Christophe Lephay
2003-11-07 14:23:13 UTC
Permalink
Post by Scott Meyers
For the node-based containers, one thing has always nagged at the
back of my mind. To increase the performance of node allocation, one
can keep a free list of nodes that have been freed. But who keeps
this free list, the container or the allocator? The allocator seems
like the logical place to do it, but I can also imagine a container
doing it. I've never bothered to check STL implementations to see if
any containers keep their own node free lists, but I'm thinking that
somebody reading this probably has. Is there any reason why a
container *can't* keep its own free list of nodes? Does anybody know
of any container implementation that actually does?
Isn't the allocator expected to be called each time a new node is created ?
If not, it would act like the "finally" in garbage collectors. I suggest
such an allocator be named "firstly" because, in the same way that you
cannot expect the "finally" code in GC to be finally called, you could not
assume the "firstly" code would be firstly called ;)

I also think that allocators offer more flexibility, particulary if it
happens, one day, that some other resource than just memory is required...

(i don't know if my two cents are relevant because i am far from being an
expert in anything)

Chris



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Raoul Gough
2003-11-07 14:28:51 UTC
Permalink
Post by Scott Meyers
For the node-based containers, one thing has always nagged at the
back of my mind. To increase the performance of node allocation,
one can keep a free list of nodes that have been freed. But who
keeps this free list, the container or the allocator? The allocator
seems like the logical place to do it, but I can also imagine a
container doing it. I've never bothered to check STL
implementations to see if any containers keep their own node free
lists, but I'm thinking that somebody reading this probably has. Is
there any reason why a container *can't* keep its own free list of
nodes? Does anybody know of any container implementation that
actually does?
All enlightenment appreciated,
I once implemented an allocator to hold a per-container-object free
list, in an attempt to gain some multi-threaded performance.
Unfortunately, it turned out to be quite tricky to guarantee a
one-to-one relationship between a container object and the allocator
object it uses. Most of the details can be seen in the thread:

http://groups.google.com/groups?th=e81a3a213042eed6

Around about message 6 in the thread is where the main difficulties
emerge. It would certainly be easier for the container to handle this
(somewhat specialized) case for itself, but I guess that would subvert
the idea of having an allocator parameter in the first place.

Ultimately though, the performance gains from my allocator were
swamped by other overheads, so I never pursued it beyond the prototype
stage.
--
Raoul Gough.
(setq dabbrev-case-fold-search nil)

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
R.F. Pels
2003-11-07 14:31:39 UTC
Permalink
Post by Scott Meyers
For the node-based containers, one thing has always nagged at the back of
my mind. To increase the performance of node allocation, one can keep a
free list of nodes that have been freed. But who keeps this free list,
the container or the allocator? The allocator seems like the logical
place to do it, but I can also imagine a container doing it. I've never
bothered to check STL implementations to see if any containers keep their
own node free lists, but I'm thinking that somebody reading this probably
has. Is there any reason why a container *can't* keep its own free list
of nodes? Does anybody know of any container implementation that actually
does?
This is my take on it. If there is a free list, that would be implementation
specific, so, nothing of it would show in the interface of either the list
or the allocator. The next thing I would ask myself is which of the two
would need to know the concept of a free list the most. The answer to that
question would IMHO be the list, for the following (partly overlapping)
reasons:

1. list already knows the concept list so it's the most apt at freelist
maintenance
2. allocator does not need list to perform its function
3. allocator would be 'poisoned' by adding the concept list to it to make
it possible for allocator to maintain a free list.
4. allocator's business is allocating memory, not maintaining free lists.
5. free lists are only relevant in the context of lists.

And there is one last thing to mention. On a more technical level, most C++
runtime libraries use a suballocator for allocating objects smaller than
the size of a memory page. Most if not all maintain one or more list of
free memory blocks. Yes, from a certain standpoint the free list
maintenance in memory suballocators is less efficient, however, letting
list maintain it's own free list might make your program less efficient
because there are two types of memory management.
--
Ruurd


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Balog Pal
2003-11-10 09:39:31 UTC
Permalink
Post by R.F. Pels
Yes, from a certain standpoint the free list
maintenance in memory suballocators is less efficient, however, letting
list maintain it's own free list might make your program less efficient
because there are two types of memory management.
Less efficient maybe in terms of memory usage [by holding some meory in that
free list instead of giving it back to the system for generic use] , but
definitely more efficient in execution time.

Note that a list always allocate the same size of elements -- and its free
list will hold only such, exact-matching blocks. There's never a search
operation, you grab the first (or last) element of the free list blindly
when allocation is needed, and free operation has nothing excelt appending
the block to the list.

General memory allocators will likely search a big enough block, and split
it, if a alrge enough one is found. Suballocators may handle some particular
sizes -- may have luck for list of ints or pointers to hit a searchless
allocator -- but it's cluck, nothing else.

Paul






[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Bo Persson
2003-11-10 19:59:17 UTC
Permalink
Post by Balog Pal
Post by R.F. Pels
Yes, from a certain standpoint the free list
maintenance in memory suballocators is less efficient, however, letting
list maintain it's own free list might make your program less efficient
because there are two types of memory management.
Less efficient maybe in terms of memory usage [by holding some meory in that
free list instead of giving it back to the system for generic use] , but
definitely more efficient in execution time.
Note that a list always allocate the same size of elements -- and its free
list will hold only such, exact-matching blocks. There's never a search
operation, you grab the first (or last) element of the free list blindly
when allocation is needed, and free operation has nothing excelt appending
the block to the list.
This is already implemented in some popular operating systems. Please
have a look at:

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/memory/base/low_fragmentation_heap.asp



Bo Persson


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Balog Pal
2003-11-07 14:35:19 UTC
Permalink
Post by Scott Meyers
For the node-based containers, one thing has always nagged at the back of
my mind. To increase the performance of node allocation, one can keep a
free list of nodes that have been freed. But who keeps this free list, the
container or the allocator? The allocator seems like the logical place to
do it, but I can also imagine a container doing it. I've never bothered to
check STL implementations to see if any containers keep their own node free
lists, but I'm thinking that somebody reading this probably has. Is there
any reason why a container *can't* keep its own free list of nodes? Does
anybody know of any container implementation that actually does?
It's not STL but may be still interesting.

Visual C's MFC has a CList class, it uses a CPlex class to manage the memory
and nodes. It's practically allocates a bunch of Nodes in one gulp
(default is 10, you can set that number in ctor). Node has the next and
prev pointer and sizeof(ARG) bytes to hold an actual element. Whenever a new
Plex set up as a list and serves as the free list. If a node is destroyed,
it's linked to the free list, and allocations grab the first node on the
free list, (allocating a new Plex if it's empty).

Allocated Plex blocks are released only when the list is destroyed, and when
it gets down to empty.

It is pretty good performance-wise. And has the drawback I can't detach a
Node from the list and attach to another list -- as memory for a Plex is
tied to an instance of a CList.

At a time I was thinking to separate the plex management from the instance
to make nodes tradeable, but then I'd have to face the release problem. As
the global management is not likely to ever empty. And check blocks when
one has all freed nodes -- or make nodes really single -- made me better
stick with what I have.

Paul



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Siemel Naran
2003-11-08 00:21:38 UTC
Permalink
Post by Scott Meyers
For the node-based containers, one thing has always nagged at the back of
my mind. To increase the performance of node allocation, one can keep a
free list of nodes that have been freed. But who keeps this free list, the
container or the allocator? The allocator seems like the logical place to
do it, but I can also imagine a container doing it. I've never bothered to
check STL implementations to see if any containers keep their own node free
lists, but I'm thinking that somebody reading this probably has. Is there
any reason why a container *can't* keep its own free list of nodes? Does
anybody know of any container implementation that actually does?
How would a container keep its list of free nodes? What kind of allocator
would we have to write?

--
+++++++++++
Siemel Naran


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Christophe Lephay
2003-11-08 13:54:14 UTC
Permalink
Post by Siemel Naran
Post by Scott Meyers
For the node-based containers, one thing has always nagged at the
back of my mind. To increase the performance of node allocation,
one can keep a free list of nodes that have been freed. But who
keeps this free list, the container or the allocator? The allocator
seems like the logical place to do it, but I can also imagine a
container doing it. I've never bothered to check STL
implementations to see if any containers keep their own node free
lists, but I'm thinking that somebody reading this probably has. Is
there any reason why a container *can't* keep its own free list of
nodes? Does anybody know of any container implementation that
actually does?
How would a container keep its list of free nodes? What kind of
allocator would we have to write?
An allocator can for sure keep track of what was previously allocated.
Keeping track of what was "desallocated" (logically speaking, because the
memory could remains) would certainly need the help of the container, like,
for instance, a "desallocator" being called each time a node is destroyed...

Chris



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Siemel Naran
2003-11-09 11:48:22 UTC
Permalink
Post by Christophe Lephay
Post by Siemel Naran
How would a container keep its list of free nodes? What kind of
allocator would we have to write?
An allocator can for sure keep track of what was previously allocated.
Keeping track of what was "desallocated" (logically speaking, because the
memory could remains) would certainly need the help of the container, like,
for instance, a "desallocator" being called each time a node is destroyed...
To get memory the container calls alloc.allocate(size_type, void*) which
returns a T*. To release memory it calls alloc.deallocate(T*, size_type).
If the custom allocator provides both methods, then can't it keep track of
both allocations and deallocations? Is this right?

Though I also read on this newsgroup (or maybe it was comp.std.c++ or
comp.lang.c++) that allocators with state cause trouble. Is that because of
what to do when we copy the container?

--
+++++++++++
Siemel Naran


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Pete Becker
2003-11-09 22:53:49 UTC
Permalink
Post by Siemel Naran
Though I also read on this newsgroup (or maybe it was comp.std.c++ or
comp.lang.c++) that allocators with state cause trouble. Is that because of
what to do when we copy the container?
It's because the standard says that containers are allowed to assume
that allocators of the same type always compare equal. That, in turn,
means that allocators with state won't work sensibly if the library
writer took advantage of this leeway. Our library doesn't make this
assumption.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Raoul Gough
2003-11-10 19:26:16 UTC
Permalink
Post by Pete Becker
Post by Siemel Naran
Though I also read on this newsgroup (or maybe it was comp.std.c++ or
comp.lang.c++) that allocators with state cause trouble. Is that because of
what to do when we copy the container?
It's because the standard says that containers are allowed to assume
that allocators of the same type always compare equal. That, in turn,
means that allocators with state won't work sensibly if the library
writer took advantage of this leeway. Our library doesn't make this
assumption.
There's also the complication of having to support rebind and
construction from an object of corresponding type. Consider a list
with a stateful allocator:

std::list<int, my_allocator<int> > my_list (my_allocator<int>());

Importantly, std::list doesn't (just) allocate objects of type
int. Most likely it only allocates objects of another type, let's say
list_node<int>, which it would do via

my_allocator<int>::rebind<list_node<int> >::other
node_alloc (copy_of_list_constructor_argument);

So the my_allocator<int> object that you pass into the list
constructor is not the object that gets used for the allocations. It
probably isn't even of the same type as the allocator used for
allocations. This means that a stateful allocator has to be able to
communicate its state between allocators for different object
sizes. AFAIK, the container is free to use multiple different rebinds
of your allocator, and could then use multiple objects of those types,
so a stateful allocator's job is not as easy as one would hope.
--
Raoul Gough.
(setq dabbrev-case-fold-search nil)

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Pete Becker
2003-11-11 16:46:39 UTC
Permalink
Post by Raoul Gough
Post by Pete Becker
Post by Siemel Naran
Though I also read on this newsgroup (or maybe it was comp.std.c++ or
comp.lang.c++) that allocators with state cause trouble. Is that because of
what to do when we copy the container?
It's because the standard says that containers are allowed to assume
that allocators of the same type always compare equal. That, in turn,
means that allocators with state won't work sensibly if the library
writer took advantage of this leeway. Our library doesn't make this
assumption.
There's also the complication of having to support rebind and
construction from an object of corresponding type.
Well, sure, but I don't regard that as "causing" trouble. It's just the
trouble you have to go through to write them.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Pete Becker
2003-11-11 22:45:36 UTC
Permalink
Post by Pete Becker
Post by Raoul Gough
Post by Pete Becker
Post by Siemel Naran
Though I also read on this newsgroup (or maybe it was comp.std.c++ or
comp.lang.c++) that allocators with state cause trouble. Is that because of
what to do when we copy the container?
It's because the standard says that containers are allowed to assume
that allocators of the same type always compare equal. That, in turn,
means that allocators with state won't work sensibly if the library
writer took advantage of this leeway. Our library doesn't make this
assumption.
There's also the complication of having to support rebind and
construction from an object of corresponding type.
Well, sure, but I don't regard that as "causing" trouble. It's just the
trouble you have to go through to write them.
I should add that that's the trouble you have to go through if you want
something that elaborate. Most "stateful" allocators are much simpler:
they maintain a free list for their size, so you don't worry about
copying state across a rebind. And a sensible container will create one
allocator for each required size, so there's no issue of copying free
lists around.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Siemel Naran
2003-11-12 19:50:27 UTC
Permalink
Post by Pete Becker
Post by Pete Becker
Post by Raoul Gough
There's also the complication of having to support rebind and
construction from an object of corresponding type.
Well, sure, but I don't regard that as "causing" trouble. It's just the
trouble you have to go through to write them.
I should add that that's the trouble you have to go through if you want
they maintain a free list for their size, so you don't worry about
copying state across a rebind. And a sensible container will create one
allocator for each required size, so there's no issue of copying free
lists around.
So how do you implement the container's copy constructor, operator=, and
destructor? Do you create a new instance of an allocator object for the
destination container, or do you copy the source container's allocator
object? And how do you implement container::operator==? Is comparing the
allocator objects part of the equation?

--
+++++++++++
Siemel Naran


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
P.J. Plauger
2003-11-13 08:49:37 UTC
Permalink
Post by Siemel Naran
Post by Pete Becker
Post by Pete Becker
Post by Raoul Gough
There's also the complication of having to support rebind and
construction from an object of corresponding type.
Well, sure, but I don't regard that as "causing" trouble. It's just the
trouble you have to go through to write them.
I should add that that's the trouble you have to go through if you want
they maintain a free list for their size, so you don't worry about
copying state across a rebind. And a sensible container will create one
allocator for each required size, so there's no issue of copying free
lists around.
So how do you implement the container's copy constructor, operator=, and
destructor? Do you create a new instance of an allocator object for the
destination container, or do you copy the source container's allocator
object?
You create a new instance of an allocator object for the destination
container by copying the source container's allocator object.
Post by Siemel Naran
And how do you implement container::operator==? Is comparing the
allocator objects part of the equation?
It's well defined for each container how to compare containers by
comparing the ordered sequences of elements that each manages.

None of these are hard problems to think through, or to implement.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Pete Becker
2003-11-13 21:19:09 UTC
Permalink
Post by Siemel Naran
So how do you implement the container's copy constructor, operator=, and
destructor? Do you create a new instance of an allocator object for the
destination container, or do you copy the source container's allocator
object?
What's the difference? Copy construct vs. default construct and assign?
If the semantics are different the allocator is badly designed.
Post by Siemel Naran
And how do you implement container::operator==? Is comparing the
allocator objects part of the equation?
No.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Raoul Gough
2003-11-11 22:48:20 UTC
Permalink
Post by Pete Becker
Post by Raoul Gough
Post by Pete Becker
Post by Siemel Naran
Though I also read on this newsgroup (or maybe it was
comp.std.c++ or comp.lang.c++) that allocators with state
cause trouble. Is that because of what to do when we copy the
container?
It's because the standard says that containers are allowed to
assume that allocators of the same type always compare
equal. That, in turn, means that allocators with state won't
work sensibly if the library writer took advantage of this
leeway. Our library doesn't make this assumption.
There's also the complication of having to support rebind and
construction from an object of corresponding type.
Well, sure, but I don't regard that as "causing" trouble. It's just
the trouble you have to go through to write them.
However, it's also specific to stateful allocators, don't you think? A
stateful my_alloc<T> object can't just have a freelist of memory for T
objects, at least not if the container might actually construct a new
my_alloc<U> object before every allocation or deallocation.

e.g. std::list::erase

iterator erase (iterator i) {
typename Allocator::template rebind<node_type>::other
temp (m_alloc); // From allocator passed to list constructor

// ...

temp.deallocate (node_ptr, 1);
// Memory goes on a freelist shared with m_alloc

return ...
} // temp destroyed here, but not the shared freelist(s)

So a stateful my_alloc<T> really has to be a general purpose
allocator, rather than just a dumb old T allocator. At least, that's
the conclusion I came to, but I still don't want to believe it :-)
--
Raoul Gough.
(setq dabbrev-case-fold-search nil)

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Pete Becker
2003-11-12 09:22:07 UTC
Permalink
Post by Raoul Gough
iterator erase (iterator i) {
typename Allocator::template rebind<node_type>::other
temp (m_alloc); // From allocator passed to list constructor
// ...
temp.deallocate (node_ptr, 1);
// Memory goes on a freelist shared with m_alloc
return ...
} // temp destroyed here, but not the shared freelist(s)
So a stateful my_alloc<T> really has to be a general purpose
allocator, rather than just a dumb old T allocator. At least, that's
the conclusion I came to, but I still don't want to believe it :-)
If you use containers that are implemented that badly, then, yes, you
have to guard against them. Please post the names of the libraries that
do that sort of thing, so that the rest of us can avoid them.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Raoul Gough
2003-11-12 20:37:29 UTC
Permalink
Post by Pete Becker
Post by Raoul Gough
iterator erase (iterator i) {
typename Allocator::template rebind<node_type>::other
temp (m_alloc); // From allocator passed to list constructor
// ...
temp.deallocate (node_ptr, 1);
// Memory goes on a freelist shared with m_alloc
return ...
} // temp destroyed here, but not the shared freelist(s)
So a stateful my_alloc<T> really has to be a general purpose
allocator, rather than just a dumb old T allocator. At least,
that's the conclusion I came to, but I still don't want to
believe it :-)
If you use containers that are implemented that badly, then, yes,
you have to guard against them. Please post the names of the
libraries that do that sort of thing, so that the rest of us can
avoid them.
So that's just being paranoid? I've never encountered one myself, but
Andy Sawyer claimed that such implementations do exist (and more
importantly, are standard-conforming):

Andy Sawyer<***@evo6.com.NoSpam> wrote in
http://groups.google.com/groups?selm=of8z1h7x.fsf%40ender.evo6.com
Post by Pete Becker
I know of library implementations which construct a single "rebind"
allocator when the container is constructed, and implementations
which construct the "rebind" allocator when required."
Unfortunately, he didn't say which implementations he was referring
to. Maybe this freedom was not intended by the standard, since one of
the container requirements (23.1/8) includes this:

"... constructors for these container types take an Allocator& argu-
ment (20.1.5), an allocator whose value type is the same as the
container's value type. A copy of this argument is used for any
memory allocation performed, by these constructors and by all member
functions, during the lifetime of each container object."

This doesn't actually make much sense (except maybe for std::vector)
since allocator<value_type> is the wrong type of allocator for most
containers. AFAIK, the standard doesn't say anything about when,
where or how many rebind allocators are constructed.

In fact, creating the rebind allocators only when needed would make a
lot of sense for a stateless allocator, since it saves you a byte in
the container object compared with having an extra (empty) member
variable.
--
Raoul Gough.
(setq dabbrev-case-fold-search nil)

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
P.J. Plauger
2003-11-13 08:49:02 UTC
Permalink
Post by Raoul Gough
Post by Pete Becker
I know of library implementations which construct a single "rebind"
allocator when the container is constructed, and implementations
which construct the "rebind" allocator when required."
Both approaches are permitted by the C++ Standard.
Post by Raoul Gough
Unfortunately, he didn't say which implementations he was referring
to. Maybe this freedom was not intended by the standard, since one of
"... constructors for these container types take an Allocator& argu-
ment (20.1.5), an allocator whose value type is the same as the
container's value type. A copy of this argument is used for any
memory allocation performed, by these constructors and by all member
functions, during the lifetime of each container object."
For a broad enough definition of "used", this is true. One "use" would
be to initialize a rebind version with it, then allocate through that
object.
Post by Raoul Gough
This doesn't actually make much sense (except maybe for std::vector)
since allocator<value_type> is the wrong type of allocator for most
containers. AFAIK, the standard doesn't say anything about when,
where or how many rebind allocators are constructed.
No, it doesn't. Leaves something to the imagination, don't it?
Post by Raoul Gough
In fact, creating the rebind allocators only when needed would make a
lot of sense for a stateless allocator, since it saves you a byte in
the container object compared with having an extra (empty) member
variable.
Assuming that the cost of construction is low, yes. But how do you
know that? (Even a stateless object may send a postcard when it's
constructed.)

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Pete Becker
2003-11-13 21:21:36 UTC
Permalink
Post by Raoul Gough
Post by Pete Becker
If you use containers that are implemented that badly, then, yes,
you have to guard against them. Please post the names of the
libraries that do that sort of thing, so that the rest of us can
avoid them.
So that's just being paranoid?
Not paranoid. Just overly concerned with minutiae. <g>
Post by Raoul Gough
I've never encountered one myself, but
Andy Sawyer claimed that such implementations do exist (and more
Er, not "more importantly," but "less importantly." If you use 'em
you've got problems, regardless of whether they conform to the standard.

Your job is to write code that works. If you can't figure out the
semantics for an allocator in a container that creates allocators
willy-nilly then your code won't work. So your choice is: don't use
allocators with state or don't use containers that create allocators
willy-nilly. If you need allocators with state, the choice is easy. <g>
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Raoul Gough
2003-11-15 01:11:22 UTC
Permalink
Post by Pete Becker
Post by Raoul Gough
Post by Pete Becker
If you use containers that are implemented that badly, then, yes,
you have to guard against them. Please post the names of the
libraries that do that sort of thing, so that the rest of us can
avoid them.
So that's just being paranoid?
Not paranoid. Just overly concerned with minutiae. <g>
Fair enough - why else would anyone program in C++ :-)
Post by Pete Becker
Post by Raoul Gough
I've never encountered one myself, but
Andy Sawyer claimed that such implementations do exist (and more
Er, not "more importantly," but "less importantly." If you use 'em
you've got problems, regardless of whether they conform to the
standard.
That's one way of looking at it. On the other hand, the standard
pretty clearly intended to allow for stateful allocators (i.e. with
per-object state), yet it turns out in practice to be very difficult
without assuming things about the specific implementation. Maybe
unintentionally so?
Post by Pete Becker
Your job is to write code that works. If you can't figure out the
semantics for an allocator in a container that creates allocators
willy-nilly then your code won't work. So your choice is: don't use
allocators with state or don't use containers that create allocators
willy-nilly. If you need allocators with state, the choice is
easy. <g>
Well, sure, in practice. It was still worthwhile for me to discuss
some of the theoretical aspects.
--
Raoul Gough.
(setq dabbrev-case-fold-search nil)

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Maciej Sobczak
2003-11-08 00:26:37 UTC
Permalink
Hi,
Post by Scott Meyers
For the node-based containers, one thing has always nagged at the back of
my mind. To increase the performance of node allocation, one can keep a
free list of nodes that have been freed. But who keeps this free list, the
container or the allocator?
The allocator seems like the logical place to
do it, but I can also imagine a container doing it.
The container certainly could do this, but then you would ask yourself
(or loudly, on the group :) ) how to change the way the container does it.
Allocators are exactly to provide the abstraction of this mechanism so
that you can (more or less) easily plug your own schema into the
container that in principle can be agnostic of such details.

Containers are for "containing".
Allocator are for "allocating".

In one of your books I've read about "separation of concerns"... ;)


Of course, node caching is a form of opimization and as all
optimizations, it can be better or worse (and more or less intelligent),
depending on the level where it is applied. This means that the door is
open and you can expect different implementations choosing different
solutions.
Certainly, standard does not impose any restrictions here. As a related
issue, remember recent discussion about how to "force" the vector to
release its memory - in essence, the containers themselves (without
involving allocators) are free to free lazily.
--
Maciej Sobczak : http://www.msobczak.com/
Programming : http://www.msobczak.com/prog/


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Thorsten Ottosen
2003-11-08 00:54:11 UTC
Permalink
Post by Scott Meyers
Is there
any reason why a container *can't* keep its own free list of nodes?
Does
anybody know of any container implementation that actually does?
FWIW, the circular_buffer container that is near submission status to boost
has performance as one as its hallmarks. It might be worth looking into.

best regards

Thorsten



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Dhruv
2003-11-08 11:42:56 UTC
Permalink
Post by Scott Meyers
For the node-based containers, one thing has always nagged at the back of
my mind. To increase the performance of node allocation, one can keep a
free list of nodes that have been freed. But who keeps this free list, the
container or the allocator? The allocator seems like the logical place to
do it, but I can also imagine a container doing it. I've never bothered to
check STL implementations to see if any containers keep their own node free
lists, but I'm thinking that somebody reading this probably has. Is there
any reason why a container *can't* keep its own free list of nodes? Does
anybody know of any container implementation that actually does?
To the best of my limited subset of limited knowledge, one such
implementation I've seen would be the Rogue Wave STL shipped with the
Borland 5.5 free compiler. That's because I saw something like free_list,
which I feel is something wrong. The allocator is responsible for taking
care of all that. An excellent implementation I feel is the libstdc++ one.
(I'm being biased here, but I'm justified!!!)...


Regards,
-Dhruv.






[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Robert Kindred
2003-11-08 11:51:59 UTC
Permalink
Post by Scott Meyers
For the node-based containers, one thing has always nagged at the back of
my mind. To increase the performance of node allocation, one can keep a
free list of nodes that have been freed. But who keeps this free list, the
container or the allocator?
<snip>
Suppose I have two containers of the same type, say one that contains open
items and one that contains closed items. If each of these containers
managed its own free pool, then there is a possibility that one could
exhaust all of its resources, while the other one was mostly idle. I think
I would like a common allocator to manage the unused resources.

my 0.02,

Robert Kindred

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
P.J. Plauger
2003-11-08 13:52:33 UTC
Permalink
Post by Robert Kindred
Post by Scott Meyers
For the node-based containers, one thing has always nagged at the back of
my mind. To increase the performance of node allocation, one can keep a
free list of nodes that have been freed. But who keeps this free list,
the
Post by Scott Meyers
container or the allocator?
<snip>
Suppose I have two containers of the same type, say one that contains open
items and one that contains closed items. If each of these containers
managed its own free pool, then there is a possibility that one could
exhaust all of its resources, while the other one was mostly idle. I think
I would like a common allocator to manage the unused resources.
Particularly if you want to splice elements between lists.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Felix Yen
2003-11-09 14:12:41 UTC
Permalink
Post by P.J. Plauger
Particularly if you want to splice elements between lists.
Strictly speaking, there's no reason why a container can't maintain
its own free list and also support splicing. As long as the spliced
containers use the same node allocator, they can interchange elements
freely. However, the splicing requirement removes any incentive to
have the container maintain its own free list.

If there were no splicing requirement, the container could allocate a
region of nodes, use this to populate its free list, allocating more
regions if necessary. Such a container could even expose a reserve()
method to give its clients indirect control over region size. The
container's memory usage grows monotonically until it is destroyed,
just like a vector. We can minimize free list initialization by
taking nodes directly from the most recently allocated region. When
we swap with another container, we swap everything. Our node
addresses are taken from a small number of regions (though the
elements they point to still have to be allocated singly). It's a
neat design.

But if I splice such a node into another container, the spliced
containers would share the allocated regions, and would have
difficulty cooperating on their destruction. In other words, the
splicing requirement forces us to allocate nodes singly. Since the
allocator is also capable of maintaining a free list, and it can do so
on behalf of all its containers, we might as well implement recycling
there.


Felix

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
John Torjo
2003-11-10 13:24:45 UTC
Permalink
Post by Felix Yen
But if I splice such a node into another container, the spliced
containers would share the allocated regions, and would have
difficulty cooperating on their destruction. In other words, the
splicing requirement forces us to allocate nodes singly. Since the
allocator is also capable of maintaining a free list, and it can do so
on behalf of all its containers, we might as well implement recycling
there.
I may have misunderstood, but I don't understand why would splicing
and maintaining a free list of nodes could cause a problem.

We should distinguish between erase() and spliced_erase() (which could
be a private function).

I don't see the problem. Please enlighten me ;)



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Felix Yen
2003-11-11 22:36:45 UTC
Permalink
Post by John Torjo
I may have misunderstood, but I don't understand why would splicing
and maintaining a free list of nodes could cause a problem.
The conflict is between splicing and region allocation, not between
splicing and free list usage. I claim that the allocator can maintain
a free list just as easily as the container. In another strand of
this thread, there's an article from one of the good folks at
Dinkumware indicating that they've developed such an allocator.

Mine is freely available, and it allocates regions:
http://home.earthlink.net/~brimar/yalloc

There's also interesting stuff in the gcc pipeline ...


Felix

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Siemel Naran
2003-11-09 11:46:29 UTC
Permalink
Post by Robert Kindred
Suppose I have two containers of the same type, say one that contains open
items and one that contains closed items. If each of these containers
managed its own free pool, then there is a possibility that one could
exhaust all of its resources, while the other one was mostly idle. I think
I would like a common allocator to manage the unused resources.
my 0.02,
You could still do it.

MyAllocator myallocator;
std::list<Item> openItems(myallocator);
std::list<Item> closedItems(myallocator);

Only thing is I don't know how to write class MyAllocator. My char(2) :).

--
+++++++++++
Siemel Naran


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Stephen Howe
2003-11-08 13:14:03 UTC
Permalink
Post by Scott Meyers
For the node-based containers, one thing has always nagged at the back of
my mind. To increase the performance of node allocation, one can keep a
free list of nodes that have been freed. But who keeps this free list, the
container or the allocator?
I would say the allocator. In some senses, I would rather it was the
allocator or some static function based on the type. If I had

std::list<SomeObj> a,b,c,d,e;

with the same allocator, I would like nodes freed from container a to be
recycleable and be used by e.

And if this was abstracted further, I would like nodes that were, say 64
bytes in size, freed from a list to be available for a set or map.

Stephen Howe



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Pete Becker
2003-11-09 11:25:16 UTC
Permalink
Post by Stephen Howe
I would say the allocator. In some senses, I would rather it was the
allocator or some static function based on the type. If I had
std::list<SomeObj> a,b,c,d,e;
with the same allocator, I would like nodes freed from container a to be
recycleable and be used by e.
And if this was abstracted further, I would like nodes that were, say 64
bytes in size, freed from a list to be available for a set or map.
Take a look at our CoreX library (online documentation at
www.dinkumware.com/refxcorex.html). The Allocators library is a toolkit
for building allocator types. You can choose a caching strategy (use
new/delete for every allocation, use size-based freelists, etc.) and a
synchronization strategy (no synchronization, separate memory manager
for each container, separate memory manager for each thread, one memory
manager with synchronized access). You can also write your own
components and plug them into the allocator.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Christopher Currie
2003-11-11 16:58:28 UTC
Permalink
Post by Scott Meyers
For the node-based containers, one thing has always nagged at the back of
my mind. To increase the performance of node allocation, one can keep a
free list of nodes that have been freed. But who keeps this free list, the
container or the allocator? The allocator seems like the logical place to
do it, but I can also imagine a container doing it.
The standard seems to lean in favor of the allocator on this point. A
footnote to the Allocator requirements table says: "It is intended that
a.allocate be an efficient means of allocating a single object of type
T, even when sizeof(T) is small. That is, there is no need for a
container to maintain its own 'free list.'" (20.1.5)

Someone earlier mentioned a "common" allocator doing this kind of memory
management. The problem with this is that there is no such animal. All
memory used by a container object comes from an allocator object owned
by it, which is copied when the container is copied. (Imagine trying to
copy the free list!)

Containers might share a common allocator *class*, but this class would
need to keep its free pool in some static or shared object (which would
require synchronization in a multi-threaded environment). I'm not sure
such an allocator would be any more useful, or have a chance at being
more efficient.

I think it's likely that the memory allocation algorithms provided by
the operating system are going to be more efficient and appropriate for
a platform than any given allocator could we devise, particularly a
portable one. The point of the allocator concept, I believe, is to allow
specific containers to get memory from sources other than "operator
new()", such as shared memory for interprocess communication, or to
conform to special segmented memory requirements.
Post by Scott Meyers
I've never bothered to check STL implementations to see if any
containers keep their own node free lists, but I'm thinking that
somebody reading this probably has. Is there any reason why a
container *can't* keep its own free list of nodes? Does anybody know
of any container implementation that actually does?
Many people have cited the trouble resource starvation between
containers. The node based containers don't have any functions for
controlling capacity. Class designers would have to make some decisions
regarding what the maximum percentage of unused nodes would be before
releasing them back to the system, which might be just when the
application would need to add several hundred new objects.

This ran on for rather longer than was probably necessary, but I think
the upshot of it is that the container might keep a free-list, but it
would probably be custom designed for the application that uses it. An
allocator class probably shouldn't, because the system is probably
better at it than the allocator can be.

Two cents, with interest,
Christopher

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Loading...