James Kanze US/ESC 60/3/141 #40763 wrote:
>
> In article <3236E824.2CF0@cds.duke.edu> Max TenEyck Woodbury
> <mtew@cds.duke.edu> writes:
>
> |> James Kanze US/ESC 60/3/141 #40763 wrote:
> |> >
> |> > In article <322DDBE8.40DC@cds.duke.edu> Max TenEyck Woodbury
> |> > <mtew@cds.duke.edu> writes:
> |> >
> |> > |> As a guess, passing an allocator INSTANCE to the string CONSTRUCTOR may be
> |> > |> a serious mistake.  It makes what should be a compact and efficent object
> |> > |> that will be used over and over again into something necessarily larger and
> |> > |> less efficent.  I'd bet that there will be more than one alternate
> |> > |> implementation (abet non-standard) that either ignores allocators or
> |> > |> uses a similar implementation to containers to achieve the same end.
> |> >
> |> > At most, it only adds one pointer.  For a container, this doesn't seem
> |> > like much to me.
>
> |> If you allow the 'it only adds one pointer' argument, you eventually end
> |> up with something like LISP; fine for what it does, but not for most
> |> practical applications.
>
> I know some practical applications using Lisp:-).
>

Yep, I know of a few myself, but my original statement stands.

> The cost is always relative.  If a feature "only adds one pointer" to
> every int in the program, I'd oppose it.  Here, however, we are talking
> about container classes; typically, they are going to measure in the
> kilobyte range of memory usage.  4 bytes more or less isn't going to be
> significant.  (FWIW: the amortised constant time for an array costs will
> cost significantly more memory; in a vector with 1000 members, for
> example, it could easily cost several 100 bytes.)
>

While I disagree with you on this point, a close review of the
standard and a bit of imagination persuaded me that it would be
possible to do allocators without any unneeded storage overhead,
so the point should be considered moot.

> |> > As I have pointed out before, the default allocator guarantees that all
> |> > instances compare equal.  So the implementation can implement a
> |> > partitial specialization on this which simply ignores the allocator
> |> > parameter.
>
> |> You're implying a standard for the quality of implimentation here, and
> |> not necessarialy the best one.  A good optimizer, while it would trim
> |> the unused code, might very well provide a low level diagnostic, which
> |> could cause untold grief in the wrong techno/political environment.
>
> I'm not implying anything.  I am saying that implementors who want to
> sell compilers will do what the customer wants.  If the customer doesn't
> want the overhead of comparing allocators in the normal case, the
> implementor will provide a specialization of the class which exploits
> the knowledge that all instances of the standard allocator compare
> equal.
>

Sorry, but you are implying that only compilers that can do unused
code elimination are to be considered candidates for general use.  I
can think of environments where any kind of optimization would actually
be detrimental.  (Specifically, student batch compile and run systems.
Old fashoned and morubund, but still a valid example.)

> I don't understand the remark concerning unused code and a low level
> diagnostic.  There is no unused code involved here, and I cannot see why
> a compiler would provide any particular diagnostic.
>

Some compilers do produce warning messages when they elimiate an unused
section of code.  Are you saying that no compiler should provide that
level of diagnostic?

> |> > If this really becomes an issue in user defined allocators, then the
> |> > compiler could always recognize the special case of operator== on the
> |> > allocator type always returning null, and optimize the pointer out.
> |> > (Implementors: don't put this high on your priority list.  IMHO, it will
> |> > never become an issue.  In the rare cases where performance is an issue,
> |> > I imagine that a user designed class tuned to the application, rather
> |> > than the general library class, will be used.  In this case, whether
> |> > there is a user defined allocator or not is indifferent.)
>
> |> Argh!!!!!
>
> Why?
>

Why?  You're arguing for introducing an unneeded feature that
causes a number of rather nasty problems and then dismiss the whole
thing as trivial.  More specificaly, see the Allocators - Argh!
thread.  (I am not talking about splice per se.)

> Although I don't think that this particular case is worthwhile, the use
> of templates does introduce a number of new cases for optimization.  For
> example, any reasonable implementation of vector will contain a loop
> with explicit calls to the destructor.  A good compiler will recognize
> that, if the destructor is known to do nothing (either implicitly, as
> with the built-in types, or because it is inline), the loop is a big
> no-op, and will also supprime the loop control code.  Looking for such
> optimizations was probably not worthwhile before templates, in the sense
> that the time spent by the compiler to check for the special case
> probably outweighed any potential gains in the generated code.
>
> If you question my assertion that time critical code will use custom
> classes: generality has its price.  If I know that my vector will have a
> compile time constant number of elements, and will never change size, I
> can write a version that is significantly faster than what is required
> by the standard.  Similarly, if I know that I can move elements with a
> simply memcpy, instead of copy construction/destruction, I can speed
> things up considerably as well.  (This latter case can actually be
> optimized by some clever partial specialization of the templates as
> well.)

Many applications will use classes not included in the standard
library.  Over time, a number of these classes will achive enough
currency to be considered for future standardization, either into
C++ itself or into particular application domains.  That says very
little about what should go into the first C++ standard.

Nor do I dispute that templates will have an impact on optimization
techniques.  They have and they will condtinue to do so.  However,
the existance of good optimizers does NOT justify ignoring design
problems in the library.

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 <3236E824.2CF0@cds.duke.edu> Max TenEyck Woodbury
<mtew@cds.duke.edu> writes:

|> James Kanze US/ESC 60/3/141 #40763 wrote:
|> >
|> > In article <322DDBE8.40DC@cds.duke.edu> Max TenEyck Woodbury
|> > <mtew@cds.duke.edu> writes:
|> >
|> > |> As a guess, passing an allocator INSTANCE to the string CONSTRUCTOR may be
|> > |> a serious mistake.  It makes what should be a compact and efficent object
|> > |> that will be used over and over again into something necessarily larger and
|> > |> less efficent.  I'd bet that there will be more than one alternate
|> > |> implementation (abet non-standard) that either ignores allocators or
|> > |> uses a similar implementation to containers to achieve the same end.
|> >
|> > At most, it only adds one pointer.  For a container, this doesn't seem
|> > like much to me.

|> If you allow the 'it only adds one pointer' argument, you eventually end
|> up with something like LISP; fine for what it does, but not for most
|> practical applications.

I know some practical applications using Lisp:-).

The cost is always relative.  If a feature "only adds one pointer" to
every int in the program, I'd oppose it.  Here, however, we are talking
about container classes; typically, they are going to measure in the
kilobyte range of memory usage.  4 bytes more or less isn't going to be
significant.  (FWIW: the amortised constant time for an array costs will
cost significantly more memory; in a vector with 1000 members, for
example, it could easily cost several 100 bytes.)

|> > As I have pointed out before, the default allocator guarantees that all
|> > instances compare equal.  So the implementation can implement a
|> > partitial specialization on this which simply ignores the allocator
|> > parameter.

|> You're implying a standard for the quality of implimentation here, and
|> not necessarialy the best one.  A good optimizer, while it would trim
|> the unused code, might very well provide a low level diagnostic, which
|> could cause untold grief in the wrong techno/political environment.

I'm not implying anything.  I am saying that implementors who want to
sell compilers will do what the customer wants.  If the customer doesn't
want the overhead of comparing allocators in the normal case, the
implementor will provide a specialization of the class which exploits
the knowledge that all instances of the standard allocator compare
equal.

I don't understand the remark concerning unused code and a low level
diagnostic.  There is no unused code involved here, and I cannot see why
a compiler would provide any particular diagnostic.

|> > If this really becomes an issue in user defined allocators, then the
|> > compiler could always recognize the special case of operator== on the
|> > allocator type always returning null, and optimize the pointer out.
|> > (Implementors: don't put this high on your priority list.  IMHO, it will
|> > never become an issue.  In the rare cases where performance is an issue,
|> > I imagine that a user designed class tuned to the application, rather
|> > than the general library class, will be used.  In this case, whether
|> > there is a user defined allocator or not is indifferent.)

|> Argh!!!!!

Why?

Although I don't think that this particular case is worthwhile, the use
of templates does introduce a number of new cases for optimization.  For
example, any reasonable implementation of vector will contain a loop
with explicit calls to the destructor.  A good compiler will recognize
that, if the destructor is known to do nothing (either implicitly, as
with the built-in types, or because it is inline), the loop is a big
no-op, and will also supprime the loop control code.  Looking for such
optimizations was probably not worthwhile before templates, in the sense
that the time spent by the compiler to check for the special case
probably outweighed any potential gains in the generated code.

If you question my assertion that time critical code will use custom
classes: generality has its price.  If I know that my vector will have a
compile time constant number of elements, and will never change size, I
can write a version that is significantly faster than what is required
by the standard.  Similarly, if I know that I can move elements with a
simply memcpy, instead of copy construction/destruction, I can speed
things up considerably as well.  (This latter case can actually be
optimized by some clever partial specialization of the templates as
well.)
--
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
]

In article <3221F075.60D5@cds.duke.edu> Max TenEyck Woodbury
<mtew@cds.duke.edu> writes:

|> James Kanze US/ESC 60/3/141 #40763 wrote:
|> > ...
|> >
|> > This problem is not unique to lists, but also affects any objects which
|> > may want to use a shared representation.  I first encountered it when
|> > trying to implement a reference counted string class.
|> >

|> I believe the argument in the original post is incorrect.

|> I've seen your comments on strings before and I am still not sure why
|> there is a problem, or if there is a problem, why it makes reference
|> count strings a special problems.

|> To be more specific, I don't see anyplace in the standard where the
|> deallocator is parameterized except through the base class template.

The deallocator is a member function of the allocator object.  I don't
know off hand how clear the working papers are, but the intent is
obvious: all dynamic memory used by a given object must be allocated and
deallocated by means of an allocator object from the same equivalence
class as that specified in the constructor.

|> From that it seems all deallocators have to handle whatever is thrown
|> at them from any allocation source.

In a way, yes.  Since anything that can be thrown at them must have been
allocated by the same object:-).  The restriction doesn't involve the
deallocator per se.  The restriction is that all memory in the object be
allocated by the specified allocator.  At all times.

An example of why this is important: consider a user defined allocator
for shared memory.  The allocator *class* manages several pools of
shared memory; each pool is shared with a different set of processes.
Each equivalence class of the instances of this allocator class manages
a separate pool.  (The operator== on the allocator class compares pool
id's.)

If I create a string using an instance which allocates in pool 1, it is
because this string must be visible in the other processes which have
access to pool 1.  (Presumably, I will also have taken precautions that
the string itself is in pool 1 as well.)  If I assign a string to it
whose memory was allocated from pool 2, I *must* make a deep copy.  The
necessary processes cannot see the memory from pool 2.

Note that the requirement here *is* that the memory be allocated from a
specific instance of the allocator.  This is not a problem of
deallocation, but of user defined specialization.

Presumably, if I need this functionality, *all* of my strings will use
the same allocator class, with e.g. the pool 0 being the special case of
unshared memory.  If the implementation is clever, it will only do the
deep copy when necessary; e.g.: when I assign a string from one pool to
another.  In this case, the deep copy is necessary by definition, since
the target processes have no access to the memory in the original string.

|> If that is the case, a reference
|> count implementation presents no more problem than any other.  I could
|> be missing something though, and your help in pointing out what I missed
|> would be appreciated.

|> That doesn't mean I like the idea of the allocator being part of the
|> constructor parameter list for strings, or any other type for that
|> mater.  It should be a compile time specification, not a run time
|> specification, UNLESS you can specify a virtual deallocator, and
|> that has problems that shouldn't even have to be considered!  (Just
|> to start, how do you know that the object being deallocated has a
|> virtual deallocator? By the time you need to invoke the deallocator,
|> you no longer have an object, just raw storage, so either everything
|> has a virtual deallocator or nothing does.)

I think that the way things are in the current draft actually works
pretty well, although I will admit that it took me some time to
understand the logic behind it.  (A good rationale would be a real help.
It would also require a significant investment of manpower, I fear.)  I
do wonder if it isn't going too far with regards to flexibility, but now
that the work has been done, I don't see any reason to remove it.
--
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, itudes et rialisations en logiciel orienti objet --
                -- A la recherche d'une activiti 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                             ]