"Andrei Alexandrescu" <andrewalex@hotmail.com> wrote in message
news:9fn386$4qaft$1@ID-14036.news.dfncis.de...

> I would say the strategy would be: try to expand by a fixed amount (say 16
> elements). If you can't, double capacity. This is simple and effective.
> Because expansion is O(1), you can afford to expand in fixed small steps.

That's true if you're only expanding one array with no other dynamic memory
activity, but if you ask for too little, something else may be allocated in
the area at the end, forcing the array to relocate.

-Dave



      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On 6 Jun 2001 23:23:03 -0400, Andrei Alexandrescu <andrewalex@hotmail.com>
wrote:
> "Niklas Matthies" <news/comp.std.c++@nmhq.net> wrote in message
> news:slrn9hqapi.pii.news/comp.std.c++@ns.nmhq.net...
> >    typedef difference_type diff_t;
> >
> >    bool   shrink (T *p, diff_t n);
> >    bool   grow   (T *p, diff_t n);
> >    diff_t grow   (T *p, diff_t min_n, diff_t max_n);
>
> Why not using size_type instead of difference_type?

Maybe because what we are passing actually _is_ a difference?

> [snip]
> > I consider these three (or six) functions to be the elementary operations
> > needed with regard to resizing. Or does anyone see some resizing need
> > that couldn't efficiently be implemented in terms of these operations?
>
> Allocators for primitive types that support efficient reallocation but not
> expansion can be implemented using the C heap.

Could you rephrase this? I'm not sure whether you are agreeing with me
or objecting. :)

-- Niklas Matthies

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

"Howard Hinnant" <hinnant@antispam.metrowerks.com> wrote in message
news:060620011923364485%hinnant@antispam.metrowerks.com...
> Though I would favor some feedback as to the availble size if the
> expand fails:
>
> void * operator new(size_t requested_size, void *, size_t&
> available_size, _Expand) throw();

How about passing in the min and max acceptable values. operator new then
provides the largest available size between the two sizes, or fails

void * operator new(void * original block, size_t min_size,size_t max_size,
_Expand);
void * operator new(nothrow_t, void * original block, size_t min_size,size_t
max_size, _Expand) throw();

The failure mechanism is std::bad_alloc, or NULL, as for normal operator
new.

Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optoelectronics
The opinions expressed in this message are not necessarily those of my
employer




      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Howard Hinnant <hinnant@antispam.metrowerks.com> wrote in message
news:<060620011923364485%hinnant@antispam.metrowerks.com>...
> In article <3b1d988f$0$12244$cc9e4d1f@news.dial.pipex.com>, Stephen
> Howe <NOSPAMsjhowe@dial.pipex.com> wrote:
>
> | 2. Now that we have vector, why should new[] ever be used? A few days ago I
> | noticed on my 32-bit implementation that sizeof(vector) was 16 bytes where a
> | point occupies 4 bytes. So new[] is space-saving and ideal if you are not
> | using any of vectors capabilities.
>
> Yes, new[] is still needed.  One size never fits all.  vector greatly
> diminishes the need for new[], and the need for auto_ptr<X[]>.  But it
> doesn't eliminate the need for these.  The overhead argument you bring
> up is one very important reason (although vector overhead with an empty
> allocator should get down to 12 bytes on a 32 bit system).

I just want to point out that the new[] "overhead" is usually 12 bytes
as well: 4 bytes for the pointer and typically 8 (sometimes 16) bytes
for the block header (the heap manager has to store the block size
somewhere.)

std::vector<T, std::allocator<T> > can move its 8 extra bytes to the
heap as well.

> Other
> reasons include the ability to transfer ownership of the memory.

... to a 'legacy' C++ function, presumably. You can already transfer
ownership to another vector using swap.

--
Peter Dimov
Multi Media Ltd.

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On 7 Jun 2001 06:16:59 -0400, Howard Hinnant <hinnant@antispam.metrowerks.com>
wrote:
[         ]
> Though I would favor some feedback as to the availble size if the
> expand fails:
>
> void * operator new(size_t requested_size, void *, size_t&
> available_size, _Expand) throw();

This is unsuitable for a threaded environment, because the
available_size may change any time.
See my recent post in this thread on comp.std.c++ for a thread-safe
approach to this problem.

-- Niklas Matthies

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

"Howard Hinnant" <hinnant@antispam.metrowerks.com> wrote in message
news:060620011129366250%hinnant@antispam.metrowerks.com...
> vector, for example, is usually going to try to expand to twice it's
> current capacity.  Assume you're a vector and you've just requested
> such an expansion.  expand answers:  Nope, can't do that.  You wonder,
> should I have asked for less?  It's like one of those games I hear on
> the radio where you try to guess how much money is in the pot.  Answer
> low enough and you get the amount you guessed.  Get greedy, and you get
> none.

I would say the strategy would be: try to expand by a fixed amount (say 16
elements). If you can't, double capacity. This is simple and effective.
Because expansion is O(1), you can afford to expand in fixed small steps.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar
---
[ 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.research.att.com/~austern/csc/faq.html                ]

In article <memo.20010605053635.57785K@brangdon.madasafish.com>, Dave
Harris <brangdon@cix.co.uk> writes
>In summary, the argument for reallocate() is much weaker than for
>expand(). It complicates the code more, and doesn't offer so much
>advantage.

Perhaps what we need is another signature for operator new:

struct _Expand {} expand;
void * operator new(size_t, void *, _Expand);

which returns either the original address if it successfully expands the
memory block, or null if it fails. Sort of like new(nothrow).

Implementors could try that now if they wished. No change is needed to
the core of the language.


Francis Glassborow      ACCU
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

In article <9fjsff$4crau$1@ID-14036.news.dfncis.de>, Andrei
Alexandrescu <andrewalex@hotmail.com> wrote:

| > Allocator's only role is to manage raw memory, nothing more.
|
| I agree, however the allocator does have the destroy() think in it. If I
| could afford a good lawyer, we would have gotten a case :o).

<grin> Yup.

| > Imho there ought to be a dialog between a vector (for example) and its
| > allocator that goes something like:
| >
| > vector:  Allocator, can you expand this block to N objects?
| > allocator:  No, but I can expand it to M objects.  Do you want that?
| > vector:  Ok, I'll take the M objects.
|
| Well, on second thought, I agree. I even start to like the expansion
| procedure, but in my opinion it should be one-step. If it's not, problems
| can appear in multithreaded environments. That's because between the time
| the allocator tells you how much memory it has at the end of the current
| block and the moment you grab that block, another thread can get that
| memory.
|
| So I think the right API is just an expand function that either succeeds or
| fails, and that's it. (By the way, I have a draft article on typed buffers.
| If anyone would be interested in reviewing it, please write me email.)

vector, for example, is usually going to try to expand to twice it's
current capacity.  Assume you're a vector and you've just requested
such an expansion.  expand answers:  Nope, can't do that.  You wonder,
should I have asked for less?  It's like one of those games I hear on
the radio where you try to guess how much money is in the pot.  Answer
low enough and you get the amount you guessed.  Get greedy, and you get
none.

So does vector guess again with a lower amount?  I say yes.  But give
vector a good hint to the right answer.  I agree that when the
allocator says it can expand to M objects, that vector can't assume the
next expand will succeed.  But it is a good guess.

So put the expand request in a loop until the request succeeds, or
until the available size is no longer satisfactory.

| If you include reallocate() in allocators, you can implement it in
| terms of std::realloc() for malloc-based allocators for primitive and
| POD types on any system. If you don't include it, you need special
| co-operation from the system.

For this to work I believe we will need to enhance new/delete to
include the expand concept so that a user-overridden new can support
it.  This does not mean I'm in favor of a new_resize expression.  I'm
not.  But I think we will need /operator/ new_expand (or something like
that).

| By the way Howard, I'm just perusing MSL online help. No expand in
| there.

That's right.  I believe I will need the standards committee's help to
do this properly.

--
Howard Hinnant
Metrowerks

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

"Niklas Matthies" <news/comp.std.c++@nmhq.net> wrote in message
news:slrn9hqapi.pii.news/comp.std.c++@ns.nmhq.net...
>    typedef difference_type diff_t;
>
>    bool   shrink (T *p, diff_t n);
>    bool   grow   (T *p, diff_t n);
>    diff_t grow   (T *p, diff_t min_n, diff_t max_n);

Why not using size_type instead of difference_type?

[snip]
> I consider these three (or six) functions to be the elementary operations
> needed with regard to resizing. Or does anyone see some resizing need
> that couldn't efficiently be implemented in terms of these operations?


Allocators for primitive types that support efficient reallocation but not
expansion can be implemented using the C heap.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar
---
[ 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.research.att.com/~austern/csc/faq.html                ]

In article <3b1d988f$0$12244$cc9e4d1f@news.dial.pipex.com>, Stephen
Howe <NOSPAMsjhowe@dial.pipex.com> wrote:

| Yes but we have two things on our hands not one.
|
| 1. Should there be builtin reallocation operators that works with
| new[]/delete[] or we we talking about adding to various containers
| allocators interface?

I think there needs to be an operator new_resize (of some syntax not
yet specified), but not necessarily a new_resize expression.  The
latter existing to support an expand interface in a new version of
allocators.

| 2. Now that we have vector, why should new[] ever be used? A few days ago I
| noticed on my 32-bit implementation that sizeof(vector) was 16 bytes where a
| point occupies 4 bytes. So new[] is space-saving and ideal if you are not
| using any of vectors capabilities.

Yes, new[] is still needed.  One size never fits all.  vector greatly
diminishes the need for new[], and the need for auto_ptr<X[]>.  But it
doesn't eliminate the need for these.  The overhead argument you bring
up is one very important reason (although vector overhead with an empty
allocator should get down to 12 bytes on a 32 bit system).  Other
reasons include the ability to transfer ownership of the memory.

In article <WiPw0sAnEhH7Ew8e@ntlworld.com>, Francis Glassborow
<francis.glassborow@ntlworld.com> wrote:

| Perhaps what we need is another signature for operator new:
|
| struct _Expand {} expand;
| void * operator new(size_t, void *, _Expand);
|
| which returns either the original address if it successfully expands the
| memory block, or null if it fails. Sort of like new(nothrow).
|
| Implementors could try that now if they wished. No change is needed to
| the core of the language.

Exactly.  We need an operator new_expand, but not a new_expand
expression.  Excellent suggestion!

Though I would favor some feedback as to the availble size if the
expand fails:

void * operator new(size_t requested_size, void *, size_t&
available_size, _Expand) throw();

--
Howard Hinnant
Metrowerks
---
[ 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.research.att.com/~austern/csc/faq.html                ]

andrewalex@hotmail.com (Andrei Alexandrescu) wrote (abridged):
> I was thinking - and am communicating with Boris Fomitchev - that
> to make allocators useful we need to expand their interface.

I am never sure how much of this stuff should be done through email, and
how much through the newsgroups. I'll understand if anyone wants me to
take this off-group.


> At a minimum, allocators must support calls for in-place
> expansion/shrinkage and for reallocation of blocks. By the way,
> both expansion and reallocation must be present even though the
> latter might seem to include the former. That's because you use
> different allocation strategies for allocators that support
> in-place expansion as opposed to those that only support
> reallocation (with potential move).

Specifically, expansion must be O(1) but reallocation may be O(N).


> On an allocator that supports reallocation but not in-place expansion

Are you suggesting that reallocate() be optional? If so that bothers me.
It means that vector still needs the alloc-move-dealloc code shown below.
The code will be in both vector and the allocator. It just seems an
inelegant design.

Wouldn't it be better to use non-member functions and get backwards
compatibility through default implementations? (Admittedly this gets into
the "specialising std algorithms" issue.)


> That is, an extended allocator's interface looks like so:

You forgot to add:

    pair<T *, size_type> allocate( size_type size );

:-) I still think its good to get the actual, rounded-up size into
vector::capacity() as early as possible.


>     bool expand(T* mem, size_type oldSize, size_type newSize);
>     void reallocate(T* mem, size_type oldSize, size_type newSize);

Did you mean for reallocate() to return a (T *)? If not, I don't
understand what it does. I thought the semantics were supposed to be
similar to realloc(). That aside, I presume the void return means the
function is not allowed to fail.

Could a conforming implementation be vaguely like:

    T *reallocate( T *pold, size_type oldSize, size_type newSize ) {
        assert( newSize >= oldSize ); // ??
        T *pNew = alloc( newSize );
        block_move( pNew, pOld, oldSize );
        deallocate( pMem, oldSize );
        return pNew;
    }

I can see that by putting this code into the allocator, we can more
easily specialise it for the case where the block happens to be growable
on the left. Is that the right idea? How big a benefit do you expect that
to be?

I should think in the common case there will be no adjacent block on the
left that is big enough. Putting in a test for it will slow down the
common case and could easily slow down the average case, too. In fact,
here are several differences between expand() and deallocate() as I
understand them:

(1) I can see how to write an allocator for which expand() is often able
to extend the block to the right, especially if the usage pattern is
stack-like. Extending to either side seems harder, less systematically
likely to happen.

(2) I can see how to write an allocator for which expand() is able to
shrink the block in most cases. As in (1), it seems unlikely that there
will be an adjacent free block for a copying shrink to copy into.

(3) Expand() has better big-O complexity, O(1) versus O(N) for expand, so
it offers a bigger benefit when it succeeds.

(4) Expand() doesn't need to copy the items. Reallocate() opens up the
block_move() can of worms. In fact, this deserves its own section...

What actually happens with the block_move()? Are we moving bytes or
objects, or a mixture of both? The above code assumes all oldSize items
are fully constructed but does not construct the new (newSize-oldSize)
items. This is probably wrong. Eg if we have a vector with size=5,
capacity=20, and append 80 items, reallocate() must move 5 items not 20.
It at least needs another size_type argument.

If reallocate() can shrink, what happens if it shrinks to smaller than
the number of constructed items? Presumably it is responsible for
destroying them correctly. Would it be more symmetrical if it was also
responsible for constructing some number of new items?

What happens about exception safety? If we always allocate a new block,
copy-construct in the new block, delete the items in the old block, and
deallocate the old block, we can handle an exception thrown during the
copy by destroying the items copied so far, then deallocating the new
block. We can give the strong guarantee. We cannot do this if we are
moving data within a single block.

I think reallocate() generally overlaps with the core functionality of
vector. My earlier point about the same block-move code being in both
emphasises this.

In summary, the argument for reallocate() is much weaker than for
expand(). It complicates the code more, and doesn't offer so much
advantage.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."
---
[ 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.research.att.com/~austern/csc/faq.html                ]

In article <9fgbd6$3uleb$1@ID-14036.news.dfncis.de>, Andrei
Alexandrescu <andrewalex@hotmail.com> wrote:

| Two notes:
|
| 1. new_resize should not throw an exception if it cannot expand the current
| block. This is not an exceptional case, it's a normal case. If expansion
| fails, you proceed with the copying reallocation.
|
| 2. As I mentioned in a parallel post, BOTH in-place expansion and
| (potentially moving) reallocation primitives should be present. That's
| because if you have guaranteed in-place reallocation, you can use a
| different allocation strategy.

I've been lurking on this thread quite a while, probably too long.
Imho a moving reallocation is not appropriate in an allocator, no
matter the underlying memory management architechture.  It is vector's
(or buffer's or whatever) job to decide on the stategy to increase
capacity.  Allocator's only role is to manage raw memory, nothing more.

Imho there ought to be a dialog between a vector (for example) and its
allocator that goes something like:

vector:  Allocator, can you expand this block to N objects?
allocator:  No, but I can expand it to M objects.  Do you want that?
vector:  Ok, I'll take the M objects.

Allocator deals with raw memory, period.  vector (or buffer) deals with
a dynamically sized array of homogenous objects.  Only vector has
enough information to decide how much memory to request, and how much
(in place) memory expansion is acceptable before starting to move
objects around.  And only vector is qualified to decide /how/ to move
those objects around if it needs to.  Are the proper semantics assign?
Move?  Swap?  What exception safety guarantees are appropriate for this
particlular expansion?  insert generally (but not universally) requires
basic.  push_back requires strong.  Build all that into allocator and
you've got another vector on your hands!

It would be great to build expand into allocator.  I'm all for it.  But
not realloc.  realloc is vector's job.  allocator::expand needs to not
only tell vector whether or not it can expand to the requested size,
but if it can't, how much it could expand to.  vector can decide
whether the available expansion size is acceptable or not.  If moving
objects has to take place, that needs to happen at a level above
allocator.  Because no one strategy for moving objects fits all.

--
Howard Hinnant
Metrowerks

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Sebastien Hitier <sebapi747@hotmail.com> wrote in message
news:9fdpsp$mji$1@newsg3.svr.pol.co.uk...

> BTW, why should we _NEVER_ acquire different memory block ?
> if we were to allow aquisition different block, we can then write a new
> operator that
> uses malloc, and a new_resize that uses realloc.

That last point: No we couldn't. The problem is a true C++ realloc() needs
to separate the business of  expand/shrink/new/delete memory blocks with the
business of calling constructors, copy constructors and destructors. They
are interleaved. That is why a straight C call to realloc() will never work.
If realloc() decided to delete the old block and allocate new block if
expanding, copy constructors would need to be called for size of old block,
the default constructors for the difference and destructors on the old
block. How are you going to do that, if your version of realloc() has
already freed the old block and returned a new bigger block? It is now too
late to take action.

The real problem with C++ realloc() is it s not a primitive, it does too
many things. That is why I proposed a primitive new_resize that just
expands/shrinks blocks, that is all. Around that would be fitted the calling
of constructors/destructors.

Stephen Howe



      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Allan W <allan_w@my-dejanews.com> wrote in message
news:7f2735a5.0106011040.73aa9dd8@posting.google.com...

> Dave meant that there are only two ways that more memory could be
> allocated to the block without requiring the data to be moved to
> a new address, which could cause problems. Both of your options do
> involve changing the base address of the data.

I realise that. It is no help at all for a C++ style realloc() but for a C
realloc(), it provides extra options for obtaining memory.

Stephen Howe





      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Dave Harris <brangdon@cix.co.uk> wrote in message
news:memo.20010602150328.21899A@brangdon.madasafish.com...

> I was concerned about dynamic resizing because it seemed heavily
> dependant on the patterns of memory allocation through-out the code and
> history. As such it is hard to reason about locally. Although we might
> occasionally get lucky and have a resizable block, to rely on this for
> life-critical performance guarantees seemed like bad engineering.

Well I am thinking that perhaps memory allocators have been designed
assuming that expansion of blocks will never occur.
Suppose the allocators were redesigned with expansion/shrinkage as a
possibility, would we get better performance out of the standard containers?

I am also thinking that due to the complexity requirements for vector, for
many implementations it capacity doubles once the old capacity is reached.
Also, reading up on memory allocators, some operate on powers of 2 lists.
That could mean that _expand/new_resize becomes a waste of time as every
time it fails due to the way the allocator has been designed.

> The resizing might be more reliable if it worked the other way about -
> shrinking rather than enlarging. Allocate a large block to begin with,
> use as much as we need, then return the excess. Currently the STD is not
> conducive to this way of working. There isn't even a guaranteed way of
> shrinking a std::vector *with* copying.

No. Personally I think that all containers should have some shrink method
which returns surplus memory back to the allocator.
Other than destruction, the container cannot know when the programmer has
"finished" with it

> For example, Microsoft's _expand is not given the old size of the block.

But it is a C function. The bookkeeping of the size of the block is hidden
from the programmer.

> That is fine for their scheme which tracks sizes itself, but would mean
> some extra overhead for other allocation schemes. Incidently, their
> _expand is a global function, which I don't think we need. We don't need
> resize for memory blocks got via operator new(), because the size of
> non-array objects is constant.

Granted. I originally proposed just new, new[] and new_resize[], no
new_resize for that reason.

> I suspect we don't need it for operator
> new[](), either. People should be encouraged to use std::vector instead
> (or perhaps Andrei's lower-level Buffer class). So I think we are only
> talking about allocator objects.

These days, I am not sure when you would use new[] in preference to vector.

> To put it another way, allocator objects are in many ways a nicer
> interface than operator new() and operator delete(). This is partly
> because they are more explicit in how they group the operations. People
> are less likely to provide an allocator::allocate() and forget to provide
> the corresponding allocator::deallocate() because they are in the same
> object. The allocator::construct() function is clearer than placement
> new. We can pass allocators around as arguments more easily than we can
> pass operator new().
>
> Thus instead of providing global functions like _expand(), perhaps we
> should add allocator::expand and then provide an allocator which
> represents the memory which underlies operator new[]().
>
> Memory in C++ is really quite diverse. We have malloc(), global operator
> new(), class-specific operator new(), global/class operator new[](), and
> allocators. All of them have their corresponding delete operations which
> must not be mixed up. They all have slightly different functionality, and
> when the functionality is the same it is presented with a different API.
> Can we consolidate all this? Have allocators which causally reflect each
> type of memory?

It has got messy :-). IMO, C++ is worse off compared to C because of the
lack of resizing.

Stephen Howe



      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

I think this realloc suggestion is trickier than it looks.  If you had any
classes like:

// warning: untested
class A
{
    int i;
    int *pi;
public:
    A(): pi(&i) {}
};

or

// warning: untested
class B
{
public:
    B() { Registry::register(this); }
    ~B() { Registry::unregister(this); }
};

You could run into serious trouble.  I think B falls under your caveat, but
I think it's worth noting that using this reallocation scheme prevents you
from extending your code to use such a registry.  In general, you can't
assume objects that can be realloc'd ever had their constructor called while
they lived in their current memory slice.

That's not to say it can't work, just that I don't think it's quite as easy
as it sounds.

"Allan W" <allan_w@my-dejanews.com> wrote in message
news:7f2735a5.0106041230.2d824c90@posting.google.com...
<snip>
> You can do it yourself.
>
> 1. Write your own global operator new in terms of malloc, and your own
> global operator delete in terms of free. The standard specifically
> makes this possible by guaranteeing that malloc() and free() are not
> implemented in terms of new/delete (which would have led to endless
> recursion).
>
> 2. Now you can use realloc on any object you obtained via new (but not
> via new[]).
>
> 3. Caveat emptor: do not use realloc on:
>   ** Any object allocated with new[] instead of new. (Or you could
>      write your own new[] and delete[] too...)
>
>   ** An element in an array
>
>   ** Any object that is pointed to by pointers not under control of
>      the code doing the reallocating. For instance, if you have a
>      vector of pointers to buffer, don't reallocate any of those
>      buffers.
>
> Hope this helps?
---
[ 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.research.att.com/~austern/csc/faq.html                ]

On 5 Jun 2001 13:35:27 -0400, Dave Harris <brangdon@cix.co.uk> wrote:
> andrewalex@hotmail.com (Andrei Alexandrescu) wrote (abridged):
> > I was thinking - and am communicating with Boris Fomitchev - that
> > to make allocators useful we need to expand their interface.
>
> I am never sure how much of this stuff should be done through email, and
> how much through the newsgroups. I'll understand if anyone wants me to
> take this off-group.

Just to jump into the discussion, I would suggest that an interface
extension should contain something like the following functions:

   typedef difference_type diff_t;

   bool   shrink (T *p, diff_t n);
   bool   grow   (T *p, diff_t n);
   diff_t grow   (T *p, diff_t min_n, diff_t max_n);

   Alternative naming: shrink -> reduce, grow -> expand.

   Preconditions for shrink(,):  p != 0, n > 0
   Preconditions for grow(,):    p != 0, n > 0
   Preconditions for grow(,,):   p != 0, min_n > 0, max_n >= min_n

   Description:

   shrink(,) will either reduce the allocated storage pointed to by p
   in-place by n elements in O(1) and return true, or else return false.

   grow(,) will either expand the allocated storage pointed to by p
   in-place by n elements in O(1) and return true, or else return false.

   grow(,,) will either expand the allocated storage pointed to by p
   in-place by at least min_n and at most max_n elements in O(1) or
   else leave the storage unchanged, and in either case return the
   number of added elements.

The reason to separate growing from shrinking is that in many
situations, it is known which one applies (push_back() for example),
so that extra tests within the resizing code are not needed.
A more general resize function is easily written:

   bool resize(T *p, diff_t n)
   {
      return   n == 0 ? true
           :   n  > 0 ? grow  (p,  n)
                      : shrink(p, -n);    // excuse the fancy formatting ;)
   }

The 3-argument grow() is useful if the caller, while not currently
needing more than min_n additional elements, doesn't mind to get a few
more elements "for free" if they are available, to prevent having to
call grow() again soon for the next few requests the caller has to
satisfy. An obvious example would be repeated push_back()s by a vector.

The reason for using difference_type instead of size_type is that I
think that both in the calling code and the implementation, it is
somewhat more likely that the amount by which to grow or to shrink is
readily available or usable than the resulting size.
Also, with grow(,,), it is usually slightly more efficient to test the
return value for zero than to compare it with the old size. The main
motivation though is not such micro-efficiency considerations, but
simpler source code.

I'm not sure whether there's a compelling reason to include a
reallocation() facility. I tend to think that it's better to leave this
to the client code, since there are hardly any performance benefits in
letting the allocator provide it as an atomic operation, and a
client-side implementation is more flexible in adapting the copying
process to specific circumstances (for example, there might be
situations in which only some of the objects need to be moved).

Another aspect to think about is that it might make sense to add

   bool   shrink_front (T *p, diff_t n);
   bool   grow_front   (T *p, diff_t n);
   diff_t grow_front   (T *p, diff_t min_n, diff_t max_n);

which do the resizing at the front of the storage area instead of at the
end, even though there doesn't seem to be any tradition of providing
such facilities. Queues that are implemented as a linked list of memory
chunks each consisting of an array of elements could benefit from such a
facility, as well as string types.

I consider these three (or six) functions to be the elementary operations
needed with regard to resizing. Or does anyone see some resizing need
that couldn't efficiently be implemented in terms of these operations?

-- Niklas Matthies

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

"Dave Harris" <brangdon@cix.co.uk> wrote in message
news:memo.20010602150328.21899A@brangdon.madasafish.com...
[excellent insights snipped]

> Can we consolidate all this? Have allocators which causally reflect each
> type of memory?

Your considerations make a lot of sense. I was thinking - and am
communicating with Boris Fomitchev - that to make allocators useful we need
to expand their interface.

At a minimum, allocators must support calls for in-place expansion/shrinkage
and for reallocation of blocks. By the way, both expansion and reallocation
must be present even though the latter might seem to include the former.
That's because you use different allocation strategies for allocators that
support in-place expansion as opposed to those that only support
reallocation (with potential move).

On an allocator that supports in-place expansion you grow buffers in small
increments - you don't double the allocated size. That is because expansion
is cheap. This way you increase your chances of getting space and you make
conservative use of memory.

On an allocator that supports reallocation but not in-place expansion (think
of an allocator<int> that uses realloc as a back-end) you need to double the
allocated size because you don't want to fall into the O(N*N) pattern. That
is, there is a chance the reallocation will find some space but you don't
know, and there's the risk of not finding that memory and copying data
around like crazy.

The buffer class template in CUJ Experts on August 2001 will support current
std allocators as well as extended allocators, selectable through traits.
Also, the extended allocators have templated constructors that take the
original allocator while rebinding. This is to support allocators with
state. That is, an extended allocator's interface looks like so:

template <class T>
struct allocator
{
    allocator();
    allocator(const allocator&);
    template <class U> allocator(const allocator<U>&);
    ...
    bool expand(T* mem, size_type oldSize, size_type newSize);
    void reallocate(T* mem, size_type oldSize, size_type newSize);
    ...
};

I am actually quite excited that we can make allocators useful.


Andrei



      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

> Are we changing the API to support poor allocators?

If poor means good, than yes, that's the idea.

--
Valentin Bonnard

---
[ 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.research.att.com/~austern/csc/faq.html                ]

"Sebastien Hitier" <sebapi747@hotmail.com> wrote in message
news:9fdpsp$mji$1@newsg3.svr.pol.co.uk...
> >
> > 1) primitive raw new_resize
> >
> > operator new_resize[] will work similarly to _expand as discussed here.
It
> > will know the size of any array of objects (just like delete[] does).
It's
> > job is to expand or contract a block of memory, insitu, that is all.
> Unlike
> > realloc(), it _NEVER_ acquires a different block. It will guaranteed by
> the
> > ISO C++ standard > operator nthat contracting will never throw an
> exception and will
> > always succeed. In contrast, on expansion, if it cannot expand the
block,
> an
> > exception is thrown (*).
>
> BTW, why should we _NEVER_ acquire different memory block ?
> if we were to allow aquisition different block, we can then write a new
> operator that
> uses malloc, and a new_resize that uses realloc.

Two notes:

1. new_resize should not throw an exception if it cannot expand the current
block. This is not an exceptional case, it's a normal case. If expansion
fails, you proceed with the copying reallocation.

2. As I mentioned in a parallel post, BOTH in-place expansion and
(potentially moving) reallocation primitives should be present. That's
because if you have guaranteed in-place reallocation, you can use a
different allocation strategy.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar
---
[ 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.research.att.com/~austern/csc/faq.html                ]

> "Andrei Alexandrescu" <andrewalex@hotmail.com> writes:
> > So I wanted to ask whether there is any support in the C++ community
> > to standardize efficient reallocation.

Chris Uzdavinis <chris@atdesk.com> wrote:
> Currently, it seems that this issue is just kind of swept under the
> rug.  When asked by people from other languages why C++ doesn't have a
> realloc-like function, the answer usually resembles "... because."
[snip]
> I think your 2-horses analogy is fitting.  A realloc-like feature was
> left out (either intentionally or otherwise), and now people think
> that there is some secret reason that only those in the inner sanctum
> of C++ know about, but certainly that omission is there for a good
> REASON that ought not be challenged.
>
> So, let's challenge it.
>
>  Perhaps there is an academic reason (E.G. "not all platforms support
> it, so it's impossible to write a standard-compliant C++ compiler for
> those platforms") but perhaps there are workarounds or concessions
> that could still be made.  In any case, it's worth a few minutes worth
> of discussion.

You can do it yourself.

1. Write your own global operator new in terms of malloc, and your own
global operator delete in terms of free. The standard specifically
makes this possible by guaranteeing that malloc() and free() are not
implemented in terms of new/delete (which would have led to endless
recursion).

2. Now you can use realloc on any object you obtained via new (but not
via new[]).

3. Caveat emptor: do not use realloc on:
  ** Any object allocated with new[] instead of new. (Or you could
     write your own new[] and delete[] too...)

  ** An element in an array

  ** Any object that is pointed to by pointers not under control of
     the code doing the reallocating. For instance, if you have a
     vector of pointers to buffer, don't reallocate any of those
     buffers.

Hope this helps?
---
[ 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.research.att.com/~austern/csc/faq.html                ]

Luis Pedro Coelho <deepblack@geocities.com> wrote:
> I do not know the interface of _expand, but I think a fitting interface
> could be:
>
> std::size_t capacity(const void*);
>
> This would return the full capacity available for that pointer. A simple
> implementation would simply return what was previously asked for, or maybe
> a zero return could be used to indicate that the memory available is
> exactly what was asked for previously. The behaviour of calling this on a
> pointer not obtained through null is undefined.

<shudder>

Pointers to objects on the heap come from many places; operator new
is only one of those places. The ability to write our own operator new
functions, either as class members or globally, allows the user to
insert additional processing.

Consider this:

    class Foo { /* ... */ };
    Foo* foo = new Foo("Yes");
    char * beginpad = reinterpret_cast<char*>(foo);
    char * endpad = beginpad + std::capacity(foo);
    beginpad += sizeof(Foo);
    if (endpad > beginpad)
        memset(beginpad, 'x', endpad-beginpad);

This fills the alignment bytes past the end of Foo with the letter 'x',
which ought to be quite legal under this proposal. If the size of Foo is
20 bytes, and if the heap rounds every request to a multiple of 32 bytes,
then we get to stuff 12 x's in there. As presented, there's no real point
to this -- but let's assume that the programmer had a good reason.

Six months from now, we discover a problem -- once the program has been
running for 3 days, it crashes. Eventually we conclude that there's some
sort of memory overwrite. So we buy (or develop) a memory trace
facility, one specifically meant to search for memory overwrites. One
of the things this package does is add 16 bytes padding to the beginning
and 16 more bytes padding to the ending of every memory allocation, to
check for memory overwrites. What does this do to the code above?

The size of Foo has not changed; it's still 20 bytes. But now, the debug
library adds 32 bytes to every request. We end up allocating 64 bytes
from the heap.

Do you see where I'm going with this? First, capacity() isn't likely to
work anymore, because it points 16 bytes past the beginning of what the
low-level heap gave to the debugging routines. But if capacity() does
manage to figure out that this is somewhere in the 64-byte hunk of
memory, that's even worse -- our program will write either 44 or 28
x's, overwriting at least some of what the debug library put in place.

You can call my example unrealistic, or too specialized to matter. But
my point is, just because the low-level heap knows that the memory
comes in 32-byte hunks, doesn't mean that the high-level logic gets to
use all 32 bytes in every hunk.

Here's a possibly more realistic example: suppose your program allocates
an array.

    Foo * fooary = new Foo[5];

The runtime system has to allocate at least 5*20=100 bytes for this
array. But it also has to store the number 5 somewhere so that when
you destroy the array, it can call all the destructors. (The size of
the heap block is NOT sufficient -- in this case it's 128 bytes,
which is enough for 6 elements, not just the 5 we asked for.) Where
is this number 5 kept? That's an implementation detail. Sometimes it's
stored in essentially a map<void*,int> -- but other times the runtime
system ends up asking for 104 bytes, and uses the first 4 bytes to
store the number of elements in the array. Again, the low-level heap
would not know anything about this.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Howard Hinnant" <hinnant@antispam.metrowerks.com> wrote in message
news:040620012107367859%hinnant@antispam.metrowerks.com...
> I've been lurking on this thread quite a while, probably too long.
> Imho a moving reallocation is not appropriate in an allocator, no
> matter the underlying memory management architechture.  It is vector's
> (or buffer's or whatever) job to decide on the stategy to increase
> capacity.  Allocator's only role is to manage raw memory, nothing more.

I agree, however the allocator does have the destroy() think in it. If I
could afford a good lawyer, we would have gotten a case :o).

> Imho there ought to be a dialog between a vector (for example) and its
> allocator that goes something like:
>
> vector:  Allocator, can you expand this block to N objects?
> allocator:  No, but I can expand it to M objects.  Do you want that?
> vector:  Ok, I'll take the M objects.

Hmmm... doesn't sound like a very natural way of doing things, but I guess
it's the most efficient.

> Allocator deals with raw memory, period.  vector (or buffer) deals with
> a dynamically sized array of homogenous objects.
> Only vector has
> enough information to decide how much memory to request, and how much
> (in place) memory expansion is acceptable before starting to move
> objects around.  And only vector is qualified to decide /how/ to move
> those objects around if it needs to.  Are the proper semantics assign?
> Move?  Swap?  What exception safety guarantees are appropriate for this
> particlular expansion?  insert generally (but not universally) requires
> basic.  push_back requires strong.  Build all that into allocator and
> you've got another vector on your hands!

Well, on second thought, I agree. I even start to like the expansion
procedure, but in my opinion it should be one-step. If it's not, problems
can appear in multithreaded environments. That's because between the time
the allocator tells you how much memory it has at the end of the current
block and the moment you grab that block, another thread can get that
memory.

So I think the right API is just an expand function that either succeeds or
fails, and that's it. (By the way, I have a draft article on typed buffers.
If anyone would be interested in reviewing it, please write me email.)

> It would be great to build expand into allocator.  I'm all for it.  But
> not realloc.  realloc is vector's job.  allocator::expand needs to not
> only tell vector whether or not it can expand to the requested size,
> but if it can't, how much it could expand to.  vector can decide
> whether the available expansion size is acceptable or not.  If moving
> objects has to take place, that needs to happen at a level above
> allocator.  Because no one strategy for moving objects fits all.

Oui.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar
---
[ 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.research.att.com/~austern/csc/faq.html                ]

"Howard Hinnant" <hinnant@antispam.metrowerks.com> wrote in message
news:040620012107367859%hinnant@antispam.metrowerks.com...
> I've been lurking on this thread quite a while, probably too long.
> Imho a moving reallocation is not appropriate in an allocator, no
> matter the underlying memory management architechture.  It is vector's
> (or buffer's or whatever) job to decide on the stategy to increase
> capacity.  Allocator's only role is to manage raw memory, nothing more.

I just sent another post in answer to yours agreeing with your points, but I
just remembered of the killer argument in favor of including reallocate()
right in the allocators.

If you include reallocate() in allocators, you can implement it in terms of
std::realloc() for malloc-based allocators for primitive and POD types on
any system. If you don't include it, you need special co-operation from the
system.

I plan to define allocator traits which will gauge the level of interface
supported by an allocator. For the sake of being able to measure performance
today, I will have to support reallocation in allocators.

By the way Howard, I'm just perusing MSL online help. No expand in there.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar
---
[ 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.research.att.com/~austern/csc/faq.html                ]

> It would be great to build expand into allocator.  I'm all for it.  But
> not realloc.  realloc is vector's job.  allocator::expand needs to not
> only tell vector whether or not it can expand to the requested size,
> but if it can't, how much it could expand to.  vector can decide
> whether the available expansion size is acceptable or not.  If moving
> objects has to take place, that needs to happen at a level above
> allocator.  Because no one strategy for moving objects fits all.

Yes but we have two things on our hands not one.

1. Should there be builtin reallocation operators that works with
new[]/delete[] or we we talking about adding to various containers
allocators interface?
2. Now that we have vector, why should new[] ever be used? A few days ago I
noticed on my 32-bit implementation that sizeof(vector) was 16 bytes where a
point occupies 4 bytes. So new[] is space-saving and ideal if you are not
using any of vectors capabilities.

Stephen Howe



      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

NOSPAMsjhowe@dial.pipex.com (Stephen Howe) wrote (abridged):
> > Hmmm. As I understand it, there are two ways in which more memory
> > may be available. The first is because of dynamic considerations.
> > [...]
>
> That not the only option. There are 2 more.

Yes, although both are dynamic. (Also both involve copying the data,
which cannot be done correctly without knowing about type.) Mainly I was
wondering here whether the static versus dynamic distinction is useful,
so I lumped all the ways in which more memory can become available during
the lifetime of the block under "dynamic".


> For a system that was say a ROM application, this could be
> the difference between life and death.

I was concerned about dynamic resizing because it seemed heavily
dependant on the patterns of memory allocation through-out the code and
history. As such it is hard to reason about locally. Although we might
occasionally get lucky and have a resizable block, to rely on this for
life-critical performance guarantees seemed like bad engineering.

Currently I am thinking it is maybe not so bad. Especially if we are
doing funky things with allocators. Eg, perhaps a critical vector is the
only one to use a specific allocator (for some region of the code). The
patterns of use of the other allocators will be irrelevant, so we can get
some local guarantees. This could be good engineering.

Since we are stuck with allocators, I favour getting as much milage out
of them as we can. A simple FIFO allocator could work well with
allocator::expand().

The resizing might be more reliable if it worked the other way about -
shrinking rather than enlarging. Allocate a large block to begin with,
use as much as we need, then return the excess. Currently the STD is not
conducive to this way of working. There isn't even a guaranteed way of
shrinking a std::vector *with* copying. Pre-allocating the space, and
then shrinking, could give local guarantees of no copying. We still need
to enlarge, of course, when we don't know a good upper bound on the size
in advance, but the function should probably be called resize() rather
than expand().

The API for this stuff needs to be carefully designed so that it can be
effectively supported by a wide range of allocators with minimal extra
bookkeeping. That was one advantage of my pair<void *,size_t> proposal
(which I still think is a good idea, by the way, even if we do this other
stuff as well).

For example, Microsoft's _expand is not given the old size of the block.
That is fine for their scheme which tracks sizes itself, but would mean
some extra overhead for other allocation schemes. Incidently, their
_expand is a global function, which I don't think we need. We don't need
resize for memory blocks got via operator new(), because the size of
non-array objects is constant. I suspect we don't need it for operator
new[](), either. People should be encouraged to use std::vector instead
(or perhaps Andrei's lower-level Buffer class). So I think we are only
talking about allocator objects.

To put it another way, allocator objects are in many ways a nicer
interface than operator new() and operator delete(). This is partly
because they are more explicit in how they group the operations. People
are less likely to provide an allocator::allocate() and forget to provide
the corresponding allocator::deallocate() because they are in the same
object. The allocator::construct() function is clearer than placement
new. We can pass allocators around as arguments more easily than we can
pass operator new().

Thus instead of providing global functions like _expand(), perhaps we
should add allocator::expand and then provide an allocator which
represents the memory which underlies operator new[]().

Memory in C++ is really quite diverse. We have malloc(), global operator
new(), class-specific operator new(), global/class operator new[](), and
allocators. All of them have their corresponding delete operations which
must not be mixed up. They all have slightly different functionality, and
when the functionality is the same it is presented with a different API.
Can we consolidate all this? Have allocators which causally reflect each
type of memory?

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."
---
[ 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.research.att.com/~austern/csc/faq.html                ]

>
> 1) primitive raw new_resize
>
> operator new_resize[] will work similarly to _expand as discussed here. It
> will know the size of any array of objects (just like delete[] does). It's
> job is to expand or contract a block of memory, insitu, that is all.
Unlike
> realloc(), it _NEVER_ acquires a different block. It will guaranteed by
the
> ISO C++ standard > operator nthat contracting will never throw an
exception and will
> always succeed. In contrast, on expansion, if it cannot expand the block,
an
> exception is thrown (*).

BTW, why should we _NEVER_ acquire different memory block ?
if we were to allow aquisition different block, we can then write a new
operator that
uses malloc, and a new_resize that uses realloc.



      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On 31 May 2001 16:53:36 -0400, Pete Becker <petebecker@acm.org> wrote:

>Dave Harris wrote:
>>
>> In fact, I thought the good allocators
>> used separate pools of fixed-sized blocks nowadays. These could never
>> co-opt following blocks. Are we changing the API to support poor
>> allocators?
>>
>
>Caching allocated blocks in same-sized free lists provides faster
>steady-state allocations at the cost of locking up otherwise usable
>memory when allocation patterns and sizes change. Memory management
>strategies don't lend themselves to labels like "good" and "poor." The
>choice of an appropriate memory management strategy depends on an
>application's pattern of memory usage. Caching allocators are often a
>good choice, but that doesn't make them inherently superior to other
>approaches.
>
>So I'd phrase the issue the other way around: should the standard
>preclude optimizing memory management strategies for less common memory
>usage patterns? Stated that way, the answer is obvious. <g>
>
I'm wondering what the impact of 64-bit architectures with LAAARGE
virtual address spaces will be on this. E.g., will a pool of virtual
1GB blocks of address space be practical? Not necessarily as
separate translation table entries. You could have a single large
virtual writable data space, or as few as convenient.

IOW, will it be feasible to pre-allocate max virtual space for
pretty much any reasonable expandable item and let page faults plug
in the physical pages transparently to the program as needed?

Thus no "actual" dynamic expanding within the program at all, just
apparent, faking dynamic size limit states etc. to enforce as-if
semantics where appropriate.

I'd guess you'd want the option of being notified by the OS when it
allocated a physical page the first time for a page in the virtual
data space, so that you could monitor for what might otherwise be a
GPF in an incorrect program. Just a curious thought.

I take it that a design should not preclude such possibilities, even
if they only occurred in libraries for special platforms. But how to
specify max expansion without apparently reserving it? (So the same
code could run on a 32-bit platform, or if GB blocks are expensive
compared to MB, and you want to be able to allocate blocks smaller
than global worst case expansion would require).

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On 04 Jun 01 05:52:13 GMT, Sebastien Hitier <sebapi747@hotmail.com> wrote:
> >
> > 1) primitive raw new_resize
> >
> > operator new_resize[] will work similarly to _expand as discussed
> > here. It will know the size of any array of objects (just like
> > delete[] does). It's job is to expand or contract a block of memory,
> > insitu, that is all. Unlike realloc(), it _NEVER_ acquires a
> > different block. It will guaranteed by the ISO C++ standard >
> > operator nthat contracting will never throw an exception and will
> > always succeed. In contrast, on expansion, if it cannot expand the
> > block, an exception is thrown (*).
>
> BTW, why should we _NEVER_ acquire different memory block ?
> if we were to allow aquisition different block, we can then write a
> new operator that uses malloc, and a new_resize that uses realloc.

The point of _expand()-like facilities is to let programs behave
differently depending on whether in-place expansion is possible or not.
For example, if in-place expansion of a vector for 5 new elements is not
possible so that one has to fall back to aquiring a new memory block,
one might want the new memory block to be not just 5 elements larger,
but significantly more (for example double its size), to prevent another
reallocation if a further elements are to be appended. In the other
situation where in-place expansion is possible, enlarging the block just
by the 5 elements needed now is fine.

A more concrete example is a stack implemented by a linked list of
memory blocks that each contain a chunk of the stack (i.e. a linked list
of arrays of stack elements). This is an approach that has the combined
benefit of preventing copying (as would be the case with vector), having
less frequent memory allocations and low memory overhead (as opposed to
a linked list implementation where each stack element gets its own
node). Such a data structure could significantly benefit from an
expand() (preferably together with some shrink()) facility to expand the
top block on stack growth instead of allocating a new one (with some
extra capacity). A FIFO queue could similarly be implemented.
(This is not to argue that the benefit would be a dramatic one, but
there certainly is one.)

-- 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.research.att.com/~austern/csc/faq.html                ]

andrewalex@hotmail.com (Andrei Alexandrescu) wrote (abridged):
> memory allocation in C++ is fundamentally warped because its
> ancestor (and historical back-end), the C heap allocator, lacks
> an appropriate primitive that reallocates a block of memory without
> moving it in memory.
>
> So I wanted to ask whether there is any support in the C++ community to
> standardize efficient reallocation.

Hmmm. As I understand it, there are two ways in which more memory may be
available. The first is because of dynamic considerations. The block
happens to be immediately followed by another free block, which can be
co-opted. How much memory is available in this way will vary during the
lifetime of the block.

I imagine this is fairly rare. In fact, I thought the good allocators
used separate pools of fixed-sized blocks nowadays. These could never
co-opt following blocks. Are we changing the API to support poor
allocators?

The second way is because of static considerations. The memory is
available because the allocator has rounded the block size up somehow.
The extra memory is effectively already owned by the caller - no other
allocation can use it - but the caller is not aware of it. The size of
this extra will not vary over the lifetime of the block. (That's what I
mean by "static" here.)

I imagine this is pretty common. Many allocators round up: for alignment
reasons, to fit the size of a fixed-size pool, or because they need a
minimum size to store their own book-keeping when the block is freed.

It would be nice if we could have a block_size() function which returned
the actual allocated size of a memory block, and which could be called at
any time. However, this would add overhead for allocation schemes which
don't otherwise need to store the size, eg fifo/alloca()-like schemes, or
arena-based schemes which free the entire arena at once.

So instead we can require the true size to be available only when the
block is just created. Eg a function like:

    std::pair<void *, size_t> alloc( size_t sz );

which returns both a pointer to the block and the maximum size which the
caller may use. The size would either be 0, or >= the requested size. I
believe every allocation strategy should be able to support this, if only
by returning 'sz', eg:

    std::pair<void *, size_t> alloc( size_t sz ) {
        void *p = malloc( sz );
        if (p == 0)
            return std::pair<void *, size_t>( 0, 0 );
        else
            return std::pair<void *, size_t>( p, sz );
    }

(This version returns 0 on failure; obviously it could throw an exception
instead. As this is a low-level function, I suspect programmers using it
would rather not have the exception. But this is a side-issue; I don't
really care either way myself.)

Clearly this is not the same as your arbitrary resize request. It only
helps at allocation time. Still, I think that covers the majority of
cases in which extra memory is likely to be available, and it does make
it easier to implement efficiently across a wide range of allocation
strategies.

Nor is it quite the same as Luis Pedro Coelho's capacity() suggestion.
His function can be called at any time, and includes dynamically
available memory. He writes:

> Consider a std::vector v. Let's say v.capacity() == v.size(). Now we
> do v.push_back(T()). The normal thing for vector to do is to
> double it's capacity (to keep push_back O(1) amortized). There
> is however the possibility that the current block of memory could
> allow a couple more elements but not double the number of elements.
> Having a function indicate exactly how many element fit in the
> current block would avoid unnecessary movement of elements in this
> case.

I am thinking along similar lines, except that I would set v.capacity()
to the true size as soon as the previous allocation was done. Thus if a
couple more elements were available, we would have
v.capacity()==v.size()+2 and the resize logic would not be invoked for
another two push_back()s. This seems more natural to me.


I'll now play devil's advocate and argue against suggestions of this
sort, including my own.

How many modules actually need resizing memory blocks? It seems to me,
only 1, namely std::vector. Any other modules should surely be defined in
terms of std::vector. And std::vector is part of the implementation, as
is std:allocator. As far as I know, a vendor is allowed to write a
version of std::vector specialised for std::allocator which talks
directly to the underlying heap. Thus the advantages of any fancy memory
API can be got anyway. There is no need to change the standard.

A less extreme implementation of std::vector could replicate the
underlying heap's round-up logic and request that much memory to start
with. This would not need a hidden API, nor even a specialised
std::vector (although in that case it would risk over-allocating when
some other allocator was used, if it had a different round-up policy).


> In thinking on how to write YASTLI so that it is as efficient as it
> gets, I stumbled again upon memory allocation.

Quite so. Is this the right way to go? The STL is supposed to be part of
the implementation provided by vendors, not implemented by 3rd parties.
It seems to me this is a feature request which is not needed by the
vendor (because they can hack it behind the scenes), nor by users
(because they can use the nice vendor-optimised std::vector).

Features only needed to implement the STL efficiently don't need to be
part of the standard.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Andrei Alexandrescu <andrewalex@hotmail.com> wrote in message
news:9ehbrn$2tr29$1@ID-14036.news.dfncis.de...
> I guess I got this efficiency streak, but if C++ 0x is anything about
> efficiency, I guess the following would be of interest.

(Digression: Good book, still devouring it on the train journey between home
and work :-) ).

I have thought about this for sometime (as I have thought about efficiency
and other matters concerning the standard library). You talk about _expand
but I would want shrinkage as well. See what I propose below:

IMO, what is required is a

operator new_resize() and new_resize.

So C++ would wind up with.

new (single object)
new[] (array objects)
new_resize[] (array objects)

and primitive raw memory operators

operator new
operator new[]
operator new_resize[]

Now a word on the primitive raw new_resize and then a word on the built in
new_resize.

1) primitive raw new_resize

operator new_resize[] will work similarly to _expand as discussed here. It
will know the size of any array of objects (just like delete[] does). It's
job is to expand or contract a block of memory, insitu, that is all. Unlike
realloc(), it _NEVER_ acquires a different block. It will guaranteed by the
ISO C++ standard that contracting will never throw an exception and will
always succeed. In contrast, on expansion, if it cannot expand the block, an
exception is thrown (*).
operator new_resize[] will work with boundary conditions as well. If the raw
pointer is null, is is equavalent to using operator new []. If the new size
is 0, it is equivalent to calling operator delete [].
If operator new_resize succeeds, the number of elements is recorded.

2)  Builtin new_resize

If you have a valid pointer to an array of objects and you call new_resize
with a size, then new_resize operator will do one of three things:

i) If the new size is the same as the old size then it does nothing.

ii) If the new size is less than the old size, then the destructors for the
objects are called in reverse order and then the primitive operator
new_resize which as mentioned above, is guaranteed to resize the block.

iii) If the new size is greater than the old size, this is where it gets
interesting. Operator new_resize is called. If it succeeds then the default
constructor is called for the balance of objects outstanding. If it fails,
then new is called. If that fails, std:: bad_alloc() is thrown, otherwise,
the copy constructor is called for existing objects, default constructor for
new objects, delete []  is applied to the old array and the new array is
returned.

By divorcing  new_resize from operator new_resize, you retain control.
operator new_resize[], just like operator new[] can be overridden globally
and on a class-specific basis.

(*) This is tricky and needs thinking about. The chances are operator
new_resize[] will fail often to expand the block. Should an exception be
thrown or not? For performance reasons, it might be better if it did not.
For compatability reasons with operator new[], it might be better if it did.

Stephen Howe




      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

"Dave Harris" <brangdon@cix.co.uk> wrote in message
news:memo.20010529184025.31511B@brangdon.madasafish.com...
> andrewalex@hotmail.com (Andrei Alexandrescu) wrote (abridged):
> > memory allocation in C++ is fundamentally warped because its
> > ancestor (and historical back-end), the C heap allocator, lacks
> > an appropriate primitive that reallocates a block of memory without
> > moving it in memory.
> >
> > So I wanted to ask whether there is any support in the C++ community to
> > standardize efficient reallocation.
>
> Hmmm. As I understand it, there are two ways in which more memory may be
> available. The first is because of dynamic considerations. The block
> happens to be immediately followed by another free block, which can be
> co-opted. How much memory is available in this way will vary during the
> lifetime of the block.
>
> I imagine this is fairly rare. In fact, I thought the good allocators
> used separate pools of fixed-sized blocks nowadays. These could never
> co-opt following blocks. Are we changing the API to support poor
> allocators?
>
> The second way is because of static considerations. The memory is
> available because the allocator has rounded the block size up somehow.
> The extra memory is effectively already owned by the caller - no other
> allocation can use it - but the caller is not aware of it. The size of
> this extra will not vary over the lifetime of the block. (That's what I
> mean by "static" here.)
>
> I imagine this is pretty common. Many allocators round up: for alignment
> reasons, to fit the size of a fixed-size pool, or because they need a
> minimum size to store their own book-keeping when the block is freed.
>
> It would be nice if we could have a block_size() function which returned
> the actual allocated size of a memory block, and which could be called at
> any time. However, this would add overhead for allocation schemes which
> don't otherwise need to store the size, eg fifo/alloca()-like schemes, or
> arena-based schemes which free the entire arena at once.
>
> So instead we can require the true size to be available only when the
> block is just created. Eg a function like:
>
>     std::pair<void *, size_t> alloc( size_t sz );
>
> which returns both a pointer to the block and the maximum size which the
> caller may use. The size would either be 0, or >= the requested size. I
> believe every allocation strategy should be able to support this, if only
> by returning 'sz', eg:
>
>     std::pair<void *, size_t> alloc( size_t sz ) {
>         void *p = malloc( sz );
>         if (p == 0)
>             return std::pair<void *, size_t>( 0, 0 );
>         else
>             return std::pair<void *, size_t>( p, sz );
>     }
>
> (This version returns 0 on failure; obviously it could throw an exception
> instead. As this is a low-level function, I suspect programmers using it
> would rather not have the exception. But this is a side-issue; I don't
> really care either way myself.)
>
> Clearly this is not the same as your arbitrary resize request. It only
> helps at allocation time. Still, I think that covers the majority of
> cases in which extra memory is likely to be available, and it does make
> it easier to implement efficiently across a wide range of allocation
> strategies.
>
> Nor is it quite the same as Luis Pedro Coelho's capacity() suggestion.
> His function can be called at any time, and includes dynamically
> available memory. He writes:
>
> > Consider a std::vector v. Let's say v.capacity() == v.size(). Now we
> > do v.push_back(T()). The normal thing for vector to do is to
> > double it's capacity (to keep push_back O(1) amortized). There
> > is however the possibility that the current block of memory could
> > allow a couple more elements but not double the number of elements.
> > Having a function indicate exactly how many element fit in the
> > current block would avoid unnecessary movement of elements in this
> > case.
>
> I am thinking along similar lines, except that I would set v.capacity()
> to the true size as soon as the previous allocation was done. Thus if a
> couple more elements were available, we would have
> v.capacity()==v.size()+2 and the resize logic would not be invoked for
> another two push_back()s. This seems more natural to me.
>
>
> I'll now play devil's advocate and argue against suggestions of this
> sort, including my own.
>
> How many modules actually need resizing memory blocks? It seems to me,
> only 1, namely std::vector. Any other modules should surely be defined in
> terms of std::vector. And std::vector is part of the implementation, as
> is std:allocator. As far as I know, a vendor is allowed to write a
> version of std::vector specialised for std::allocator which talks
> directly to the underlying heap. Thus the advantages of any fancy memory
> API can be got anyway. There is no need to change the standard.
>
> A less extreme implementation of std::vector could replicate the
> underlying heap's round-up logic and request that much memory to start
> with. This would not need a hidden API, nor even a specialised
> std::vector (although in that case it would risk over-allocating when
> some other allocator was used, if it had a different round-up policy).
>
>
> > In thinking on how to write YASTLI so that it is as efficient as it
> > gets, I stumbled again upon memory allocation.
>
> Quite so. Is this the right way to go? The STL is supposed to be part of
> the implementation provided by vendors, not implemented by 3rd parties.
> It seems to me this is a feature request which is not needed by the
> vendor (because they can hack it behind the scenes), nor by users
> (because they can use the nice vendor-optimised std::vector).
>

But do we want the memory allocation strategy of std::vector to suffer a
huge hit because the user writes her own allocator, even if it uses
_exactly_ the same strategy as std::allocator (e.g. by deferring to a
contained std::allocator instance)?

As I understand it, part of the idea behind the standard library is that all
the parts are essentially independent, aside from specializations. However,
though I can specialize e.g. std::sort to work efficiently for my new
iterators into my new container, because the _algorithm_ for sorting needs
to change, it is a lot of work to specialize std::vector for my custom
allocator, just because the implementation has access to hidden parts of
std::allocator, which I thus cannot replicate.

> Features only needed to implement the STL efficiently don't need to be
> part of the standard.

AFAIK, some features of the core C++ language were only added to facilitate
implementing the STL.

Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optoelectronics
The opinions expressed in this message are not necessarily those of my
employer
---
[ 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.research.att.com/~austern/csc/faq.html                ]

Dave Harris wrote:
>
> In fact, I thought the good allocators
> used separate pools of fixed-sized blocks nowadays. These could never
> co-opt following blocks. Are we changing the API to support poor
> allocators?
>

Caching allocated blocks in same-sized free lists provides faster
steady-state allocations at the cost of locking up otherwise usable
memory when allocation patterns and sizes change. Memory management
strategies don't lend themselves to labels like "good" and "poor." The
choice of an appropriate memory management strategy depends on an
application's pattern of memory usage. Caching allocators are often a
good choice, but that doesn't make them inherently superior to other
approaches.

So I'd phrase the issue the other way around: should the standard
preclude optimizing memory management strategies for less common memory
usage patterns? Stated that way, the answer is obvious. <g>

--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.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.research.att.com/~austern/csc/faq.html                ]

"Pete Becker" <petebecker@acm.org> wrote in message
news:3B1639AF.7ECF3741@acm.org...
> Dave Harris wrote:
> >
> > In fact, I thought the good allocators
> > used separate pools of fixed-sized blocks nowadays. These could never
> > co-opt following blocks. Are we changing the API to support poor
> > allocators?
> >
>
> Caching allocated blocks in same-sized free lists provides faster
> steady-state allocations at the cost of locking up otherwise usable
> memory when allocation patterns and sizes change. Memory management
> strategies don't lend themselves to labels like "good" and "poor." The
> choice of an appropriate memory management strategy depends on an
> application's pattern of memory usage. Caching allocators are often a
> good choice, but that doesn't make them inherently superior to other
> approaches.

Makes a lot of sense.

> So I'd phrase the issue the other way around: should the standard
> preclude optimizing memory management strategies for less common memory
> usage patterns? Stated that way, the answer is obvious. <g>

I'm not sure I understand. So, basically, do you think expand could be good
or bad? I mean, it can't be bad because an implementation is allowed to
always return 0 (no room), but do you think there is potential for
performance improvements if allocators supported expansion?


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar




      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

"Dave Harris" <brangdon@cix.co.uk> wrote in message
news:memo.20010529184025.31511B@brangdon.madasafish.com...
> andrewalex@hotmail.com (Andrei Alexandrescu) wrote (abridged):
> > memory allocation in C++ is fundamentally warped because its
> > ancestor (and historical back-end), the C heap allocator, lacks
> > an appropriate primitive that reallocates a block of memory without
> > moving it in memory.
> >
> > So I wanted to ask whether there is any support in the C++ community to
> > standardize efficient reallocation.
>
> Hmmm. As I understand it, there are two ways in which more memory may be
> available. The first is because of dynamic considerations. The block
> happens to be immediately followed by another free block, which can be
> co-opted. How much memory is available in this way will vary during the
> lifetime of the block.

That not the only option. There are 2 more.

1) It could be that the block before the current block is free and is
sufficient. With C++ objects, providing they were the right size, you could
invoke copy constructors and destructors in pairs (or a memmove() if builtin
types) and move the array backwards. For a system that was say a ROM
application, this could be the difference between life and death.

2) It could be that the block before the current block is free and is
insufficient and block after is free and also insufficient but combined is
enough. Again, moving the array backwards, reclaiming the free memory means
you have done reallocation.

>From the C library source code I have seen, most reallocs() tryo to expand
the current block and if that fails they allocate a bigger block, copy and
free the old block.

Stephen Howe



      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Andrei Alexandrescu wrote:
>
> "Pete Becker" <petebecker@acm.org> wrote in message
> news:3B1639AF.7ECF3741@acm.org...
> > So I'd phrase the issue the other way around: should the standard
> > preclude optimizing memory management strategies for less common memory
> > usage patterns? Stated that way, the answer is obvious. <g>
>
> I'm not sure I understand. So, basically, do you think expand could be good
> or bad? I mean, it can't be bad because an implementation is allowed to
> always return 0 (no room), but do you think there is potential for
> performance improvements if allocators supported expansion?
>

I think _expand could be useful. I'm undecided on whether it should be
added.

--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.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.research.att.com/~austern/csc/faq.html                ]

> > andrewalex@hotmail.com (Andrei Alexandrescu) wrote (abridged):
> > > memory allocation in C++ is fundamentally warped because its
> > > ancestor (and historical back-end), the C heap allocator, lacks
> > > an appropriate primitive that reallocates a block of memory without
> > > moving it in memory.
> > >
> > > So I wanted to ask whether there is any support in the C++ community to
> > > standardize efficient reallocation.

> "Dave Harris" <brangdon@cix.co.uk> wrote
> > Hmmm. As I understand it, there are two ways in which more memory may be
> > available. The first is because of dynamic considerations. The block
> > happens to be immediately followed by another free block, which can be
> > co-opted. How much memory is available in this way will vary during the
> > lifetime of the block.

"Stephen Howe" <NOSPAMsjhowe@dial.pipex.com> wrote:
> That not the only option. There are 2 more.
>
> 1) It could be that the block before the current block is free and is
> sufficient. With C++ objects, providing they were the right size, you could
> invoke copy constructors and destructors in pairs (or a memmove() if builtin
> types) and move the array backwards. For a system that was say a ROM
> application, this could be the difference between life and death.
>
> 2) It could be that the block before the current block is free and is
> insufficient and block after is free and also insufficient but combined is
> enough. Again, moving the array backwards, reclaiming the free memory means
> you have done reallocation.
>
> >From the C library source code I have seen, most reallocs() tryo to expand
> the current block and if that fails they allocate a bigger block, copy and
> free the old block.

Dave meant that there are only two ways that more memory could be
allocated to the block without requiring the data to be moved to
a new address, which could cause problems. Both of your options do
involve changing the base address of the data.

----
allan_w@my-dejanews.com is a "Spam Magnet" and replies will not be
read. Please reply in newsgroups only. Sorry!
---
[ 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.research.att.com/~austern/csc/faq.html                ]

"Stephen Howe" <NOSPAMsjhowe@dial.pipex.com> wrote in message news:<3b17090d$0$12243$cc9e4d1f@news.dial.pipex.com>...
> "Dave Harris" <brangdon@cix.co.uk> wrote in message
> news:memo.20010529184025.31511B@brangdon.madasafish.com...
> > andrewalex@hotmail.com (Andrei Alexandrescu) wrote (abridged):
> > > memory allocation in C++ is fundamentally warped because its
> > > ancestor (and historical back-end), the C heap allocator, lacks
> > > an appropriate primitive that reallocates a block of memory without
> > > moving it in memory.
> > >
> > > So I wanted to ask whether there is any support in the C++ community to
> > > standardize efficient reallocation.
> >
> > Hmmm. As I understand it, there are two ways in which more memory may be
> > available. The first is because of dynamic considerations. The block
> > happens to be immediately followed by another free block, which can be
> > co-opted. How much memory is available in this way will vary during the
> > lifetime of the block.
>
> That not the only option. There are 2 more.
>
> 1) It could be that the block before the current block is free and is
> sufficient. With C++ objects, providing they were the right size, you could
> invoke copy constructors and destructors in pairs (or a memmove() if builtin
> types) and move the array backwards. For a system that was say a ROM
> application, this could be the difference between life and death.

This does not meet the requirements for _expand, namely that the block
is resized in place. If the block cannot be resized without moving it,
_expand must do nothing and return NULL.

The point is that _expand (or renew, or std::allocator::expand, or
whatever we choose to call this thing) deals only with raw memory and
therefore does not know how to copy objects.

> 2) It could be that the block before the current block is free and is
> insufficient and block after is free and also insufficient but combined is
> enough. Again, moving the array backwards, reclaiming the free memory means
> you have done reallocation.

Same as above. If copying is involved then you're talking about something
else besides the simple, low-level _expand function under discussion.

> From the C library source code I have seen, most reallocs() tryo to expand
> the current block and if that fails they allocate a bigger block, copy and
> free the old block.

Dave has argued that expanding a block in place would rarely (never?)
be possible with most "good" modern allocators, since they use separate
memory pools for different sized blocks. Apparently at least some
implementors of realloc() disagree with this claim.

I'm not an expert on memory allocation strategies, but I suspect that even
with a multiple-free-list algorithm, it might still be possible to merge
adjacent blocks.
---
[ 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.research.att.com/~austern/csc/faq.html                ]

On 01 Jun 01 14:58:20 GMT, Andrei Alexandrescu <andrewalex@hotmail.com> wrote:
> "Pete Becker" <petebecker@acm.org> wrote in message
> news:3B1639AF.7ECF3741@acm.org...
> > Dave Harris wrote:
> > >
> > > In fact, I thought the good allocators used separate pools of
> > > fixed-sized blocks nowadays. These could never co-opt following
> > > blocks. Are we changing the API to support poor allocators?
> >
> > Caching allocated blocks in same-sized free lists provides faster
> > steady-state allocations at the cost of locking up otherwise usable
> > memory when allocation patterns and sizes change. Memory management
> > strategies don't lend themselves to labels like "good" and "poor." The
> > choice of an appropriate memory management strategy depends on an
> > application's pattern of memory usage. Caching allocators are often a
> > good choice, but that doesn't make them inherently superior to other
> > approaches.
>
> Makes a lot of sense.
>
> > So I'd phrase the issue the other way around: should the standard
> > preclude optimizing memory management strategies for less common
> > memory usage patterns? Stated that way, the answer is obvious. <g>
>
> I'm not sure I understand. So, basically, do you think expand could be
> good or bad? I mean, it can't be bad because an implementation is
> allowed to always return 0 (no room), but do you think there is
> potential for performance improvements if allocators supported
> expansion?

I'm not Pete Becker, but one conceivable situation is where a vector is
created and used in a stack-like fashion, and where for the duration of
that usage, no other heap allocations take place (or at least happen to
not significantly affect the free space behind the vector's storage).

Without expand(), the vector is copied each time its implementation
decides that it has to grow. With expand(), it only needs to be copied
if the free space following the vector becomes too small. It is quite
likely that the free space becoming to small is not always the case, but
only for some of the resizings, and in the best case for none of them.

In such situations (regardless of how likely they are), expand() clearly
provides potential for performance improvements (regardless of how
significant these improvements might be for a particular application).

-- 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.research.att.com/~austern/csc/faq.html                ]

Maciej Sobczak wrote:
...
> such a platform, but... realloc calls for flat memory model at least for the
> free store. I wouldn't die for it, but this is how I understand the way
> realloc would be implemented. From the point of view of the Standard, it
> would be too much of a constraint, so it's not there.

It's not too much of a constraint, and it is there. See section 20.1.4
of the standard; you can find std::realloc() in <cstdlib>.

A more real problem is that the standard's allocator requirements don't
include a reallocate() function. There's also no way to get the
equivalent functionality for arrays allocated with 'new'. That second
feature is not truly independent; if reallocate() were added to the
allocator requirements, then std::allocator<T>::reallocate() would be
useable on arrays of type T allocated with 'new'.
---
[ 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.research.att.com/~austern/csc/faq.html                ]

"Luis Pedro Coelho" <deepblack@geocities.com> wrote:
> I do not know the interface of _expand, but I think a fitting interface
> could be:
>
> std::size_t capacity(const void*);
>
> This would return the full capacity available for that pointer.

I don't think this would work, because more memory could be allocated
between calling capacity() and trying to resize the block, for example:

char *x = new char[20];
std::size_t cap = capacity(x); // maybe x is at the end of the heap, so
returns several 100MBs
char *y = new char[20]; // allocated immediately after x, previous capacity
of x now invalid

Or have I misunderstood your proposal?

Regards,

--
Edwin Young


---
[ 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.research.att.com/~austern/csc/faq.html                ]

Chris Uzdavinis wrote:

>  Perhaps there is an academic reason (E.G. "not all platforms support
> it, so it's impossible to write a standard-compliant C++ compiler for
> those platforms") but perhaps there are workarounds or concessions
> that could still be made.  In any case, it's worth a few minutes worth
> of discussion.

This is not a good  reason. The function which Andrei is asking for is a
question: How much more memory can I use in this block? A conforming
implementation could be one which alway replied none.

I do not know the interface of _expand, but I think a fitting interface
could be:

std::size_t capacity(const void*);

This would return the full capacity available for that pointer. A simple
implementation would simply return what was previously asked for, or maybe
a zero return could be used to indicate that the memory available is
exactly what was asked for previously. The behaviour of calling this on a
pointer not obtained through null is undefined.

IMHO, this is better than a half-realloc, because if we had a function like

bool half_realloc(const void*, std::size_t);

which returned true if there is more memory available, there are some
possibilities which would be negleted. Consider a std::vector v. Let's say
v.capacity() == v.size(). Now we do v.push_back(T()). The normal thing for
vector to do is to double it's capacity (to keep push_back O(1) amortized).
There is however the possibility that the current block of memory could
allow a couple more elements but not double the number of elements. Having
a function indicate exactly how many element fit in the current block would
avoid unnecessary movement of elements in this case.

I am assuming here that this functionallaty would go both in the global
operator new and in the allocator interface.


Regards,
--
Luis Pedro Coelho.

Check out my game of Hearts, a card game, for KDE at:
http://www.geocities.com/deepblack9/index.html


      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

"Chris Uzdavinis" <chris@atdesk.com> wrote in message
news:j6elte5qvp.fsf@explicit.atdesk.com...
> Currently, it seems that this issue is just kind of swept under the
> rug.  When asked by people from other languages why C++ doesn't have a
> realloc-like function, the answer usually resembles "... because."
>
> Sometimes some vague qualifications are thrown in " ... because it
> really complicates some things."  Of course, 'some things' is never
> quite defined, and it's usually just dropped at that.

The article at:

http://gethelp.devx.com/techtips/cpp_pro/10min/2001/may/10min0501.asp

considers the problem a given but... presents std::vector as the solution!

>  Perhaps there is an academic reason (E.G. "not all platforms support
> it, so it's impossible to write a standard-compliant C++ compiler for
> those platforms") but perhaps there are workarounds or concessions
> that could still be made.  In any case, it's worth a few minutes worth
> of discussion.

There is no serious reason. Most platforms do support in-place expansion of
dynamically-allocated memory. Platforms that don't support it can just
always return 0 from expand, case in which you take the
alloc-copy-destroy-dealloc route.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar
---
[ 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.research.att.com/~austern/csc/faq.html                ]

Hi,

My thought:
The Standard is quite specific in the place where it says that somparing
pointers is allowed only for pointers pointing into the same object or the
same array (plus past-the-end) (yeah, I know that less<T*> is defined). I
was wandering why. On any platform with the flat memory model, we have
pointer comparisons for granted, so - the problem is with platforms without
this model. I can imagine the hardware so heavily segmented, that every
object and array on the free store is in the distinct segment (on the
hardware level). The Standard would be still possible to get implemented on
such a platform, but... realloc calls for flat memory model at least for the
free store. I wouldn't die for it, but this is how I understand the way
realloc would be implemented. From the point of view of the Standard, it
would be too much of a constraint, so it's not there.

However, the battle is not lost for me. On 99% platforms, realloc would be
implemented without any serious hacking - it's probably already there, with
the C memory manager. What about that 1% left? There, realloc is still
implementable - just always behaves like the normal realloc faced with no
place behind the given block: it allocates new block, copies memory and then
frees the old block, or complains, or something.

Maciej Sobczak, http://www.cern.ch/Maciej.Sobczak
"in theory, there is no difference between theory and practice - but in
practice, there is"




      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On 27 May 01 10:54:54 GMT, Luis Pedro Coelho <deepblack@geocities.com> wr=
ote:
[=B7=B7=B7]
> I do not know the interface of _expand, but I think a fitting interface=
=20
> could be:
>=20
> std::size_t capacity(const void*);
>=20
> This would return the full capacity available for that pointer. A simpl=
e=20
> implementation would simply return what was previously asked for, or ma=
ybe=20
> a zero return could be used to indicate that the memory available is=20
> exactly what was asked for previously. The behaviour of calling this on=
 a=20
> pointer not obtained through null is undefined.
>=20
> IMHO, this is better than a half-realloc, because if we had a function =
like
>=20
> bool half_realloc(const void*, std::size_t);
>=20
> which returned true if there is more memory available, there are some=20
> possibilities which would be negleted. Consider a std::vector v. Let's =
say=20
> v.capacity() =3D=3D v.size(). Now we do v.push_back(T()). The normal th=
ing for=20
> vector to do is to double it's capacity (to keep push_back O(1) amortiz=
ed).=20
> There is however the possibility that the current block of memory could=
=20
> allow a couple more elements but not double the number of elements. Hav=
ing=20
> a function indicate exactly how many element fit in the current block w=
ould=20
> avoid unnecessary movement of elements in this case.

The interface should be designed such that it is usable in a thread-safe
fashion. I.e. with your capacity() proposal, there's the problem that
between calling capacity() and doing the actual resizing with some
realloc() equivalent, another thread could cause the available capacity
to decrease between the two calls. Therefore asking for the available
capacity and allocating it should always be provided as an atomic
facility.

Normally, one needs to increase the memory by some specific amount, not
less and not more, so _expand() exactly fits that purpose. For
situations like the one you pointed out, where more flexibility would be
useful, it would make sense to provide a function that gets two size
parameters passed that specify a range, and where the function should
increase the memory as much as possible within that range, if possible
at all; and return the new size. Something like:

   std::size_t mem_grow(const void *mem,
                        std::size_t min_size,
                        std::size_t max_size);

   char *cp =3D new char[20];
   ...
   // increase to at least 30 bytes, and up to 40 bytes if possible:
   std::size_t new_size =3D mem_grow(cp, 30, 40);
   if (new_size < 30) { /* failed, memory size ist unchanged */ }

-- 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.research.att.com/~austern/csc/faq.html                ]

Luis Pedro Coelho said on 27 May 01 10:54:54 GMT:
>I do not know the interface of _expand, but I think a fitting interface
>could be:
>
>std::size_t capacity(const void*);

It would be problematic to implement this, if I understand your intent
correctly (e.g. the user would then be allowed to use as many bytes
as were returned by the call).
For example, the last memory block allocated on a system that supports
virtual memory may temporarily have 'infinite' capacity. What would
the function return ?
Also, large blocks of free memory may exist after the block of interest.
Do they necessarily need to be merged and assigned if 'capacity' is
called ?

>IMHO, this is better than a half-realloc, because if we had a function like
>
>bool half_realloc(const void*, std::size_t);
>
>which returned true if there is more memory available, there are some
>possibilities which would be negleted. Consider a std::vector v. Let's say
>v.capacity() == v.size(). Now we do v.push_back(T()). The normal thing for
>vector to do is to double it's capacity (to keep push_back O(1) amortized).
>There is however the possibility that the current block of memory could
>allow a couple more elements but not double the number of elements. Having
>a function indicate exactly how many element fit in the current block would
>avoid unnecessary movement of elements in this case.

This is a good point.

Maybe the function could return the maximum memory
that can actually be allocated, up to the requested size ?

I'm afraid that this could take us too far... there are too many factors
involved in defining an 'optimum' memory allocation policy.


What about just tuning std::vector<T,default_allocator> to use a backdoor
into the memory subsystem ?
Would this conflict with the user's ability to redefine the global new
and delete operators ?



All this reminds me of the good old Macintosh 'handles': void** pointers,
allowing the system to re-locate the memory blocks to avoid heap
fragmentation...

Regards - Ivan

---
[ 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.research.att.com/~austern/csc/faq.html                ]

"Andrei Alexandrescu" <andrewalex@hotmail.com> wrote in message
news:9ehbrn$2tr29$1@ID-14036.news.dfncis.de...
> [This reminds me of the story with the solid rocket boosters of the Space
> Shuttle which were built to fit the standard railroad gauge for enabling
> railroad transportation through a tunnel....

The story is false.  See http://www.snopes.com/spoons/fracture/gauge.htm



      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On 24 May 2001 14:49:23 -0400, Andrei Alexandrescu <andrewalex@hotmail.com> wrote:
[         ]
> The neighbors in Redmond, known for their practicality, incarnated
> that primitive in the form of _expand, which does half of what realloc
> does: expands a block in place, and does nothing if that's not
> possible. (Does C99 define anything like that?)

C99 doesn't.

> So I wanted to ask whether there is any support in the C++ community to
> standardize efficient reallocation.

For what it's worth, you have my support, it's something I've wished for
for quite some time.

-- Niklas Matthies

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

"Andrei Alexandrescu" <andrewalex@hotmail.com> writes:

> So I wanted to ask whether there is any support in the C++ community
> to standardize efficient reallocation.

Currently, it seems that this issue is just kind of swept under the
rug.  When asked by people from other languages why C++ doesn't have a
realloc-like function, the answer usually resembles "... because."

Sometimes some vague qualifications are thrown in " ... because it
really complicates some things."  Of course, 'some things' is never
quite defined, and it's usually just dropped at that.

I think your 2-horses analogy is fitting.  A realloc-like feature was
left out (either intentionally or otherwise), and now people think
that there is some secret reason that only those in the inner sanctum
of C++ know about, but certainly that omission is there for a good
REASON that ought not be challenged.

So, let's challenge it.

 Perhaps there is an academic reason (E.G. "not all platforms support
it, so it's impossible to write a standard-compliant C++ compiler for
those platforms") but perhaps there are workarounds or concessions
that could still be made.  In any case, it's worth a few minutes worth
of discussion.


--
Chris

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

24 May 2001 14:49:23 -0400 Andrei Alexandrescu                      :

>So I wanted to ask whether there is any support in the C++ community to
>standardize efficient reallocation.

Although it is for library implementors only (BTW I like this ugly syntax -
"_expand"), I want it to present.

--
jk

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

"Andrei Alexandrescu" <andrewalex@hotmail.com> wrote in message
news:9ehbrn$2tr29$1@ID-14036.news.dfncis.de...

[snip]

> So I wanted to ask whether there is any support in the C++ community to
> standardize efficient reallocation.
>

Efficiency Ballot
Vote for one only:

[    ]   Keep things as they are

[ X ]   Support portable reallocation

-cd




      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

I guess I got this efficiency streak, but if C++ 0x is anything about
efficiency, I guess the following would be of interest.

In thinking on how to write YASTLI so that it is as efficient as it gets, I
stumbled again upon memory allocation.

As I, um, discussed in my older post "Again on renew, realloc, and
efficiency" (see
http://groups.google.com/groups?q=renew+author:andrei&ic=1&selm=7i9aef%24ed0
%241%40nnrp1.deja.com), memory allocation in C++ is fundamentally warped
because its ancestor (and historical back-end), the C heap allocator, lacks
an appropriate primitive that reallocates a block of memory without moving
it in memory. The realloc function does too much by taking initiative to
copy memory if no space is available at the end of the currently allocated.
For C, moving things around with memcpy worked just fine, but C++ needed
more, and so it basically dropped any reallocation opportunities from day
one. C++ has new and delete but not renew or anything similar.

C++ allocators are meant to work with the free store and therefore don't
support the notion of reallocation at all. There's no means to tell an
allocator "well, see this memory block, do you have an extra available 1024
bytes at its end? If so, I'd like those".

And so in the dusk of second millenium, the most modern C++ library does not
have a means to support optimal memory allocation.

[This reminds me of the story with the solid rocket boosters of the Space
Shuttle which were built to fit the standard railroad gauge for enabling
railroad transportation through a tunnel. The standard railroad gauge was
defined to match the tramway gauge (4 feet, 8 inches). The tramway gauge was
built with the same tools as wagons. Wagons used that gauge to match the
standard wheel ruts. The wheel rutted roads started back during the Roman
empire and were formed by Roman war chariots. The 4 feet, 8 inches width of
Roman chariots was meant to fit the backs of two parallel horses.]

Many things are needed for ending this sorry state of affairs. The first is
to standardize a primitive. The neighbors in Redmond, known for their
practicality, incarnated that primitive in the form of _expand, which does
half of what realloc does: expands a block in place, and does nothing if
that's not possible. (Does C99 define anything like that?)

Then, an appropriate mechanism of taking advantage of that in C++ must be
devised. And finally, the standard allocators and library must define
interfaces that support the notion of reallocation.

So I wanted to ask whether there is any support in the C++ community to
standardize efficient reallocation.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar
---
[ 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.research.att.com/~austern/csc/faq.html                ]