On Fri, 08 Jul 2005 13:57:52 +0000, Pablo Halpern wrote:

>
> The solution to Issue 431 (Swapping containers with unequal allocators)
> is not to come up with a small "fix" to the wording of the standard, but
> to examine how per-instance allocators should work in the first place.
> My proposal addresses the bigger issue of the STL allocator model as a
> whole, from which a solution to Issue 431 emerges from a consideration
> of basic principles.
Have you had any takers yet? This thread seems very quiet. I like your
solution to the DR and to the issue of stateful allocators in general.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Sorry about the slow response.  I've been on vacation and virtually cut
off from the Internet.

We were discussing my allocator proposal, which can be found here:
http://home.earthlink.net/~phalpern/cpp/HalpernAllocatorProposal.pdf

"Branimir Maksimovic" <bmaxa@volomp.com> wrote:
[snip]
>Pablo Halpern wrote:
>> Interesting suggestion, but it does not appear that you have fully read
>> the proposal.  Your mechanism depends on all allocators having
>> indefinate life spans.
>
>No. Allocators should live until objects that are allocated with them
>live. Simple reference counting will do the job.

That is not the point.  Reference counting does not give you control
over the life-span of an allocator (or any other object), it just
ensures that it is destroyed when no longer used.  If you want to ensure
that an allocator is no longer used when, e.g. a specific function
returns, you cannot do that with reference counting.  You must ensure
that the allocator cannot possibly still be used when the function is
done.

A classic example of this is a region allocator -- one that allocates
memory from a larger blocks and never returns it.  When the region for
which the allocator is done has returned, you want to be able to return
all of the large blocks to the global heap.  If you don't control when
the allocator is destroyed (with reference counting you lose that
control), then the large blocks will remain allocated indefinately,
possibly causing the program to run out of memory.

[snip]
>> Consider a shared-memory allocator.  You want precise control over what
>> goes into a shared memory segment and what does not.  If allocators
>> moved around or if a given container could end up with elements
>> allocated from different allocators, this control would be lost.
>
>Well, if one wants shared memory vector for example, she would not
>swap with different one.

Can you be sure that no function you call will ever use swap()?  I have
recently revised the discussion in the paper to add more detail as to
why objects should not change allocators after creation (in most
circumstances).  Take a look -- its in section 2.4.

>> I'd be hard-pressed to write a reasonable program if swap()
>> could suddenly change an object's storage class from static to automatic
>> (block-scope) storage.
>
>We are talking about dynamic memory management. So why make allocators
>automatic in the first place? Anyway by using auto allocator that
>have it's own state is pretty dangerous in any situation.

The region allocator example is a very real example (that we use in our
own code) for putting an allocator on the stack.
>
>>
>> Finally, your proposal requires an extra pointer for every node of a
>> list or map.  Many people would find that overhead unacceptable.
>
>I agree this tend to be rather expensive, but there is also overhead
>for every construction/copy construction of tmp allocators that will
>keep that pointer anyway. So this trades size for speed, but copying
>stack
>allocators trade speed for size. There is always some overhead,
>question
>is just what is more important at particular time.

Stateful allocators in general just contain a pointer to an imp-object
and that it is the imp object that lives on the stack.  Only the small
object containing the pointer is copied and only when the entire
container is copied, not each element.

Our real-world experience validates that this is a performance win.

Pablo Halpern                 phalpern@halpernwightsoftware.com
Author: The C++ Standard Library from Scratch
http://www.halpernwightsoftware.com/stdlib-scratch

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Sorry for the slow response.  I've been away.

Arno <aschoedl@think-cell.com> wrote:

>
>Hello Pablo,
>
>first of all, I am only a very unimportant reader of this list, and
>have no bearing whatsoever on any decisionmaker.

All inputs are appreciated.
>
>I like your proposal in general. The only major flaw I see with it is
>the special role of new_allocator. I would like the proposal to be
>leaner to avoid committing to a particular implementation. Your
>new_allocator does not support non-T* pointers, which I use and like.
>
>What do you _really_ need to solve your problem?
>
>4, but only uses_new_allocator, which should mean
>construct_with_allocator, 5, 7, 9. That's it.

There seems to be some text missing in your post, as the last sentence
starts in the middle.  I'll try to answer you question:

With regard to implementation, *something* must be said about the
default allocator and how to create new polymorphic allocators.  In
order to create a derived class of allocator_implementation, you must
have the base class, otherwise nothing can interoperate.

With regard to is_new_allocator, this feature is there specifically to
allow one to create other types of policy-based allocators that follow
the new rules (i.e. are not copied on container copy construction).
Otherwise, there would only be std::allocator and everything else.

My proposal does not change anything in with respect to pointers.  The
existing template-policy allocators are still usable with my proposal.
Besides, the standard already states that the 'pointer' type for any
allocator must be T*.  I'd be curious to know what you do with non-T*
pointers wrt allocators.  Do you have allocators for which 'pointer' is
not a typedef for T*?  Can use use your special allocators with vector
and set?

>
>8, 10, 11, 12 extend allocator usage beyond containers, which is
>laudible, but could be done with the old allocator concept as well,
>thus it is really an orthogonal proposal.

I don't agree.

Item 8 sets the precident that things that use allocators should be
compatible with the new model.  If this were not the case, the new model
would become useless for anything other than vector<string> or
vector<vector>, etc.  We want the allocator-sharing to work with as many
data types as possible, ESPECIALLY standard data types.

Item 10 enhances pair to work with allocators so that map and set can
follow the new semantics.  Also, pair can be thought of as a special
case of a container and thus should be brought into line with other
containers.

Item 11 makes it easier to implement the new model for new user-defined
data types.  It makes little sense as a separate proposal, since its
usefulness is entirely dependent on the acceptence of the rest of the
proposal.  In addition, the functions being overloaded are exactly the
functions that are currently used to implement STL containers.  Without
the new overloads, these algorithms become less useful once the new
model is adopted.

Item 12 is arguably orthogonal to the rest of the proposal except that
the removal of automatic allocator copying makes adoption of this piece
more urgent.  It's a pretty minor point, regardless.

>
>Arno

Thanks for your comments.
Pablo Halpern                 phalpern@halpernwightsoftware.com
Author: The C++ Standard Library from Scratch
http://www.halpernwightsoftware.com/stdlib-scratch

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

[This message is cross-posted.  Responses to comp.std.c++ only, please]

The solution to Issue 431 (Swapping containers with unequal allocators)
is not to come up with a small "fix" to the wording of the standard, but
to examine how per-instance allocators should work in the first place.
My proposal addresses the bigger issue of the STL allocator model as a
whole, from which a solution to Issue 431 emerges from a consideration
of basic principles.  The entire document is long (23 pages, including
bibliography, table of contents, etc.) although the formal proposal is
only about 3 pages.  The proposal can be found at
http://home.earthlink.net/~phalpern/cpp/HalpernAllocatorProposal.pdf .
I am looking for a member of the library WG to work with me to refine
this proposal and help move it on the standards track.  Any takers?

Below is the conclusion section to whet your appetite:

The 1998 C++ standard defines an allocator model in which allocation
policy is specified as a template parameter to container class
templates.  We found the standard's allocator model deficient in a
number of respects: container types instantiated with one allocator do
not interoperate with otherwise identical container types instantiated
with different allocators.  Even when this is not an issue, the
semantics of copying allocators causes one to lose control over his/her
allocator objects, making per-instance allocators impractical.

The BDE project uses a powerful model, developed by John Lakos, of
per-instance allocators that cleanly separate a container's memory
allocation policy from its type and value.  BDE containers automatically
share their allocator with their contained elements, producing a single
memory allocation domain for each complex object. This mechanism proved
very powerful, easy to use and easy to extend.  We were able to use it
extensively to achieve data sharing, increase efficiency, and facilitate
testing.

Merging Lakos's allocator model into an existing implementation of the
C++ standard library, we were able to get the best of both worlds.  Our
new STL continues to comply with the 1998 standard, but we were able to
get the benefits of per-instance allocators on which we had come to
rely.  In addition, we implemented a solution to an outstanding standard
library issue 431 (Swapping containers with unequal allocators) that is
consistent with our allocator philosophy. Our experience provides an
existing implementation and points the way to a general approach that
can be incorporated into the emerging revision of the standard.

Pablo Halpern                 phalpern@halpernwightsoftware.com
Author: The C++ Standard Library from Scratch
http://www.halpernwightsoftware.com/stdlib-scratch


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

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Hello Pablo,

first of all, I am only a very unimportant reader of this list, and
have no bearing whatsoever on any decisionmaker.

I like your proposal in general. The only major flaw I see with it is
the special role of new_allocator. I would like the proposal to be
leaner to avoid committing to a particular implementation. Your
new_allocator does not support non-T* pointers, which I use and like.

What do you _really_ need to solve your problem?

4, but only uses_new_allocator, which should mean
construct_with_allocator, 5, 7, 9. That's it.

8, 10, 11, 12 extend allocator usage beyond containers, which is
laudible, but could be done with the old allocator concept as well,
thus it is really an orthogonal proposal.

Arno



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Pablo Halpern wrote:
> [This message is cross-posted.  Responses to comp.std.c++ only, please]
>
> The solution to Issue 431 (Swapping containers with unequal allocators)
> is not to come up with a small "fix" to the wording of the standard, but
> to examine how per-instance allocators should work in the first place.

Well just to add first thought one can do something like this:

const size_t align = 7; // 8 bytes alignment
const size_t header_size = (sizeof(allocator_t*) + align) & ~align;
// allocator_t is base class type
void* operator new(size_t s, allocator_t* a = 0)throw (std::bad_alloc)
{
  if(!a)a=default_alloc();
  void* p = a->allocate(s+header_size);
  *(allocator_t*)p = a;
  return (char*)p+header_size;
}

void operator delete(void* p)throw ()
{
  allocator_t* a = (allocator_t*)((char*)p-header_size);
  a->deallocate(p);
}

Containers just call p =new (&alloc) T and delete p,
so there would be no problems with swap, splice etc and also
one do not need to tie allocators with objects in constructors.

Greetings, Bane.



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Branimir Maksimovic <bmaxa@volomp.com> wrote:

[snip]
>void* operator new(size_t s, allocator_t* a = 0)throw (std::bad_alloc)
[snip]
>void operator delete(void* p)throw ()
>{
>  allocator_t* a = (allocator_t*)((char*)p-header_size);
>  a->deallocate(p);
>}
>
>Containers just call p =new (&alloc) T and delete p,
>so there would be no problems with swap, splice etc and also
>one do not need to tie allocators with objects in constructors.

Interesting suggestion, but it does not appear that you have fully read
the proposal.  Your mechanism depends on all allocators having
indefinate life spans.  The motivation for my proposal comes from
experience and research that shows that the most useful allocators are
not global and have limited life spans. Pay particular attention to the
section "Who's got my allocator?".  Swap and splice have serious
problems with non-global allocators, and that is why the proposal
settles on a particular resolution for Issue 431.

In addition, the benefits of allocators are seriously reduced if
specific objects cannot be forever tied to a specific allocator.
Consider a shared-memory allocator.  You want precise control over what
goes into a shared memory segment and what does not.  If allocators
moved around or if a given container could end up with elements
allocated from different allocators, this control would be lost.  This
is why we advocate that swap should not, by default, swap the allocator.
Think of an allocator similarly to the way you think about storage
class.  I'd be hard-pressed to write a reasonable program if swap()
could suddenly change an object's storage class from static to automatic
(block-scope) storage.

Finally, your proposal requires an extra pointer for every node of a
list or map.  Many people would find that overhead unacceptable.

Regards,
Pablo Halpern                 phalpern@halpernwightsoftware.com
Author: The C++ Standard Library from Scratch
http://www.halpernwightsoftware.com/stdlib-scratch

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Pablo Halpern wrote:
> Branimir Maksimovic <bmaxa@volomp.com> wrote:
>
> [snip]
> >void* operator new(size_t s, allocator_t* a = 0)throw (std::bad_alloc)
> [snip]
> >void operator delete(void* p)throw ()
> >{
> >  allocator_t* a = (allocator_t*)((char*)p-header_size);
> >  a->deallocate(p);
> >}
> >
> >Containers just call p =new (&alloc) T and delete p,
> >so there would be no problems with swap, splice etc and also
> >one do not need to tie allocators with objects in constructors.
>
> Interesting suggestion, but it does not appear that you have fully read
> the proposal.  Your mechanism depends on all allocators having
> indefinate life spans.

No. Allocators should live until objects that are allocated with them
live. Simple reference counting will do the job.

void* operator new(size_t s, allocator_t* a = 0)throw (std::bad_alloc)
{
 a.inc_ref();
 // .......
}

void operator delete(void* p)throw ()
{
  allocator_t* a = (allocator_t*)((char*)p-header_size);
  a->dec_ref();
  a->deallocate(a /* was p, my error */);
}


>
> In addition, the benefits of allocators are seriously reduced if
> specific objects cannot be forever tied to a specific allocator.

I don't understand this. Object is forever tied to specific allocator.
One can only mimic that different allocators are used, but they all
have to point to same allocator in order to successfully deallocate.

> Consider a shared-memory allocator.  You want precise control over what
> goes into a shared memory segment and what does not.  If allocators
> moved around or if a given container could end up with elements
> allocated from different allocators, this control would be lost.

Well, if one wants shared memory vector for example, she would not
swap with different one.

> I'd be hard-pressed to write a reasonable program if swap()
> could suddenly change an object's storage class from static to automatic
> (block-scope) storage.

We are talking about dynamic memory management. So why make allocators
automatic in the first place? Anyway by using auto allocator that
have it's own state is pretty dangerous in any situation.

>
> Finally, your proposal requires an extra pointer for every node of a
> list or map.  Many people would find that overhead unacceptable.

I agree this tend to be rather expensive, but there is also overhead
for every construction/copy construction of tmp allocators that will
keep that pointer anyway. So this trades size for speed, but copying
stack
allocators trade speed for size. There is always some overhead,
question
is just what is more important at particular time.

Greetings, Bane.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Branimir Maksimovic wrote:
>
> void* operator new(size_t s, allocator_t* a = 0)throw (std::bad_alloc)
> {
>  a.inc_ref();
>  // .......
> }
>
> void operator delete(void* p)throw ()
> {
>   allocator_t* a = (allocator_t*)((char*)p-header_size);
>   a->dec_ref();
>   a->deallocate(a /* was p, my error */);
> }
>
>

Didn't saw more errors in less numbers of lines.
That happens to me when working late at night.:)

> void* operator new(size_t s, allocator_t* a = 0)throw (std::bad_alloc)
> {
  if(!a)a=default_alloc();
  a->inc_ref();
>  // .......
> }
>
> void operator delete(void* p)throw ()
> {
  void* mem = ((char*)p-header_size);
  allocator_t* a = *(allocator_t**)mem;
  a->deallocate(mem);
  a->dec_ref();
> }

Greetings, Bane.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]