Roman Lechtchinsky <wolfro@cs.tu-berlin.de> wrote in article
<324BF7CB.6CA3@cs.tu-berlin.de>...
>...The January WP states:
>
>2 Default arguments shall not be specified in a declaration or a defini-
>  tion of a specialization. [temp.param]
>
>I suppose this means that the following is illegal:
>
>template <class Key, class T, class Compare = less<Key>,
>class Allocator = allocator>
>class map;   // from [lib.map]
>
>template <class Key, class T, class Compare = less<Key> >
>class map<Key, T, Compare, allocator>;

You're right, it is illegal. However, the following is legal:

template <class Key, class T, class Compare>
clas map<Key, T, Compare, allocator>;

... and it does what you apparently intend.

Disallowing default arguments for specializations is like disallowing
default arguments in the definition of a function declared to have a
default argument. It's just a way of making sure that the default arguments
agree in all versions of the template. If any of the template parameters
remain "unbound," as Compare does above, it uses the same default argument
as the unspecialized template.

I looked through the WP and couldn't find a paragraph that states this
explicitly, but I cannot imagine any other sensible interpretation of this
rule. Does anybody know the citation?
--
Bradd W. Szonye
bradds@concentric.net
http://www.concentric.net/~bradds
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Stan Friesen wrote:
>
> In article <3247F1F9.11F2@cds.duke.edu>, Max TenEyck Woodbury <mtew@cds.duke.edu> writes:
> |>
> |> YIKES! This is scarry!  The normal case would be comparison
> |> between default allocators and they would always compare equal.
> |> That would be 99+% of the cases and you call that 'very rare ...
> |> so the optimization isn't worthwhile.'
>
> Nope.  That is NOT what he said.
>
> With the *default* allocator, the system will use the *partial* *specialization*
> that simply does not even *attempt* to do the run time comparison.
>

Excuse me, but what kind of magic would it use to avoid doing the comparison?
With run time differentiation, the comparison has to be in the algorithms (not
in the container or allocator, in the algorithm).  Unless a mechanism, which
does not currently exist, is introduced to distinguish between allocators with
run-time differentiation and allocators without run-time differentiation, and
the algorithm is selected on the basis of that mechanism, every algorithm that
does pointer assignment must test the allocator for compatibility.  Without
that mechanism, the default allocator, even though it does not require run-time
differentiation would use the algorithms with the allocator comparison in them.
With that mechanism, partial specialization might be a viable way to distinguish
the different algorithms required, but that mechanism is missing from the
standard.

> Thus 99+% of the case will simply lack the run time check altogether.
>

99+% of the cases will have a meaningless check unless a lot of complicated
extra mechanism is introduced to make it possible to skip the tests.

> Of the remaining <1% of the cases (the *user**defined* allocators), only
> a few will actually behave like the default allocator and be comparison
> independent.  Thus the case where the optimization of eliminating the
> generated code for an unused comparison is useful will occur in < 0.1%
> of the cases, probably far less.
>

Most user defined allocators will be there to handle such things as the
difference between __near, __far and __huge pointers in PC applications in
a type safe fashion.  Most of them will not make any use of run-time
differentiation.  For them, run-time differentiation would be a waste of
time.

Further, if run-time differentiation is not mandated by the standard, a
user who wants it can add it by putting the test in a specialized pointer
assignment operator and adding other mechanism as needed.  Bluntly,
run-time differentiation of address spaces is a function that belongs
with specialized types of pointers, not in the allocator mechanism.
Allocators are the mechanism that will drag in those specialized pointer
types, but the allocator itself need not be involved in that kind of
run-time differentiation.

mtew@cds.duke.edu
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

James Kanze US/ESC 60/3/141 #40763 wrote:
>=20
> The default allocator should be handled by partial specialization of th=
e
> template.  In that case, there is no particular optimization needed on
> the part of the compiler.
>=20

I wonder if this is possible. The January WP states:

2 Default arguments shall not be specified in a declaration or a defini=AD
  tion of a specialization. [temp.param]

I suppose this means that the following is illegal:

template <class Key, class T, class Compare =3D less<Key>,
class Allocator =3D allocator>
class map;   // from [lib.map]

template <class Key, class T, class Compare =3D less<Key> >
class map<Key, T, Compare, allocator>;

Maybe someone could explain why this restriction is necessary?

Bye

Roman


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

In article <3247F1F9.11F2@cds.duke.edu>, Max TenEyck Woodbury <mtew@cds.duke.edu> writes:
|>
|> YIKES! This is scarry!  The normal case would be comparison
|> between default allocators and they would always compare equal.
|> That would be 99+% of the cases and you call that 'very rare ...
|> so the optimization isn't worthwhile.'

Nope.  That is NOT what he said.

With the *default* allocator, the system will use the *partial* *specialization*
that simply does not even *attempt* to do the run time comparison.

Thus 99+% of the case will simply lack the run time check altogether.

Of the remaining <1% of the cases (the *user**defined* allocators), only
a few will actually behave like the default allocator and be comparison
independent.  Thus the case where the optimization of eliminating the
generated code for an unused comparison is useful will occur in < 0.1%
of the cases, probably far less.

--
swf@elsegundoca.ncr.com  sarima@ix.netcom.com

The peace of God be with you.
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Reposting article removed by rogue canceller.

I missed the first part of the discussion...but what exactly is the run
time problem with allocators?

Is someone complaining about the fact that member functions such as
address(), etc. are non-static member functions rather than static ones--
and that there has to be an allocator object which they are bound to?

I don't see how this is a problem with any decent compiler.

Just do

template <class Type, class Allocator = allocator >
class Foo
{
 //
        // Standard set of typedefs, to define pointer, reference, etc.
 //
        pointer bar ( value_type baz) { return Allocator().address(baz); }
 // instead of Allocator::address(baz);
};

This allows run time determination if necessary.  However, one would hope
that if the Allocator() being used is a "simple" one (trivial default
constructor, no data, all member functions inline), that any "overhead"
involved in the construction of the object and the member function call
would be optimized out of existence, and that the resulting code would be
just as efficient as the static member function call.

Am I putting too much faith in the optimizing ability of compilers here?

Or am I missing the original poster's point entirely?

Scott



--
/--------------------------------------------------------------------------\
|Scott Johnson -- Professional (sometimes) SW Engineer and all-purpose Geek|
|I don't speak for nobody but myself, which everyone else is thankful for  |
\--------------------------------------------------------------------------/
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Max TenEyck Woodbury <mtew@cds.duke.edu> writes:

>
> James Kanze US/ESC 60/3/141 #40763 wrote:

> > While I am at it, I will respond to a point you bring up later as well.
> > The efficient solution I describe does not require any particular
> > optimization on the part of the compiler.  It does require that the
> > compiler support partial specialization.  But this is required by the
> > standard anyway.  Partial specialization is not an optimization, but a
> > way of telling the compiler: if this template instantiation meets the
> > following criteria, use this implementation instead of the more general
> > one.
> >
>
> I believe that this line of argument differes from some of
> the previous presentations on this subject.  More specificialy
> they differ from statements that I believe were yours, however
> I did not keep a careful record of exactly who said what so I
> could be wrong.  Those arguments followed the outline that
> telling the compiler that a certain run time test would always
> come out a certain way would cause the compiler to suppress
> generating code for the untaken branch and that it should not
> even mention that suppression in a diagnostic.  The test in
> question was the equality test on the allocator.  Partial
> specialization didn't come into it at that level.

Just to clarify, I actually mentioned both possibilities.  The
specialization works for the standard case, where the user uses the
default allocator.  The compiler optimization would only come into play
in the case of a user defined allocator which always compared equal.
IMHO, such cases should be very rare, and so the optimization isn't
worthwhile.

    [Concerning my example using shared memory...]
> I'm not at all convinced.  The shared memory stings seem to be
> rare beasties in this applications and might as well be a
> seperate type.  Where they interact with MyStrings, the
> appropriate conversion routines should be called.  Being a
> shared memory application, they should have volitile attribute
> in a number of critical places anyway and that alone might
> have significant impact the algorithms.  Including them in a
> map that was not completely shared memory aware would be
> disaster in the making...

I'm not sure I disagree.  But this is *THE* application for user defined
allocators; without allowing run-time testing of equivalence of the
allocators, they become almost worthless.

I do agree about the problems concerning locking.  Basically, this
strategy will only work if some sort of a global lock is used; the
application takes the lock for the complete time of the request, and not
just on a strick as needed basis.  While this is certainly the easiest
implementation for communicating processes to use shared memory, it has
other drawbacks, and is certainly not the only solution.

Your comments concerning the shared map are correct with regards to the
STL map.  The map maintains deep copies, and uses the default copy
constructor to create them.  Since, as I pointed out in my explaination,
the default copy constructor always constructs in the normal heap,
there's trouble in the making.  Ideally, the STL map should use pass its
allocator to the copy constructor; in practice, this means that it could
not be used for objects which do not have an allocator parameter (which
normally would include all objects that do not use dynamic memory, and
of course, all of the built-in types).

I'll admit that I'm curious myself as to what the committee thinks about
this.  It seems like a major argument in favor of your point of view.
(I also liked your explination of what an allocator is which followed.)

--
James Kanze           (+33) 88 14 49 00          email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs Bourgeois, 67000 Strasbourg, France
Conseils en informatique industrielle --
                            -- Beratung in industrieller Datenverarbeitung
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

J. Kanze wrote:
>
> Max TenEyck Woodbury <mtew@cds.duke.edu> writes:
>
> >
> > James Kanze US/ESC 60/3/141 #40763 wrote:
>
> > > While I am at it, I will respond to a point you bring up later as well.
> > > The efficient solution I describe does not require any particular
> > > optimization on the part of the compiler.  It does require that the
> > > compiler support partial specialization.  But this is required by the
> > > standard anyway.  Partial specialization is not an optimization, but a
> > > way of telling the compiler: if this template instantiation meets the
> > > following criteria, use this implementation instead of the more general
> > > one.
> > >
> >
> > I believe that this line of argument differes from some of
> > the previous presentations on this subject.  More specificialy
> > they differ from statements that I believe were yours, however
> > I did not keep a careful record of exactly who said what so I
> > could be wrong.  Those arguments followed the outline that
> > telling the compiler that a certain run time test would always
> > come out a certain way would cause the compiler to suppress
> > generating code for the untaken branch and that it should not
> > even mention that suppression in a diagnostic.  The test in
> > question was the equality test on the allocator.  Partial
> > specialization didn't come into it at that level.
>
> Just to clarify, I actually mentioned both possibilities.  The
> specialization works for the standard case, where the user uses the
> default allocator.  The compiler optimization would only come into play
> in the case of a user defined allocator which always compared equal.
> IMHO, such cases should be very rare, and so the optimization isn't
> worthwhile.
>

YIKES! This is scarry!  The normal case would be comparison
between default allocators and they would always compare equal.
That would be 99+% of the cases and you call that 'very rare ...
so the optimization isn't worthwhile.'  I wonder what you
consider common...  (OK.  I'm over reacting, but you're simply
wrong here.)

>     [Concerning my example using shared memory...]
> > I'm not at all convinced.  The shared memory stings seem to be
> > rare beasties in this applications and might as well be a
> > seperate type.  Where they interact with MyStrings, the
> > appropriate conversion routines should be called.  Being a
> > shared memory application, they should have volitile attribute
> > in a number of critical places anyway and that alone might
> > have significant impact the algorithms.  Including them in a
> > map that was not completely shared memory aware would be
> > disaster in the making...
>
> I'm not sure I disagree.  But this is *THE* application for user defined
> allocators; without allowing run-time testing of equivalence of the
> allocators, they become almost worthless.
>

Let's try the mirror approach.  Assume that each memory pool
has a seperate allocator type.  Operation within pools are cheap
and shallow copies are done where possible.  Operations between
different pool allocators and between the pool and default
allocator invoke a conversion routine.  The conversion routine
gets to decide if a deep or shallow copy is needed.  Algorithms
do not have to worry about allocator differences; they just use
the routines allocators provide if they need to.  The users code
is very much like any other code that deals with objects of
inter-convertable types and will contain no more (and no fewer)
supprises than any code of this type is likely to have.

The way I see it, allocators were an answer to the problem with
pointers in segmented architectures.  There you have these __near
and __far pointers and you have to put up a guard to make sure
you don't mix them up too much.  The problems with segmented
pointers are similar enough to the shared memory problem that the
one abstraction can handle both sets of solutions.  However, where
shared memory problems are fortunately rare, problems with
segmented pointers are all too common in a fairly large class of
application.

> I do agree about the problems concerning locking.  Basically, this
> strategy will only work if some sort of a global lock is used; the
> application takes the lock for the complete time of the request, and not
> just on a strick as needed basis.  While this is certainly the easiest
> implementation for communicating processes to use shared memory, it has
> other drawbacks, and is certainly not the only solution.
>
> Your comments concerning the shared map are correct with regards to the
> STL map.  The map maintains deep copies, and uses the default copy
> constructor to create them.  Since, as I pointed out in my explaination,
> the default copy constructor always constructs in the normal heap,
> there's trouble in the making.  Ideally, the STL map should use pass its
> allocator to the copy constructor; in practice, this means that it could
> not be used for objects which do not have an allocator parameter (which
> normally would include all objects that do not use dynamic memory, and
> of course, all of the built-in types).
>
> I'll admit that I'm curious myself as to what the committee thinks about
> this.  It seems like a major argument in favor of your point of view.
> (I also liked your explination of what an allocator is which followed.)

The locking belongs in the pointer operators, which are defined in
association with the allocator, but is not strictly a part
of the allocator itself.  The actual lock is either in the pointer
(not likely), in the target object or global.  Any lock in the
container or string would be to lock the string attributes or the
container itself, not to lock the contents of the string or container.
It might be possible to put such a lock in the allocator, but it
really should be an object in its own right so it can be included
in the target objects as well as the container, but that's up to the
user.

As for the problem with map copy, the routines in an allocator are
there to split memory allocation away from object construction and
to split object destuction away from memory deallocation.  There is
no requirement in respect to the usual new and delete and new[] and
delete[] operators.  If you don't want the copy on the heap, you
should be able to override the definition of those operators to get
the desired effect.  Those overrides probably belong in the
allocator.  (No, I didn't check the spec to make sure that is in
fact the case.  I'm just stating an opinion.)

mtew@cds.duke.edu


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

In article <R.521at0$c65@shelob.aracnet.com> sj@aracnet.com (Scott
Johnson) writes:

|> I missed the first part of the discussion...but what exactly is the run
|> time problem with allocators?

The problem being discussed concerns the fact that two instances of the
same allocator type are not necessarily equivalent.  And that an
instance of the allocator is a parameter to all of the constructors.

This leads to the "problem" that when assigning one object to another, a
deep copy must be used if the allocators are not equivalent.

The argument for this behavior is that it allows the user to write code
such as a = b without worrying whether the corresponding objects are in
the same free space arena; the implementation does a run-time check, and
uses deep copy if necessary.  Also, that this behavior does not cost
anything for the normal case of using the default allocator type, given
a good implementation with partitial specialization for the default
allocator.

The argument against is that this introduces excessive (or at least
extra) complexity, and doesn't really buy us as much as it should, given
that, e.g.: it is not sufficient to create a e.g. vector with the correct
allocator if the contained objects also allocate memory dynamically,
since vector will create the member objects using the default allocator
object, and not its own allocator object.

--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils,    tudes et r   alisations en logiciel orient    objet --
                -- A la recherche d'une activit    dans une region francophone
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

James Kanze US/ESC 60/3/141 #40763 wrote:
>
> In article <R.521at0$c65@shelob.aracnet.com> sj@aracnet.com (Scott
> Johnson) writes:
>
> |> I missed the first part of the discussion...but what exactly is the run
> |> time problem with allocators?
>
> The problem being discussed concerns the fact that two instances of the
> same allocator type are not necessarily equivalent.  And that an
> instance of the allocator is a parameter to all of the constructors.
>

This feature was introduced by the draft C++ standard.  It is not in the
original STL.

> This leads to the "problem" that when assigning one object to another, a
> deep copy must be used if the allocators are not equivalent.
>

Actually, the problem is more with the assignment via pointers than
with ordinary object level assignments.

> The argument for this behavior is that it allows the user to write code
> such as a = b without worrying whether the corresponding objects are in
> the same free space arena; the implementation does a run-time check, and
> uses deep copy if necessary.  Also, that this behavior does not cost
> anything for the normal case of using the default allocator type, given
> a good implementation with partitial specialization for the default
> allocator.
>

The cost is part of the question in dispute.  It only costs nothing
if the result of the allocator comparison is available at compile
time and if the compiler is smart enough to eliminate the redundant
code.  This is a common situation but may not be common enough to
warrent the extra complexity, especially if equivalent function can
be produced by a simpler mechanism.

Technically, the problem is a bit deeper than just free space
management.  Allocators are a hook for hanging all the different
address space issues on.  That includes managing different kinds
of pointers in 16-bit PC applications as well as the more esoteric
shared memory applications that supply the usual working examples.

> The argument against is that this introduces excessive (or at least
> extra) complexity, and doesn't really buy us as much as it should, given
> that, e.g.: it is not sufficient to create a e.g. vector with the correct
> allocator if the contained objects also allocate memory dynamically,
> since vector will create the member objects using the default allocator
> object, and not its own allocator object.
>

There is also an issue around the level of abstraction allocators
represent.  Until the indroduction of run-time differentiation,
allocators were a place to hang type definitions and a few inline
function templates.  It was a hook in a corner (primarily the
conversion routines) that you didn't have to worry about if you
didn't need to use it, and a safety check on pointer assignments.
With run time differentiation, anybody who writes an assignment
via pointers has to check the allocator equivalence if they don't
do a deep copy every time.  It also weakened the power of the
compile time safety checks since there can now be incompatible
pointer assignments that can only be checked at run time.

mtew@cds.duke.edu
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

In article <3247F1F9.11F2@cds.duke.edu> Max TenEyck Woodbury
<mtew@cds.duke.edu> writes:

|> J. Kanze wrote:

|> > Just to clarify, I actually mentioned both possibilities.  The
|> > specialization works for the standard case, where the user uses the
|> > default allocator.  The compiler optimization would only come into play
|> > in the case of a user defined allocator which always compared equal.
|> > IMHO, such cases should be very rare, and so the optimization isn't
|> > worthwhile.
|> >

|> YIKES! This is scarry!  The normal case would be comparison
|> between default allocators and they would always compare equal.
|> That would be 99+% of the cases and you call that 'very rare ...
|> so the optimization isn't worthwhile.'  I wonder what you
|> consider common...  (OK.  I'm over reacting, but you're simply
|> wrong here.)

Not overreacting, but misinterpreting.  (I guess I wasn't that clear.)

The default allocator should be handled by partial specialization of the
template.  In that case, there is no particular optimization needed on
the part of the compiler.

The only time the special compiler optimization is a win is when the
user provides an allocator type (for which there is, of course, no
partial specialization), and all instances of this allocator type always
compare equal.

Given the current specifications, IMHO, this case should, in fact, never
occur.  As far as I can tell, the user defined allocator *MUST* provide
a constructor which can be called with a single argument of the default
allocator type.  Otherwise, the classes will not compile, since the
default argument for the allocator parameter will not have the correct
type.  But to be useful, a user defined allocator type must do something
different, and presumably incompatible, with the default allocator type.
Thus be able to distinguish between the two.

|> >     [Concerning my example using shared memory...]
|> > > I'm not at all convinced.  The shared memory stings seem to be
|> > > rare beasties in this applications and might as well be a
|> > > seperate type.  Where they interact with MyStrings, the
|> > > appropriate conversion routines should be called.  Being a
|> > > shared memory application, they should have volitile attribute
|> > > in a number of critical places anyway and that alone might
|> > > have significant impact the algorithms.  Including them in a
|> > > map that was not completely shared memory aware would be
|> > > disaster in the making...
|> >
|> > I'm not sure I disagree.  But this is *THE* application for user defined
|> > allocators; without allowing run-time testing of equivalence of the
|> > allocators, they become almost worthless.

|> Let's try the mirror approach.  Assume that each memory pool
|> has a seperate allocator type.  Operation within pools are cheap
|> and shallow copies are done where possible.  Operations between
|> different pool allocators and between the pool and default
|> allocator invoke a conversion routine.

This is precisely the problem.  The conversion routine makes some
algorithms awkward.  More importantly, it means that e.g.: I cannot sort
a set, or for that matter, even create a set of pointers to strings
where some of the strings are in shared memory, and others not.

As far as I can tell, the dynamic testing of the allocator is a way of
getting around the fact that templates use compile-time type checking.
An alternative solution would have been to create a base class without
the allocator, then derive a distinct class for each distinct allocator
type.  Functions manipulating the base class would get some sort of
dynamic adaptation to the correct allocator.

|> The conversion routine
|> gets to decide if a deep or shallow copy is needed.

How do you write a generic function which can determine this.  If the
function uses something like "c1 = Container( c2.begin() , c2.end() )",
then a deep copy gets called everytime.  And if it just uses assign, c1
and c2 must have the same type.  So in fact, you need two distinct
functions.

|> Algorithms
|> do not have to worry about allocator differences; they just use
|> the routines allocators provide if they need to.  The users code
|> is very much like any other code that deals with objects of
|> inter-convertable types and will contain no more (and no fewer)
|> supprises than any code of this type is likely to have.

|> The way I see it, allocators were an answer to the problem with
|> pointers in segmented architectures.  There you have these __near
|> and __far pointers and you have to put up a guard to make sure
|> you don't mix them up too much.  The problems with segmented
|> pointers are similar enough to the shared memory problem that the
|> one abstraction can handle both sets of solutions.  However, where
|> shared memory problems are fortunately rare, problems with
|> segmented pointers are all too common in a fairly large class of
|> application.

I'll admit that the problem of segmented pointers never occured to me.
When I last used an 80x86 architecture, I just compiled everything in
large, and didn't worry about it.  IMHO, the use of near pointers is an
optimization; the compiler/linker should figure it out as part of the
optimization process, rather than my having to worry about it.

I also find it hard that problems of segmented memory would have
preoccupied the committee to this point.  All of the newer Windows
systems use 32 bit flat addressing (I think), so the problem is no
longer present for the Intel architecture.  (There are, of course,
people using 16 bit 80186's in embedded systems, controllers, etc.  I
don't think that the committee introduced the compication of allocators
just for them, however.)

|> > I do agree about the problems concerning locking.  Basically, this
|> > strategy will only work if some sort of a global lock is used; the
|> > application takes the lock for the complete time of the request, and not
|> > just on a strick as needed basis.  While this is certainly the easiest
|> > implementation for communicating processes to use shared memory, it has
|> > other drawbacks, and is certainly not the only solution.
|> >
|> > Your comments concerning the shared map are correct with regards to the
|> > STL map.  The map maintains deep copies, and uses the default copy
|> > constructor to create them.  Since, as I pointed out in my explaination,
|> > the default copy constructor always constructs in the normal heap,
|> > there's trouble in the making.  Ideally, the STL map should use pass its
|> > allocator to the copy constructor; in practice, this means that it could
|> > not be used for objects which do not have an allocator parameter (which
|> > normally would include all objects that do not use dynamic memory, and
|> > of course, all of the built-in types).
|> >
|> > I'll admit that I'm curious myself as to what the committee thinks about
|> > this.  It seems like a major argument in favor of your point of view.
|> > (I also liked your explination of what an allocator is which followed.)

|> The locking belongs in the pointer operators, which are defined in
|> association with the allocator, but is not strictly a part
|> of the allocator itself.  The actual lock is either in the pointer
|> (not likely), in the target object or global.  Any lock in the
|> container or string would be to lock the string attributes or the
|> container itself, not to lock the contents of the string or container.
|> It might be possible to put such a lock in the allocator, but it
|> really should be an object in its own right so it can be included
|> in the target objects as well as the container, but that's up to the
|> user.

I don't think so.  This is like putting locking in the operator<< for
IO.  IMHO, the locking is, and should remain, an application problem.
Only the application can determine what is critical, and what isn't.
(The simplest solution, of course, is just to lock the entire shared
resources for each individual request.  Not optimal, but sufficient for
many problems.)

|> As for the problem with map copy, the routines in an allocator are
|> there to split memory allocation away from object construction and
|> to split object destuction away from memory deallocation.  There is
|> no requirement in respect to the usual new and delete and new[] and
|> delete[] operators.  If you don't want the copy on the heap, you
|> should be able to override the definition of those operators to get
|> the desired effect.  Those overrides probably belong in the
|> allocator.  (No, I didn't check the spec to make sure that is in
|> fact the case.  I'm just stating an opinion.)

If I have understood correctly, I think you are correct.  The problem in
map, set, etc. as currently specified in the standard is that when
copying the objects into the container, they use the default copy
constructor, which is passed the default argument "allocator()", i.e.: a
*default* allocator, and not the allocator of the container.  And I do
not see any way of specifying and/or implementing them so that they
would copy using their own allocator, but would still work for types not
having an allocator parameter.

Because of this, and the problem with the default argument, I have
actually changed my opinion to agree with you.  Actually, without your
points concerning the allocator as a convenient depository for the
typedef's, and a convenient mechanism for separating allocation from
destruction, I would argue for removing it entirely.

I would be seriously interested in hearing from some of the committee
members who were present at the discussions where the current rules were
adopted.  The committee obviously considered the fact that the choice
deep/shallow copy would depend on whether the allocators tested equal,
since they made the complexity of some operations dependant on the
results of comparing allocators.  I'd like to understand the rationale
behind the default argument.  Is the absense of a constructor using the
default allocator type a simple oversight in the wording of the
standard, or is there something I'm missing here?  I'd also like to know
the committee's position concerning things like:

 typedef basic_string< wchar_t ,
                       string_char_traits< wchar_t > ,
                          MyAlloc >
                     MyString ;
 vector< MyString , MyAlloc >
                     v( MyAlloc( someSpecialPool ) ) ;

>From all that I can see, the actual MyString's in v will allocate memory
using the default parameter, even though I have requested "v" to get all
of its memory from "someSpecialPool".

Anyway, I'd like to thank you for clarifying my own thinking on this
subject.
--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils,    tudes et r   alisations en logiciel orient    objet --
                -- A la recherche d'une activit    dans une region francophone
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Max TenEyck Woodbury <mtew@cds.duke.edu> wrote:

> However, they should be an
> exclusively compile time mechanism.

FWIW I agree. Until now I thought that the use of allocators in the
standard library was 100% compiletime. Thanks for hilighting this
problem.

> Let's
> fix the problem now rather than later.


--
Lars Farm, lars.farm@ite.mh.se
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Max TenEyck Woodbury <mtew@cds.duke.edu> wrote in article
<32404A98.5BBF@cds.duke.edu>...
> James Kanze US/ESC 60/3/141 #40763 wrote:
> >
> > The standard does not mandate a quality of implementation, in any way,
> > shape, form or fashion.  Nor should it.
>
> But your arguments base what should or should not be in the standard
> on quality of implementation.  Since the standard should NOT be setting
> quality standards for implementations, those lines of arguments are
> questionable.

A standards body has to design the language in a way that, if all of it is
well-implemented, creates an excellent product. No compiler vender will get
all of the standard done correctly *and* well. There will be trade-offs.
For example, Microsoft implements virtual functions and multiple
inheritance very well (as well as dynamic shared-library linking, an
extension), but their exception stuff IMHO sucks. It imposes overhead even
when you don't use it. However I'd rather have "older" and "more important"
(ie, used in more real programs) features optimized than "new" and "handy"
features; I think Microsoft made the right choice of what to do correctly
*and* well in their current implementation, especially since exception
handling still isn't entirely stable.

> While the lack of an efficient implementation is a strong argument
> against a feature, the presence of implementations that depend on
> the quality of an implementation is not an argument for that feature.

But don't all features depend on quality of implementation? If the vendor
doesn't do it well, either you don't use that feature, you don't buy from
that vendor, or you mutter curses under your breath at work.

> > I cannot see where it adds a layer of complexity.  I do not find the
> > added complexity overwhelming.
>
> To see the extra complexity, try compairing an effieient and
> correct implementation with the feature to the extant STL.

I'm not sure what your problem is here. Allocators allow programmers to set
up memory pools and the like for "almost free." Once the allocator exists,
the algorithms and containers use them automatically! If the C++ library
doesn't deal with these issues, then programmers will... I've reimplemented
most of iostreams to add very small features in the past, because the
iostreams design wasn't quite open and flexible enough. I don't want to do
that again with containers and algorithms, or with iostreams for that
matter.

I can understand your grief if you're planning on implementing the library.
Allocators are one more tidbit of stay-up-all-night-at-the-keyboard
headache--from the library vendor's point of view. From the user's point of
view, they make our lives *easier*, which is more important. The library
only gets written once; users write code a lot. The code to manage custom
memory allocations within the algorithms and containers only gets written
once.

> The added complexity is not overwelming.  It is unnecessary.

Unnecessary to whom? The compiler vendor? Since when is it unimportant to
give users added functionality that they would ordinarily need to provide
themselves at great difficulty? Given that the complexity is not
overwhelming, why *not* provide this important service? Have you ever tried
to provide a custom new() as a *user* of a library? It sucks, because the
current de-facto standard only goes halfway in giving you what you need.

> There is another point to be considered.  Given an application
> where different allocators should be used but where operations
> where the types derived from those allocators rarely interact,
> all those operations that have potential allocator interactions
> have to include a run time test for that interaction.

But that's the point of wrapping these interactions up in the library
rather than in user code. Allocators are mostly for helping containers
manage memory in an open, customizable way.

> > Agreed.  This seems to be a characteristic of standards in general.  In
> > the case of C++, it is exaberated by the fact that the language itself
> > is very complicated, and by the fact that we are not yet seeing the
> > finished product.
>
> All the more reason for not introducing new features without a
> demonstrated need for it.

So, since the language is complicated, and standards documents are
complicated, we should strike out a provision that makes life easier on
users who want to do advanced memory management?

Keep in mind that the allocator system may also be very useful if
provisions for garbage collection ever make it into a future language
revision.

> > Note that I don't disagree with your basic premise.  All I am saying is
> > that in this particular case, the added complexity is not that high,
all
> > things considered.
> >
>
> But is it needed at all?

Necessary, no. Useful, yes. Helpful to the user, yes. Would you prefer a
shackled-to-new's-allocation-method implementation? Forget about ever using
a container on in-place constructed objects like cout and friends.

> So a rarely used feature that could be implemented, with some work, in
> a different way gets to muddy up the otherwise clean design of the
> library.  I believe those were the ones that "The design and evolution
> of C++" (or whatever its exact title is) recomended be dropped.

Yes, I see allocators in the "rarely used" category. I also see them in the
category of things that you'll sorely miss if you do need them. Sort of
like re-writing two thirds of iostreams because nobody thought to make them
support non-blocking i/o (or timeout i/o) in the original spec. Try writing
a non-blocking, socket manipulation class based on an old iostream model
and see how much you regret the fact that the stuff is missing from ios.
Allocators are in the same vein. Who knows, the sudden use of virtual
memory and memory-mapped files in the 85%-market-share PC world may make
customizable memory pools a suddenly very desirable feature.

> > I have already posted an example in which the allocators use different
> > pools of shared memory.  Assigning between pools requires a deep copy;
> > within the same pool only copy on write.
>
> I've seen the reference, but did the pool ID have to be a run time
> parameter?  Could it have been a compile time parameter?

What about when the pool ID is the handle to one of many memory-mapped
files in shared memory? You expect to know this handle at compile time?

> 1) Exceptions are acknowledged to be an important feature with a wide
> range of applications.  Run time allocator differentiation is a mostly
> hypothetical feature with few expected applications.

I think the memory-mapped-file/shared-memory-handle example is a good one.
I hope to make use of my OS vendor's support for this without *all* of it
being implementation defined or custom, in-house code.

> I agree that the allocator serves a function.  I think a lot of that
> function is comprimised by run time differentation.

I think allocators are crippled *unless* they allow run-time
differentiation, if only because of the "file handles as memory pool
handles" situation.

> Note:  I sense a communication problem here.  I am complaining about
> run time differentation of allocators specifically.  While allocators
> in general cover an inherantly messy topic, they serve a purpose and
> I am not arguing for their elimination.  However, they should be an
> exclusively compile time mechanism.

Thank you for pointing this out. I was also under the impression that you
disliked allocators in general. However, I disagree that there's no need
for run-time differentiation. Before starting to write my reply I might
have agreed with you, but the memory-mapped-file example has me convinced.

> Run time differentiation of allocators with its impact on strings and
> containers may not be that cheap.  Strings are something almost every
> practical application has to deal with.  Messing up any aspect of their
> specification is likely to have a significant impact eventually.  Let's
> fix the problem now rather than later.

But partial template specialization *does* leave string and containers
efficient for the "normal" case of global-new memory. Runtime allocators
*also* allow for memory sources known only at compile time, such as special
pools of memory handed out by the operating system at run-time.

In case you're not familiar with memory-mapped files, it's a mechanism
Win32 has for mapping a stretch of private or process-shared memory to
either a file or the virtual page swap. You can use these mappings to
communicate with other processes, or to access files as if they are a part
of ordinary memory. The OS hands out the memory pools at runtime with a
handle. Say that an allocator, mmf_allocator, compares equal for the same
pool and unequal for different pools. Using a container or algorithm can
then transparently write to a file or communicate with another program!
Using this mechanism, the container can "know" whether it's moving memory
around in its own space or somebody elses. When you splice in the same
pool, you relink the nodes. When you splice into a different pool, the data
gets deep-copied into *another process's address space* or *written into a
file on disk*.

That's a level of functionality that I'd personally like to have.
Especially if it comes "free" with my compiler.
--
Bradd W. Szonye
bradds@ix.netcom.com
http://www.geocities.com/SouthBeach/2447


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Lars Farm <lars.farm@ite.mh.se> wrote in article
<199609191812302138320@dialup102-6-14.swipnet.se>...
> Max TenEyck Woodbury <mtew@cds.duke.edu> wrote:
>
> > However, they should be an
> > exclusively compile time mechanism.
>
> FWIW I agree. Until now I thought that the use of allocators in the
> standard library was 100% compiletime. Thanks for hilighting this
> problem.

What problem?

I agree with James Kanze... if we're going to bother with allocators at
all, include the provision for runtime identification. The cases where you
need an allocator other than the default but *don't* need runtime checking
are rare.

If you don't have allocators, it's nearly impossible to control where a
container gets its memory from. If you don't have run-time checking, you
can't implement the most useful forms of custom allocation: shared memory,
memory-mapped files, and segmented addressing. Otherwise, you're limited to
heap optimization allocators.

I've worked with container libraries where moving data between processes
involves unpacking, translating, re-translating, and re-packing the
container data. I'd much rather just say "a = b." Considering the explosion
of networking, virtual memory, shared memory, and client-server data
marshaling, I'd like to be able to wrap up the code to deal with these
technologies in small, simple packages that work with the existing
containers and algorithms. The allocator protocol/interface looks like a
great starting point.

By the way... I like to write the applications *and* the compilers. I can
appreciate both points of view.
--
Bradd W. Szonye
bradds@ix.netcom.com
http://www.geocities.com/SouthBeach/2447


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

James Kanze US/ESC 60/3/141 #40763 wrote:
>
> In article <32404A98.5BBF@cds.duke.edu> Max TenEyck Woodbury
> <mtew@cds.duke.edu> writes:
>
> |> James Kanze US/ESC 60/3/141 #40763 wrote:
>
> |> > The standard does not mandate a quality of implementation, in any way,
> |> > shape, form or fashion.  Nor should it.
>
> |> But your arguments base what should or should not be in the standard
> |> on quality of implementation.  Since the standard should NOT be setting
> |> quality standards for implementations, those lines of arguments are
> |> questionable.
>
> My argument is based on the fact the one of the stated goals of C++ is
> run-time efficiency.  Obviously, the standard cannot impose this, but
> one of the criteria for including a feature is that is must be
> implementable in an efficient manner.  Obviously, the standard doesn't
> mandate that any given implementation implement the feature in an
> efficient manner, but without prove that such an implementation is
> possible, the committee should, and probably would, reject the
> implementation.
>
> Your arguments against run-time checking of the allocator have been
> partially based on the loss of efficiency it may cause in programs that
> don't need it.  I am simply pointing out that there is a solution which
> does not involve any loss of efficiency.
>

I beleive your argument is that it is OK to introduce extra
complexity and then optimize it away.  I'd perfer to see a
situation where the templating process only introduces the
added complexity when needed.

> While I am at it, I will respond to a point you bring up later as well.
> The efficient solution I describe does not require any particular
> optimization on the part of the compiler.  It does require that the
> compiler support partial specialization.  But this is required by the
> standard anyway.  Partial specialization is not an optimization, but a
> way of telling the compiler: if this template instantiation meets the
> following criteria, use this implementation instead of the more general
> one.
>

I believe that this line of argument differes from some of
the previous presentations on this subject.  More specificialy
they differ from statements that I believe were yours, however
I did not keep a careful record of exactly who said what so I
could be wrong.  Those arguments followed the outline that
telling the compiler that a certain run time test would always
come out a certain way would cause the compiler to suppress
generating code for the untaken branch and that it should not
even mention that suppression in a diagnostic.  The test in
question was the equality test on the allocator.  Partial
specialization didn't come into it at that level.

> |> There is another point to be considered.  Given an application
> |> where different allocators should be used but where operations
> |> where the types derived from those allocators rarely interact,
> |> all those operations that have potential allocator interactions
> |> have to include a run time test for that interaction.  If run
> |> time differentiation is not allowed, that test would not be
> |> needed.  The correct case would be chosen at compile time,
> |> depending on which allocators were involved.
>
> This is a difficult point.  If objects using two allocators never
> interact, the allocators should probably be of different types.  In
> practice, however, because there will be no partial specialization for
> these types, the allocator instances will be compared anyway.
>
> In the main utilisation for customized allocators that I can think of,
> however, they will interact, and the run-time test is necessary.  To
> return to my example of a system using shared memory.  The solution I
> would propose would have a custom allocator, ShMemAllocator, with at
> least two constructors: one which specifies which pool of shared memory
> to use, and one which takes an "allocator" as argument, and uses
> unshared memory.  If there is a need for strings in shared memory, the
> application will not use "wstring" at all, but rather:
>
>         typedef basic_string< wchar_t ,
>                               string_char_traits< wchar_t > ,
>                           ShMemAllocator >
>                             MyString ;
>
> Except for using MyString instead of wstring, all of the application
> programs will be written as usual, without paying any attention to the
> fact that some of the strings may be in shared memory.  Temporaries,
> local variables, and such, will be created using the standard heap,
> because of the default argument for the allocator in the class
> definition.  (This is the reason for the second constructor in
> ShMemAllocator!)  Strings in shared memory must be created by special
> routines anyway, since they must ensure not only that all memory
> allocated by the string object is in shared memory, but also that the
> object itself is in shared memory, and can be located in some way by the
> other processes.  Such routines will, of course, pass the appropriate
> allocator parameter to the MyString constructor.
>
> Done this way, only the routines which actually construct the strings in
> shared memory need to be aware of the fact that they are in shared
> memory.  Under your proposal, the user of MyString must be aware of
> which strings are or are not in shared memory; the decision between deep
> copy (using, presumably, s1.assign( s2.begin() , s2.end() )) and shallow
> (the classical operator=).  Under the current standard proposal, this is
> handled by basic_string itself.
>

I'm not at all convinced.  The shared memory stings seem to be
rare beasties in this applications and might as well be a
seperate type.  Where they interact with MyStrings, the
appropriate conversion routines should be called.  Being a
shared memory application, they should have volitile attribute
in a number of critical places anyway and that alone might
have significant impact the algorithms.  Including them in a
map that was not completely shared memory aware would be
disaster in the making...

>     [...]
> |> I agree that the allocator serves a function.  I think a lot of that
> |> function is comprimised by run time differentation.
>
>     [...]
> |> Note:  I sense a communication problem here.  I am complaining about
> |> run time differentation of allocators specifically.  While allocators
> |> in general cover an inherantly messy topic, they serve a purpose and
> |> I am not arguing for their elimination.  However, they should be an
> |> exclusively compile time mechanism.
>
> Curiously, this is where we differ.  I agree with much of your general
> comment.  I actually think that have allocator at all is probably
> unnecessary complexity; the only real application for it that I can
> think of is shared memory, which seems to be a bit of a special case
> anyway, and is not in general addressed by the standard.  (The allocator
> may be used to get the object to use a heap in the shared memory, but
> there is nothing to synchronize concurrent access, for example.)  So I
> really think that we could do without the allocator.
>

The allocator in the STL is the combination of two useful
classes that interact fairly strongly.  Its first use
is a catchment for names for the base type and types derived
from the base type and is a good potential resting place for
attributes of those derivatives.  Of particular interest are
the pointer types.  It can be used to differentiate pointers
to shared and non-shared memory, as in your example.  More
commonly, it can be used to differentiate '__near', '__far'
and '__huge' pointers in a segmented memory environment.
The second use provides access to the four components of
object management -- memory allocation, object construction,
object destruction, and memory deallocation.  The seperation
between memory allocation and object construction, and the
seperation between object destruction and memory allocation
is deliberate and significant.

Note particularly that neither of these uses necessitate
any memory be set asside in an object that includes an
allocator.  In fact, if there was any way to assure that
an allocator NEVER required actual storage, it would make
its function clearer.  (The impact of different allocators
is in other objects declared with the types defined by the
allocator, never in the allocator itself.)

> If we have the allocator, however, I feel that it should be tested at
> run-time, as the current draft requires, in order to support the above
> scenario.
>

But run time differentation as opposed to compile time
differentation just does not fit into the logical structure
of allocators.  All that run time synchronization belongs in
the types defined by the allocator, not in the allocator
itself.

mtew@cds.duke.edu
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Bradd W. Szonye wrote:
>
> Max TenEyck Woodbury <mtew@cds.duke.edu> wrote in article
> <32404A98.5BBF@cds.duke.edu>...
> > James Kanze US/ESC 60/3/141 #40763 wrote:
> > >
> > > The standard does not mandate a quality of implementation, in any way,
> > > shape, form or fashion.  Nor should it.
> >
> > But your arguments base what should or should not be in the standard
> > on quality of implementation.  Since the standard should NOT be setting
> > quality standards for implementations, those lines of arguments are
> > questionable.
>
> A standards body has to design the language in a way that, if all of it is
> well-implemented, creates an excellent product. No compiler vender will get
> all of the standard done correctly *and* well. There will be trade-offs.
> For example, Microsoft implements virtual functions and multiple
> inheritance very well (as well as dynamic shared-library linking, an
> extension), but their exception stuff IMHO sucks. It imposes overhead even
> when you don't use it. However I'd rather have "older" and "more important"
> (ie, used in more real programs) features optimized than "new" and "handy"
> features; I think Microsoft made the right choice of what to do correctly
> *and* well in their current implementation, especially since exception
> handling still isn't entirely stable.
>

Excuse me, but I don't see what this has to do with the current argument.

> > While the lack of an efficient implementation is a strong argument
> > against a feature, the presence of implementations that depend on
> > the quality of an implementation is not an argument for that feature.
>
> But don't all features depend on quality of implementation? If the vendor
> doesn't do it well, either you don't use that feature, you don't buy from
> that vendor, or you mutter curses under your breath at work.
>

Not really.  The presence of a feature in the standard should
depend on a demonstrated need for the feature and its expected
frequency of usage.  The lack of a good implementation will reduce
usage, but a good implementation will not increase usage beyond
the need for the feature.

> > > I cannot see where it adds a layer of complexity.  I do not find the
> > > added complexity overwhelming.
> >
> > To see the extra complexity, try compairing an effieient and
> > correct implementation with the feature to the extant STL.
>
> I'm not sure what your problem is here. Allocators allow programmers to set
> up memory pools and the like for "almost free." Once the allocator exists,
> the algorithms and containers use them automatically! If the C++ library
> doesn't deal with these issues, then programmers will... I've reimplemented
> most of iostreams to add very small features in the past, because the
> iostreams design wasn't quite open and flexible enough. I don't want to do
> that again with containers and algorithms, or with iostreams for that
> matter.
>

That 'almost free' costs every user of the library something.

The problem is not allocators per se.  It is their run time
differentiation.  As I pointed out in a reply to James,
allocators are a usefull abstraction.  The problem is in
trying to turn an abstraction into a storage using object.

As to reimplementing library routines, that is a common
problem that anybody who has delt with any language eventually
faces.  C and C++ are much more amiable to this kind of thing
than most languages.  However, I believe that adding this feature
actually decreases the flexability of the package because it puts
complexity into the wrong places.  Run time differentiation puts
the complexity into the algorithms rather than into the conversion
routines.

> I can understand your grief if you're planning on implementing the library.
> Allocators are one more tidbit of stay-up-all-night-at-the-keyboard
> headache--from the library vendor's point of view. From the user's point of
> view, they make our lives *easier*, which is more important. The library
> only gets written once; users write code a lot. The code to manage custom
> memory allocations within the algorithms and containers only gets written
> once.
>

While I'm mildly interested in implementation problems, I'm most
directly concerned with getting a portable application to work on
a number of different machines.  In particular, its a program that
deals with fairly large amounts of data (many arrays of small to
moderate sized vectors and strings).  If the STL is done right,
I'll be putting togeather a number of specialized containers and
algorithms to handle these problems.  I also want to be able to
leave the job behind someday and be sure that a reasonably competent
programmer will be able to maintain it.  That means if someday it
needs to run in a shared memory environment, they will not have to
call me up to find out what the blankity blank dash dash I was doing
when I wrote it originally.

In studying the STL, I was impressed by its good conceptual design
and more than a little anoyed by the fact that the absence of critical
language features messed up its implementation.  That caused me to look
at what the draft standard had to say on the subject.  It took a while
to realize that the conceptual integrity of allocators had been
breached and a number of problems that I had planned to isolate to
conversion routines had escaped their bounds and now had to be delt
with in a wide variaty of different places.  What really gets to me
is that some people actually think that the change is an improvement!

> > The added complexity is not overwelming.  It is unnecessary.
>
> Unnecessary to whom? The compiler vendor? Since when is it unimportant to
> give users added functionality that they would ordinarily need to provide
> themselves at great difficulty? Given that the complexity is not
> overwhelming, why *not* provide this important service? Have you ever tried
> to provide a custom new() as a *user* of a library? It sucks, because the
> current de-facto standard only goes halfway in giving you what you need.
>

Because it is NOT an important service.  It is an invetation to
sloppy programming.  Instead of confining the problems associated
with different address spaces to a set of nicely delineated
conversion routines, it dumps it into the lap of everyone who
has to deal with writing an algorithm.

> > There is another point to be considered.  Given an application
> > where different allocators should be used but where operations
> > where the types derived from those allocators rarely interact,
> > all those operations that have potential allocator interactions
> > have to include a run time test for that interaction.
>
> But that's the point of wrapping these interactions up in the library
> rather than in user code. Allocators are mostly for helping containers
> manage memory in an open, customizable way.
>

I expect that these interactions will end up in the library.  I
very much want them confined to the library.  I want them confined
to as small a corner of the library as possible!  This particular
feature lets those interactions escape from what was a very resticted
corner of the library.  This feature necessitates consideration in
user code of allocator interaction, not the reverse.  Without this
feature, interaction between different memory spaces must go through
the conversion routines and calls to those conversion routines are
inserted automatically at compile time.  Adding the feature means
that the user has to become aware of those conversion routines and
has to figure out where to insert the proper calls to them.

> > > Agreed.  This seems to be a characteristic of standards in general.  In
> > > the case of C++, it is exaberated by the fact that the language itself
> > > is very complicated, and by the fact that we are not yet seeing the
> > > finished product.
> >
> > All the more reason for not introducing new features without a
> > demonstrated need for it.
>
> So, since the language is complicated, and standards documents are
> complicated, we should strike out a provision that makes life easier on
> users who want to do advanced memory management?
>

But it doesn't do that.  In fact it makes that job harder.

> Keep in mind that the allocator system may also be very useful if
> provisions for garbage collection ever make it into a future language
> revision.
>

I don't see that that necessitates run time differentation of
allocators.

> > > Note that I don't disagree with your basic premise.  All I am saying is
> > > that in this particular case, the added complexity is not that high, all
> > > things considered.
> > >
> >
> > But is it needed at all?
>
> Necessary, no. Useful, yes. Helpful to the user, yes. Would you prefer a
> shackled-to-new's-allocation-method implementation? Forget about ever using
> a container on in-place constructed objects like cout and friends.
>

Please stop.  You are talking about allocators as in the STL.  I'm talking
about Allocators as in run time differentation in the draft standard.

> > So a rarely used feature that could be implemented, with some work, in
> > a different way gets to muddy up the otherwise clean design of the
> > library.  I believe those were the ones that "The design and evolution
> > of C++" (or whatever its exact title is) recomended be dropped.
>
> Yes, I see allocators in the "rarely used" category. I also see them in the
> category of things that you'll sorely miss if you do need them. Sort of
> like re-writing two thirds of iostreams because nobody thought to make them
> support non-blocking i/o (or timeout i/o) in the original spec. Try writing
> a non-blocking, socket manipulation class based on an old iostream model
> and see how much you regret the fact that the stuff is missing from ios.
> Allocators are in the same vein. Who knows, the sudden use of virtual
> memory and memory-mapped files in the 85%-market-share PC world may make
> customizable memory pools a suddenly very desirable feature.
>

I'm already dealing with PCs and that's why I hate run time
differentiation!

> > > I have already posted an example in which the allocators use different
> > > pools of shared memory.  Assigning between pools requires a deep copy;
> > > within the same pool only copy on write.
> >
> > I've seen the reference, but did the pool ID have to be a run time
> > parameter?  Could it have been a compile time parameter?
>
> What about when the pool ID is the handle to one of many memory-mapped
> files in shared memory? You expect to know this handle at compile time?
>

In my opinion, if you are mixing objects from your different pools to
the point where you need run time differentiation as opposed to compile
time differentiation, you have hopelessly muddled your design.  As for
your handles, that should be a piece of information internal to your
pool implementation, not something you hang out for public display...

> > 1) Exceptions are acknowledged to be an important feature with a wide
> > range of applications.  Run time allocator differentiation is a mostly
> > hypothetical feature with few expected applications.
>
> I think the memory-mapped-file/shared-memory-handle example is a good one.
> I hope to make use of my OS vendor's support for this without *all* of it
> being implementation defined or custom, in-house code.
>

I hope to be able to use the STL without having to wade through
all those 'fine' memory-mapped-file/shared-memory-handle routines
when I want to extend it a little bit.  I want to be assured that
copying an object from one container with a given allocator class
to another container with the same allocator class will work.  Run
time differentiation prevents that from happening.

> > I agree that the allocator serves a function.  I think a lot of that
> > function is comprimised by run time differentation.
>
> I think allocators are crippled *unless* they allow run-time
> differentiation, if only because of the "file handles as memory pool
> handles" situation.
>

I think you may not understand the issue.

> > Note:  I sense a communication problem here.  I am complaining about
> > run time differentation of allocators specifically.  While allocators
> > in general cover an inherantly messy topic, they serve a purpose and
> > I am not arguing for their elimination.  However, they should be an
> > exclusively compile time mechanism.
>
> Thank you for pointing this out. I was also under the impression that you
> disliked allocators in general. However, I disagree that there's no need
> for run-time differentiation. Before starting to write my reply I might
> have agreed with you, but the memory-mapped-file example has me convinced.
>

So stuff the handle in an array and pass the array index as a
template parameter to your particular allocator implementation.
Operations within one file get the efficent algorithms appropriate
to having a single address space.  Operations between files
automatically invoke the deep copy embeded in your templatized
conversion routine.  DON'T inflict an allocator comparison on each
and every assignment in my programs.

> > Run time differentiation of allocators with its impact on strings and
> > containers may not be that cheap.  Strings are something almost every
> > practical application has to deal with.  Messing up any aspect of their
> > specification is likely to have a significant impact eventually.  Let's
> > fix the problem now rather than later.
>
> But partial template specialization *does* leave string and containers
> efficient for the "normal" case of global-new memory. Runtime allocators
> *also* allow for memory sources known only at compile time, such as special
> pools of memory handed out by the operating system at run-time.
>

Read the comments on string and container algorithms to understand the
problem.  Without run time specialization, the problem is indead confined
to the string and container classes.  In fact it is confined to only one
or two operations in those classes.  With run time differentiation, there
is an impact on many other parts of the library and user code as well.

> In case you're not familiar with memory-mapped files, it's a mechanism
> Win32 has for mapping a stretch of private or process-shared memory to
> either a file or the virtual page swap. You can use these mappings to
> communicate with other processes, or to access files as if they are a part
> of ordinary memory. The OS hands out the memory pools at runtime with a
> handle. Say that an allocator, mmf_allocator, compares equal for the same
> pool and unequal for different pools. Using a container or algorithm can
> then transparently write to a file or communicate with another program!
> Using this mechanism, the container can "know" whether it's moving memory
> around in its own space or somebody elses. When you splice in the same
> pool, you relink the nodes. When you splice into a different pool, the data
> gets deep-copied into *another process's address space* or *written into a
> file on disk*.
>

I'm not sure that Atlas had memory mapped files, but I think I
remember something similar from the IBM System 360 model 44.  It was
not a new concept when it was included in DECs VMS for the PDP 11/780
in the late 70's.  There were tools for dealing with it (poorly) in
BLISS and a number of other languages.  Its not a new idea.

Your use the word 'automatically' here is inappropriate in my opinion.
The container or algorithm, and in some cases the user, has to test
for the condition explicitly.  I believe 'automaticly' in this context
should be reserved to situations where the compiler makes the
differentiation in all cases.  That can only happen it there is no
run time differentiation.

> That's a level of functionality that I'd personally like to have.
> Especially if it comes "free" with my compiler.
>

I'd perfer the greater functionality, and fewer potential
program defects that would come without run-time differentiation.


mtew@cds.duke.edu
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Reposting article removed by rogue canceller.

Bradd W. Szonye wrote:
>
> Max TenEyck Woodbury <mtew@cds.duke.edu> wrote in article
> <32404A98.5BBF@cds.duke.edu>...
> > James Kanze US/ESC 60/3/141 #40763 wrote:
> > >
> > > The standard does not mandate a quality of implementation, in any way,
> > > shape, form or fashion.  Nor should it.
> >
> > But your arguments base what should or should not be in the standard
> > on quality of implementation.  Since the standard should NOT be setting
> > quality standards for implementations, those lines of arguments are
> > questionable.
>
> A standards body has to design the language in a way that, if all of it is
> well-implemented, creates an excellent product. No compiler vender will get
> all of the standard done correctly *and* well. There will be trade-offs.
> For example, Microsoft implements virtual functions and multiple
> inheritance very well (as well as dynamic shared-library linking, an
> extension), but their exception stuff IMHO sucks. It imposes overhead even
> when you don't use it. However I'd rather have "older" and "more important"
> (ie, used in more real programs) features optimized than "new" and "handy"
> features; I think Microsoft made the right choice of what to do correctly
> *and* well in their current implementation, especially since exception
> handling still isn't entirely stable.
>

Excuse me, but I don't see what this has to do with the current argument.

> > While the lack of an efficient implementation is a strong argument
> > against a feature, the presence of implementations that depend on
> > the quality of an implementation is not an argument for that feature.
>
> But don't all features depend on quality of implementation? If the vendor
> doesn't do it well, either you don't use that feature, you don't buy from
> that vendor, or you mutter curses under your breath at work.
>

Not really.  The presence of a feature in the standard should
depend on a demonstrated need for the feature and its expected
frequency of usage.  The lack of a good implementation will reduce
usage, but a good implementation will not increase usage beyond
the need for the feature.

> > > I cannot see where it adds a layer of complexity.  I do not find the
> > > added complexity overwhelming.
> >
> > To see the extra complexity, try compairing an effieient and
> > correct implementation with the feature to the extant STL.
>
> I'm not sure what your problem is here. Allocators allow programmers to set
> up memory pools and the like for "almost free." Once the allocator exists,
> the algorithms and containers use them automatically! If the C++ library
> doesn't deal with these issues, then programmers will... I've reimplemented
> most of iostreams to add very small features in the past, because the
> iostreams design wasn't quite open and flexible enough. I don't want to do
> that again with containers and algorithms, or with iostreams for that
> matter.
>

That 'almost free' costs every user of the library something.

The problem is not allocators per se.  It is their run time
differentiation.  As I pointed out in a reply to James,
allocators are a usefull abstraction.  The problem is in
trying to turn an abstraction into a storage using object.

As to reimplementing library routines, that is a common
problem that anybody who has delt with any language eventually
faces.  C and C++ are much more amiable to this kind of thing
than most languages.  However, I believe that adding this feature
actually decreases the flexability of the package because it puts
complexity into the wrong places.  Run time differentiation puts
the complexity into the algorithms rather than into the conversion
routines.

> I can understand your grief if you're planning on implementing the library.
> Allocators are one more tidbit of stay-up-all-night-at-the-keyboard
> headache--from the library vendor's point of view. From the user's point of
> view, they make our lives *easier*, which is more important. The library
> only gets written once; users write code a lot. The code to manage custom
> memory allocations within the algorithms and containers only gets written
> once.
>

While I'm mildly interested in implementation problems, I'm most
directly concerned with getting a portable application to work on
a number of different machines.  In particular, its a program that
deals with fairly large amounts of data (many arrays of small to
moderate sized vectors and strings).  If the STL is done right,
I'll be putting togeather a number of specialized containers and
algorithms to handle these problems.  I also want to be able to
leave the job behind someday and be sure that a reasonably competent
programmer will be able to maintain it.  That means if someday it
needs to run in a shared memory environment, they will not have to
call me up to find out what the blankity blank dash dash I was doing
when I wrote it originally.

In studying the STL, I was impressed by its good conceptual design
and more than a little anoyed by the fact that the absence of critical
language features messed up its implementation.  That caused me to look
at what the draft standard had to say on the subject.  It took a while
to realize that the conceptual integrity of allocators had been
breached and a number of problems that I had planned to isolate to
conversion routines had escaped their bounds and now had to be delt
with in a wide variaty of different places.  What really gets to me
is that some people actually think that the change is an improvement!

> > The added complexity is not overwelming.  It is unnecessary.
>
> Unnecessary to whom? The compiler vendor? Since when is it unimportant to
> give users added functionality that they would ordinarily need to provide
> themselves at great difficulty? Given that the complexity is not
> overwhelming, why *not* provide this important service? Have you ever tried
> to provide a custom new() as a *user* of a library? It sucks, because the
> current de-facto standard only goes halfway in giving you what you need.
>

Because it is NOT an important service.  It is an invetation to
sloppy programming.  Instead of confining the problems associated
with different address spaces to a set of nicely delineated
conversion routines, it dumps it into the lap of everyone who
has to deal with writing an algorithm.

> > There is another point to be considered.  Given an application
> > where different allocators should be used but where operations
> > where the types derived from those allocators rarely interact,
> > all those operations that have potential allocator interactions
> > have to include a run time test for that interaction.
>
> But that's the point of wrapping these interactions up in the library
> rather than in user code. Allocators are mostly for helping containers
> manage memory in an open, customizable way.
>

I expect that these interactions will end up in the library.  I
very much want them confined to the library.  I want them confined
to as small a corner of the library as possible!  This particular
feature lets those interactions escape from what was a very resticted
corner of the library.  This feature necessitates consideration in
user code of allocator interaction, not the reverse.  Without this
feature, interaction between different memory spaces must go through
the conversion routines and calls to those conversion routines are
inserted automatically at compile time.  Adding the feature means
that the user has to become aware of those conversion routines and
has to figure out where to insert the proper calls to them.

> > > Agreed.  This seems to be a characteristic of standards in general.  In
> > > the case of C++, it is exaberated by the fact that the language itself
> > > is very complicated, and by the fact that we are not yet seeing the
> > > finished product.
> >
> > All the more reason for not introducing new features without a
> > demonstrated need for it.
>
> So, since the language is complicated, and standards documents are
> complicated, we should strike out a provision that makes life easier on
> users who want to do advanced memory management?
>

But it doesn't do that.  In fact it makes that job harder.

> Keep in mind that the allocator system may also be very useful if
> provisions for garbage collection ever make it into a future language
> revision.
>

I don't see that that necessitates run time differentation of
allocators.

> > > Note that I don't disagree with your basic premise.  All I am saying is
> > > that in this particular case, the added complexity is not that high, all
> > > things considered.
> > >
> >
> > But is it needed at all?
>
> Necessary, no. Useful, yes. Helpful to the user, yes. Would you prefer a
> shackled-to-new's-allocation-method implementation? Forget about ever using
> a container on in-place constructed objects like cout and friends.
>

Please stop.  You are talking about allocators as in the STL.  I'm talking
about Allocators as in run time differentation in the draft standard.

> > So a rarely used feature that could be implemented, with some work, in
> > a different way gets to muddy up the otherwise clean design of the
> > library.  I believe those were the ones that "The design and evolution
> > of C++" (or whatever its exact title is) recomended be dropped.
>
> Yes, I see allocators in the "rarely used" category. I also see them in the
> category of things that you'll sorely miss if you do need them. Sort of
> like re-writing two thirds of iostreams because nobody thought to make them
> support non-blocking i/o (or timeout i/o) in the original spec. Try writing
> a non-blocking, socket manipulation class based on an old iostream model
> and see how much you regret the fact that the stuff is missing from ios.
> Allocators are in the same vein. Who knows, the sudden use of virtual
> memory and memory-mapped files in the 85%-market-share PC world may make
> customizable memory pools a suddenly very desirable feature.
>

I'm already dealing with PCs and that's why I hate run time
differentiation!

> > > I have already posted an example in which the allocators use different
> > > pools of shared memory.  Assigning between pools requires a deep copy;
> > > within the same pool only copy on write.
> >
> > I've seen the reference, but did the pool ID have to be a run time
> > parameter?  Could it have been a compile time parameter?
>
> What about when the pool ID is the handle to one of many memory-mapped
> files in shared memory? You expect to know this handle at compile time?
>

In my opinion, if you are mixing objects from your different pools to
the point where you need run time differentiation as opposed to compile
time differentiation, you have hopelessly muddled your design.  As for
your handles, that should be a piece of information internal to your
pool implementation, not something you hang out for public display...

> > 1) Exceptions are acknowledged to be an important feature with a wide
> > range of applications.  Run time allocator differentiation is a mostly
> > hypothetical feature with few expected applications.
>
> I think the memory-mapped-file/shared-memory-handle example is a good one.
> I hope to make use of my OS vendor's support for this without *all* of it
> being implementation defined or custom, in-house code.
>

I hope to be able to use the STL without having to wade through
all those 'fine' memory-mapped-file/shared-memory-handle routines
when I want to extend it a little bit.  I want to be assured that
copying an object from one container with a given allocator class
to another container with the same allocator class will work.  Run
time differentiation prevents that from happening.

> > I agree that the allocator serves a function.  I think a lot of that
> > function is comprimised by run time differentation.
>
> I think allocators are crippled *unless* they allow run-time
> differentiation, if only because of the "file handles as memory pool
> handles" situation.
>

I think you may not understand the issue.

> > Note:  I sense a communication problem here.  I am complaining about
> > run time differentation of allocators specifically.  While allocators
> > in general cover an inherantly messy topic, they serve a purpose and
> > I am not arguing for their elimination.  However, they should be an
> > exclusively compile time mechanism.
>
> Thank you for pointing this out. I was also under the impression that you
> disliked allocators in general. However, I disagree that there's no need
> for run-time differentiation. Before starting to write my reply I might
> have agreed with you, but the memory-mapped-file example has me convinced.
>

So stuff the handle in an array and pass the array index as a
template parameter to your particular allocator implementation.
Operations within one file get the efficent algorithms appropriate
to having a single address space.  Operations between files
automatically invoke the deep copy embeded in your templatized
conversion routine.  DON'T inflict an allocator comparison on each
and every assignment in my programs.

> > Run time differentiation of allocators with its impact on strings and
> > containers may not be that cheap.  Strings are something almost every
> > practical application has to deal with.  Messing up any aspect of their
> > specification is likely to have a significant impact eventually.  Let's
> > fix the problem now rather than later.
>
> But partial template specialization *does* leave string and containers
> efficient for the "normal" case of global-new memory. Runtime allocators
> *also* allow for memory sources known only at compile time, such as special
> pools of memory handed out by the operating system at run-time.
>

Read the comments on string and container algorithms to understand the
problem.  Without run time specialization, the problem is indead confined
to the string and container classes.  In fact it is confined to only one
or two operations in those classes.  With run time differentiation, there
is an impact on many other parts of the library and user code as well.

> In case you're not familiar with memory-mapped files, it's a mechanism
> Win32 has for mapping a stretch of private or process-shared memory to
> either a file or the virtual page swap. You can use these mappings to
> communicate with other processes, or to access files as if they are a part
> of ordinary memory. The OS hands out the memory pools at runtime with a
> handle. Say that an allocator, mmf_allocator, compares equal for the same
> pool and unequal for different pools. Using a container or algorithm can
> then transparently write to a file or communicate with another program!
> Using this mechanism, the container can "know" whether it's moving memory
> around in its own space or somebody elses. When you splice in the same
> pool, you relink the nodes. When you splice into a different pool, the data
> gets deep-copied into *another process's address space* or *written into a
> file on disk*.
>

I'm not sure that Atlas had memory mapped files, but I think I
remember something similar from the IBM System 360 model 44.  It was
not a new concept when it was included in DECs VMS for the PDP 11/780
in the late 70's.  There were tools for dealing with it (poorly) in
BLISS and a number of other languages.  Its not a new idea.

Your use the word 'automatically' here is inappropriate in my opinion.
The container or algorithm, and in some cases the user, has to test
for the condition explicitly.  I believe 'automaticly' in this context
should be reserved to situations where the compiler makes the
differentiation in all cases.  That can only happen it there is no
run time differentiation.

> That's a level of functionality that I'd personally like to have.
> Especially if it comes "free" with my compiler.
>

I'd perfer the greater functionality, and fewer potential
program defects that would come without run-time differentiation.


mtew@cds.duke.edu
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

I missed the first part of the discussion...but what exactly is the run
time problem with allocators?

Is someone complaining about the fact that member functions such as
address(), etc. are non-static member functions rather than static ones--
and that there has to be an allocator object which they are bound to?

I don't see how this is a problem with any decent compiler.

Just do

template <class Type, class Allocator = allocator >
class Foo
{
 //
        // Standard set of typedefs, to define pointer, reference, etc.
 //
        pointer bar ( value_type baz) { return Allocator().address(baz); }
 // instead of Allocator::address(baz);
};

This allows run time determination if necessary.  However, one would hope
that if the Allocator() being used is a "simple" one (trivial default
constructor, no data, all member functions inline), that any "overhead"
involved in the construction of the object and the member function call
would be optimized out of existence, and that the resulting code would be
just as efficient as the static member function call.

Am I putting too much faith in the optimizing ability of compilers here?

Or am I missing the original poster's point entirely?

Scott



--
/--------------------------------------------------------------------------\
|Scott Johnson -- Professional (sometimes) SW Engineer and all-purpose Geek|
|I don't speak for nobody but myself, which everyone else is thankful for  |
\--------------------------------------------------------------------------/
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

In article <323C6318.617C@cds.duke.edu> Max TenEyck Woodbury
<mtew@cds.duke.edu> writes:

|> James Kanze US/ESC 60/3/141 #40763 wrote:

|> > One of the reasons I suspect that the impact was understood is that it
|> > is, in fact, not very great.  It does mean a bit more work for the
|> > implementor, particularly if he wants a quality implementation.  But it
|> > makes things somewhat easier for the user, with no cost for the users
|> > who do not need the feature (supposing a quality implementation).

|> There you are proposing a quality of implementation standard.  Quality of
|> implementation is a topic most standard commitees seem to avoid (to put
|> it mildly).

The standard does not mandate a quality of implementation, in any way,
shape, form or fashion.  Nor should it.

On the other hand, one of the proclaimed goals of C++ is that there can
be an efficient implementation.  In fact, within the standards committee,
the lack of an efficient implementation of a given feature is a strong
argument against that feature.  My discussions concerning how to
implement the classes efficiently with the current definition of
allocators is meant simply as a proof that this particular argument
against them is not valid: there is an efficient implementation.
Whether a specific implementor chooses to use it or not is his business
(in a very literal sense); the standard cannot require it.

This is true of everything in the C++ standard, however.  The standard
does not forbid the compiler from generating a ten second empty loop
after each statement.  No one would argue that C++'s having statements
is a misfeature because of this, however.

|> > Once understood, it is apparent that the whole thing "hangs together" in
|> > a way that cannot be the result of chance or blind stumbling by the
|> > committee.

|> I disagree.  Run time instation of allocators and run time checks that
|> allocators are compatible add a layer of complexity to both strings and
|> containers.  The rest of the structure hangs together but this particular
|> feature has the flavor of a 'tag end' or after thought.

I cannot see where it adds a layer of complexity.  I do not find the
added complexity overwhelming.

I also find that the detailed description of the allocator requirements,
and the fact that in some cases, the complexity is given as depending on
whether the allocators compare equal, as a strong sign that considerable
thought went into this extension as well.

|> The impact is NOT on the allocator itself.  The impact is on strings and
|> containers.  I'm not saying that there isn't a logical structure to the
|> standard.  On the contrary, it is quite well structured.  That does NOT
|> mean that it is easy to understand all the implications embeded in the
|> standard.

Agreed.  This seems to be a characteristic of standards in general.  In
the case of C++, it is exaberated by the fact that the language itself
is very complicated, and by the fact that we are not yet seeing the
finished product.

|> > |> > Although the solution adopted by the committee is more complex than I
|> > |> > would have proposed, I cannot see where it has had a "negative impact on
|> > |> > the language", or that there is a "potential source of inoperability".
|> >
|> > |> The extra code needed to deal with complex allocators makes any library
|> > |> implementation larger and compile times slower, if for no other reason
|> > |> than the number of characters that will have to be processed by the
|> > |> front end.  That's a negative impact.
|> >
|> > This is part of the standard library.  While not yet the case, I would
|> > presume that once the standard is a standard, given the size and
|> > complexity of the library (and of the language in general), it will be
|> > integrated into the compiler, most likely in the form of precompiled
|> > headers which are automatically loaded.

|> Here you are presuming on a number of implementation details which are
|> irrelavant.  However, even precompiled headers reflect the complexity of
|> the material precompiled.  Unneeded complexity is still a looser.

I am only showing that the problem has a known solution.

Note that I don't disagree with your basic premise.  All I am saying is
that in this particular case, the added complexity is not that high, all
things considered.

|> > |> "potential source of inoperability" is probably a poor choice of words.
|> > |> I was trying to convey the increased risk of implementation defects
|> > |> caused by the increased complexity.
|> >
|> > This is C++.  In this particular case, I don't see the risk as being
|> > particularly high.  Much less than, say, namespaces, for example.

|> Argh!  Have you never heard of Murphy's law.  Unless you have some
|> special dispensation from its action, ANY new feature has a potential
|> for creating problems.  (Before you say something about the whole STL,
|> remeber that there are existing implementations of an STL.  It has
|> had time for many [pobably most] of its defects to be exposed. This
|> new feature does not fall into that class.)

I agree with your statement concerning Murphy's law; in fact, I agree
with much of what you are saying.  But I am trying to put things in
perspective.  The added complexity of this feature is small compared to
that of untold number of other new features.

You mention the STL globally, for example.  As other postings have
recently pointed out, none of the current implementations of STL are in
any way "usable"; for the moment, the STL is a beautiful feasibility
study, but still needs to be industrialized.  In particular, there is a
great deal of work still needed with regards to the behavior of the STL
in the presence of exceptions from the instantiating classes.

If you were reacting against the entire STL, on the grounds of its
complexity, I could almost go along with you.  Given that we have the
STL, and in a version which requires member templates and partial
specialization anyway, I find it difficult to see where the added
complexity of comparing the allocators makes a difference.

|> > |> > The case which triggered this discussion, splice, is almost certainly a
|> > |> > simple oversight.  Had I and the others involved in the discussion
|> > |> > really understood what was being proposed in the standard, it would have
|> > |> > been recognized as such immediately.
|> >
|> > |> Is it the only oversight?
|> >
|> > Almost certainly not.  The C standard is significantly less complicated,
|> > and has been around now for a certain time, yet every now and then
|> > someone comes across an oversight.  The committee members are human, and
|> > despite their best efforts, there will be errors, contradictions, and
|> > oversights in the final standard.  Or they will be the first standards
|> > committee not to have some.
|> >
|> > |> Is the additional complexity needed?
|> >
|> > What does it mean by needed?  I don't need it for my current
|> > application, if that is what you mean.

|> By needed, I mean "Is there no other way to get the function it
|> provides?"

There is no easy way.  IMHO, the functionality is rare enough that we
don't really need to provide for it in the standard, and I probably
would have adopted a solution in which all instances of a given type of
allocator must compare equal.  But I don't find the added complexity of
the solution adopted particularly frightening.  In context, of course.

|> > I have no problem envisaging applications where it would be useful.
|> > From a users point of view, the current situation represents less
|> > complexity than the alternatives.
|> >

|> 1) Please describe such an application and show that it could not
|> possibly be solved without this feature.

I have already posted an example in which the allocators use different
pools of shared memory.  Assigning between pools requires a deep copy;
within the same pool only copy on write.

|> 2) The current situation is the HP STL and it does NOT have either
|> of the features under discussion.  I believe that argues for the
|> exclusion of the features rather than their inclusion.

The current situation is the HP STL, and it does not support exceptions.
Does this mean we should not have exceptions in the language?

The current situation is the HP STL, and it does not use member
templates nor partial specialization (for obvious reasons).  Should we
refuse the changes in the draft which require the standard library to
use these?

|> > |> Unless
|> > |> the answer to both questions is an unequivacal yes, there is a problem.
|> >
|> > The answer will never be an unequivacal yes, as long as the committee is
|> > made up of human beings.
|> >
|> > |> > |>     Given that all instances of an allocator have to be
|> > |> > |> functionally equivalent, is there a real need to specify special
|> > |> > |> constructors for each allocator instance?  Is it worth the
|> > |> > |> complication and potential misunderstanding this feature has
|> > |> > |> demonstrated it can cause?
|> > |> >
|> > |> > The whole point is that *not* all instances of an allocator must be
|> > |> > functionally equivalent.  And the implementation must adapt, using
|> > |> > different techniques when the instances are not functionally equivalent.
|> > |> > In cases where this test is significant, the implementation is free to
|> > |> > partially specialize the template for the default allocator (for which
|> > |> > all instances *are* functionally equivalent).  Most of the time, I
|> > |> > imagine that the cost of the extra test is negligible.  I also imagine
|> > |> > that in every case where all instances are functionally equivalent,
|> > |> > operator== will be an inline function, so the compiler should be able to
|> > |> > optimize the test away, and dead code elimination remove the more
|> > |> > complex branch which will never be taken.  (This is well within the
|> > |> > scope of what, I believe, most optimizers today are already capable of
|> > |> > doing.)
|> >
|> > |> Ask the converse question -- why not have all the instances of an
|> > |> allocator be functionally equivalent?  If they were, the extra complexity
|> > |> complexity ends up in conversion constructors between instances with
|> > |> different allocators.  That looks like a better place for it than buried
|> > |> in odd corners of the algorithms.
|> >
|> > In sum, it is better to put the added complexity in the users lap,
|> > rather than to hide it away somewhere deep in the implementation.  I
|> > don't agree.
|> >

|> Not quite the point.  The STL as it exists has amazingly few traps and
|> gotcha's.

Really?  I find it fairly tricky, myself.  At least in comparison with
e.g.: the Booch Components, or my own classes, that I used previously.
I accept its complexity for two reasons:

1. It buys us a lot.  The STL does a lot, lot more than the
corresponding classes in the Booch components, or my own classes.

2. It is orthogonal.  The complexity is there, but we can master it,
because of the orthogonality.  The STL is not a set of random templates,
but a system.

My interpretation of the current situation with regards to the allocator
is that it "fits in" with the rest.

|> One of its main strengths is its effeciency.  It uses features
|> of the language to select the best implementation for a particular
|> combination of algorithm and data structure.  With only a little effort,
|> a user can determine exactly what run time characteristics a particular
|> piece of code will have.  These new features necessitate a change it that
|> philosiphy.  They can change the running time of a piece of code drasticly.
|> They introduce code that is expected to be routinely optimized away.

These new features only affect the running time of a peice of code if
they are used.  And there is no code that is expected to be routinely
optimized away.

|> One of the strongest criticisms of C++ vs C is that it procuduces
|> unexpected amounts of code for what seems to be fairly simple actions.
|> Up till this feature, the STL has NOT been a contributor to this problem.
|> This should NOT change.

It hasn't?  Like most reasonable C++ container classes, the STL "hides"
a certain amount of what is going on.  Incrementing an iterator may
entail significantly more overhead than incrementing a pointer, for
example.  If STL didn't hide this code, there would be no point in using
it.

|> Further, the extra complexity may not end up in the users lap at all.
|> The conversion constructor should probably be a template member of the
|> container or string class.  That would isolate the complexity in a
|> sepearate and identifiable entity that would only be introduced into
|> a program if it was actually needed.

The extra complexity is *ONLY* present if you instantiate a container
with a user defined allocator.  In I would guess 99% of the cases, you
never mention the allocator, and you get no added complexity.

|> > |> > The only real problem I see today is that the only document we have on
|> > |> > all of this is the draft standard.  Which is a draft, and is a standard,
|> > |> > not an instructional text.  Which means that the driving ideas, and how
|> > |> > it is meant to be used, are often not immediatly apparent.
|> >
|> > |> That and no one is likely to implement the new stuff completely before
|> > |> the standard passes.  Some degree of certainty that a reliable
|> > |> implementation exists and that this fancy piece of brick-a-brack really
|> > |> serves a useful function would make me and I suspect a lot of other
|> > |> folks happier.
|> >
|> > I suspect that most of the implementors (Rogue Wave, et al.) are waiting
|> > mainly for a decision concerning exception safety in the library.  This
|> > will have a major impact on their code.  In addition, I can imagine that
|> > they are waiting for a compiler which supports member templates and
|> > partial specialization.
|> >
|> > The problems that I see are *NOT* in the library itself.  The solution
|> > to this problem is known, and is not that difficult.  At least, if your
|> > compiler supports partial specialization.  Most don't at present.

|> I think that is too strong a statement.  The other problems you mentioned
|> are much more immediate and actually block detailed evaluation of these
|> features.  That does NOT mean that the library does not have problems.
|> The fact that the impact of these features will not be properly evaluated
|> before the adoption of the standard is a compelling argument for postponing
|> their inclusion in the standard.

I'm not sure what other problems you are thinking of.

The entire standard library, as proposed, is totally untested.  The
allocator feature no more no less than the rest.  IMHO, this *IS* a
problem.  I would be much happier if we were standardizing "existing
practice".  The other side of the coin, however, is that the "existing
practice" for C++ system libraries is pretty much limited to iostream.
So we have a choice between two evils: "inventing" the library in the
standardization committee, or offering so little that people cannot
begin working.

On the whole, I think STL, despite certain weaknesses, is a good
compromize.  While not really tested, it is coherent enough that one can
analyse it fairly well.  There is a proof of concept implementation
which "proves" feasibility for a number of specific issues (but far from
all).  I don't think the allocator feature changes this evaluation much
one way or another; IMHO, a more important point would be a proof of
concept with regards to what happens (or can happen) when an exception
is thrown.

|> There is nothing to prevent an implementer from including these features
|> as extensions.  If they can work out the problems, fine.  However,
|> requiring the feature to be present in all implementations does not
|> look like a good idea at this time.

That is my opinion with regards to the complicated stuff, like
namespaces and RTTI.  I actively oppose namespace as a complication
which costs more than it buys, for example.  I for the life of me put
the allocator handling in the same category.  It is cheap enough that I
don't really care.
--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils,    tudes et r   alisations en logiciel orient    objet --
                -- A la recherche d'une activit    dans une region francophone
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

James Kanze US/ESC 60/3/141 #40763 wrote:
>
> In article <323C6318.617C@cds.duke.edu> Max TenEyck Woodbury
> <mtew@cds.duke.edu> writes:
>
> |> James Kanze US/ESC 60/3/141 #40763 wrote:
>
> |> > One of the reasons I suspect that the impact was understood is that it
> |> > is, in fact, not very great.  It does mean a bit more work for the
> |> > implementor, particularly if he wants a quality implementation.  But it
> |> > makes things somewhat easier for the user, with no cost for the users
> |> > who do not need the feature (supposing a quality implementation).
>
> |> There you are proposing a quality of implementation standard.  Quality of
> |> implementation is a topic most standard commitees seem to avoid (to put
> |> it mildly).
>
> The standard does not mandate a quality of implementation, in any way,
> shape, form or fashion.  Nor should it.

But your arguments base what should or should not be in the standard
on quality of implementation.  Since the standard should NOT be setting
quality standards for implementations, those lines of arguments are
questionable.

>
> On the other hand, one of the proclaimed goals of C++ is that there can
> be an efficient implementation.  In fact, within the standards committee,
> the lack of an efficient implementation of a given feature is a strong
> argument against that feature.  My discussions concerning how to
> implement the classes efficiently with the current definition of
> allocators is meant simply as a proof that this particular argument
> against them is not valid: there is an efficient implementation.
> Whether a specific implementor chooses to use it or not is his business
> (in a very literal sense); the standard cannot require it.
>

While the lack of an efficient implementation is a strong argument
against a feature, the presence of implementations that depend on
the quality of an implementation is not an argument for that feature.

> This is true of everything in the C++ standard, however.  The standard
> does not forbid the compiler from generating a ten second empty loop
> after each statement.  No one would argue that C++'s having statements
> is a misfeature because of this, however.
>

Tru, but irrelavant.

> |> > Once understood, it is apparent that the whole thing "hangs together" in
> |> > a way that cannot be the result of chance or blind stumbling by the
> |> > committee.
>
> |> I disagree.  Run time instation of allocators and run time checks that
> |> allocators are compatible add a layer of complexity to both strings and
> |> containers.  The rest of the structure hangs together but this particular
> |> feature has the flavor of a 'tag end' or after thought.
>
> I cannot see where it adds a layer of complexity.  I do not find the
> added complexity overwhelming.
>

To see the extra complexity, try compairing an effieient and
correct implementation with the feature to the extant STL.

The added complexity is not overwelming.  It is unnecessary.

> I also find that the detailed description of the allocator requirements,
> and the fact that in some cases, the complexity is given as depending on
> whether the allocators compare equal, as a strong sign that considerable
> thought went into this extension as well.
>

There is another point to be considered.  Given an application
where different allocators should be used but where operations
where the types derived from those allocators rarely interact,
all those operations that have potential allocator interactions
have to include a run time test for that interaction.  If run
time differentiation is not allowed, that test would not be
needed.  The correct case would be chosen at compile time,
depending on which allocators were involved.

> |> The impact is NOT on the allocator itself.  The impact is on strings and
> |> containers.  I'm not saying that there isn't a logical structure to the
> |> standard.  On the contrary, it is quite well structured.  That does NOT
> |> mean that it is easy to understand all the implications embeded in the
> |> standard.
>
> Agreed.  This seems to be a characteristic of standards in general.  In
> the case of C++, it is exaberated by the fact that the language itself
> is very complicated, and by the fact that we are not yet seeing the
> finished product.
>

All the more reason for not introducing new features without a
demonstrated need for it.

> |> > |> > Although the solution adopted by the committee is more complex than I
> |> > |> > would have proposed, I cannot see where it has had a "negative impact on
> |> > |> > the language", or that there is a "potential source of inoperability".
> |> >
> |> > |> The extra code needed to deal with complex allocators makes any library
> |> > |> implementation larger and compile times slower, if for no other reason
> |> > |> than the number of characters that will have to be processed by the
> |> > |> front end.  That's a negative impact.
> |> >
> |> > This is part of the standard library.  While not yet the case, I would
> |> > presume that once the standard is a standard, given the size and
> |> > complexity of the library (and of the language in general), it will be
> |> > integrated into the compiler, most likely in the form of precompiled
> |> > headers which are automatically loaded.
>
> |> Here you are presuming on a number of implementation details which are
> |> irrelavant.  However, even precompiled headers reflect the complexity of
> |> the material precompiled.  Unneeded complexity is still a looser.
>
> I am only showing that the problem has a known solution.
>
> Note that I don't disagree with your basic premise.  All I am saying is
> that in this particular case, the added complexity is not that high, all
> things considered.
>

But is it needed at all?

> |> > |> "potential source of inoperability" is probably a poor choice of words.
> |> > |> I was trying to convey the increased risk of implementation defects
> |> > |> caused by the increased complexity.
> |> >
> |> > This is C++.  In this particular case, I don't see the risk as being
> |> > particularly high.  Much less than, say, namespaces, for example.
>
> |> Argh!  Have you never heard of Murphy's law.  Unless you have some
> |> special dispensation from its action, ANY new feature has a potential
> |> for creating problems.  (Before you say something about the whole STL,
> |> remeber that there are existing implementations of an STL.  It has
> |> had time for many [pobably most] of its defects to be exposed. This
> |> new feature does not fall into that class.)
>
> I agree with your statement concerning Murphy's law; in fact, I agree
> with much of what you are saying.  But I am trying to put things in
> perspective.  The added complexity of this feature is small compared to
> that of untold number of other new features.
>
> You mention the STL globally, for example.  As other postings have
> recently pointed out, none of the current implementations of STL are in
> any way "usable"; for the moment, the STL is a beautiful feasibility
> study, but still needs to be industrialized.  In particular, there is a
> great deal of work still needed with regards to the behavior of the STL
> in the presence of exceptions from the instantiating classes.
>

Exception handling and interrupts never were a strong point of C.  The
attempt to address the issue in C++ is something I have been watching
with great interest.  Some of the comments I've seen on the subject
have been on a par with the code a COBOL programmer I once knew
generated when introduced to ALGOL, but I've kept my opinion on the
subject to myself so far, since it did not have an impact on applications
I have had to deal with directly.  Any way, that's a topic for another
thread.

> If you were reacting against the entire STL, on the grounds of its
> complexity, I could almost go along with you.  Given that we have the
> STL, and in a version which requires member templates and partial
> specialization anyway, I find it difficult to see where the added
> complexity of comparing the allocators makes a difference.
>

My personal reaction to the STL is one of mild bemusement.  There is
a great potential in templates and the STL is a good (possibly very
good) example of their proper usage.  It has been an excelent tool
for finding exactly where the template technology needed work.  There
are a few places in it where I wonder if simpler and more elegant
techniques than those used would work when template implementations
are more uniformly implemented, but I realize that getting it to do
something with existing implementations has to come first.  I am
very worried that these work arounds may become embeded in the C++
standard.

> |> > |> > The case which triggered this discussion, splice, is almost certainly a
> |> > |> > simple oversight.  Had I and the others involved in the discussion
> |> > |> > really understood what was being proposed in the standard, it would have
> |> > |> > been recognized as such immediately.
> |> >
> |> > |> Is it the only oversight?
> |> >
> |> > Almost certainly not.  The C standard is significantly less complicated,
> |> > and has been around now for a certain time, yet every now and then
> |> > someone comes across an oversight.  The committee members are human, and
> |> > despite their best efforts, there will be errors, contradictions, and
> |> > oversights in the final standard.  Or they will be the first standards
> |> > committee not to have some.
> |> >
> |> > |> Is the additional complexity needed?
> |> >
> |> > What does it mean by needed?  I don't need it for my current
> |> > application, if that is what you mean.
>
> |> By needed, I mean "Is there no other way to get the function it
> |> provides?"
>
> There is no easy way.  IMHO, the functionality is rare enough that we
> don't really need to provide for it in the standard, and I probably
> would have adopted a solution in which all instances of a given type of
> allocator must compare equal.  But I don't find the added complexity of
> the solution adopted particularly frightening.  In context, of course.
>

So a rarely used feature that could be implemented, with some work, in
a different way gets to muddy up the otherwise clean design of the
library.  I believe those were the ones that "The design and evolution
of C++" (or whatever its exact title is) recomended be dropped.

> |> > I have no problem envisaging applications where it would be useful.
> |> > From a users point of view, the current situation represents less
> |> > complexity than the alternatives.
> |> >
>
> |> 1) Please describe such an application and show that it could not
> |> possibly be solved without this feature.
>
> I have already posted an example in which the allocators use different
> pools of shared memory.  Assigning between pools requires a deep copy;
> within the same pool only copy on write.
>

I've seen the reference, but did the pool ID have to be a run time
parameter?  Could it have been a compile time parameter?

> |> 2) The current situation is the HP STL and it does NOT have either
> |> of the features under discussion.  I believe that argues for the
> |> exclusion of the features rather than their inclusion.
>
> The current situation is the HP STL, and it does not support exceptions.
> Does this mean we should not have exceptions in the language?
>

1) Exceptions are acknowledged to be an important feature with a wide
range of applications.  Run time allocator differentiation is a mostly
hypothetical feature with few expected applications.

2) That discussion belongs in another thread.

> The current situation is the HP STL, and it does not use member
> templates nor partial specialization (for obvious reasons).  Should we
> refuse the changes in the draft which require the standard library to
> use these?
>

There should NOT be an explict requirement for any particular feature
to be used in an implementation unless it has a direct impact on the
feature being implemented.  Member templates and partial specialization
should not be treated any differently than any other language feature
in this respect.

> |> > |> Unless
> |> > |> the answer to both questions is an unequivacal yes, there is a problem.
> |> >
> |> > The answer will never be an unequivacal yes, as long as the committee is
> |> > made up of human beings.
> |> >
> |> > |> > |>     Given that all instances of an allocator have to be
> |> > |> > |> functionally equivalent, is there a real need to specify special
> |> > |> > |> constructors for each allocator instance?  Is it worth the
> |> > |> > |> complication and potential misunderstanding this feature has
> |> > |> > |> demonstrated it can cause?
> |> > |> >
> |> > |> > The whole point is that *not* all instances of an allocator must be
> |> > |> > functionally equivalent.  And the implementation must adapt, using
> |> > |> > different techniques when the instances are not functionally equivalent.
> |> > |> > In cases where this test is significant, the implementation is free to
> |> > |> > partially specialize the template for the default allocator (for which
> |> > |> > all instances *are* functionally equivalent).  Most of the time, I
> |> > |> > imagine that the cost of the extra test is negligible.  I also imagine
> |> > |> > that in every case where all instances are functionally equivalent,
> |> > |> > operator== will be an inline function, so the compiler should be able to
> |> > |> > optimize the test away, and dead code elimination remove the more
> |> > |> > complex branch which will never be taken.  (This is well within the
> |> > |> > scope of what, I believe, most optimizers today are already capable of
> |> > |> > doing.)
> |> >
> |> > |> Ask the converse question -- why not have all the instances of an
> |> > |> allocator be functionally equivalent?  If they were, the extra complexity
> |> > |> complexity ends up in conversion constructors between instances with
> |> > |> different allocators.  That looks like a better place for it than buried
> |> > |> in odd corners of the algorithms.
> |> >
> |> > In sum, it is better to put the added complexity in the users lap,
> |> > rather than to hide it away somewhere deep in the implementation.  I
> |> > don't agree.
> |> >
>
> |> Not quite the point.  The STL as it exists has amazingly few traps and
> |> gotcha's.
>
> Really?  I find it fairly tricky, myself.  At least in comparison with
> e.g.: the Booch Components, or my own classes, that I used previously.
> I accept its complexity for two reasons:
>
> 1. It buys us a lot.  The STL does a lot, lot more than the
> corresponding classes in the Booch components, or my own classes.
>
> 2. It is orthogonal.  The complexity is there, but we can master it,
> because of the orthogonality.  The STL is not a set of random templates,
> but a system.
>
> My interpretation of the current situation with regards to the allocator
> is that it "fits in" with the rest.
>

I agree that the allocator serves a function.  I think a lot of that
function is comprimised by run time differentation.

> |> One of its main strengths is its effeciency.  It uses features
> |> of the language to select the best implementation for a particular
> |> combination of algorithm and data structure.  With only a little effort,
> |> a user can determine exactly what run time characteristics a particular
> |> piece of code will have.  These new features necessitate a change it that
> |> philosiphy.  They can change the running time of a piece of code drasticly.
> |> They introduce code that is expected to be routinely optimized away.
>
> These new features only affect the running time of a peice of code if
> they are used.  And there is no code that is expected to be routinely
> optimized away.
>

That is only true for implementations above a specific quality and
is not true if you also consider compile times as relavent.

> |> One of the strongest criticisms of C++ vs C is that it procuduces
> |> unexpected amounts of code for what seems to be fairly simple actions.
> |> Up till this feature, the STL has NOT been a contributor to this problem.
> |> This should NOT change.
>
> It hasn't?  Like most reasonable C++ container classes, the STL "hides"
> a certain amount of what is going on.  Incrementing an iterator may
> entail significantly more overhead than incrementing a pointer, for
> example.  If STL didn't hide this code, there would be no point in using
> it.
>

On the other hand, by calling it an 'iterator' and not a 'pointer', it
gives appropriate warning that the operation may not be simple.  Your
point is that some complexity is 'hidden'.  That overstates the case.
My point is that this complexity is well documented and the resulting
code may actually be simpler than experience with such general purpose
constructs would indicate.

> |> Further, the extra complexity may not end up in the users lap at all.
> |> The conversion constructor should probably be a template member of the
> |> container or string class.  That would isolate the complexity in a
> |> sepearate and identifiable entity that would only be introduced into
> |> a program if it was actually needed.
>
> The extra complexity is *ONLY* present if you instantiate a container
> with a user defined allocator.  In I would guess 99% of the cases, you
> never mention the allocator, and you get no added complexity.
>

Only if your compiler knows enough to drop the dead code.

Note:  I sense a communication problem here.  I am complaining about
run time differentation of allocators specifically.  While allocators
in general cover an inherantly messy topic, they serve a purpose and
I am not arguing for their elimination.  However, they should be an
exclusively compile time mechanism.

> |> > |> > The only real problem I see today is that the only document we have on
> |> > |> > all of this is the draft standard.  Which is a draft, and is a standard,
> |> > |> > not an instructional text.  Which means that the driving ideas, and how
> |> > |> > it is meant to be used, are often not immediatly apparent.
> |> >
> |> > |> That and no one is likely to implement the new stuff completely before
> |> > |> the standard passes.  Some degree of certainty that a reliable
> |> > |> implementation exists and that this fancy piece of brick-a-brack really
> |> > |> serves a useful function would make me and I suspect a lot of other
> |> > |> folks happier.
> |> >
> |> > I suspect that most of the implementors (Rogue Wave, et al.) are waiting
> |> > mainly for a decision concerning exception safety in the library.  This
> |> > will have a major impact on their code.  In addition, I can imagine that
> |> > they are waiting for a compiler which supports member templates and
> |> > partial specialization.
> |> >
> |> > The problems that I see are *NOT* in the library itself.  The solution
> |> > to this problem is known, and is not that difficult.  At least, if your
> |> > compiler supports partial specialization.  Most don't at present.
>
> |> I think that is too strong a statement.  The other problems you mentioned
> |> are much more immediate and actually block detailed evaluation of these
> |> features.  That does NOT mean that the library does not have problems.
> |> The fact that the impact of these features will not be properly evaluated
> |> before the adoption of the standard is a compelling argument for postponing
> |> their inclusion in the standard.
>
> I'm not sure what other problems you are thinking of.
>
> The entire standard library, as proposed, is totally untested.  The
> allocator feature no more no less than the rest.  IMHO, this *IS* a
> problem.  I would be much happier if we were standardizing "existing
> practice".  The other side of the coin, however, is that the "existing
> practice" for C++ system libraries is pretty much limited to iostream.
> So we have a choice between two evils: "inventing" the library in the
> standardization committee, or offering so little that people cannot
> begin working.
>

NOT TRUE.  Very large chunks of the standard, including a lot of the
STL, is based on existing implemntations and has been through a LOT of
testing and field trials.  There are a number of significant pieces that
have not been implemented, but not enough to warrent the phrase 'totally
untested'.

In particular, there is a widely available implementation of the STL.
Its design includes compile time differentiation of allocators (abet
the implementation is necessarily kluged to get arround missing
compiler features).

OK... I think I see what might have happened.  The HP STL could not
implement compile time allocator differentiation because of a lack
of a universally implemented compiler feature.  It put a crude macro
in its place.  The comittee put run time differentation in place of
the macro.  While the run time differentiator is fractionally better
than the macro, what was really needed was to go back to the original
design.

> On the whole, I think STL, despite certain weaknesses, is a good
> compromize.  While not really tested, it is coherent enough that one can
> analyse it fairly well.  There is a proof of concept implementation
> which "proves" feasibility for a number of specific issues (but far from
> all).  I don't think the allocator feature changes this evaluation much
> one way or another; IMHO, a more important point would be a proof of
> concept with regards to what happens (or can happen) when an exception
> is thrown.
>
> |> There is nothing to prevent an implementer from including these features
> |> as extensions.  If they can work out the problems, fine.  However,
> |> requiring the feature to be present in all implementations does not
> |> look like a good idea at this time.
>
> That is my opinion with regards to the complicated stuff, like
> namespaces and RTTI.  I actively oppose namespace as a complication
> which costs more than it buys, for example.  I for the life of me put
> the allocator handling in the same category.  It is cheap enough that I
> don't really care.

Run time differentiation of allocators with its impact on strings and
containers may not be that cheap.  Strings are something almost every
practical application has to deal with.  Messing up any aspect of their
specification is likely to have a significant impact eventually.  Let's
fix the problem now rather than later.

mtew@cds.duke.edu


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

In article <32404A98.5BBF@cds.duke.edu> Max TenEyck Woodbury
<mtew@cds.duke.edu> writes:

|> James Kanze US/ESC 60/3/141 #40763 wrote:

    [Again, I am cutting the parts of the article where we are just
 disagreeing, and will only react to the places where I am sure that
 my statements have been misunderstood...]

|> > The standard does not mandate a quality of implementation, in any way,
|> > shape, form or fashion.  Nor should it.

|> But your arguments base what should or should not be in the standard
|> on quality of implementation.  Since the standard should NOT be setting
|> quality standards for implementations, those lines of arguments are
|> questionable.

My argument is based on the fact the one of the stated goals of C++ is
run-time efficiency.  Obviously, the standard cannot impose this, but
one of the criteria for including a feature is that is must be
implementable in an efficient manner.  Obviously, the standard doesn't
mandate that any given implementation implement the feature in an
efficient manner, but without prove that such an implementation is
possible, the committee should, and probably would, reject the
implementation.

Your arguments against run-time checking of the allocator have been
partially based on the loss of efficiency it may cause in programs that
don't need it.  I am simply pointing out that there is a solution which
does not involve any loss of efficiency.

While I am at it, I will respond to a point you bring up later as well.
The efficient solution I describe does not require any particular
optimization on the part of the compiler.  It does require that the
compiler support partial specialization.  But this is required by the
standard anyway.  Partial specialization is not an optimization, but a
way of telling the compiler: if this template instantiation meets the
following criteria, use this implementation instead of the more general
one.

|> There is another point to be considered.  Given an application
|> where different allocators should be used but where operations
|> where the types derived from those allocators rarely interact,
|> all those operations that have potential allocator interactions
|> have to include a run time test for that interaction.  If run
|> time differentiation is not allowed, that test would not be
|> needed.  The correct case would be chosen at compile time,
|> depending on which allocators were involved.

This is a difficult point.  If objects using two allocators never
interact, the allocators should probably be of different types.  In
practice, however, because there will be no partial specialization for
these types, the allocator instances will be compared anyway.

In the main utilisation for customized allocators that I can think of,
however, they will interact, and the run-time test is necessary.  To
return to my example of a system using shared memory.  The solution I
would propose would have a custom allocator, ShMemAllocator, with at
least two constructors: one which specifies which pool of shared memory
to use, and one which takes an "allocator" as argument, and uses
unshared memory.  If there is a need for strings in shared memory, the
application will not use "wstring" at all, but rather:

 typedef basic_string< wchar_t ,
                       string_char_traits< wchar_t > ,
                          ShMemAllocator >
                     MyString ;

Except for using MyString instead of wstring, all of the application
programs will be written as usual, without paying any attention to the
fact that some of the strings may be in shared memory.  Temporaries,
local variables, and such, will be created using the standard heap,
because of the default argument for the allocator in the class
definition.  (This is the reason for the second constructor in
ShMemAllocator!)  Strings in shared memory must be created by special
routines anyway, since they must ensure not only that all memory
allocated by the string object is in shared memory, but also that the
object itself is in shared memory, and can be located in some way by the
other processes.  Such routines will, of course, pass the appropriate
allocator parameter to the MyString constructor.

Done this way, only the routines which actually construct the strings in
shared memory need to be aware of the fact that they are in shared
memory.  Under your proposal, the user of MyString must be aware of
which strings are or are not in shared memory; the decision between deep
copy (using, presumably, s1.assign( s2.begin() , s2.end() )) and shallow
(the classical operator=).  Under the current standard proposal, this is
handled by basic_string itself.

    [...]
|> I agree that the allocator serves a function.  I think a lot of that
|> function is comprimised by run time differentation.

    [...]
|> Note:  I sense a communication problem here.  I am complaining about
|> run time differentation of allocators specifically.  While allocators
|> in general cover an inherantly messy topic, they serve a purpose and
|> I am not arguing for their elimination.  However, they should be an
|> exclusively compile time mechanism.

Curiously, this is where we differ.  I agree with much of your general
comment.  I actually think that have allocator at all is probably
unnecessary complexity; the only real application for it that I can
think of is shared memory, which seems to be a bit of a special case
anyway, and is not in general addressed by the standard.  (The allocator
may be used to get the object to use a heap in the shared memory, but
there is nothing to synchronize concurrent access, for example.)  So I
really think that we could do without the allocator.

If we have the allocator, however, I feel that it should be tested at
run-time, as the current draft requires, in order to support the above
scenario.
--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils,    tudes et r   alisations en logiciel orient    objet --
                -- A la recherche d'une activit    dans une region francophone
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

James Kanze US/ESC 60/3/141 #40763 wrote:
>
> In article <322DF902.1065@cds.duke.edu> Max TenEyck Woodbury
> <mtew@cds.duke.edu> writes:
>
> |>     The allocator in the ANSI standard is another animal entirely.
> |> It is now has a parameter to the constructor for strings and
> |> containers.  By differentiating the allocator instances, it is now
> |> possible to require that storage allocated through one allocator
> |> instance only be deallocated through the same instance.  This
> |> means that there have to be run-time checks in various algorithms
> |> to assure that the allocator instances are compatible before some
> |> operations can be performed.
>
> |>     While I suspect that this was not the intent of the commitee,
> |> the failure to insist that all allocators of the same class can
> |> interoperate is a significant omission.  It is already having a
> |> negative impact on the language as other threads in this newsgroup
> |> have demonstrated.  The draft needs to be ammended to remove this
> |> potential source of inoperability.
>
> Why do you think that it is not the intent of the committee.  This is
> definitly something added with regards to the HP implementation; I can
> only presume that it was intentionally added, and not by accident.

Agreed that it was intentionally added, but was its impact understood?
More importantly, given the extant code (the HP implementation of
the STL and various string classes) could a simpler mechanism have
achieved the same end without introducing the additional complexity?

> The text is very clear (once you find it) as to what is required of an
> allocator.  In at least some cases, the complexity of a function is
> specified as depending on whether the allocators of the two containers
> compare equal.  It looks more to me as if the committee knew exactly
> what they were doing, probably more than I or some of the others
> discussing this do.

The fact that the allocator requirements are remote from the section
where they have their impact is the strongest reason for raising the
question about how much consideration was given to that impact.

> Although the solution adopted by the committee is more complex than I
> would have proposed, I cannot see where it has had a "negative impact on
> the language", or that there is a "potential source of inoperability".

The extra code needed to deal with complex allocators makes any library
implementation larger and compile times slower, if for no other reason
than the number of characters that will have to be processed by the
front end.  That's a negative impact.

"potential source of inoperability" is probably a poor choice of words.
I was trying to convey the increased risk of implementation defects
caused by the increased complexity.

> The case which triggered this discussion, splice, is almost certainly a
> simple oversight.  Had I and the others involved in the discussion
> really understood what was being proposed in the standard, it would have
> been recognized as such immediately.

Is it the only oversight?  Is the additional complexity needed?  Unless
the answer to both questions is an unequivacal yes, there is a problem.

>
> |>     Given that all instances of an allocator have to be
> |> functionally equivalent, is there a real need to specify special
> |> constructors for each allocator instance?  Is it worth the
> |> complication and potential misunderstanding this feature has
> |> demonstrated it can cause?
>
> The whole point is that *not* all instances of an allocator must be
> functionally equivalent.  And the implementation must adapt, using
> different techniques when the instances are not functionally equivalent.
> In cases where this test is significant, the implementation is free to
> partially specialize the template for the default allocator (for which
> all instances *are* functionally equivalent).  Most of the time, I
> imagine that the cost of the extra test is negligible.  I also imagine
> that in every case where all instances are functionally equivalent,
> operator== will be an inline function, so the compiler should be able to
> optimize the test away, and dead code elimination remove the more
> complex branch which will never be taken.  (This is well within the
> scope of what, I believe, most optimizers today are already capable of
> doing.)

Ask the converse question -- why not have all the instances of an
allocator be functionally equivalent?  If they were, the extra complexity
complexity ends up in conversion constructors between instances with
different allocators.  That looks like a better place for it than buried
in odd corners of the algorithms.

> The only real problem I see today is that the only document we have on
> all of this is the draft standard.  Which is a draft, and is a standard,
> not an instructional text.  Which means that the driving ideas, and how
> it is meant to be used, are often not immediatly apparent.

That and no one is likely to implement the new stuff completely before
the standard passes.  Some degree of certainty that a reliable
implementation exists and that this fancy piece of brick-a-brack really
serves a useful function would make me and I suspect a lot of other
folks happier.

> What we really need is the second edition of Plauger's book.  (Having
> seen the proposed library be totally redesigned while the first edition
> was being printed, I can imagine that he will not be bringing the second
> edition out until there is significantly more stability in the standard
> that at present.  Once burned, twice wary, as they say.)

Almost exactly the point I was trying to make...

mtew@cds.duke.edu
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

In article <3234C629.2863@cds.duke.edu> Max TenEyck Woodbury
<mtew@cds.duke.edu> writes:
|> James Kanze US/ESC 60/3/141 #40763 wrote:
|> >
|> > In article <322DF902.1065@cds.duke.edu> Max TenEyck Woodbury
|> > <mtew@cds.duke.edu> writes:
|> >
|> > |>     The allocator in the ANSI standard is another animal entirely.
|> > |> It is now has a parameter to the constructor for strings and
|> > |> containers.  By differentiating the allocator instances, it is now
|> > |> possible to require that storage allocated through one allocator
|> > |> instance only be deallocated through the same instance.  This
|> > |> means that there have to be run-time checks in various algorithms
|> > |> to assure that the allocator instances are compatible before some
|> > |> operations can be performed.
|> >
|> > |>     While I suspect that this was not the intent of the commitee,
|> > |> the failure to insist that all allocators of the same class can
|> > |> interoperate is a significant omission.  It is already having a
|> > |> negative impact on the language as other threads in this newsgroup
|> > |> have demonstrated.  The draft needs to be ammended to remove this
|> > |> potential source of inoperability.
|> >
|> > Why do you think that it is not the intent of the committee.  This is
|> > definitly something added with regards to the HP implementation; I can
|> > only presume that it was intentionally added, and not by accident.

|> Agreed that it was intentionally added, but was its impact understood?

I rather suspect it was.  The members of the library group are no
dummies.

One of the reasons I suspect that the impact was understood is that it
is, in fact, not very great.  It does mean a bit more work for the
implementor, particularly if he wants a quality implementation.  But it
makes things somewhat easier for the user, with no cost for the users
who do not need the feature (supposing a quality implementation).

Once understood, it is apparent that the whole thing "hangs together" in
a way that cannot be the result of chance or blind stumbling by the
committee.

|> More importantly, given the extant code (the HP implementation of
|> the STL and various string classes) could a simpler mechanism have
|> achieved the same end without introducing the additional complexity?

Perhaps.  It probably depends on your definition of simpler.  See below.

|> > The text is very clear (once you find it) as to what is required of an
|> > allocator.  In at least some cases, the complexity of a function is
|> > specified as depending on whether the allocators of the two containers
|> > compare equal.  It looks more to me as if the committee knew exactly
|> > what they were doing, probably more than I or some of the others
|> > discussing this do.

|> The fact that the allocator requirements are remote from the section
|> where they have their impact is the strongest reason for raising the
|> question about how much consideration was given to that impact.

The allocator requirements immediately precede the definition of the
standard default allocator.  Within the standard, this seems to be the
standard practice.  (The iterator requirements, for example, precede the
description of the predefined iterators, although one could well argue
that it has more impact on the algorithms section.)

This is linked to what a standard (as opposed to a tutorial text) should
be.  In a tutorial text, things will be described where they have a
major impact, and if it means describing something twice (perhaps from a
different point of view), so be it.  In a standard, ideally, everything
will be described exactly once; duplicate descriptions introduce the
risk of contradictions.

|> > Although the solution adopted by the committee is more complex than I
|> > would have proposed, I cannot see where it has had a "negative impact on
|> > the language", or that there is a "potential source of inoperability".

|> The extra code needed to deal with complex allocators makes any library
|> implementation larger and compile times slower, if for no other reason
|> than the number of characters that will have to be processed by the
|> front end.  That's a negative impact.

This is part of the standard library.  While not yet the case, I would
presume that once the standard is a standard, given the size and
complexity of the library (and of the language in general), it will be
integrated into the compiler, most likely in the form of precompiled
headers which are automatically loaded.

|> "potential source of inoperability" is probably a poor choice of words.
|> I was trying to convey the increased risk of implementation defects
|> caused by the increased complexity.

This is C++.  In this particular case, I don't see the risk as being
particularly high.  Much less than, say, namespaces, for example.

|> > The case which triggered this discussion, splice, is almost certainly a
|> > simple oversight.  Had I and the others involved in the discussion
|> > really understood what was being proposed in the standard, it would have
|> > been recognized as such immediately.

|> Is it the only oversight?

Almost certainly not.  The C standard is significantly less complicated,
and has been around now for a certain time, yet every now and then
someone comes across an oversight.  The committee members are human, and
despite their best efforts, there will be errors, contradictions, and
oversights in the final standard.  Or they will be the first standards
committee not to have some.

|> Is the additional complexity needed?

What does it mean by needed?  I don't need it for my current
application, if that is what you mean.

I have no problem envisaging applications where it would be useful.

James Kanze US/ESC 60/3/141 #40763 wrote:
>
> In article <3234C629.2863@cds.duke.edu> Max TenEyck Woodbury
> <mtew@cds.duke.edu> writes:
> |> James Kanze US/ESC 60/3/141 #40763 wrote:
> |> >
> |> > In article <322DF902.1065@cds.duke.edu> Max TenEyck Woodbury
> |> > <mtew@cds.duke.edu> writes:
> |> >
> |> > |>     The allocator in the ANSI standard is another animal entirely.
> |> > |> It is now has a parameter to the constructor for strings and
> |> > |> containers.  By differentiating the allocator instances, it is now
> |> > |> possible to require that storage allocated through one allocator
> |> > |> instance only be deallocated through the same instance.  This
> |> > |> means that there have to be run-time checks in various algorithms
> |> > |> to assure that the allocator instances are compatible before some
> |> > |> operations can be performed.
> |> >
> |> > |>     While I suspect that this was not the intent of the commitee,
> |> > |> the failure to insist that all allocators of the same class can
> |> > |> interoperate is a significant omission.  It is already having a
> |> > |> negative impact on the language as other threads in this newsgroup
> |> > |> have demonstrated.  The draft needs to be ammended to remove this
> |> > |> potential source of inoperability.
> |> >
> |> > Why do you think that it is not the intent of the committee.  This is
> |> > definitly something added with regards to the HP implementation; I can
> |> > only presume that it was intentionally added, and not by accident.
>
> |> Agreed that it was intentionally added, but was its impact understood?
>
> I rather suspect it was.  The members of the library group are no
> dummies.

I agrre that they are not dummies.  However they are human.

>
> One of the reasons I suspect that the impact was understood is that it
> is, in fact, not very great.  It does mean a bit more work for the
> implementor, particularly if he wants a quality implementation.  But it
> makes things somewhat easier for the user, with no cost for the users
> who do not need the feature (supposing a quality implementation).
>

There you are proposing a quality of implementation standard.  Quality of
implementation is a topic most standard commitees seem to avoid (to put
it mildly).

> Once understood, it is apparent that the whole thing "hangs together" in
> a way that cannot be the result of chance or blind stumbling by the
> committee.
>

I disagree.  Run time instation of allocators and run time checks that
allocators are compatible add a layer of complexity to both strings and
containers.  The rest of the structure hangs together but this particular
feature has the flavor of a 'tag end' or after thought.

> |> More importantly, given the extant code (the HP implementation of
> |> the STL and various string classes) could a simpler mechanism have
> |> achieved the same end without introducing the additional complexity?
>
> Perhaps.  It probably depends on your definition of simpler.  See below.
>
> |> > The text is very clear (once you find it) as to what is required of an
> |> > allocator.  In at least some cases, the complexity of a function is
> |> > specified as depending on whether the allocators of the two containers
> |> > compare equal.  It looks more to me as if the committee knew exactly
> |> > what they were doing, probably more than I or some of the others
> |> > discussing this do.
>
> |> The fact that the allocator requirements are remote from the section
> |> where they have their impact is the strongest reason for raising the
> |> question about how much consideration was given to that impact.
>
> The allocator requirements immediately precede the definition of the
> standard default allocator.  Within the standard, this seems to be the
> standard practice.  (The iterator requirements, for example, precede the
> description of the predefined iterators, although one could well argue
> that it has more impact on the algorithms section.)
>

The impact is NOT on the allocator itself.  The impact is on strings and
containers.  I'm not saying that there isn't a logical structure to the
standard.  On the contrary, it is quite well structured.  That does NOT
mean that it is easy to understand all the implications embeded in the
standard.

> This is linked to what a standard (as opposed to a tutorial text) should
> be.  In a tutorial text, things will be described where they have a
> major impact, and if it means describing something twice (perhaps from a
> different point of view), so be it.  In a standard, ideally, everything
> will be described exactly once; duplicate descriptions introduce the
> risk of contradictions.
>

I do not disagree, but this is not relavant to the discussion.

> |> > Although the solution adopted by the committee is more complex than I
> |> > would have proposed, I cannot see where it has had a "negative impact on
> |> > the language", or that there is a "potential source of inoperability".
>
> |> The extra code needed to deal with complex allocators makes any library
> |> implementation larger and compile times slower, if for no other reason
> |> than the number of characters that will have to be processed by the
> |> front end.  That's a negative impact.
>
> This is part of the standard library.  While not yet the case, I would
> presume that once the standard is a standard, given the size and
> complexity of the library (and of the language in general), it will be
> integrated into the compiler, most likely in the form of precompiled
> headers which are automatically loaded.
>

Here you are presuming on a number of implementation details which are
irrelavant.  However, even precompiled headers reflect the complexity of
the material precompiled.  Unneeded complexity is still a looser.

> |> "potential source of inoperability" is probably a poor choice of words.
> |> I was trying to convey the increased risk of implementation defects
> |> caused by the increased complexity.
>
> This is C++.  In this particular case, I don't see the risk as being
> particularly high.  Much less than, say, namespaces, for example.

Argh!  Have you never heard of Murphy's law.  Unless you have some
special dispensation from its action, ANY new feature has a potential
for creating problems.  (Before you say something about the whole STL,
remeber that there are existing implementations of an STL.  It has
had time for many [pobably most] of its defects to be exposed. This
new feature does not fall into that class.)

>
> |> > The case which triggered this discussion, splice, is almost certainly a
> |> > simple oversight.  Had I and the others involved in the discussion
> |> > really understood what was being proposed in the standard, it would have
> |> > been recognized as such immediately.
>
> |> Is it the only oversight?
>
> Almost certainly not.  The C standard is significantly less complicated,
> and has been around now for a certain time, yet every now and then
> someone comes across an oversight.  The committee members are human, and
> despite their best efforts, there will be errors, contradictions, and
> oversights in the final standard.  Or they will be the first standards
> committee not to have some.
>
> |> Is the additional complexity needed?
>
> What does it mean by needed?  I don't need it for my current
> application, if that is what you mean.
>

By needed, I mean "Is there no other way to get the function it
provides?"

> I have no problem envisaging applications where it would be useful.
> From a users point of view, the current situation represents less
> complexity than the alternatives.
>

1) Please describe such an application and show that it could not
possibly be solved without this feature.

2) The current situation is the HP STL and it does NOT have either
of the features under discussion.  I believe that argues for the
exclusion of the features rather than their inclusion.

> |> Unless
> |> the answer to both questions is an unequivacal yes, there is a problem.
>
> The answer will never be an unequivacal yes, as long as the committee is
> made up of human beings.
>
> |> > |>     Given that all instances of an allocator have to be
> |> > |> functionally equivalent, is there a real need to specify special
> |> > |> constructors for each allocator instance?  Is it worth the
> |> > |> complication and potential misunderstanding this feature has
> |> > |> demonstrated it can cause?
> |> >
> |> > The whole point is that *not* all instances of an allocator must be
> |> > functionally equivalent.  And the implementation must adapt, using
> |> > different techniques when the instances are not functionally equivalent.
> |> > In cases where this test is significant, the implementation is free to
> |> > partially specialize the template for the default allocator (for which
> |> > all instances *are* functionally equivalent).  Most of the time, I
> |> > imagine that the cost of the extra test is negligible.  I also imagine
> |> > that in every case where all instances are functionally equivalent,
> |> > operator== will be an inline function, so the compiler should be able to
> |> > optimize the test away, and dead code elimination remove the more
> |> > complex branch which will never be taken.  (This is well within the
> |> > scope of what, I believe, most optimizers today are already capable of
> |> > doing.)
>
> |> Ask the converse question -- why not have all the instances of an
> |> allocator be functionally equivalent?  If they were, the extra complexity
> |> complexity ends up in conversion constructors between instances with
> |> different allocators.  That looks like a better place for it than buried
> |> in odd corners of the algorithms.
>
> In sum, it is better to put the added complexity in the users lap,
> rather than to hide it away somewhere deep in the implementation.  I
> don't agree.
>

Not quite the point.  The STL as it exists has amazingly few traps and
gotcha's.  One of its main strengths is its effeciency.  It uses features
of the language to select the best implementation for a particular
combination of algorithm and data structure.  With only a little effort,
a user can determine exactly what run time characteristics a particular
piece of code will have.  These new features necessitate a change it that
philosiphy.  They can change the running time of a piece of code drasticly.
They introduce code that is expected to be routinely optimized away.

One of the strongest criticisms of C++ vs C is that it procuduces
unexpected amounts of code for what seems to be fairly simple actions.
Up till this feature, the STL has NOT been a contributor to this problem.
This should NOT change.

Further, the extra complexity may not end up in the users lap at all.
The conversion constructor should probably be a template member of the
container or string class.  That would isolate the complexity in a
sepearate and identifiable entity that would only be introduced into
a program if it was actually needed.

> |> > The only real problem I see today is that the only document we have on
> |> > all of this is the draft standard.  Which is a draft, and is a standard,
> |> > not an instructional text.  Which means that the driving ideas, and how
> |> > it is meant to be used, are often not immediatly apparent.
>
> |> That and no one is likely to implement the new stuff completely before
> |> the standard passes.  Some degree of certainty that a reliable
> |> implementation exists and that this fancy piece of brick-a-brack really
> |> serves a useful function would make me and I suspect a lot of other
> |> folks happier.
>
> I suspect that most of the implementors (Rogue Wave, et al.) are waiting
> mainly for a decision concerning exception safety in the library.  This
> will have a major impact on their code.  In addition, I can imagine that
> they are waiting for a compiler which supports member templates and
> partial specialization.
>
> The problems that I see are *NOT* in the library itself.  The solution
> to this problem is known, and is not that difficult.  At least, if your
> compiler supports partial specialization.  Most don't at present.

I think that is too strong a statement.  The other problems you mentioned
are much more immediate and actually block detailed evaluation of these
features.  That does NOT mean that the library does not have problems.
The fact that the impact of these features will not be properly evaluated
before the adoption of the standard is a compelling argument for postponing
their inclusion in the standard.

There is nothing to prevent an implementer from including these features
as extensions.  If they can work out the problems, fine.  However,
requiring the feature to be present in all implementations does not
look like a good idea at this time.

mtew@cds.duke.edu
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

First, an appology.  I've been under the misapprehension that
the standard's specification for allocators was roughly the one in
the HP STL implementation.  In that implementation allocators are
to C arrays much as iterators are to C pointers.  Even more than
iterators, they are a place to hang a few attributes and functions
without necessarily taking up any actual storage.  In the HP STL
implementation, the allocator is idealy a template parameter and
in practice a macro.  Allocators are a mechanism to use the type
safety checks of C++ to assure that objects in different storage
domains did not get accidently mixed with each other.  It is a
compile time check.

    The allocator in the ANSI standard is another animal entirely.
It is now has a parameter to the constructor for strings and
containers.  By differentiating the allocator instances, it is now
possible to require that storage allocated through one allocator
instance only be deallocated through the same instance.  This
means that there have to be run-time checks in various algorithms
to assure that the allocator instances are compatible before some
operations can be performed.

    While I suspect that this was not the intent of the commitee,
the failure to insist that all allocators of the same class can
interoperate is a significant omission.  It is already having a
negative impact on the language as other threads in this newsgroup
have demonstrated.  The draft needs to be ammended to remove this
potential source of inoperability.

    Given that all instances of an allocator have to be
functionally equivalent, is there a real need to specify special
constructors for each allocator instance?  Is it worth the
complication and potential misunderstanding this feature has
demonstrated it can cause?


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

In article <322DF902.1065@cds.duke.edu> Max TenEyck Woodbury
<mtew@cds.duke.edu> writes:

|>     The allocator in the ANSI standard is another animal entirely.
|> It is now has a parameter to the constructor for strings and
|> containers.  By differentiating the allocator instances, it is now
|> possible to require that storage allocated through one allocator
|> instance only be deallocated through the same instance.  This
|> means that there have to be run-time checks in various algorithms
|> to assure that the allocator instances are compatible before some
|> operations can be performed.

|>     While I suspect that this was not the intent of the commitee,
|> the failure to insist that all allocators of the same class can
|> interoperate is a significant omission.  It is already having a
|> negative impact on the language as other threads in this newsgroup
|> have demonstrated.  The draft needs to be ammended to remove this
|> potential source of inoperability.

Why do you think that it is not the intent of the committee.  This is
definitly something added with regards to the HP implementation; I can
only presume that it was intentionally added, and not by accident.

The text is very clear (once you find it) as to what is required of an
allocator.  In at least some cases, the complexity of a function is
specified as depending on whether the allocators of the two containers
compare equal.  It looks more to me as if the committee knew exactly
what they were doing, probably more than I or some of the others
discussing this do.

Although the solution adopted by the committee is more complex than I
would have proposed, I cannot see where it has had a "negative impact on
the language", or that there is a "potential source of inoperability".

The case which triggered this discussion, splice, is almost certainly a
simple oversight.  Had I and the others involved in the discussion
really understood what was being proposed in the standard, it would have
been recognized as such immediately.

|>     Given that all instances of an allocator have to be
|> functionally equivalent, is there a real need to specify special
|> constructors for each allocator instance?  Is it worth the
|> complication and potential misunderstanding this feature has
|> demonstrated it can cause?

The whole point is that *not* all instances of an allocator must be
functionally equivalent.  And the implementation must adapt, using
different techniques when the instances are not functionally equivalent.
In cases where this test is significant, the implementation is free to
partially specialize the template for the default allocator (for which
all instances *are* functionally equivalent).  Most of the time, I
imagine that the cost of the extra test is negligible.  I also imagine
that in every case where all instances are functionally equivalent,
operator== will be an inline function, so the compiler should be able to
optimize the test away, and dead code elimination remove the more
complex branch which will never be taken.  (This is well within the
scope of what, I believe, most optimizers today are already capable of
doing.)

The only real problem I see today is that the only document we have on
all of this is the draft standard.  Which is a draft, and is a standard,
not an instructional text.  Which means that the driving ideas, and how
it is meant to be used, are often not immediatly apparent.

What we really need is the second edition of Plauger's book.  (Having
seen the proposed library be totally redesigned while the first edition
was being printed, I can imagine that he will not be bringing the second
edition out until there is significantly more stability in the standard
that at present.  Once burned, twice wary, as they say.)
--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils,    tudes et r   alisations en logiciel orient    objet --
                -- A la recherche d'une activit    dans une region francophone



[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]