On Tue, 26 Jul 2005 15:40:53 +0000, Pablo Halpern wrote:

> This morning I posted a revision to my allocator proposal at:
> http://home.earthlink.net/~phalpern/cpp/HalpernAllocatorProposal.pdf
>
> This is a serious and significant proposal aimed at making allocators
> more useful and, in the process, resolving issue 431 (swapping
> containers with unequal allocators).

How are things with this proposal? How did the treblanc presentation go?
What technical objections were raised? How were they overcome/addressed?

-apm

---
[ 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                       ]

A few posts back I said I would post the paper Mr. Halpern refers to.
It mainly explores the pitfalls and benefits of using stateful
allocators in existing STL implementations -- or any implementation of
an "STL" container that has "value semantics."
http://www.lancediduck.com/papers/Cpp/StatefulSTL.pdf

---
[ 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                       ]

Such an adapter would look like this at least for sequence containers

Of course this code can be made faster, easier to use, etc etc etc but
it demonstrates that the major ideas found in the proposal can be done
using existing STL implementations. The only standard change that would
be requireed it to make "Lakos Allocator Semantics" the default. They
are readily available as an option.
http://www.lancediduck.com/papers/Cpp/StatefulSTL2.pdf

---
[ 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                       ]

lancediduck@nyc.rr.com wrote:

>The fact is that every major STL supplier already supports polymorphic
>allocators. I've tested this with Roguewave, Dinkumwave, STLPort, and
>gnu on Sun, gcc, MSVC, aCC, etc, and others I know of have tested it on
>Comeau and gcc. I haven't tested using Mr Hinnant's offering, but
>I'm sure polymorphic allocators work there as well.

I take issue with your definition of "works" here.  All of the libraries
you site allow allocators to carry state, thus allowing an allocator to
contain a pointer to a polymorphic type.  However, the issues I state in
the paper still exist. You sent me a memo in which you yourself listed
many of these issues. Most notably:

  1. The asymetry between copy construction and assignment cause one to
lose control over the allocator.
  2. It is difficult resize a vector if the allocator does not have a
default constructor.
  3. It is difficult to get a container and its contained elements to
share the same allcator.
  4. It is unclear what certain constructs SHOULD do.

>Mr. Halpern's proposal largely just makes polymorphic allocators the
>default instead of stateless.

Actually, my proposal says a heck of a lot more.  It addresses the
issues listed above.

You may be zeroing in on the default allocator because it is probably
the most controversial part of the proposal, now that I've backed away
from changing the semantics of swap().

>Making it the default solves nothing -

It solves the interoperability of "vocabulary" types like std::string
and std::vector<int>.  It allows existing software libraries that don't
explicitly use allocators to work with client code that does use
allocators.

>worse, it renders millions of current applications suddenly
>nonstandard, and to restandardize them implies rebuilding all of them,
>adding in "default singleton allocator instances" to the
>initialization routines, and an extra pointer to everybody's
>containers whether they need it or not. Even if the committee DID adopt
>every word of Mr Halpern proposal, there is no way every organization
>is going to pour effort into reworking already built and tested code.
>It would largely just make the standard ineffective.

I'm not sure what you mean "render millions of current applications
suddenly nonstandard."  Lots of third-party code was rebuilt using our
enhanced STL and they work fine. They were standard-conforming before
the change and they remain conforming after the change.

Could you describe what you mean by 'adding in "default singleton
allocator instances" to the initialization routines'?

If you're concerned about recompilation, I will just say that most
development organizations I've worked for are not afraid to recompile
every 10 years or so, when a new standard is ratified and implemented by
compiler vendors.  When evaluating proposed changes to the standard
based on compatibility with the old standard, I draw the line at
recompilation -- if the vast majority of old code compiles and has the
same semantics under the new standard, that's good enough for me.

As far as the extra pointer is concerned, I've already addressed that
issue in a previous post.

>Support for polymorphic behavior in allocator::operator==, max_size,
>allocate, and deallocate is already the de facto standard. Making it
>the de jure standard would be largely a no brainer, except for
>std::string, where the standard explicitly allows for reference counted
>implementations. I'm not really sure of just what stateful allocator
>semantics are for reference counting.

The issue of reference counting in the presence of unequal allocators is
independent of my proposal, but I'll give my opinion: If the original
and copy use different allocators, then make a deep-copy.  For example,
If the copy is supposed to go into shared memory but the original is not
in shared memory, you'd better make a deep copy.

>But given that every STL vendor already supports polymorphic
>allocators, at least for the functions of interest, it would be far
>easier to standardize a container adapter that wraps the problematic
>container functions. For example, a "stateful vector adapter" would
>wrap
>1. resize (because T may also hold something that wants an allocator)
>2. default constructor (this is the worst problem, not swap)
>3. swap
>4. size_t constructor (because it call resize)
>5. non const iterator
>6. any mutating operator

Could we see some examples?  (Interface would be enough.)

>Then using the adapter approach, we don't have to try to figure out
>the correct behavior for everybody up front - choose a suitable
>default for the standard, and a way to adapt it for the special cases.
>Then all you need is a library - and since unequal allocators are a
>very niche problem, a 3rd party adapter library is a far better
>solution than having everybody rework existing applications so that we
>could use "Lakos Allocators" as the default.

Again, you assert that everybody would have to rework existing
applications.  I say it ain't so.  We have real-world experience to show
that no changes need to be made in client code UNLESS it wants to take
advantage of the new features.  The default allocator still uses
new/delete unless constructed with a different implementation object.
Compile-time allocators are still supported with both the old and new
semantics (selectable via traits).

Cheers,

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                       ]

-->You sent me a memo in which you yourself listed  many of these
issues. Most notably:
-- > 1. The asymetry between copy construction and assignment cause one
to lose control over --the allocator.
-- > 2. It is difficult resize a vector if the allocator does not have
a
-->default constructor.
-- > 3. It is difficult to get a container and its contained elements
to
--share the same allcator.
-->  4. It is unclear what certain constructs SHOULD do.


They aren't issues, but observations. This weekend I'll correct
some spelling errors and references and post it for all to reference.
Specifically --
1. The "asymmetry" does not cause one to lose control over
allocators. Indeed the paper presents code examples on precisely how to
maintain control. Perhaps I need to speak to the examples more.
2. It is not difficult at all to resize a vector where the allocator
does not have a default constructor. Indeed, the very same code example
demonstrates how to do it.
3. It is not difficult to get a container and its contained elements to
"share" the same allocator. Again, the code sample shows you how.
4. It is unclear what certain constructs should do because there are no
postconditions specified for operations on containers that test
allocator comparisions
Mr. Hinnant sounds like he has done a lot of work in this area -
personally I don't care WHAT the standard behavior is for "unequal
allocators," as long as it is standard - that tells me when I need
to make a specialty container, and when I don't.

>You may be zeroing in on the default allocator because it is probably
>the most controversial part of the proposal
No-I am zeroing in on changing std::allocator< > from being stateless
to having state (i.e a this pointer) as the library default. Right now
the state of the world is that it is the other way around.

>>Making it the default solves nothing -
-->It solves the interoperability of "vocabulary" types like
std::string
-->and std::vector<int>.  It allows existing software libraries that
don't
-->explicitly use allocators to work with client code that does use
-->allocators.


They are already "interoperable." I'm sure we all know how to
make them interoperate using the std algorithms, so that point is moot.
If you are looking for "interoperability" between libraries
deployed in binary form, which I think you are trying to achieve, then
using ANY template library to achieve that, no matter what namespace it
resides in, is likely a misapplication. Trying to make std::vector<int>
or std::string (what about std::wstring??) binary compatible is a
misuse of a STL library implementation, not a problem with the library
design itself. It is easy to make STL compatible binary compatible
containers -they just don't reside in ::std. If all you are trying
to do is just make a way to pass allocators around and want your
solution to live in namespace std ...
"vocabulary type" is an application domain concept. We don't have
to change the standard to solve application problems.


 --> I'm not sure what you mean "render millions of current
applications
-->suddenly nonstandard."  Lots of third-party code was rebuilt using
our
-->enhanced STL and they work fine.

It works fine against my code too. Why? Because I have learned, from
most other successful libraries out there, not to rely on ANY STL
implementation for anything critical. I have often had to incorporate
TWO STL implementations in the code to get things to work (I've used
your offering and the native simultaneously too)
This is not a new practice. Many libraries avoid using the C standard
libraries for the same reason - they don't have to eat someone
else's bugs.
But that is library coders. Most C++ programmers are just guys wanting
to get their job done, and not manage the needs of libraries. The
default polymorphic allocator, required for backward compatibility,
just adds to the list a things that the library needs, and a library
users has to manage.
As for the "million of applications" --The upgrade process would be
this if the proposal were adopted: first, compiler writers would
contract with the library vendors to get upgrades. The vendors will
have to modify their expensive tests to account for the proposed
changes. The compiler vendors would test the new libraries with the
systems guys.
These compilers would now be delivered. The embedded systems community
quits using any of it because their platforms can barely handle the
stateless allocator containers they have been trying to adapt for 10
years.
OK the corporate and academic IT guys are still on board - and remain
noncompliant until they recompile and retest their libraries just for
the sake of now making "polymorphic allocators" the default.
Changing this portion of a well established standard is not academic.

-->We have real-world experience to show that no changes need to be
made in client code
I have real world experience with this too. TONS of it. You are correct
that no application code syntax changes are needed, only systems
requirements change (i.e. that pesky default polymorphic allocator), to
get exactly what you had before. What did that buy me? Other than
needing to support more system requirements??


As for the "adapter" OK I'll try to write up a sample and try to
test it with an implementation using an EDG front end with Plum Hall
suite of tests. It isn't high on my to do list, but easy enough.
The problem is detecting when a type can take an extra allocator
argument. "traits" probably isn't good enough for a general
solution, but good enough for a demo of vector of fairly simple user
types. There are ambiguities in the standard about type deduction in
partial specialization, so THAT part of the standard would have to be
"enhanced" as well. Like I said -- TONS of real world experience
with this.
I would invite you to study the COM Automation containers, which there
are STL wrappers for. These are the "vocabulary types" and
"interoperability" concepts you are looking for. Also look at the work
of the CORBA community. I invited J Lakos to make this same study as
well -- maybe it needs to be said on a public forum instead????

But thanks for making the proposal -it gets the community talking
about this again. Good conversation and good reason to pour a few extra
beers!!! :)
Cheers Lance

---
[ 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                       ]

>But thanks for making the proposal -it gets the community talking
>about this again. Good conversation and good reason to pour a few extra
>beers!!! :)
>Cheers Lance

Indeed.  At least we can agree on that!  Thanks for the input.
- Pablo

---
[ 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                       ]

On Fri, 26 Aug 2005 00:16:11 -0600, Pablo Halpern wrote:

> I want to thank everybody for their feedback on my proposal.
> Today I posted a second revision at
> http://home.earthlink.net/~phalpern/cpp/HalpernAllocatorProposal.pdf.  I
> also formally submitted it to the Library WG for consideration in the
> meeting next month.

It is not clear to me exactly why wherever you have an allocator parameter
it tends to be a pointer rather than a reference. Why is that please? Will
the proposal specify what the behaviour is when the pointer is null?

---
[ 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                       ]

"Peter Dimov" <pdimov@gmail.com> wrote:

>You might want to add a 'size_t alignment' argument to
>bde::Allocator::allocate. It's not strictly required as you can usually
>infer it from 'size' and require the client to round 'size' up when the
>heuristic would fail, but it's much easier to be explicit.

Yes. I think that's a good idea. I debated adding it before, but stuck
with the interface we used in our implementation.

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                       ]

public@marlowa.plus.com (Andrew Marlow) wrote:

>It is not clear to me exactly why wherever you have an allocator parameter
>it tends to be a pointer rather than a reference. Why is that please? Will
>the proposal specify what the behaviour is when the pointer is null?

In general, it is easiest to construct an allocator object from a class
derived from allocator_implementation.  The automatic conversion from
allocator_implementation* to allocator<T> does the rest.  For example,
given a region allocator declaration:

    class region_allocator : public std::allocator_implementation {...};

It is simpler to write:

    region_allocator myAlloc;
    vector<int> myVector(&myAlloc);

than it is to write the equivalent:

    region_allocator myAllocImp;
    std::allocator<int> myAlloc(&myAllocImp);
    vector<int> myVector(myAlloc);

Being pedantic, region_allocator should really be named
region_allocator_implementation.  However, once you start using this
style of allocator, you start thinking of the implementation class as
the actual allocator, with std::allocator<T> being just a wrapper for
backwards compatibility.  By passing in a pointer to the implementation
class object, we also make it explicit that only the pointer is being
copied, not the entire implementation object.

Thanks for asking.

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                       ]

The fact is that every major STL supplier already supports polymorphic
allocators. I've tested this with Roguewave, Dinkumwave, STLPort, and
gnu on Sun, gcc, MSVC, aCC, etc, and others I know of have tested it on
Comeau and gcc. I haven't tested using Mr Hinnant's offering, but
I'm sure polymorphic allocators work there as well.

Mr. Halpern's proposal largely just makes polymorphic allocators the
default instead of stateless. Making it the default solves nothing -
worse, it renders millions of current applications suddenly
nonstandard, and to restandardize them implies rebuilding all of them,
adding in "default singleton allocator instances" to the
initialization routines, and an extra pointer to everybody's
containers whether they need it or not. Even if the committee DID adopt
every word of Mr Halpern proposal, there is no way every organization
is going to pour effort into reworking already built and tested code.
It would largely just make the standard ineffective.

Support for polymorphic behavior in allocator::operator==, max_size,
allocate, and deallocate is already the de facto standard. Making it
the de jure standard would be largely a no brainer, except for
std::string, where the standard explicitly allows for reference counted
implementations. I'm not really sure of just what stateful allocator
semantics are for reference counting.

But given that every STL vendor already supports polymorphic
allocators, at least for the functions of interest, it would be far
easier to standardize a container adapter that wraps the problematic
container functions. For example, a "stateful vector adapter" would
wrap
1. resize (because T may also hold something that wants an allocator)
2. default constructor (this is the worst problem, not swap)
3. swap
4. size_t constructor (because it call resize)
5. non const iterator
6. any mutating operator

Then using the adapter approach, we don't have to try to figure out
the correct behavior for everybody up front - choose a suitable
default for the standard, and a way to adapt it for the special cases.
Then all you need is a library - and since unequal allocators are a
very niche problem, a 3rd party adapter library is a far better
solution than having everybody rework existing applications so that we
could use "Lakos Allocators" as the default. The C++ community
could equally ruminate on making the "grow factor" in vectors have
polymorphic behavior, or the page size in a deque, or the type of error
thrown for range_error, but the 1995 committee mercifully burnt these
value in, and no one second guesses it. Indeed the whole idea of the
STL is that specialized containers could be easily designed to use a
wide range of existing algorithms. Second guessing the 1995 containers
interafaces completely misses the point.
"To use the STL is to extend it"

---
[ 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                       ]

I want to thank everybody for their feedback on my proposal.
Today I posted a second revision at
http://home.earthlink.net/~phalpern/cpp/HalpernAllocatorProposal.pdf.  I
also formally submitted it to the Library WG for consideration in the
meeting next month.

The previous version (if you care) is at
http://home.earthlink.net/~phalpern/cpp/HalpernAllocatorProposal-050725.pdf

The main difference between this version and the previous one is that I
have reversed my stance on swap, largely because of the arguments
(mostly Howard's) in this thread.  Although I believed that the
theoretical meaning of swap should be to swap values, I now see that its
most common uses are to swap entire objects.  I've replaced the section
about swap with a section about move-semantic operations (including
swap).  The paper no longer proposes a swap_move function but does
propose a swap_value function which does not swap allocators and does
not make O(1) and nothrow guarantees unless the allocators are equal.

There is also a small but important addition in the middle of page ten,
giving another example of how template-based allocator policy is
difficult to use.

Please keep the discussion going.  The real debate starts now!

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:
> I want to thank everybody for their feedback on my proposal.
> Today I posted a second revision at
> http://home.earthlink.net/~phalpern/cpp/HalpernAllocatorProposal.pdf.  I
> also formally submitted it to the Library WG for consideration in the
> meeting next month.

You might want to add a 'size_t alignment' argument to
bde::Allocator::allocate. It's not strictly required as you can usually
infer it from 'size' and require the client to round 'size' up when the
heuristic would fail, but it's much easier to be explicit.

---
[ 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                       ]

"Ion Gazta=F1aga" <igaztanaga@gmail.com> wrote:

> One thing I don't like is a polimorphic allocator because:
>
>-> I can't place it in shared memory, because the virtual pointer would
>be valid only for one process, and I don't think the standard will ever
>standarize inter-process polimorphic objects (virtual tables, typeid-s,
>etc...)

Pointers of any kind (vtbl or otherwise) can only work in shared memory
if all of the processes map that memory to the same logical address
range.  Typically, this requires that the shared memory only be used by
identical process images, in which case the vtbl pointers are valid.  If
a particular application on a particular OS doesn't work that way, you
can revert to using old-style non-polymorphic allocators, exactly as you
would have to do if my proposal is not accepted.

>-> Some allocators, for example, segregated storage node allocators
>(Boost.Pool, for example), used without synchronization objects like
>mutexes, just need two pointer operations to allocate/deallocate a
>node. A call to a virtual function would be maybe too expensive.
>Although I have no data to prove it as a big reason. Or arena
>allocators can define deallocations like a empty function that can be
>easily eliminated if it's inline. Just a point to think about.

Again, optimizations can be made by reverting to non-polymorphic
allocators in performance-critical sections.  You lose the type
inter-operability, but retain the ability to have stateful allocators
that work and the sharing of allocators between a container and its
contained elements.

The important thing to remember about the proposal is that it does not
eliminate the ability to instantiate types using allocator template
policies.  It simply provides a second mechanism of associating an
allocator with a container -- a method that preserves the container's
type.
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                       ]

{repeat submission}

In article <9pchf11o63qib8h56fap5g5445gjac5ce2@4ax.com>,
 phalpern@halpernwightsoftware.org (Pablo Halpern) wrote:

> Howard Hinnant <hinnant@metrowerks.com> wrote:
>
> >In article <kibje1dvqt54imt1gfmli3a7j8d0top4u8@4ax.com>,
> > Pablo Halpern <phalpern@halpernwightsoftware.org> wrote:
> >
> >
> >Given standard containers of type C, values c1 and c2:
> >
> >To exchange memory ownership you do:
> >
> >swap(c1, c2);
> >
> >To exchange values without exchanging memory ownership you do:
> >
> >{C tmp(c1); c1 = c2; c2 = tmp;}
> >
> >I don't think we need new names for these simple operations.
>
> If we want to do generic programming, then both operations must be
> named.  swap_value is needed because only by using a named algorithm can
> one specialize the algorithm for specific types.  For example, a type
> that does not use allocators could implement swap_value with the same
> efficiency (and no-throw guarantee) as swap_move (what you are calling
> simply swap).

swap_value may be a useful function.  But I'm still wondering if it
needs to be standardized.  And maybe swap_everything_but_the_allocator
would be a better name?

> >And I
> >really don't think we want to change the observable semantics of either
> >one.  And making either one act like the other would be changing
> >observable semantics.  Specifically, if swap ceases to exchange memory
> >ownership, changes include:
> >
> >1. Exception safety goes from nothrow to basic, unless more memory is
> >thrown at the problem to create a strong guarantee.
> >
> >2. Outstanding iterators/pointers/references are now invalidated.
> >
> >3.  For vector and string, there are observable differences via the
> >capacity() member (capacities are no longer exchanged).
> >
> >4.  Performance goes from O(1) to O(N).
> >
> >5.  Memory swell goes from 0 to N, or if we adopt the strong variant 2N.
>
> If, on the other hand, swap ceases to associate a container with the
> allocator that was used at construction then:
>
> 1. The purpose of associating a specific container with a specific
> allocator is undermined.  The programmer cannot thoughtfully associate a
> container with an allocator and expect it to remain that way unless he
> studiously avoids passing a modifiable container to any function that he
> did not write himself.

That general sentiment can be widened:

The programmer cannot thoughtfully associate a
container with data and expect it to remain that way unless he
studiously avoids passing a modifiable container to any function that he
did not write himself.

I.e. A useful function must document its effects.

> 2. The container could end up outliving its allocator.

Is this not true regardless?

> 3. Memory could be leaked because an arena allocator does not control
> all of the memory that it was thought to control.

But it is always possible to leak memory if you misuse the tools.

> 4. Memory allocated with one allocator could accidentally, end up
> holding pointers to memory that was allocated with a different
> allocator, causing problems with, e.g. shared memory.

Perhaps shared memory allocators that reference different segments
should refuse to swap, or should overload swap to do what you want (see
example below).

> My point of view is that allocators are a heck of a lot more useful and
> theoretically consistent if we keep the no-movement guarantee -- so much
> so that I am willing to give up the other guarantees, knowing that
> careful use of swap could restore those guarantees in places where they
> are compromised.  Your point of view (I'm sure you'll correct me if I'm
> mis-stating it) is that perserving the other two guarantees for existing
> code is paramount, even if one cannot fully control the life of the
> allocator (i.e., one cannot expect the allocator to remain unchanged
> when calling a function that one did not write and which makes no
> explicit guarantees).

I took a look at some of the std::algorithms that use swap, and I am not
convinced at all that a no-movement guarantee would be universally
useful.  For example consider:

typedef std::vector<T, my_arena_allocator<T> > Vec;
std::deque<Vec> data;
..
// populate data
..
std::reverse(data.begin(), data.end());

Now ether the call to reverse is an O(N) process and the allocators have
been reversed as well as the T's.  Or this is an O(N*M) process and the
T's have been reversed but the allocators haven't.

Either way will work.  Which is best?  The first is (at least) M times
faster and consumes less memory.

> >Specifically I believe we can seamlessly support non-equal arena
> >allocators, and with some restrictions, non-equal shared memory
> >allocators.
>
> Seamlessly support non-equal arena allocators?  Please explain.  Some
> restrictions on shared memory allocators?

Simply that swap swaps allocators, nothing more.  When arena allocators
are swapped, they swap arenas.  In the deque<Vec> reverse example above,
the last Vec would now reference the arena that the first Vec used to
and vice-versa.

> To make allocators more useful, I proposed:
>
> 1. That it be possible to explicitly specify an allocator on
> copy-construction and that a container indicate (via a trait) that it
> can be copy-constructed with an extra allocator argument.  (Yes, I know
> that this is not technically copy-construction.  I'm talking about
> intended effect -- which is to copy something while specifying the
> allocator for the copy.)

What's wrong with this existing constructor?

template <class InputIterator>
   container(InputIterator first, InputIterator last,
             const Allocator& = Allocator());

> 2. Taking advantage of the trait described above, that the allocator
> used for a container be shared with the elements of that container.

What's wrong with?

typedef vector<T, my_allocator<T> > Vec;
deque<Vec, my_allocator<Vec> > data;

> 3. That containers with different TYPES of allocators be able to
> inter-operate, i.e., the type of the allocator does not always affect
> the type of the container.
>
> The last point requires polymorphic allocators.  Unequal allocators
> assume a new dimention when the allocator in question is polymophic
> because, unlike the arena or "restricted shared memory" examples, the
> underlying allocation mechanism for each allocator can be fundamentally
> different.  If the allocator for an object changes, then the object is
> not only allocating into a different region, it may be using an entirely
> different allocation mechanism.  This so goes against the grain of what
> the programmer is trying to do, that it makes me wonder if polymorphic
> allocators are useful under that circumstance.
>
> To make them useful, I proposed a semantic for swap that would preserve
> a container's allocator state (and thus its allocator type, in the case
> of polymorphic allocators).  For polymorphic allocators, at least, this
> has been fundamental to my use of allocators for some time.  If we want
> to support polymorphic allocators, I ask that, at the very least, there
> be an allocator trait to indicate whether the allocator should be
> allowed to be swapped - thus determining the swap algorithm for a
> container instantiated with that allocator type.
>
> Traits let us support all of my proposal except the default polymorphic
> allocator without impinging on currently-expected behavior.  Indeed,
> nothing would change for existing code.
>
> So, while I'm not sure you necessarily care about or support the rest of
> the proposal, would you agree that it is at least not horibly
> objectionable if we remove the polymorphic default allocator and made
> swap controlable by a trait?

Here's a demo of std::reverse that doesn't swap allocators.  Sorry for
the length, but most of it is just to make a demo allocator:

#include <vector>
#include <algorithm>
#include <cassert>

struct buff
{
    buff(char* buf, std::size_t size) : p_(buf), buf_(buf),
                                        size_(size), orig_size_(size) {}

    char* allocate(std::size_t n);
    void deallocate(void*, std::size_t);

    void swap(buff& b) {std::swap(p_, b.p_);
                        std::swap(buf_, b.buf_);
                        std::swap(size_, b.size_);
                        std::swap(orig_size_, b.orig_size_);}

    char* p_;
    char* buf_;
    std::size_t size_;
    std::size_t orig_size_;
};

char*
buff::allocate(std::size_t n)
{
    if (n > size_)
        throw std::bad_alloc();
    char* ret = buf_;
    buf_ += n;
    size_ -= n;
    return ret;
}

inline
void
buff::deallocate(void* p, std::size_t)
{
    assert(p_ <= p && p < p_ + orig_size_);
}

template <class T>
class arena_alloc
    : private buff
{
public:
    typedef std::size_t    size_type;
    typedef std::ptrdiff_t difference_type;
    typedef T*        pointer;
    typedef const T*  const_pointer;
    typedef T&        reference;
    typedef const T&  const_reference;
    typedef T         value_type;
    template <class U> struct rebind { typedef arena_alloc<U> other; };

    arena_alloc(void* p, size_type n) : buff((char*)p, n) {}
    template <class U> arena_alloc(const arena_alloc<U>& a) : buff(a) {};

    pointer allocate(size_type n, const void* = 0)
        {return (pointer)buff::allocate(n*sizeof(T));}
    void deallocate(pointer p, size_type n) {buff::deallocate(p, n);}

    size_type max_size() const {return buff::size_ / sizeof(T);}

    pointer address(reference x) const {return &x;}
    const_pointer address(const_reference x) const {return &x;}

    void construct(pointer p, const T& val) {::new(p) T(val);}
    void destroy(pointer p) {p->~T();}

    void swap(arena_alloc& a) {buff::swap(a);}

    template <class U> bool equal(const arena_alloc<U>& a) const
        {return p_ == a.p_;}
private:
    arena_alloc& operator=(const arena_alloc&);

    template <class U> friend class arena_alloc;
};

template <class T>
inline
void
swap(arena_alloc<T>& x, arena_alloc<T>& y)
{
    x.swap(y);
}

template <class T, class U>
inline
bool
operator==(const arena_alloc<T>& x, const arena_alloc<U>& y)
{
    return x.equal(y);
}

template <class T, class U>
inline
bool
operator!=(const arena_alloc<T>& x, const arena_alloc<U>& y)
{
    return !(x == y);
}

template <class T>
void
swap(std::vector<T, arena_alloc<T> >& x,
     std::vector<T, arena_alloc<T> >& y)
{
    std::vector<T, arena_alloc<T> > tmp(x);
    x = y;
    y = tmp;
}

int main()
{
    typedef std::vector<int, arena_alloc<int> > Vec;
    const unsigned N1 = 120;
    unsigned char buf1[N1];
    const unsigned N2 = 80;
    unsigned char buf2[N2];
    Vec v[2] = {Vec(10, 0, arena_alloc<int>(buf1, N1)),
                Vec(20, 0, arena_alloc<int>(buf2, N2))};
    std::reverse(v, v+2);
    assert(v[0].size() == 20);
    assert(v[0].get_allocator() == arena_alloc<int>(buf1, N1));
    assert(v[1].size() == 10);
    assert(v[1].get_allocator() == arena_alloc<int>(buf2, N2));
}

The part I want to draw attention to is the overloaded swap in
arena_alloc's namespace.  Sorry, I used an arena allocator instead of a
polymorphic allocator just to keep the demo small, but I don't think
that will affect my point.

Here I've turned a std::algorithm (that uses swap, and the standard swap
swaps allocators in my implementation) into one that swaps without
swapping allocators.  The asserts do not fire in this example, and
memory integrity is maintained.  I.e. the above demo does exactly what
you want.

Now, simply comment out the overloaded swap in the above demo, and
change the asserts in main and you get allocator-swapping behavior
(assuming std::swap swaps allocators of course):

    assert(v[0].size() == 20);
    assert(v[1].get_allocator() == arena_alloc<int>(buf1, N1));
    assert(v[1].size() == 10);
    assert(v[0].get_allocator() == arena_alloc<int>(buf2, N2));

Also in this version, I was able to reduce the size of my first buffer:

    const unsigned N1 = 40;  // down from 120

The point of this demo is to demonstrate a few points:

1.  If swap swaps allocators, containers with unequal allocators can be
safe, fast, and memory efficient.

2.  If you don't want your allocators to be swapped, you can overload
swap to get the behavior you want.  This is still safe, but no longer
fast, and memory efficient.

We get all this flexibility with a very tiny change in the std::lib:
swap(container, container) swaps the container's allocators.  I don't
see a need for swap traits.  You can already customize swap (at least in
the working paper - N1804).

-Howard

---
[ 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                       ]

I can certainly sympathize with the desire to avoid mentioning an
allocator's type in the type of a container.  For hard real-time
applications that make heavy use of custom allocation strategies (e.g.,
memory pools, stacks, etc.), interoperability with separately developed
libraries predicated upon the use of std::allocator can be too costly
if not impossible.

The other issues Pablo raises notwithstanding, I wonder whether a
standard-supplied concrete allocator handle/polymorphic body pair would
help mitigate this problem somewhat by encouraging library authors to
support this interface?

---
[ 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                       ]

hinnant@metrowerks.com (Howard Hinnant) wrote:

>In article <9pchf11o63qib8h56fap5g5445gjac5ce2@4ax.com>,
> phalpern@halpernwightsoftware.org (Pablo Halpern) wrote:
>
>> Howard Hinnant <hinnant@metrowerks.com> wrote:
>>
.
>
>swap_value may be a useful function.  But I'm still wondering if it
>needs to be standardized.  And maybe swap_everything_but_the_allocator
>would be a better name?

I'll be glad to quibble about names when the main concepts are agreed
to.

.
>I took a look at some of the std::algorithms that use swap, and I am not
>convinced at all that a no-movement guarantee would be universally
>useful.  For example consider:
>
>typedef std::vector<T, my_arena_allocator<T> > Vec;
>std::deque<Vec> data;
>..
>// populate data
>..
>std::reverse(data.begin(), data.end());
>
>Now ether the call to reverse is an O(N) process and the allocators have
>been reversed as well as the T's.  Or this is an O(N*M) process and the
>T's have been reversed but the allocators haven't.
>
>Either way will work.  Which is best?  The first is (at least) M times
>faster and consumes less memory.

My proposal specifically mentions that certain standard algorithms
(notably the sort algorithms) should use swap_object and should be
documented as such.  I think that needs to be broadened to include any
aloghrithm that shifts objects within an iterator range.  That would
include most standard algorithms that use swap today.  It is interesting
to note that this particular use of swap has nothing to do with
exception safety (since sort, reverse, etc work on objects that don't
guarantee a nothrow or O(1) swap).

>> >Specifically I believe we can seamlessly support non-equal arena
>> >allocators, and with some restrictions, non-equal shared memory
>> >allocators.
>>
>> Seamlessly support non-equal arena allocators?  Please explain.  Some
>> restrictions on shared memory allocators?
>
>Simply that swap swaps allocators, nothing more.  When arena allocators
>are swapped, they swap arenas.  In the deque<Vec> reverse example above,
>the last Vec would now reference the arena that the first Vec used to
>and vice-versa.

Then what you call support is really non-support.  Just defining what
happens does not make it good, it just makes your limitations explicit.
This does not give us a means for associating an allocator with an
object and being sure that the allocator does not move. (You do
partially address this issue below...)

>> To make allocators more useful, I proposed:
>>
>> 1. That it be possible to explicitly specify an allocator on
>> copy-construction and that a container indicate (via a trait) that it
>> can be copy-constructed with an extra allocator argument.  (Yes, I know
>> that this is not technically copy-construction.  I'm talking about
>> intended effect -- which is to copy something while specifying the
>> allocator for the copy.)
>
>What's wrong with this existing constructor?
>
>template <class InputIterator>
>   container(InputIterator first, InputIterator last,
>             const Allocator& = Allocator());

Doesn't work well inside of templates.  Some objects may use allocators
but not use iterators.  A vector cannot share its allocator with an
object of type X unless it knows (at compile time) how to construct a
copy of an X using a specific allocator.  The extra constructor and the
trait that indicates the presence of that constructor let's a container
share its allocator with any class designed to support this idiom.
>
>> 2. Taking advantage of the trait described above, that the allocator
>> used for a container be shared with the elements of that container.
>
>What's wrong with?
>
>typedef vector<T, my_allocator<T> > Vec;
>deque<Vec, my_allocator<Vec> > data;

This shares the TYPE of allocator with elemements, but not the allocator
INSTANCE information.  It also doesn't allow the 'data' object to be
used easily or efficiently with other types of vector:

    vector<T> normalVec;
    // Logic to insert normalVec into data:
    {
       Vec extraCopy(normalVec.begin(), normalVec.end(),
                     data.get_allocator();
       data.push_back(extraCopy);
    }

While the above could be made into a template function, it shouldn't
need to be.  Inserting something into a container should not require
such complication or inefficiency.  IMO, the fact that a container's
type is bound to its allocator type is the main reason that allocators
are so rarely used.  It is why I advocate a polymorphic allocator.

[lots of quoted material snipped]
>
>Here's a demo of std::reverse that doesn't swap allocators.  Sorry for
>the length, but most of it is just to make a demo allocator:

[allocator imp snipped]

>template <class T>
>void
>swap(std::vector<T, arena_alloc<T> >& x,
>     std::vector<T, arena_alloc<T> >& y)
>{
>    std::vector<T, arena_alloc<T> > tmp(x);
>    x = y;
>    y = tmp;
>}

Allocators are already hard for most people to grasp.  Forcing a user to
use partial template specialization whenever they want to use an
allocator of a specific type is pretty burdensome.  Also, where would
this declaration of swap go?  It can't be in <vector> because <vector>
doesn't know about arena_alloc.  It can be in "arena_alloc.h" but then
we can only overload it for the known containers.  User-defined or
third-party container libraries would be left out.

[snip]
>
>The point of this demo is to demonstrate a few points:
>
>1.  If swap swaps allocators, containers with unequal allocators can be
>safe, fast, and memory efficient.
>
>2.  If you don't want your allocators to be swapped, you can overload
>swap to get the behavior you want.  This is still safe, but no longer
>fast, and memory efficient.
>
>We get all this flexibility with a very tiny change in the std::lib:
>swap(container, container) swaps the container's allocators.  I don't
>see a need for swap traits.  You can already customize swap (at least in
>the working paper - N1804).

But overloading swap in this way does NOT give me what I want.  With the
overload EVERY use of swap will use this version, which is unncessarily
slow in the case where a swap_move would be appropriate (e.g. sorting,
reverse, etc.)  It is for this reason that I want TWO swap functions,
one that is used when you absolutely don't want to swap the allocator
(and are willing to give up certain guarantees), and the other to be
used when you don't mind swapping the allocator.

I might concede that the default swap should swap the allocator (I'm not
conceding yet, but I am thinking about it).  But I am not ready to give
up a separate swap_value algorithm that does not swap allocators.  If
for no other reason, the sheer existance of a standard swap_value
alternative should give engineers pause to consider which type of swap
they really need.  Honestly, I'm not sure why you are so resistant to
this small addition.

Swap is not the core of my proposal.  In fact, this discussion is making
me think that my proposal might have a better chance if I eliminate
mention of issue 431 entirely, since it seems to distract attention from
the core concepts.
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                       ]

On Wed, 17 Aug 2005 03:01:12 +0000, Pablo Halpern wrote:

>>Simply that swap swaps allocators, nothing more.  When arena allocators
>>are swapped, they swap arenas.  In the deque<Vec> reverse example above,
>>the last Vec would now reference the arena that the first Vec used to
>>and vice-versa.
>
> Then what you call support is really non-support.  Just defining what
> happens does not make it good, it just makes your limitations explicit.
> This does not give us a means for associating an allocator with an
> object and being sure that the allocator does not move.

Indeed. I don't like the current situation where one can lose control over
ones allocators. Surely this is the main problem that Pablo is addressing
and I think it does need to be solved.

-Andrew M.

---
[ 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                       ]

On Fri, 29 Jul 2005 23:10:03 +0000, Howard Hinnant wrote:
> What we do need to do is add support for unequal allocators.  If in
> doing that, we can preserve the interface (with existing semantics) we
> already have today, then I believe the programming community will be
> better off for it.  I believe it can be done.

Could you post details on how you way is different from Pablo's?

> Specifically I believe we can seamlessly support non-equal arena
> allocators, and with some restrictions, non-equal shared memory
> allocators.

Some specific details would be nice. Pablo's spec is quite specific. I
realise that it involves a polymorphic default allocator which you dont
like, but what would you do instead?

Regards,

Andrew Marlow

---
[ 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                       ]

In article <pan.2005.08.08.18.16.23.535381@marlowa.plus.com>,
 Andrew Marlow <public@marlowa.plus.com> wrote:

> On Fri, 29 Jul 2005 23:10:03 +0000, Howard Hinnant wrote:
> > What we do need to do is add support for unequal allocators.  If in
> > doing that, we can preserve the interface (with existing semantics) we
> > already have today, then I believe the programming community will be
> > better off for it.  I believe it can be done.
>
> Could you post details on how you way is different from Pablo's?
>
> > Specifically I believe we can seamlessly support non-equal arena
> > allocators, and with some restrictions, non-equal shared memory
> > allocators.
>
> Some specific details would be nice. Pablo's spec is quite specific. I
> realise that it involves a polymorphic default allocator which you dont
> like, but what would you do instead?

My basic premise is that allocator state should be bound to the memory
it has allocated, and that the swap functions for the containers should
remain O(1), even when allocators compare non-equal.  Here's a brief
paper on this issue:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1599.html

Today, the swap function, and list::splice are the only opportunities in
the library for memory ownership to be transferred away from the
allocator that allocated it.  Tomorrow you will (probably) need to add
to that list:  move constructors and move assignment.  Move assignment
can always be implemented in terms of swap, so that one adds nothing
new.  Move construction will need to transfer memory ownership from
source to target, and thus allocator state should be transferred along
too.

Today's allocators are required to be neither assignable nor swappable.
They will need to become swappable, and move assignable to meet these
container demands (or perhaps only swappable if containers are required
to move assign using swap).  My experiments with arena allocators are
showing no problems in doing so.

-Howard

---
[ 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                       ]

Howard Hinnant <hinnant@metrowerks.com> wrote:

>In article <kibje1dvqt54imt1gfmli3a7j8d0top4u8@4ax.com>,
> Pablo Halpern <phalpern@halpernwightsoftware.org> wrote:
>
>
>Given standard containers of type C, values c1 and c2:
>
>To exchange memory ownership you do:
>
>swap(c1, c2);
>
>To exchange values without exchanging memory ownership you do:
>
>{C tmp(c1); c1 = c2; c2 = tmp;}
>
>I don't think we need new names for these simple operations.

If we want to do generic programming, then both operations must be
named.  swap_value is needed because only by using a named algorithm can
one specialize the algorithm for specific types.  For example, a type
that does not use allocators could implement swap_value with the same
efficiency (and no-throw guarantee) as swap_move (what you are calling
simply swap).

>And I
>really don't think we want to change the observable semantics of either
>one.  And making either one act like the other would be changing
>observable semantics.  Specifically, if swap ceases to exchange memory
>ownership, changes include:
>
>1. Exception safety goes from nothrow to basic, unless more memory is
>thrown at the problem to create a strong guarantee.
>
>2. Outstanding iterators/pointers/references are now invalidated.
>
>3.  For vector and string, there are observable differences via the
>capacity() member (capacities are no longer exchanged).
>
>4.  Performance goes from O(1) to O(N).
>
>5.  Memory swell goes from 0 to N, or if we adopt the strong variant 2N.

If, on the other hand, swap ceases to associate a container with the
allocator that was used at construction then:

1. The purpose of associating a specific container with a specific
allocator is undermined.  The programmer cannot thoughtfully associate a
container with an allocator and expect it to remain that way unless he
studiously avoids passing a modifiable container to any function that he
did not write himself.

2. The container could end up outliving its allocator.

3. Memory could be leaked because an arena allocator does not control
all of the memory that it was thought to control.

4. Memory allocated with one allocator could accidentally, end up
holding pointers to memory that was allocated with a different
allocator, causing problems with, e.g. shared memory.

>What we do need to do is add support for unequal allocators.  If in
>doing that, we can preserve the interface (with existing semantics) we
>already have today, then I believe the programming community will be
>better off for it.  I believe it can be done.

I tried, and ended up with the compromises you already mentioned (loss
of the nothrow guarantee and a chance that swap would be O(N), etc.).
When all allocators of a given type compare equal, then all three swap
guarantees hold: O(1), nothrow, and no movement of allocators.  Once
they can be unequal, something has to give.  Our core disagreement is
over what should be given up by default.

My point of view is that allocators are a heck of a lot more useful and
theoretically consistent if we keep the no-movement guarantee -- so much
so that I am willing to give up the other guarantees, knowing that
careful use of swap could restore those guarantees in places where they
are compromised.  Your point of view (I'm sure you'll correct me if I'm
mis-stating it) is that perserving the other two guarantees for existing
code is paramount, even if one cannot fully control the life of the
allocator (i.e., one cannot expect the allocator to remain unchanged
when calling a function that one did not write and which makes no
explicit guarantees).

>> I'd be curious to know how you control when memory is returned from the
>> arena allocator if the allocator can suddenly end up used by an
>> unrelated object.  Have you ever written an arena allocator that
>> allocates from a stack buffer?
>
>Yes.  Speaking not just about allocators and containers, but more
>broadly, whenever I give a stack based pointer or reference to an
>object, I am careful to note the relative lifetimes.  I am careful when
>I give an arena allocator to a container, and I am careful when I give a
>stack-based rdbuf to a stream.

Which means that you cannot call a function that might swap the
containers either today or in a future revision.  This works for small
performance tweeks, but do we want to relegate allocators to small
performance tweeks?  Was it worth the complexity to add them in the
first place?

>> You seem to be dismissing the need to control allocator lifetime,
>
>Not at all.  I understand that issue and have written much code to
>ensure such lifetime issues are not violated.
>
>I am in sympathy with your motivations.  But I believe we can achieve
>some (not all) of your objectives with far smaller changes to the
>std::lib.

I'm sure there are things we could agree on.  Are there any parts of my
proposal that you would like to see adopted?

>Specifically I believe we can seamlessly support non-equal arena
>allocators, and with some restrictions, non-equal shared memory
>allocators.

Seamlessly support non-equal arena allocators?  Please explain.  Some
restrictions on shared memory allocators?

>I do not believe we can support a polymorphic default allocator, nor do
>I believe we can reverse the decision made a decade ago that the choice
>of allocator effects a container's type (I don't mean to imply that we
>can't support user-defined polymorphic allocators).

With careful use of swap(), one can keep all the needed guarantees, so
lets move away from that issue for the moment.  Let's also step away
from the default allocator issue and talk about other aspects of the
proposal.

To make allocators more useful, I proposed:

1. That it be possible to explicitly specify an allocator on
copy-construction and that a container indicate (via a trait) that it
can be copy-constructed with an extra allocator argument.  (Yes, I know
that this is not technically copy-construction.  I'm talking about
intended effect -- which is to copy something while specifying the
allocator for the copy.)

2. Taking advantage of the trait described above, that the allocator
used for a container be shared with the elements of that container.

3. That containers with different TYPES of allocators be able to
inter-operate, i.e., the type of the allocator does not always affect
the type of the container.

The last point requires polymorphic allocators.  Unequal allocators
assume a new dimention when the allocator in question is polymophic
because, unlike the arena or "restricted shared memory" examples, the
underlying allocation mechanism for each allocator can be fundamentally
different.  If the allocator for an object changes, then the object is
not only allocating into a different region, it may be using an entirely
different allocation mechanism.  This so goes against the grain of what
the programmer is trying to do, that it makes me wonder if polymorphic
allocators are useful under that circumstance.

To make them useful, I proposed a semantic for swap that would preserve
a container's allocator state (and thus its allocator type, in the case
of polymorphic allocators).  For polymorphic allocators, at least, this
has been fundamental to my use of allocators for some time.  If we want
to support polymorphic allocators, I ask that, at the very least, there
be an allocator trait to indicate whether the allocator should be
allowed to be swapped - thus determining the swap algorithm for a
container instantiated with that allocator type.

Traits let us support all of my proposal except the default polymorphic
allocator without impinging on currently-expected behavior.  Indeed,
nothing would change for existing code.

So, while I'm not sure you necessarily care about or support the rest of
the proposal, would you agree that it is at least not horibly
objectionable if we remove the polymorphic default allocator and made
swap controlable by a trait?

If we can get that far, then we can discuss whether the default
allocator should be polymorphic.
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                       ]

Hi Pablo,

 I've been reading your proposal and I find some interesting things,
but I agree with Howard that I prefer a non-throwing swapping with
unequal allocators.

> 3. That containers with different TYPES of allocators be able to
> inter-operate, i.e., the type of the allocator does not always affect
> the type of the container.
>
> The last point requires polymorphic allocators.

 One thing I don't like is a polimorphic allocator because:

-> I can't place it in shared memory, because the virtual pointer would
be valid only for one process, and I don't think the standard will ever
standarize inter-process polimorphic objects (virtual tables, typeid-s,
etc...)

-> Some allocators, for example, segregated storage node allocators
(Boost.Pool, for example), used without synchronization objects like
mutexes, just need two pointer operations to allocate/deallocate a
node. A call to a virtual function would be maybe too expensive.
Although I have no data to prove it as a big reason. Or arena
allocators can define deallocations like a empty function that can be
easily eliminated if it's inline. Just a point to think about.

Regards,

Ion

---
[ 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                       ]

Howard Hinnant <hinnant@metrowerks.com> wrote:

>My basic premise is that allocator state should be bound to the memory
>it has allocated, and that the swap functions for the containers should
>remain O(1), even when allocators compare non-equal.  Here's a brief
>paper on this issue:
>
>http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1599.html

To be clear, I agree with the part of your premise that allocator state
should be bound to the memory it has allocated.  It is the requirement
that swap remain O(1) at the cost of losing control over the allocator
that I disagree with.  I want to be able to call a function that I
didn't write and know that my allocator will not be swapped out from
under me.

>Today, the swap function, and list::splice are the only opportunities in
>the library for memory ownership to be transferred away from the
>allocator that allocated it.  Tomorrow you will (probably) need to add
>to that list:  move constructors and move assignment.  Move assignment
>can always be implemented in terms of swap, so that one adds nothing
>new.  Move construction will need to transfer memory ownership from
>source to target, and thus allocator state should be transferred along
>too.

I have no problem with allocator state moving on move-construction and
move-assignment.  The term "move" caries the conotation that the object
is being moved, not copied.  In some sense, the moved object retains the
identity of the original.

>Today's allocators are required to be neither assignable nor swappable.
>They will need to become swappable, and move assignable to meet these
>container demands (or perhaps only swappable if containers are required
>to move assign using swap).  My experiments with arena allocators are
>showing no problems in doing so.

Making allocators swappable is trivial.  Making them useful is another
matter ;-)

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                       ]

hinnant@metrowerks.com (Howard Hinnant) wrote:

>In article <7ibbe1hu4omoqsfibanas46idf9u6i5hjo@4ax.com>,
> phalpern@halpernwightsoftware.org (Pablo Halpern) wrote:
>
>> This morning I posted a revision to my allocator proposal at:
>> http://home.earthlink.net/~phalpern/cpp/HalpernAllocatorProposal.pdf
>
>In private correspondence Pablo asked me to express my concerns
>publicly.  So here goes...

Thank you for the feedback, Howard.  Before I respond to your post
point-by-point, I will make some general observations and comments:

With the exception of one point you make about exceptions, your focus is
mostly centered on the performance aspects of my proposal.  There is
nothing wrong with that, but you do not address the core question that
my propsoal attempts to answer: how do we make allocators more useful?

In my proposal, I attempt to describe an allocator model that:
1. Is methodologically sound and consistent
2. Contributes to program correctness
3. Is easy to use in a wide variety of circumstances
4. Is flexible

To paraphrase "The Mythical Man Month", it doesn't matter if you can
process a million items per second if you get the wrong answer.
Similarly, it doesn't help to make allocators ultra efficient if, in
doing so we invite subtle bugs or handicap the model such that it can
only be used in extremely limited circumstances.

Yes, my proposal does have associated overhead.  How serious that
overhead is will depend on the application, but there are ways to
eliminate the overhead in places where performance is critical.

>I have serious reservations about making the default allocator a
>non-empty class (as proposed).  The current overhead for the Freescale
>vector<T> (with default allocator) is 3 words.  If I am not mistaken,
>this proposal would mandate a 4 word overhead.

Yes, the footprint for a typical implementation of vector would be one
word larger using our stateful allocator compared to the current default
stateless allocator.  Other stateful allocators might add more overhead.

Let's compare the overhead imposed by our allocator to the overhead
imposed by other aspects of the library or language.  A typical malloc
implementation adds about 8 words of book-keeping overhead to each
allocation.  The vtbl pointer adds one word to each object that has
virtual functions, even when the concrete type of that object is known
at compile time (i.e., no function will be called polymorphically).  On
average, a vector wastes half of the memory it allocates because it uses
exponentical growth in order to achieve amortized constant-time appends.

Mitigating the overhead is the fact that the majority of containers hold
simple objects that do not have allocators, so the overhead is minor
compared to the total memory consumption of the container.  Also, the
overhead can be reduced to zero by reverting to the old allocator model
and instantiating the container with a zero-sized allocator type.  In
fact, it might be a good idea to add such an allocator class to my
proposal.  Perhaps we should call it std::simple_allocator or something
like that.

The proposal to use a non-empty, polymorphic allocator for the standard
allocator is based on the desire to allow objects to interoperate when
they use different allocators.  A large part of the benefit of my
proposal is that one can create an std::string using a custom allocator
but it is still an std::string, (not something like an
std::basic_string<char, char_traits<char>, lakos_allocator<char> >). The
choice of a non-empty default allocator is arguably a violation of the
zero-overhead principle, but that principle has to be balanced against
the implicit "put useful things in the standard" principle.  This is one
concept that needs standardization just to be useful -- a third-party
library cannot do it.

>That may not sound like much at first, but when considering containers
>of containers, a 33% jump in space overhead is significant.  And the
>overhead jump for other containers (that often store multiple
>allocators) can be worse:  list and set overhead jumps from 3 words to 5
>words, 67% (in the Freescale implementation).

Then perhaps Freescale should reconsider this strategy.  It works great
for empty allocators but causes additional overhead for any stateful
allocator, whether or not the stateful allocator is the default
allocator.  It would also be trivial to specialize the implementation
for std::allocator<T> so that only one pointer to an
allocator_implementation can be shared by the different allocators, thus
reducing the overhead back to one word.

In any case, I don't believe it is right to consider a proposal on the
basis of whether some implementations would be easier to adapt than
others, unless it would be egregiously difficult for everybody, which is
not the case here.

>All that being said, I'm very much in favor of improved support for
>client-defined stateful allocators, including the ability for different
>objects of the same type to get their memory from different sources.
>And I'm also in favor of support for unequal allocators (e.g. private
>buffers).

Then we're on the same page on this point.

>Indeed it is the unequal (private buffer) application that motivates
>option 3 of lwg 431:
>
>http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1599.html
>
>If swap exchanges memory ownership between containers, then allocator
>state (which may be required to deallocate that memory) should follow
>the memory it owns.

That's a big "IF".  I totally agree that IF memory changes hands THEN
the allocator must go with it.  The swap() part of my proposal limits
the circumstances under which memory changes hands, however.

>This is analogous to tr1::shared_ptr and its custom deleter.  The memory
>and the deleter are paired at construction time.  And though one can
>pass around ownership of this memory from shared_ptr to shared_ptr, you
>can not separate the memory from the deleter that owns it.  If you
>transfer memory ownership, you also implicitly transfer ownership of the
>paired deleter too.

I don't think the analogy holds.  A shared pointer holds a resource
allocated by the client and shared among multple pointers.  The deleter
belongs to the client and is connected to that resource.  A container,
on the other hand, is responsible for its own resource allocation and
does not open up its resources to direct outside manipulation.  The
allocator belongs to the container.

[Snip ... Howard goes into more detail about how allocator and memory
must move together]

>If instead we refuse to transfer memory ownership among containers (and
>so make swap O(N), or sometimes O(N)), then we will have a situation
>similar to list<T>::size().  People won't be able to use it because just
>the threat of something changing from O(1) to O(N) is enough to make
>something useless.

There are a number of ways that the user of swap() can ensure that they
will not get O(N) behavior, as described in my paper.  The typical
performance penalty will not be huge, and profiling can find the places
where careful allocator usage should be used to eliminate O(N) swaps.
It is not useless.  In fact, I argue that a default swap that exchanges
allocators is useless in the general case (see below).

> And to make things even worse, it takes what should
>be a non-throwing operation and turns it into something that could
>throw.  This completely invalidates code such as:
>
>template <class T1, class T2>
>inline
>std::pair<T1, T2>&
>strong_assign_pair(std::pair<T1, T2>& x, std::pair<T1, T2> y)
>{
>    x.first.swap(y.first);
>    x.second.swap(y.second);  // assumes nothrow
>    return x;
>}

Yes, there are circumstances (like the one you show) where my algorithm
can cause subtle bugs, but there are other circumstances where swapping
allocators causes subtle (and not so subtle) bugs.  Its an unfortunate
reality.

The above code is not valid for arbitrary T2, since a) T2 might not have
a swap member and if it does, b) it might not be a nothrow operation.  I
will grant, however, that under specific situations, the user may need
this to be a nothrow operation.  In that case he/she has the option of
a) making sure that all his/her objects use the same allocator or b)
using swap_move.  The important thing is that the user is aware that an
allocator might move, and has structured his/her code accordingly.  The
situation is similar to that of turning on a compiler switch that
enables unsafe levels of optimization for code sections that are
carefully structured to avoid the problems.  You wouldn't want to
structure all of your code this way, though.

>All that being said, if an allocator author really doesn't want his
>allocator to swap when the container swaps, then that is trivial to
>accomplish:
>
>inline void swap(my_allocator&, my_allocator&) {}

That would be a disaster, since then memory would be swapped and the
allocator would not be swapped.  If this were an option, then Issue 431
would be closed.  I would consider an extra template parameter or
allocator trait that would tell the compiler which swap to use for a
given container type.  Still I would want the default behavior to not
swap the allocator.

>The proposed swap (formally swap_value) with the strong exception
>guarantee is extravagantly expensive when allocators are unequal.  It
>requires a complete copy to be made of both containers, temporarily
>requiring 4 containers in memory at once.  This goes completely against
>the current philosophy in the standard:  support the strongest exception
>safety guarantees you can <em>that don't incur extra overhead</em>.

Interesting.  When a vector outgrows its capacity, it also uses double
the memory.  My algorithm is specifically designed to cause a minimum of
surprises for code that currently makes the nothrow assumption, without
swapping the allocators.  It could be made faster by weakening the
exception guarantees, so it is a compromise between adhearing to the
principle that allocators should not move and breaking as little code as
possible.  I will return to this principle again...

>Quite frankly if my swap suddenly decided it needed to make temporary
>copies of both arguments, I'd much rather get an assert or an exception
>to let me know.  Then if I really wanted to go to that expense, I'd make
>it explicit rather than hiding it under something named swap.

Of course, if you run out of memory, you WILL get an exception :-).

Seriously, again there is a premature optimization issue here.  Most
containers are not huge, most huge containers are never swapped, and
most swaps will not require O(N) time and double memory (because the
allocator will usually be equal).  The important thing is to make
programs more likely to be CORRECT.  This brings me back to the basic
principle of allocators that don't move...

>An O(N) swap, max_size, or size (all allowed by the standard) is so
>counterintuitive that it is dangerous, especially to generic code.  It
>is like putting operator[](size_t) on std::list.  Just say no. ;-)

Strong statements indeed!  Counterintuitive?  May I remind you that the
generic swap() algorithm is O(N)?

Now, back to the basic principle that I've been refering to over and
over.  (I will be giving a talk on this subject at C++ Connections in
November.)  Studies have shown that per-type allocators provide little
benefit (see [Berger02] in the bibligraphy of the proposal).  There are
two main types of useful allocators: arena allocators that provide
higher performance over a limited region of the program and special
allocators that provide shared memory allocation or other special
allocation services.  Both require that the programmer have absolute
control over when the allocator is used and for what.  Imagine you
create a string which is intended to be put into shared memory and which
must allocate all of its memory from the same shared memory pool.  Now,
assume a typical manipulation function like this:

    void munge(std::string* s) {
        std::string tmp;
        // Create a value for tmp using segments of *s
        s->swap(tmp);  // Reflect changes into s
    }

    std::string* mySharedStringPtr =
        new(SharedMemAllocator) std::string(SharedMemAllocator);

    munge(mySharedStringPtr);

If swap exchanges the allocators, then the contents of
*mySharedStringPtr are no longer shared!  Worse, mySharedStringPtr
continues to point to a shared memory object which now contains a
pointer to unshared memory.

This example encapsulates the main principle in my allocator proposal:
allocators should be an attribute of the CONTAINER, not of the VALUE of
the container.  If we violate this abstraction -- if we let a common
external function tamper with an implementation decision on a given
container -- then we severely limit the usefulness of stateful
allocators, and allocators will remain a mysterious backwater used in
very narrow contexts.

I believe that the overhead imposed by adopting my proposal is well
within the norm for other parts of the standard library.  Our experience
is that the usefulness of allocators is dramatically increased by our
use of this model.  And the proposal still allows the old model to be
chosen if performance is more important than flexibility in a given
context.

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                       ]

Howard Hinnant wrote:

> Indeed it is the unequal (private buffer) application that motivates
> option 3 of lwg 431:
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1599.html
>
> If swap exchanges memory ownership between containers, then allocator
> state (which may be required to deallocate that memory) should follow
> the memory it owns.
>

Pablo has probably already addressed this point better than I can, but
as an average user, I don't agree with this solution.  When I've used
per-container allocators it has been to optimise cases where I have
specific knowledge about the lifetime of the subsystem.

Examples would be loading up an xml file using tinyxml or in per-render
operations, where the data is cleaned up after each render completes.
In both these examples, it would be a disaster if some of the resources
got out of sync and tried to hang around.  Its not the container
lifetime thats important here, its the overall subsystem lifetime.
Somewhere, in some other system, would live a different container that
is quite happy to hang around with my buffer allocator, but I want that
buffer back!

Although in this case a swap is slow I fail to see how any other
solution is valid.  The next best would be to throw an exception, but
why should correct code suddenly fail due to a lack of optimisation?  We
may as well start throwing exceptions if people insert near the front of
a vector.

I'd rather use swap knowing it is blindingly fast when possible, and
correct always.  All other solutions seem to end up with a swap that is
always blindingly fast, and correct when possible.

Geoff

---
[ 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                       ]

In article <fi2ge197lm9ttsmhb4r8v9cfjdmdq2joao@4ax.com>,
 Pablo Halpern <phalpern@halpernwightsoftware.org> wrote:

> Both require that the programmer have absolute
> control over when the allocator is used and for what.  Imagine you
> create a string which is intended to be put into shared memory and which
> must allocate all of its memory from the same shared memory pool.  Now,
> assume a typical manipulation function like this:
>
>     void munge(std::string* s) {
>         std::string tmp;
>         // Create a value for tmp using segments of *s
>         s->swap(tmp);  // Reflect changes into s
>     }
>
>     std::string* mySharedStringPtr =
>         new(SharedMemAllocator) std::string(SharedMemAllocator);
>
>     munge(mySharedStringPtr);
>
> If swap exchanges the allocators, then the contents of
> *mySharedStringPtr are no longer shared!  Worse, mySharedStringPtr
> continues to point to a shared memory object which now contains a
> pointer to unshared memory.

But the solution to this problem is already in common use today (and is
also in your paper):

    void munge(std::string* s) {
        std::string tmp(s->get_allocator());
        // Create a value for tmp using segments of *s
        s->swap(tmp);  // Reflect changes into s
    }

Sorry, but I'm not swayed by this argument.  Being careful in this way
to support non-equal allocators is old news to me (I've been doing it
for years).

> There are
> two main types of useful allocators: arena allocators that provide
> higher performance over a limited region of the program and special
> allocators that provide shared memory allocation or other special
> allocation services.

I've built arena allocators and not felt the need for such a drastic
redesign of the std::lib to make them safe and efficient.  If two
containers which are swapped (exchanging memory) also swap allocators,
the code continues to work whether or not the two allocators are equal
(point to the same arena).

I've not built shared memory allocators.  But I have had thoughtful
discussions with Ion Gaztanaga, author of Shmem on this subject.  I
understand that problems arise when different containers from different
shared memory segments are swapped.  But I also understand that this
problem does not exist when both shared memory allocators are in the
same segment (even if they are not equal).

O(N) swaps are no more correct than O(1) swaps with unequal allocators.
Either decision can result in broken code.  Hobbling all container swaps
with O(N) behavior when two allocators are not equal, just to support
the one case of different-segment shared memory allocators does not seem
like a good deal to me.  The existence of unequal arena allocators, and
same-segment but unequal shared memory allocators that will benefit from
O(1) swaps, combined with the O(N) performance gain and nothrow
exception guarantee strongly tilt the decision in favor of O(1) swap
imho.

Additionally, if container::swap is always O(1), then clients needing an
O(N) variant of the idea (say for different-segment shared memory
containers) can very easily accomplish it with an explicit
copy-assign-assign sequence -- no need to introduce a new name like
swap_value.  If he also needs strong exception safety, changing that to
copy-copy-swap-swap isn't overly burdensome.  This is all existing
interface, no new stuff to learn.

Otoh, if swap is sometimes O(N), the client that needs O(1) swap must
now rely on a new function with a different name (swap_move) that has
the functionality he normally expects out of swap (since 1998).  This
seems like an error prone interface to me.

Just my .02 (you asked). ;-)

-Howard

---
[ 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                       ]

In article
<42e96769$0$5397$5a62ac22@per-qv1-newsreader-01.iinet.net.au>,
 Geoff Carlton <gcarlton@iinet.net.au> wrote:

> Howard Hinnant wrote:
>
> > Indeed it is the unequal (private buffer) application that motivates
> > option 3 of lwg 431:
> >
> > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1599.html
> >
> > If swap exchanges memory ownership between containers, then allocator
> > state (which may be required to deallocate that memory) should follow
> > the memory it owns.
> >
>
> Pablo has probably already addressed this point better than I can, but
> as an average user, I don't agree with this solution.  When I've used
> per-container allocators it has been to optimise cases where I have
> specific knowledge about the lifetime of the subsystem.
>
> Examples would be loading up an xml file using tinyxml or in per-render
> operations, where the data is cleaned up after each render completes.
> In both these examples, it would be a disaster if some of the resources
> got out of sync and tried to hang around.  Its not the container
> lifetime thats important here, its the overall subsystem lifetime.
> Somewhere, in some other system, would live a different container that
> is quite happy to hang around with my buffer allocator, but I want that
> buffer back!
>
> Although in this case a swap is slow I fail to see how any other
> solution is valid.  The next best would be to throw an exception, but
> why should correct code suddenly fail due to a lack of optimisation?  We
> may as well start throwing exceptions if people insert near the front of
> a vector.
>
> I'd rather use swap knowing it is blindingly fast when possible, and
> correct always.  All other solutions seem to end up with a swap that is
> always blindingly fast, and correct when possible.

Thank you for your thoughtful reply.

My concern is that an O(N) swap is not always correct.  Such a swap can
invalidate code which depends on a nothrow exception safety guarantee
(as shown in a previous post).

Would it be possible for you to post demo code that expresses your
concern?  I do want to understand it better.

-Howard

---
[ 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,
Can I show a working example?  Good question!

I must admit I have never come across the case in the wild.  Swapping
whole vectors is something that I do rarely, and optimising a subsystem
using an allocator is similarly rare, so I've never yet seen an overlap.

Also after working around several examples, it is such an odd situation
that its hard to argue a case in which it strikes.  Playing around with
a short life expectant vector in such a way as swap is sort of like
playing with fire.

The simplest example is of TinyXml (improved to use allocators), except
for the fact that it doesn't use std containers and its std string is
well encapsulated.  As such I'll have to give an example where the
TiXmlNode's "value" string is publically accessable.

std::string replaceString;

void DoSomething(TiXmlNode* node)
{
 std::swap(node->value, replaceString);
}

void LoadData()
{
 // allocate in blocks of 1024 bytes and free at the end
 // all the tinyxml stuff is created using this allocator
 MultiPileAllocator myalloc(1024);

 {
  TiXmlDocument mydoc(&myalloc);
  mydoc.LoadFile("in.xml");
  DoSomething(mydoc.RootElement());
  mydoc.SaveFile("out.xml");
 }
}

Ok so here we create a structure of something, use it, then discard it.
    The problem is inadvertantly exchanging allocators with objects of a
different lifetime.

Interestingly many examples that I experimented with actually work fine
in VS7.1, since their implementation only does the quick swap if the
allocators are equal.

Geoff


Howard Hinnant wrote:

> Thank you for your thoughtful reply.
>
> My concern is that an O(N) swap is not always correct.  Such a swap can
> invalidate code which depends on a nothrow exception safety guarantee
> (as shown in a previous post).
>
> Would it be possible for you to post demo code that expresses your
> concern?  I do want to understand it better.
>
> -Howard
>
> ---
> [ 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                       ]
>

---
[ 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                       ]

Howard Hinnant <hinnant@metrowerks.com> wrote:

>> If swap exchanges the allocators, then the contents of
>> *mySharedStringPtr are no longer shared!  Worse, mySharedStringPtr
>> continues to point to a shared memory object which now contains a
>> pointer to unshared memory.
>
>But the solution to this problem is already in common use today (and is
>also in your paper):
>
>    void munge(std::string* s) {
>        std::string tmp(s->get_allocator());
>        // Create a value for tmp using segments of *s
>        s->swap(tmp);  // Reflect changes into s
>    }
>
>Sorry, but I'm not swayed by this argument.  Being careful in this way
>to support non-equal allocators is old news to me (I've been doing it
>for years).

But most people *haven't* done this for years.  I work with a lot of
intermediate-level C++ programmers and I can tell you that most of them
don't even know the purpose of the allocator argument in container
constructors!

If there were two types of standard swap (e.g. swap_value and
swap_move), then people would eventually learn to pick among them
carefully.  A well-written function prototype would have an associated
comment stating whether or not the allocator of the object being passed
in is likely to change, and this issue would be mute.

If I call a function that was written 5 years ago (or yesterday, even),
and if that function uses swap, and if swap exchanges the allocator, I'm
sunk.  Yes, there will be errors caused by the loss of the nothrow
guarantee, but much more rarely, IMO, because, as I show in the paper,
most of that code remains safe with the rollback guarantee. (I
acknowlege that the example in your previous post is an exception)

>> There are
>> two main types of useful allocators: arena allocators that provide
>> higher performance over a limited region of the program and special
>> allocators that provide shared memory allocation or other special
>> allocation services.
>
>I've built arena allocators and not felt the need for such a drastic
>redesign of the std::lib to make them safe and efficient.  If two
>containers which are swapped (exchanging memory) also swap allocators,
>the code continues to work whether or not the two allocators are equal
>(point to the same arena).

I'd be curious to know how you control when memory is returned from the
arena allocator if the allocator can suddenly end up used by an
unrelated object.  Have you ever written an arena allocator that
allocates from a stack buffer?  You should; it's fun and very fast.  But
don't do it if you expect the allocator to live after the stack frame is
gone.

You seem to be dismissing the need to control allocator lifetime, yet in
our work we need this all the time (the stack-based allocators is one of
our staples).  I say from experience as a client (not just a library
developer) that within a short time, the principle of allocators not
changing gets into your bones!  The question is simple: do you want
control over memory or not?  If not, then don't use allocators.  If so,
then you need to ensure that the allocator is used when you want it and
ONLY when you want it.  Otherwise, what's the point?

>I've not built shared memory allocators.  But I have had thoughtful
>discussions with Ion Gaztanaga, author of Shmem on this subject.  I
>understand that problems arise when different containers from different
>shared memory segments are swapped.  But I also understand that this
>problem does not exist when both shared memory allocators are in the
>same segment (even if they are not equal).

So? What if one of the allocators isn't even a shared memory allocator,
as in my example?  The fact that *some* unequal allocators have *some*
level of compatibility isn't very compelling.

>O(N) swaps are no more correct than O(1) swaps with unequal allocators.
>Either decision can result in broken code.  Hobbling all container swaps
>with O(N) behavior when two allocators are not equal, just to support
>the one case of different-segment shared memory allocators does not seem
>like a good deal to me.  The existence of unequal arena allocators, and
>same-segment but unequal shared memory allocators that will benefit from
>O(1) swaps, combined with the O(N) performance gain and nothrow
>exception guarantee strongly tilt the decision in favor of O(1) swap
>imho.

Seems like a stretch to me. Remember, since allocators are not part of
the *type* of the object, the unequal allocators my not even belong to
the same family (i.e. their allocator_implementation objects may belong
to different derived classes). In my experience, this is more often the
case than not.

>Additionally, if container::swap is always O(1), then clients needing an
>O(N) variant of the idea (say for different-segment shared memory
>containers) can very easily accomplish it with an explicit
>copy-assign-assign sequence -- no need to introduce a new name like
>swap_value.  If he also needs strong exception safety, changing that to
>copy-copy-swap-swap isn't overly burdensome.  This is all existing
>interface, no new stuff to learn.

Everything in the standard library can be accomplished in user code.  So
what?  If its not a standard function, then it won't become a standard
practice.  Even if I accept that swap() should do a swap_move (which I
don't), a version of swap that does a swap_value is essential to
promoting the writing of correct code (i.e. where the programmer
thoughtfully chooses the correct swap).  Moreover, swap_value can be
optimized for certain cases.  For example vector<pod-type>::swap_value
can be optimized by the library vendor to use much less auxiliary
storage.

>Otoh, if swap is sometimes O(N), the client that needs O(1) swap must
>now rely on a new function with a different name (swap_move) that has
>the functionality he normally expects out of swap (since 1998).  This
>seems like an error prone interface to me.

The 1998 standard swap has the qualities of both swap_move and
swap_value because the standard allows all allocators of a given type to
be assumed equal.  Which ever form of swap we choose will break
someone's 1998 assumption.  Even in implementations that allow unequal
allocators, some vendors chose the swap_move (nothrow) semantic while
others chose the swap_value (allocators don't change) semantic.

Unfortunately, I think the swap discussion is detracting attention from
other parts of the proposal.  Even if I lose the swap argument, I
believe the rest of the proposal has merit and should be discussed
(unless you think it's ready for adoption as-is :-) ).

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                       ]

In article <kibje1dvqt54imt1gfmli3a7j8d0top4u8@4ax.com>,
 Pablo Halpern <phalpern@halpernwightsoftware.org> wrote:

> If there were two types of standard swap (e.g. swap_value and
> swap_move), then people would eventually learn to pick among them
> carefully.  A well-written function prototype would have an associated
> comment stating whether or not the allocator of the object being passed
> in is likely to change, and this issue would be mute.

Today the standard only blesses equal-allocators.  And the following
functionality exists today:

Given standard containers of type C, values c1 and c2:

To exchange memory ownership you do:

swap(c1, c2);

To exchange values without exchanging memory ownership you do:

{C tmp(c1); c1 = c2; c2 = tmp;}

I don't think we need new names for these simple operations.  And I
really don't think we want to change the observable semantics of either
one.  And making either one act like the other would be changing
observable semantics.  Specifically, if swap ceases to exchange memory
ownership, changes include:

1. Exception safety goes from nothrow to basic, unless more memory is
thrown at the problem to create a strong guarantee.

2. Outstanding iterators/pointers/references are now invalidated.

3.  For vector and string, there are observable differences via the
capacity() member (capacities are no longer exchanged).

4.  Performance goes from O(1) to O(N).

5.  Memory swell goes from 0 to N, or if we adopt the strong variant 2N.

What we do need to do is add support for unequal allocators.  If in
doing that, we can preserve the interface (with existing semantics) we
already have today, then I believe the programming community will be
better off for it.  I believe it can be done.

> I'd be curious to know how you control when memory is returned from the
> arena allocator if the allocator can suddenly end up used by an
> unrelated object.  Have you ever written an arena allocator that
> allocates from a stack buffer?

Yes.  Speaking not just about allocators and containers, but more
broadly, whenever I give a stack based pointer or reference to an
object, I am careful to note the relative lifetimes.  I am careful when
I give an arena allocator to a container, and I am careful when I give a
stack-based rdbuf to a stream.

> You seem to be dismissing the need to control allocator lifetime,

Not at all.  I understand that issue and have written much code to
ensure such lifetime issues are not violated.

I am in sympathy with your motivations.  But I believe we can achieve
some (not all) of your objectives with far smaller changes to the
std::lib.

Specifically I believe we can seamlessly support non-equal arena
allocators, and with some restrictions, non-equal shared memory
allocators.

I do not believe we can support a polymorphic default allocator, nor do
I believe we can reverse the decision made a decade ago that the choice
of allocator effects a container's type (I don't mean to imply that we
can't support user-defined polymorphic allocators).

-Howard

---
[ 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 morning I posted a revision to my allocator proposal at:
http://home.earthlink.net/~phalpern/cpp/HalpernAllocatorProposal.pdf

This is a serious and significant proposal aimed at making allocators
more useful and, in the process, resolving issue 431 (swapping
containers with unequal allocators).

Don't let the length of the paper scare you.  It is very conversational
and a reasonably quick read.  The last few pages are the formal part of
the proposal.  I hope to integrate feedback from this newsgroup and
submit it to the committee in tine for consideration at their October
meeting.  I am not certain I can make it to the October meeting myself,
so I am still looking for a partner to champion this proposal.
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                       ]

In article <7ibbe1hu4omoqsfibanas46idf9u6i5hjo@4ax.com>,
 phalpern@halpernwightsoftware.org (Pablo Halpern) wrote:

> This morning I posted a revision to my allocator proposal at:
> http://home.earthlink.net/~phalpern/cpp/HalpernAllocatorProposal.pdf

In private correspondence Pablo asked me to express my concerns
publicly.  So here goes...

I have serious reservations about making the default allocator a
non-empty class (as proposed).  The current overhead for the Freescale
vector<T> (with default allocator) is 3 words.  If I am not mistaken,
this proposal would mandate a 4 word overhead.

That may not sound like much at first, but when considering containers
of containers, a 33% jump in space overhead is significant.  And the
overhead jump for other containers (that often store multiple
allocators) can be worse:  list and set overhead jumps from 3 words to 5
words, 67% (in the Freescale implementation).

All that being said, I'm very much in favor of improved support for
client-defined stateful allocators, including the ability for different
objects of the same type to get their memory from different sources.
And I'm also in favor of support for unequal allocators (e.g. private
buffers).

Indeed it is the unequal (private buffer) application that motivates
option 3 of lwg 431:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1599.html

If swap exchanges memory ownership between containers, then allocator
state (which may be required to deallocate that memory) should follow
the memory it owns.

This is analogous to tr1::shared_ptr and its custom deleter.  The memory
and the deleter are paired at construction time.  And though one can
pass around ownership of this memory from shared_ptr to shared_ptr, you
can not separate the memory from the deleter that owns it.  If you
transfer memory ownership, you also implicitly transfer ownership of the
paired deleter too.

std::unique_ptr will be formally proposed in a paper this fall, and will
also have custom deleter support, and will also inseparably bind the
memory and its deleter.

Once a container's allocator allocates memory, then that allocator is
just a deleter, and must be inseparably bound to that allocated memory
(if we are going to support unequal allocators, and transfer of memory
ownership among containers).

If instead we refuse to transfer memory ownership among containers (and
so make swap O(N), or sometimes O(N)), then we will have a situation
similar to list<T>::size().  People won't be able to use it because just
the threat of something changing from O(1) to O(N) is enough to make
something useless.  And to make things even worse, it takes what should
be a non-throwing operation and turns it into something that could
throw.  This completely invalidates code such as:

template <class T1, class T2>
inline
std::pair<T1, T2>&
strong_assign_pair(std::pair<T1, T2>& x, std::pair<T1, T2> y)
{
    x.first.swap(y.first);
    x.second.swap(y.second);  // assumes nothrow
    return x;
}

All that being said, if an allocator author really doesn't want his
allocator to swap when the container swaps, then that is trivial to
accomplish:

inline void swap(my_allocator&, my_allocator&) {}

The proposed swap (formally swap_value) with the strong exception
guarantee is extravagantly expensive when allocators are unequal.  It
requires a complete copy to be made of both containers, temporarily
requiring 4 containers in memory at once.  This goes completely against
the current philosophy in the standard:  support the strongest exception
safety guarantees you can <em>that don't incur extra overhead</em>.

Quite frankly if my swap suddenly decided it needed to make temporary
copies of both arguments, I'd much rather get an assert or an exception
to let me know.  Then if I really wanted to go to that expense, I'd make
it explicit rather than hiding it under something named swap.

An O(N) swap, max_size, or size (all allowed by the standard) is so
counterintuitive that it is dangerous, especially to generic code.  It
is like putting operator[](size_t) on std::list.  Just say no. ;-)

-Howard

---
[ 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                       ]