In article <uu0i2e0d1.fsf@boost-consulting.com>,
 dave@boost-consulting.com (David Abrahams) wrote:

> Next question: do we want users forming T* to uninitialized memory, or
> would a void* actually be safer?

I kind of like of my previously posted interpol/bind example.  This
would be complicated by having to deal with a void* instead of T*, and
no extra safety would be achieved:

vector::allocator magically obtains memory (perhaps in void* form) and
sends vector a pointer to that memory as a T* (or more correctly an
allocator_type<T>::pointer).

vector then sends that T* to either allocator_type::construct (in
current day constructors) or to functor in the proposed constructor.

I see no safety or other advantage in asking functor to traffic in void*
instead of T*.  The vector is already holding the T* to uninitialized
memory before it calls the functor.  Why downcast it?

-Howard

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

In article <uzmryucxd.fsf@boost-consulting.com>,
 David Abrahams <dave@boost-consulting.com> wrote:

> Howard Hinnant <hinnant@metrowerks.com> writes:
>
> > struct empty_func
> > {
> >     template <class T>
> >     void operator()(T*, size_t) {}
> > };
>
> The T* is wrong here.  It has to be void*.  If you form a T* to
> uninitialized memory the behavior is undefined.

This has been a fascinating post for me to reply to!  A real education.
While writing this post I've changed my mind from caring what the
signature is, to not caring, and back again! :-)

First off lets get what's allowable out of the way:

I plead for equal footing with existing practice:

20.4.1:

template <class T>
class allocator
{
public:
    ...
    typedef T*        pointer;
    ...
    void construct(pointer p, const T& val);
    ...
};

Clients of std::allocator<T>::construct are trafficking in uninitialized
memory when they form the T* to pass to construct, else they would be
constructing on top of initialized memory.

Of course the author of the functor must understand (as
allocator::construct does) that the T* does point to uninitialized
memory, and the functor is responsible for transforming that memory into
initialized memory (constructing the T's).

Given the prior practice of allocator::construct, I argue that it is
alright, and perhaps even preferable to continue with functor(T*, size)
rather than functor(void*, size).

Now...

The chances that your legacy function has exactly the interface of (T*,
size_t) are pretty remote, so you're probably going to need an adaptor
anyway.  I went out looking for a concrete example to play with and
randomly found:

http://www.oreilly.com/catalog/masteralgoc/chapter/ch13.html

> int interpol(const double *x, const double *fx, int n,
>              double *z, double *pz, int m);
>
> Determines the value of a function at specified points using polynomial
> interpolation. Points at which values are known are specified by the caller
> in x. The known values of the function at each point in x are specified in
> fx. Points at which values are to be determined are specified in z. The
> values calculated for the points passed in z are returned in pz. The number
> of values in x and fx is specified as n. The number of points in z (and thus
> returned in pz) is specified as m. It is the responsibility of the caller to
> manage the storage associated with x, fx, z, and pz.

Given that you want to write:

vector<double>
interpolate(const vector<double>& x,
            const vector<double>& fx,
            const vector<double>& z);

to interface with interpol, it might look something like:

class apply_interpol
{
public:
    apply_interpol(const vector<double>& x,
                   const vector<double>& fx,
                   const vector<double>& z)
        : x_(x), fx_(fx), z_(z) {}

    void operator() const (double* pz, size_t m)
    {
       assert(x.size() == fx.size());
       assert(z.size() == m);
       if (interpol(x.data(), fx.data(), x.size(),
           const_cast<double*>(z.data()), pz, m))
           throw "oops";
    }
private:
    const vector<double>& x_;
    const vector<double>& fx_;
    const vector<double>& z_;
};

inline
vector<double>
interpolate(const vector<double>& x,
            const vector<double>& fx,
            const vector<double>& z)
{
    return vector<double>(z.size(), apply_interpol(x, fx, z));
}

If the functor must traffic in void* instead of double*, throw an extra
cast into apply_interpol, not a big deal.

However my first attempt at writing this function looked like:

struct do_nothing
{
    template <class T>
    void operator()(T*, size_t) {}
};

inline
vector<double>
interpolate(const vector<double>& x,
            const vector<double>& fx,
            const vector<double>& z)
{
    assert(x.size() == fx.size());
    vector<double> pz(z.size(), do_nothing());
    if (interpol(x.data(), fx.data(), x.size(),
        const_cast<double*>(z.data()), pz.data(), z.size()))
           throw "oops";
    return pz;
}

And this first attempt is probably superior to my apply_interpol
solution.  At least it seems simpler to me.  And in this rewrite, the
interface which do_nothing must meet is irrelevant: (pointer, size),
(void*, size), (iter, iter), whatever.

At this point I didn't care what the interface for the functor would be.

But then I realized the following would also work quite nicely:

inline
vector<double>
interpolate(const vector<double>& x,
            const vector<double>& fx,
            const vector<double>& z)
{
   assert(x.size() == fx.size());
   return vector<double>
    (
        z.size(),
        bind
        (
            interpol,
            x.data(), fx.data(), x.size(),
            const_cast<double*>(z.data()), _1, _2
        )
    );
}

And I really like this solution.  However it depends on the
functor(pointer, size) interface.  Other interfaces (iter, iter) or
(void*, size) would require further adaptors which would do nothing but
obfuscate this code.

Counterpoint:  My latest (bind) solution doesn't do the error checking
for the case that interpol fails.

CounterCounterpointer:  interpol is just an example.  Legacy functions
exist that fill in arrays of scalars and return void.

Well, I've spent the evening arguing with myself.  Maybe I should give
somebody else a chance to get a word in edge-wise. ;-)

-Howard

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

David Abrahams wrote:
> Howard Hinnant <hinnant@metrowerks.com> writes:
>
>
>>struct empty_func
>>{
>>    template <class T>
>>    void operator()(T*, size_t) {}
>>};
>
>
> The T* is wrong here.  It has to be void*.  If you form a T* to
> uninitialized memory the behavior is undefined.

That's a good point. I've been always hesitant here, and the standard
library doesn't help. For example, std::allocator uses T* in several
places where void* would be the case. raw_storage_iterator also comes to
mind, although it has a better justification.

So I'm unsure on whether it would be best to use (T*, T*) or (void*,
size_t) for specifying ranges. For one thing, the latter won't allow
using the standard algorithms uninitialized_copy and uninitialized_fill.


Andrei

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

hinnant@metrowerks.com (Howard Hinnant) writes:

> First off lets get what's allowable out of the way:
>
> I plead for equal footing with existing practice:
>
> 20.4.1:
>
> template <class T>
> class allocator
> {
> public:
>     ...
>     typedef T*        pointer;
>     ...
>     void construct(pointer p, const T& val);
>     ...
> };
>
> Clients of std::allocator<T>::construct are trafficking in
> uninitialized memory when they form the T* to pass to construct,
> else they would be constructing on top of initialized memory.

And do clients use that interface without invoking undefined behavior?
You have to either get the core language fixed so it's legal to use
that interface, or you have to pass void*. [=B9] Seems pretty cut and
dried to me.


Footnotes:=20
[=B9] or tell me that my understanding of the core language lo these few
    years is wrong.  Wouldn't surprise me _too_ much.

--=20
Dave Abrahams
Boost Consulting
www.boost-consulting.com

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

David Abrahams wrote:
> hinnant@metrowerks.com (Howard Hinnant) writes:
>=20
>=20
>>First off lets get what's allowable out of the way:
>>
>>I plead for equal footing with existing practice:
>>
>>20.4.1:
>>
>>template <class T>
>>class allocator
>>{
>>public:
>>    ...
>>    typedef T*        pointer;
>>    ...
>>    void construct(pointer p, const T& val);
>>    ...
>>};
>>
>>Clients of std::allocator<T>::construct are trafficking in
>>uninitialized memory when they form the T* to pass to construct,
>>else they would be constructing on top of initialized memory.
>=20
>=20
> And do clients use that interface without invoking undefined behavior?
> You have to either get the core language fixed so it's legal to use
> that interface, or you have to pass void*. [=B9] Seems pretty cut and
> dried to me.

I think the interface can be used legally. The clients who form a T*=20
from a void* via a static_cast. If the allocator converts it back to=20
void* via another static_cast, we're in legal territory as far as I=20
understand. Such casts should be fine because they take us back from=20
where we were. Right?


Andrei

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

"Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail@moderncppdesign.com> writes:

> I think the interface can be used legally. The clients who form a T*
> from a void* via a static_cast. If the allocator converts it back to
> void* via another static_cast, we're in legal territory as far as I
> understand. Such casts should be fine because they take us back from
> where we were. Right?

Yup, I guess you're right and I was wrong.

Next question: do we want users forming T* to uninitialized memory, or
would a void* actually be safer?

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

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

David Abrahams wrote:
> Next question: do we want users forming T* to uninitialized memory, or
> would a void* actually be safer?

I think in the allocator case it's a bug to use T* in lieu of void*, but
that's too late to fix. In the case of raw_storage_iterator, T* is a
must because the iterator must know how to increment.

Andrei

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

David Abrahams wrote:
> Howard Hinnant <hinnant@metrowerks.com> writes:
>
> > struct empty_func
> > {
> >     template <class T>
> >     void operator()(T*, size_t) {}
> > };
>
> The T* is wrong here.  It has to be void*.  If you form a T* to
> uninitialized memory the behavior is undefined.

Citation, please? I know that the behavior is undefined if a program
tries to read the value of an uninitialized pointer, and that it's also
undefined if the program tries to read the value of the uninitialized
memory that it points at.  However, I'm not aware of any reason that
makes it undefined behavior to form a  pointer to uninitialized memory.
It's my understanding that if the behavior were undefined, the malloc()
family would be useless.

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

SeeWebsiteForEmail@moderncppdesign.com ("Andrei Alexandrescu (See Website For Email)") writes:

> David Abrahams wrote:
>> Next question: do we want users forming T* to uninitialized memory, or
>> would a void* actually be safer?
>
> I think in the allocator case it's a bug to use T* in lieu of void*, but
> that's too late to fix.

Maybe; maybe not.  How much code would it break?

> In the case of raw_storage_iterator, T* is a
> must because the iterator must know how to increment.

I don't think T* has to appear anywhere other than as a template
argument.

raw_storage_iterator is pretty much useless in generic code, anyway,
because no algorithm designed to assign through an ordinary iterator
is going to try to go back and destroy all the objects it assigned
into in case of an exception.  Using raw_storage_iterator can almost
never be exception-safe.

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

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

dave@boost-consulting.com (David Abrahams) wrote (abridged):
> Next question: do we want users forming T* to uninitialized memory, or
> would a void* actually be safer?

For me the most expressive signature for this kind of thing is:

    template <class T>
    T *operator()(void *, size_t);

where the address returned is the same as that passed, but of the correct
type.

-- Dave Harris, Nottingham, UK.

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

Howard Hinnant <hinnant@metrowerks.com> writes:

> struct empty_func
> {
>     template <class T>
>     void operator()(T*, size_t) {}
> };

The T* is wrong here.  It has to be void*.  If you form a T* to
uninitialized memory the behavior is undefined.

Of course, you could arrange for the library always to pass void* so
that T is deduced as void, but I hope you know what I'm driving at:
the library must pass void* to the function.

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

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

Howard Hinnant wrote:
> In article <42E7FCF9.9040802@moderncppdesign.com>,
>  "Andrei Alexandrescu (See Website for Email)"
>  <seewebsiteforemail@moderncppdesign.com> wrote:
>>Oh. Would you say that negotiate_alloc(p, 0, s, ps) is equivalent to
>>expand_to_eob(p, s)?
>
>
> <nod> That's my current understanding.

That would be great, if what followed wasn't actually illustrating a
discrepancy.

>>Yes, but on the other hand your negotiate_alloc could expand to
>>min_size every time you call it.
>
>
> And every call to new can throw an exception.  There's always QOI issues
> in allocators.  Those with low quality tend to not get used.  Believe it
> or not, we vendors are not out to get you. ;-)

Ok, that brings my hopes up.

>>I think a good interface is negotiate_alloc with the guarantee that it
>>allocates the *largest possible block* within the limits. In other
>>words, an immediately subsequent call to negotiate_alloc that attempts
>>to expand the same pointer should fail, barring other threads or
>>interrupts.
>
>
> I believe we're in violent agreement on the intent.  This is what I
> currently have:
>
>
>>The intention of this function is to expand a block of memory in place to
>>preferred_size, but failing to do that, expand to min_size. Failure is only
>>indicated (with a zero return) if the memory block cannot be expanded to
>>min_size.

This blows the door off my hopes, or beats the pants off them, to use
two phrases that I just learned.

I can only read the above one way: the expansion will either grow the
chunk to preferred_size, or min_size. Never something between min_size
or preferred_size.

That's as good as useless, and asks for my expand_to_eob function,
which in turn is as elegant as an elephant in a Yugo. The Latins would
say: "Testis unus, testis nullus." I'm not going to translate that :o).

> I'm open to suggestions on better wording.  Your paragraph above isn't
> quite the standardeze we need because a larger expand might succeed if
> preferred_size was the limiting factor on the last call.

"The intention of this function is to expand a block of memory in
place to preferred_size, but failing to do that, expand to any size
greater than or equal to min_size. Failure is only indicated (with a
zero return) if the memory block cannot be expanded to any size in the
range [min_size, preferred_size]."

This is what everybody is going to need: the caller is in expansion
mode, and failing to expand as much as it wants, it would want not to
expand by some dingy size, but to the maximum size available.

Now really, which scenario is more likely?

"If you have $1000, give them to me. Otherwise, give me 50c."

or

"If you have $1000, give them to me. Otherwise, give me all you can."

> However precise wording is not exactly a priority right now as the C
> committee hasn't even looked at this, much less said: yep, this is just
> what we need.

Maybe they didn't like the existing wording ;o).

> Failing acceptance in the C community, we could still lobby for a C++
> interface in the allocator requirements that would support this
> functionality.  However I fear that without the underlying C support
> such an interface might be under utilized.  I can write my own heap
> manager to support this interface, but I suspect that not very many
> programmers are willing to do that.

Yah that would be great. By the way, the semantics of in-place
expansion must be extended to new-allocated memory. Otherwise it will
become the Cinderella of dynamic allocation and nobody's gonna like
using it. I already give the advice to use malloc if you can (deal
with PODs) even in C++. I'd hate to tell people that now they can
forget everything about void* operator new(size_t) because using the C
interface is better in all cases.


Andrei

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

In article <slrndeg6kh.1jfl.usenet-nospam@nmhq.net>,
 usenet-nospam@nmhq.net (Niklas Matthies) wrote:

> On 2005-07-27 22:44, Howard Hinnant wrote:
> :
> >> >>int negotiate_alloc(void* ptr, size_t min_size,
> >> >>                               size_t preferred_size,
> >> >>                               size_t* size_received);
> :
> >> The intention of this function is to expand a block of memory in
> >> place to preferred_size, but failing to do that, expand to
> >> min_size. Failure is only indicated (with a zero return) if the
> >> memory block cannot be expanded to min_size.
>
> Doesn't this mean that
>
>    negotiate_alloc(p, a, b, ps)
>
> is pretty much equivalent to
>
>    negotiate_alloc(p, b, b, ps) ||
>    negotiate_alloc(p, a, a, ps)
>
> ?
>
> (Yes, the available size might change between the two calls, but
> that's not worse than if the change happened before the first call.)
>
> I agree with Andrei that the function should expand to the maximum
> available size between a and b. The vector example certainly would
> like to have it this way.

Your wording is certainly my intent.  If my words say that the one call
is equivalent to the two calls in your example, then my wording is
incorrect, and inconsistent with my current implementations.

Of course we also start to get into QOI issues here.  How much do you
(can you) mandate in the standard, and how much do you leave to the
vendor's discretion?

For example the current description of malloc is simply:

> The malloc function allocates space for an object whose size is specified
> by size and whose value is indeterminate.

> Returns:
>
> The malloc function returns either a null pointer or a pointer to the
> allocated space.

A literal reading allows malloc to return a null pointer on every other
call just because it is in a grumpy mood.  But of course nobody ships
such grumpy mallocs (except perhaps for stress testing) because the
grumpiness quickly transfers to the paying customer.

But I think we're all in agreement on the intent, and if better proposed
wording is offered, I'm grateful.

-Howard

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

In article <42E850D9.8000908@moderncppdesign.com>,
 seewebsiteforemail@moderncppdesign.com ("Andrei Alexandrescu (See
 Website for Email)") wrote:

> "The intention of this function is to expand a block of memory in
> place to preferred_size, but failing to do that, expand to any size
> greater than or equal to min_size. Failure is only indicated (with a
> zero return) if the memory block cannot be expanded to any size in the
> range [min_size, preferred_size]."

I like that much better, thanks.  Except <nit> the expansion is actually
allowed to go over preferred_size and report success (e.g. for alignment
purposes).  But I've fixed up my copy of the paper with your ">= words"
in case I re-issue it.

> > However precise wording is not exactly a priority right now as the C
> > committee hasn't even looked at this, much less said: yep, this is just
> > what we need.
>
> Maybe they didn't like the existing wording ;o).

<chuckle>  I just received a note of hope for this Fall. :-)

> > Failing acceptance in the C community, we could still lobby for a C++
> > interface in the allocator requirements that would support this
> > functionality.  However I fear that without the underlying C support
> > such an interface might be under utilized.  I can write my own heap
> > manager to support this interface, but I suspect that not very many
> > programmers are willing to do that.
>
> Yah that would be great. By the way, the semantics of in-place
> expansion must be extended to new-allocated memory. Otherwise it will
> become the Cinderella of dynamic allocation and nobody's gonna like
> using it. I already give the advice to use malloc if you can (deal
> with PODs) even in C++. I'd hate to tell people that now they can
> forget everything about void* operator new(size_t) because using the C
> interface is better in all cases.

This is a very interesting point.

To date I have not developed access to this functionality via new[].
I've only accessed it via the library's allocator interface, and
subsequently via vector (and also an extension container:
Metrowerks::cdeque).

I'm open to suggestions on how to access this functionality via new[] in
a backwards compatible, intuitive and exception safe fashion.

-Howard

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

On 2005-07-28 17:13, Howard Hinnant wrote:
> In article <slrndeg6kh.1jfl.usenet-nospam@nmhq.net>, Niklas Matthies wrote:
>> On 2005-07-27 22:44, Howard Hinnant wrote:
>> :
>> >> >>int negotiate_alloc(void* ptr, size_t min_size,
>> >> >>                               size_t preferred_size,
>> >> >>                               size_t* size_received);
>> :
>> >> The intention of this function is to expand a block of memory in
>> >> place to preferred_size, but failing to do that, expand to
>> >> min_size. Failure is only indicated (with a zero return) if the
>> >> memory block cannot be expanded to min_size.
:
>>    negotiate_alloc(p, b, b, ps) ||
>>    negotiate_alloc(p, a, a, ps)
:
>> I agree with Andrei that the function should expand to the maximum
>> available size between a and b. The vector example certainly would
>> like to have it this way.
>
> Your wording is certainly my intent.  If my words say that the one call
> is equivalent to the two calls in your example, then my wording is
> incorrect, and inconsistent with my current implementations.

Your wording says that the received size is either preferred_size
or (failing that) min_size. E.g. it would be correct to write:

   int success = negotiate_alloc(p, min, max, ps);
   assert(!success || *ps == min || *ps == max);

But what we want is the more general postcondition:

   int success = negotiate_alloc(p, min, max, ps);
   assert(!success || (min <= *ps && *ps <= max));

QoI then kicks in in that the implementation should maximize *ps
whithin those constraints.

-- Niklas Matthies

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

Howard Hinnant wrote:
> In article <42E850D9.8000908@moderncppdesign.com>,
>  seewebsiteforemail@moderncppdesign.com ("Andrei Alexandrescu (See
>  Website for Email)") wrote:
>
>
>>"The intention of this function is to expand a block of memory in
>>place to preferred_size, but failing to do that, expand to any size
>>greater than or equal to min_size. Failure is only indicated (with a
>>zero return) if the memory block cannot be expanded to any size in the
>>range [min_size, preferred_size]."
>
>
> I like that much better, thanks.  Except <nit> the expansion is actually
> allowed to go over preferred_size and report success (e.g. for alignment
> purposes).  But I've fixed up my copy of the paper with your ">= words"
> in case I re-issue it.

That's true. If there's also any way to express that "more is better",
then we struck gold. Let's try again:

"The intention of this function is to expand a block of memory in
place to the largest possible size in the interval [min_size,
preferred_size]. An implementation is allowed to expand to a size
larger than preferred_size. Failure is only indicated (with a
zero return) if the memory block cannot be expanded."

>>Yah that would be great. By the way, the semantics of in-place
>>expansion must be extended to new-allocated memory. Otherwise it will
>>become the Cinderella of dynamic allocation and nobody's gonna like
>>using it. I already give the advice to use malloc if you can (deal
>>with PODs) even in C++. I'd hate to tell people that now they can
>>forget everything about void* operator new(size_t) because using the C
>>interface is better in all cases.
>
>
> This is a very interesting point.
>
> To date I have not developed access to this functionality via new[].
> I've only accessed it via the library's allocator interface, and
> subsequently via vector (and also an extension container:
> Metrowerks::cdeque).
>
> I'm open to suggestions on how to access this functionality via new[] in
> a backwards compatible, intuitive and exception safe fashion.

You may want to provide an interface similar to the expansion
interface, just with different names and function templates instead of
functions. You see, the keyword "new" weren't needed if templates were
in vigor back then; "new T" could have been a library call
"std::new<T>()", and "new T[size]" could have been
"std::new<T>(size)". Consequently, you don't need new keywords and new
syntax for renewing. You can just define a couple of functions like
those you have for malloc, except that sizes are in multiples of
sizeof(T) and pointers are to T*.

Exceptions aren't a big issue; objects aren't actually moved, just
destroyed (and we know that destructors don't throw) and it's quite
possible that renew fails, so using error codes is appropriate.

template <class T>
size_t sizeof_new(T* ptr);

template <class T>
T* request_new(size_t size_requested, size_t* size_received);

template <class T>
bool renew(T* ptr, size_t objects_requested,
     size_t* objects_received);

template <class T>
bool negotiate_renew(T* ptr, size_t min_objects,
     size_t preferred_objects,
     size_t* objects_received);

It will be a bit of a challenge to figure out whether sizeof_new just
returns the bytes or keeps track of the objects constructed. Things
could get tricky.


Andrei

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

In article <42EA294D.7070105@moderncppdesign.com>,
 seewebsiteforemail@moderncppdesign.com ("Andrei Alexandrescu (See
 Website for Email)") wrote:

> You may want to provide an interface similar to the expansion
> interface, just with different names and function templates instead of
> functions.

This is essentially what I've done with the allocator interface, except
of course allocator traffics in uninitialized memory.  Apply a container
to it, and viola! initialized memory.

> Exceptions aren't a big issue; objects aren't actually moved, just
> destroyed (and we know that destructors don't throw) and it's quite
> possible that renew fails, so using error codes is appropriate.
>
> template <class T>
> size_t sizeof_new(T* ptr);
>
> template <class T>
> T* request_new(size_t size_requested, size_t* size_received);
>
> template <class T>
> bool renew(T* ptr, size_t objects_requested,
>      size_t* objects_received);
>
> template <class T>
> bool negotiate_renew(T* ptr, size_t min_objects,
>      size_t preferred_objects,
>      size_t* objects_received);

Questions:

void foo()
{
    size_t size_received;
    T* p = request_new<T>(10, &size_received);
    // the call to request_new is exception safe:
    // If construction of one of the 10 T's throws
    // any already constructed T's are destructed and
    // the memory is deallocated (just like new[])

    // What if size_received == 11?  Did I really want 11
    // constructed T's, or just room to construct 11?

    bool b = negotiate_renew(p, 11, 20, &size_received);
    // Exception safe?  What if the expand is successful,
    // (out to 20), but the 15th T constructor throws?
    // Destruct the previous 14 T's and deallocate p,
    // and propagate the exception?  Sounds good.
}

// but...

void bar()
{
    size_t size_received;
    unique_ptr<T[], compatible_deleter> sp(request_new<T>(10,
                                        &size_received)
    bool b = negotiate_renew(sp.get(), 11, 20, &size_received);
    // Now if the 15th T constructor throws, and I clean up as
    // before (in foo), I get a double delete problem as
    // ~unique_ptr runs.
}

I avoided these issues in allocator because it traffics in raw memory.
But they need to be dealt with if we are to propose this interface
(which traffics in objects instead of raw memory).  I don't currently
know the best answers.

More issues:  Is this interface compatible with new?  (what if new is
replaced?)  Are they compatible with malloc?  I avoided these issues in
allocator because the implementation can detect at link time if new has
been replaced, and thus disable this functionality in std::allocator
(expand always fails in std::allocator if new has been replaced).  A
user-defined allocator (e.g. malloc_alloc) can make up its own rules,
vector doesn't care.

-Howard

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

Howard Hinnant wrote:
> In article <42EA294D.7070105@moderncppdesign.com>,
>  seewebsiteforemail@moderncppdesign.com ("Andrei Alexandrescu (See
>  Website for Email)") wrote:
>
>
>>You may want to provide an interface similar to the expansion
>>interface, just with different names and function templates instead of
>>functions.
>
>
> This is essentially what I've done with the allocator interface, except
> of course allocator traffics in uninitialized memory.  Apply a container
> to it, and viola! initialized memory.

(voila? :o))

>>template <class T>
>>size_t sizeof_new(T* ptr);
>>
>>template <class T>
>>T* request_new(size_t size_requested, size_t* size_received);
>>
>>template <class T>
>>bool renew(T* ptr, size_t objects_requested,
>>     size_t* objects_received);
>>
>>template <class T>
>>bool negotiate_renew(T* ptr, size_t min_objects,
>>     size_t preferred_objects,
>>     size_t* objects_received);
>
>
> Questions:
>
> void foo()
> {
>     size_t size_received;
>     T* p = request_new<T>(10, &size_received);
>     // the call to request_new is exception safe:
>     // If construction of one of the 10 T's throws
>     // any already constructed T's are destructed and
>     // the memory is deallocated (just like new[])
>
>     // What if size_received == 11?  Did I really want 11
>     // constructed T's, or just room to construct 11?
>
>     bool b = negotiate_renew(p, 11, 20, &size_received);
>     // Exception safe?  What if the expand is successful,
>     // (out to 20), but the 15th T constructor throws?
>     // Destruct the previous 14 T's and deallocate p,
>     // and propagate the exception?  Sounds good.
> }

This harkens back to the issue I've mentioned: does new[] track the
amount of allocated memory, the allocated object count, or both? I
suspect that today's new[] tracks both, or cooperates with the low-level
allocation routines such that one can always be inferred from the other
(e.g., "byte_count is always sizeof(T) * object_count rounded up to the
nearest multiple of 64").

> // but...
>
> void bar()
> {
>     size_t size_received;
>     unique_ptr<T[], compatible_deleter> sp(request_new<T>(10,
>                                         &size_received)
>     bool b = negotiate_renew(sp.get(), 11, 20, &size_received);
>     // Now if the 15th T constructor throws, and I clean up as
>     // before (in foo), I get a double delete problem as
>     // ~unique_ptr runs.
> }
>
> I avoided these issues in allocator because it traffics in raw memory.
> But they need to be dealt with if we are to propose this interface
> (which traffics in objects instead of raw memory).  I don't currently
> know the best answers.

Me neither. In the case above I'm thinking that only the extra 4 Ts
constructed by negotiate_renew should be destroyed. But that would
require the new[]-allocated arrays to hold both "capacity" and
"objects". If some implementation managed to do with only one, they'll
find it undesirable to add one word of overhead to each array allocation.

One way to solve that would be to only provide a low-level expansion
interface for new[], an interface that never creates or destroys
objects, and let the user deal with the rest. But that would be arcane.

The more I think of it, the more complicated the issue seems. Solving
with added overhead is easy; solving with a clunky interface is doable;
I can't yet find a solution that has an elegant interface, a set of nice
semantics, and no overhead at the same time.

Because you hit the nail on the head with your examples: creating an
array from scratch is an all-or-nothing proposition. So handling
exceptional cases is easy. Expanding an array, if failing due to
construction issues, leaves the system in the awkward situations of
having to report that raw memory size has grown but initialized memory
hasn't all that much.

Oh, I have an idea. How about contracting back the memory in the case of
construction failure?

// Returns the number of *objects* pointed to by ptr
template <class T>
size_t objectsof_new(T* ptr);

// We can drop this one
// template <class T>
// T* request_new(size_t size_requested, size_t* size_received);

// In case a ctor throws, destroys all newly-constructed objects
// and contracts back memory to where it was
// Otherwise, do the deed
template <class T>
bool renew(T* ptr, size_t objects_requested,
     size_t* objects_received);

// Ditto
template <class T>
bool negotiate_renew(T* ptr, size_t min_objects,
     size_t preferred_objects,
     size_t* objects_received);

> More issues:  Is this interface compatible with new?

Yah.

> (what if new is
> replaced?)

Then you aren't allowed to rely on it.

> Are they compatible with malloc?

Not necessarily.

> I avoided these issues in
> allocator because the implementation can detect at link time if new has
> been replaced, and thus disable this functionality in std::allocator
> (expand always fails in std::allocator if new has been replaced).

Is this portably reliable enough?


Andrei

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

In article <IKK0oL.1EBJ@beaver.cs.washington.edu>,
 SeeWebsiteForEmail@moderncppdesign.com ("Andrei Alexandrescu (See
 Website For Email)") wrote:

> Oh, I have an idea. How about contracting back the memory in the case of
> construction failure?
>
> // Returns the number of *objects* pointed to by ptr
> template <class T>
> size_t objectsof_new(T* ptr);
>
> // We can drop this one
> // template <class T>
> // T* request_new(size_t size_requested, size_t* size_received);
>
> // In case a ctor throws, destroys all newly-constructed objects
> // and contracts back memory to where it was
> // Otherwise, do the deed
> template <class T>
> bool renew(T* ptr, size_t objects_requested,
>      size_t* objects_received);
>
> // Ditto
> template <class T>
> bool negotiate_renew(T* ptr, size_t min_objects,
>      size_t preferred_objects,
>      size_t* objects_received);

After you destruct the extra objects, and shrink the memory back, you
rethrow the exception right?  I think it would be bad manners to have
the runtime lib swallow an exception generated in a T constructor.

So using renew (or negotiate_renew) is essentially unsafe unless you
have it wrapped in a try/catch, or you have a local smart pointer
hanging on to the original pointer.

Sounds like a good reason to always use vector instead. ;-)

> > I avoided these issues in
> > allocator because the implementation can detect at link time if new has
> > been replaced, and thus disable this functionality in std::allocator
> > (expand always fails in std::allocator if new has been replaced).
>
> Is this portably reliable enough?

<shrug>  It takes either runtime magic or compiler magic.  It isn't that
hard to do in the compiler, but we don't currently do it.  The trick is
to create a private alias of the runtime's operator new (one that is not
"weak linked").  At run time you can check if the alias and operator new
still point to the same function.  If they don't point to the same
function, new has been replaced.  Fwiw, it was Gabriel Dos Reis that
first pointed this out to me.

Another trick is to just have the native new set a private __global when
it runs, then you can check the status of that global.  But that one is
a bit more of a hack as you can only tell if new has been replaced after
you call it.

-Howard

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

Howard Hinnant wrote:
> After you destruct the extra objects, and shrink the memory back, you
> rethrow the exception right?  I think it would be bad manners to have
> the runtime lib swallow an exception generated in a T constructor.

Yes, that was the idea. Restore things where they were and rethrow.

> So using renew (or negotiate_renew) is essentially unsafe unless you
> have it wrapped in a try/catch, or you have a local smart pointer
> hanging on to the original pointer.

Ummmm... not unsafe (depending on what you mean by unsafe). It's not
unsafe in the sense that "you lose precious information forever". The
regular rules about resource management of course apply.

 > Sounds like a good reason to always use vector instead. ;-)

Vector still has a problem - by the way, has that been addressed by a
standards paper? std::vector forces you to initialize its elements in
ways that not always are desirable. My idea was to add a constructor (or
a resize() overload) to vector that takes a functor(iterator, iterator).
That functor is provided by client and initializes the freshly-added
range. With that last addition, we could say that std::vector is as good
as it could ever get. I'm still forced to not use it in an application
because of that lack of flexibility.

>>>I avoided these issues in
>>>allocator because the implementation can detect at link time if new has
>>>been replaced, and thus disable this functionality in std::allocator
>>>(expand always fails in std::allocator if new has been replaced).
>>
>>Is this portably reliable enough?
>
>
> <shrug>  It takes either runtime magic or compiler magic.  It isn't that
> hard to do in the compiler, but we don't currently do it.  The trick is
> to create a private alias of the runtime's operator new (one that is not
> "weak linked").  At run time you can check if the alias and operator new
> still point to the same function.  If they don't point to the same
> function, new has been replaced.  Fwiw, it was Gabriel Dos Reis that
> first pointed this out to me.
>
> Another trick is to just have the native new set a private __global when
> it runs, then you can check the status of that global.  But that one is
> a bit more of a hack as you can only tell if new has been replaced after
> you call it.

A great place to apply the "useless work" idiom that's on my "to submit
to the patent office" list:

delete new int;

:o)


Andrei

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

In article <IKK7nu.1I9F@beaver.cs.washington.edu>,
 SeeWebsiteForEmail@moderncppdesign.com ("Andrei Alexandrescu (See
 Website For Email)") wrote:

> Vector still has a problem - by the way, has that been addressed by a
> standards paper? std::vector forces you to initialize its elements in
> ways that not always are desirable. My idea was to add a constructor (or
> a resize() overload) to vector that takes a functor(iterator, iterator).
> That functor is provided by client and initializes the freshly-added
> range. With that last addition, we could say that std::vector is as good
> as it could ever get. I'm still forced to not use it in an application
> because of that lack of flexibility.

<nod>  I want this too (and I've heard others speak in favor of it too).
But nobody has written it up and I'm so buried in my current proposal
work that I don't think I'm going to get a chance to write it up.  You
volunteering?  If you do, you'll need to stick some "restricted
template" wording on it to disambiguate it from other constructors.  And
as well as the "please don't initialize" motivation, another good use
case is "initialize with legacy C function" (functor(pointer, size)
might be better because of this use case).

> A great place to apply the "useless work" idiom that's on my "to submit
> to the patent office" list:
>
> delete new int;
>
> :o)

Where do I send the royalty checks? ;-)

-Howard

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

Howard Hinnant wrote:
> In article <IKK7nu.1I9F@beaver.cs.washington.edu>,
>  SeeWebsiteForEmail@moderncppdesign.com ("Andrei Alexandrescu (See
>  Website For Email)") wrote:
>
> > Vector still has a problem - by the way, has that been addressed by a
> > standards paper? std::vector forces you to initialize its elements in
> > ways that not always are desirable. My idea was to add a constructor (or
> > a resize() overload) to vector that takes a functor(iterator, iterator).
> > That functor is provided by client and initializes the freshly-added
> > range. With that last addition, we could say that std::vector is as good
> > as it could ever get. I'm still forced to not use it in an application
> > because of that lack of flexibility.
>
> <nod>  I want this too (and I've heard others speak in favor of it too).
> But nobody has written it up and I'm so buried in my current proposal
> work that I don't think I'm going to get a chance to write it up.  You
> volunteering?  If you do, you'll need to stick some "restricted
> template" wording on it to disambiguate it from other constructors.  And
> as well as the "please don't initialize" motivation, another good use
> case is "initialize with legacy C function" (functor(pointer, size)
> might be better because of this use case).

resize() has the advantage that it isn't so overloaded.  Perhaps
provide one with an extra std::noinitialize argument.

For similar reasons (tight loops) I'd like to see
  assert(v.size() < v.capacity());
  v.unchecked_push_back(x);
where the motivation is not to prevent the copy-construction, but to
prevent the growth testing.

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

wade@stoner.com wrote:
> resize() has the advantage that it isn't so overloaded.

Yes, I was thinking of only resize() and giving up on the constructor.
  The incremental efficiency gain from doing things in the constructor
proper is in the noise.

> Perhaps
> provide one with an extra std::noinitialize argument.

NO. You don't want noinitialize. You want to specify a functor. If the
user writes a functor that ignores its arguments, the onus is fully on
them. But we don't want the standard to endorse and simplify such
advanced and rare uses as uninitialized growth.

> For similar reasons (tight loops) I'd like to see
>   assert(v.size() < v.capacity());
>   v.unchecked_push_back(x);
> where the motivation is not to prevent the copy-construction, but to
> prevent the growth testing.

I believe that's again not a big winner. Focusing on the big prize is
the way to go instead of shredding microoptimizations.


Andrei

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

In article <42F01C56.5090504@moderncppdesign.com>,
 "Andrei Alexandrescu (See Website for Email)"
 <seewebsiteforemail@moderncppdesign.com> wrote:

> wade@stoner.com wrote:
> > resize() has the advantage that it isn't so overloaded.
>
> Yes, I was thinking of only resize() and giving up on the constructor.
>   The incremental efficiency gain from doing things in the constructor
> proper is in the noise.

I can see the attractiveness of:

v.resize(n, functor());

However, I see it as attractive only in addition to, not instead of:

vector<T> v(n, functor());

There are no problems with implementability.  The standardeze may take a
little extra head scratching, but we've done it before.  No expense
should be spared in this department just for making the standard easier
to write.

Just off-the-cuff, I'm thinking something like:

template <class F> vector(size_type n, F f);

If F is convertible to value_type, then has the same effects as:

vector(n, static_cast<value_type>(f));

else has the same effects as:

vector v;
v.reserve(n);
f(v.data(), n);
v.size() = n;  // pseudo code

If f throws an exception it is responsible for destructing all T's it
has so far constructed.

Naturally the wording above isn't precise enough for a standard.  Just
trying to get the intent out there.  It might need a little more wording
to disambiguate it from the v(iterator, iterator) constructor.  But the
standardeze is the problem, not the implementability (so we should push
for it).

-Howard

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

Howard Hinnant wrote:
> I can see the attractiveness of:
>
> v.resize(n, functor());
>
> However, I see it as attractive only in addition to, not instead of:
>
> vector<T> v(n, functor());

Ehm, ok. But why insist on (pointer, size) instead of what all of the
stl does - (pointer, pointer)?


Andrei

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

In article <42F0516B.5000706@moderncppdesign.com>,
 "Andrei Alexandrescu (See Website for Email)"
 <seewebsiteforemail@moderncppdesign.com> wrote:

> Howard Hinnant wrote:
> > I can see the attractiveness of:
> >
> > v.resize(n, functor());
> >
> > However, I see it as attractive only in addition to, not instead of:
> >
> > vector<T> v(n, functor());
>
> Ehm, ok. But why insist on (pointer, size) instead of what all of the
> stl does - (pointer, pointer)?

"Insist" is too strong of a word.  "Preference" probably better fits
here.  My rationale is that I currently see two strong use cases:

1.  Avoid initialization for scalars.
2.  Initialize using a legacy code function.

Assuming (pointer, size) they (probably) look like:

struct empty_func
{
    template <class T>
    void operator()(T*, size_t) {}
};

extern "C" void legacy_function(double*, size_t);

int main()
{
   vector<double> v1(N, empty_func());
   vector<double> v2(N, legacy_function);
}

Assuming (iterator,iterator) then they (probably) look like:

struct empty_func
{
    template <class It>
    void operator()(It, It) {}
};

extern "C" void legacy_function(double*, size_t);

extern "C" {typedef void (*F)(double*, size_t);}

struct wrapper
{
    F f_;
    explicit wrapper(F f) : f_(f) {}
    template <class It>
    void operator()(It first, It last)
    {
        if (first != last)
           f_(&*first, last-first);
    }
};

int main()
{
    vector<double> v1(N, empty_func());
    vector<double> v2(N, wrapper(legacy_function));
}

I.e. I'm assuming that "legacy_function" is going to be an existing C
function, and the style there is (pointer, size) instead of
(pointer,pointer).  Adapting the style manually (as shown in my second
example above) isn't the end of the world, but my preference is not to
have to do it.

If on the other hand, legacy_function isn't really old code, but modern
code, then it isn't hard to write it in the (pointer, size) style with
no loss of performance or generality.

Or modern code could use "generation" or "transformation" iterators such
as found in the boost::iterators lib, and the existing vector(iter,
iter) constructor.  Thus I see the motivation for the proposed (n,
functor) constructor as less strong for interfacing to modern code.

But it isn't anything I'm going to loose any sleep over. :-)

-Howard

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

In article <42E708AC.8010700@moderncppdesign.com>,
 "Andrei Alexandrescu (See Website for Email)"
 <seewebsiteforemail@moderncppdesign.com> wrote:

> No. My next question is: how in the world is expand_to_eob not part of
> the specification?

> // max: upon input, the max size asked for
> //      upon return, the actual size granted
> void expand_to_eob(void* ptr, size_t & max) {
>    while (resize_alloc(ptr, max, &max) == 0) {
>    }
> }

The only significant difference between your expand_to_eob and my
negotiate_alloc:

> int negotiate_alloc(void* ptr, size_t min_size,
>                                size_t preferred_size,
>                                size_t* size_received);

is that I'm allowing the client to specify a minimum acceptable
expansion.

Let's say I'm writing vector<T>::push_back, and I'm at the part where my
size() == capacity().

So now I would prefer to expand my block in place.  Ideally I would like
to expand by a factor of 2, or 1.5, or 1.6 or whatever.  But at a
minimum, I need sizeof(T) more bytes.  If I can't get at least that
much, then I need to attempt the traditional reallocate dance.

Your expand_to_eob interface will go to the trouble to expand a block
even if it results in less than sizeof(T) bytes.  negotiate_alloc will
be able to return faster in this scenario because it will know that it
does not need to modify the heap structure.

Now look at vector::insert(pos, n, value):  In this scenario I don't
just need sizeof(T) more bytes, I need n*sizeof(T) more bytes (assuming
size() == capacity()).  I'm even more likely now to have to reallocate
instead of expand in place.  But I still want to check if I can expand
in place.  Is it not best to get that answer as quickly as possible?

Admittedly merging the next free block to the end of a currently
allocated block isn't super expensive.  Indeed, compared to allocating a
new block, copying all the existing data over, and deallocating the old
block, the expand-in-place is dirt cheap.  But when you compare the cost
of expand-in-place with the cost of doing nothing, nothing just beats
the pants off expand-in-place.

-Howard

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

Howard Hinnant wrote:
> In article <42E708AC.8010700@moderncppdesign.com>,
>  "Andrei Alexandrescu (See Website for Email)"
>  <seewebsiteforemail@moderncppdesign.com> wrote:
>
>
>>No. My next question is: how in the world is expand_to_eob not part of
>>the specification?
>
>
>>// max: upon input, the max size asked for
>>//      upon return, the actual size granted
>>void expand_to_eob(void* ptr, size_t & max) {
>>   while (resize_alloc(ptr, max, &max) == 0) {
>>   }
>>}
>
> The only significant difference between your expand_to_eob and my
> negotiate_alloc:
>
>
>>int negotiate_alloc(void* ptr, size_t min_size,
>>                               size_t preferred_size,
>>                               size_t* size_received);
>
>
> is that I'm allowing the client to specify a minimum acceptable
> expansion.

Oh. Would you say that negotiate_alloc(p, 0, s, ps) is equivalent to
expand_to_eob(p, s)?

> Let's say I'm writing vector<T>::push_back, and I'm at the part where my
> size() == capacity().
>
> So now I would prefer to expand my block in place.  Ideally I would like
> to expand by a factor of 2, or 1.5, or 1.6 or whatever.  But at a
> minimum, I need sizeof(T) more bytes.  If I can't get at least that
> much, then I need to attempt the traditional reallocate dance.
>
> Your expand_to_eob interface will go to the trouble to expand a block
> even if it results in less than sizeof(T) bytes.  negotiate_alloc will
> be able to return faster in this scenario because it will know that it
> does not need to modify the heap structure.

Yes, but on the other hand your negotiate_alloc could expand to
min_size every time you call it.

I think a good interface is negotiate_alloc with the guarantee that it
allocates the *largest possible block* within the limits. In other
words, an immediately subsequent call to negotiate_alloc that attempts
to expand the same pointer should fail, barring other threads or
interrupts.


Andrei

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

In article <42E7FCF9.9040802@moderncppdesign.com>,
 "Andrei Alexandrescu (See Website for Email)"
 <seewebsiteforemail@moderncppdesign.com> wrote:

> > The only significant difference between your expand_to_eob and my
> > negotiate_alloc:
> >
> >
> >>int negotiate_alloc(void* ptr, size_t min_size,
> >>                               size_t preferred_size,
> >>                               size_t* size_received);
> >
> >
> > is that I'm allowing the client to specify a minimum acceptable
> > expansion.
>
> Oh. Would you say that negotiate_alloc(p, 0, s, ps) is equivalent to
> expand_to_eob(p, s)?

<nod> That's my current understanding.

> > Let's say I'm writing vector<T>::push_back, and I'm at the part where my
> > size() == capacity().
> >
> > So now I would prefer to expand my block in place.  Ideally I would like
> > to expand by a factor of 2, or 1.5, or 1.6 or whatever.  But at a
> > minimum, I need sizeof(T) more bytes.  If I can't get at least that
> > much, then I need to attempt the traditional reallocate dance.
> >
> > Your expand_to_eob interface will go to the trouble to expand a block
> > even if it results in less than sizeof(T) bytes.  negotiate_alloc will
> > be able to return faster in this scenario because it will know that it
> > does not need to modify the heap structure.
>
> Yes, but on the other hand your negotiate_alloc could expand to
> min_size every time you call it.

And every call to new can throw an exception.  There's always QOI issues
in allocators.  Those with low quality tend to not get used.  Believe it
or not, we vendors are not out to get you. ;-)

> I think a good interface is negotiate_alloc with the guarantee that it
> allocates the *largest possible block* within the limits. In other
> words, an immediately subsequent call to negotiate_alloc that attempts
> to expand the same pointer should fail, barring other threads or
> interrupts.

I believe we're in violent agreement on the intent.  This is what I
currently have:

> The intention of this function is to expand a block of memory in place to
> preferred_size, but failing to do that, expand to min_size. Failure is only
> indicated (with a zero return) if the memory block cannot be expanded to
> min_size.

I'm open to suggestions on better wording.  Your paragraph above isn't
quite the standardeze we need because a larger expand might succeed if
preferred_size was the limiting factor on the last call.

However precise wording is not exactly a priority right now as the C
committee hasn't even looked at this, much less said: yep, this is just
what we need.

Failing acceptance in the C community, we could still lobby for a C++
interface in the allocator requirements that would support this
functionality.  However I fear that without the underlying C support
such an interface might be under utilized.  I can write my own heap
manager to support this interface, but I suspect that not very many
programmers are willing to do that.

-Howard

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

On 2005-07-27 22:44, Howard Hinnant wrote:
:
>> >>int negotiate_alloc(void* ptr, size_t min_size,
>> >>                               size_t preferred_size,
>> >>                               size_t* size_received);
:
>> The intention of this function is to expand a block of memory in
>> place to preferred_size, but failing to do that, expand to
>> min_size. Failure is only indicated (with a zero return) if the
>> memory block cannot be expanded to min_size.

Doesn't this mean that

   negotiate_alloc(p, a, b, ps)

is pretty much equivalent to

   negotiate_alloc(p, b, b, ps) ||
   negotiate_alloc(p, a, a, ps)

?

(Yes, the available size might change between the two calls, but
that's not worse than if the change happened before the first call.)

I agree with Andrei that the function should expand to the maximum
available size between a and b. The vector example certainly would
like to have it this way.

-- Niklas Matthies

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