SeeWebsiteForEmail@moderncppdesign.com ("Andrei Alexandrescu (See Website for Email)") wrote in message news:<30heubF2vu1h0U1@uni-berlin.de>...
> "Mathieu Mazerolle" <mathieu.mazerolle@gmail.com> wrote in message
> news:854db3d.0411140348.2dd3ee55@posting.google.com...
>>>

> > Given the very low probability of reaching that last step, I don't
> > think your proposal is a good one.
>
> Sorry, but this whole argument is completely misguided and mistaken.

Do you mean the whole post, or the issue raised in the original post,
which I was addressing, which was performance?

> It is a well-known and widely-discussed fact that C++'s memory primitives
> have a problem that stems from the hallmark of bad design that realloc() is.
> See for example http://www.armdevzone.com/EABI/malloc_helpers.htm.

Totally agreed. I think it's important to bring that up, as there
doesn't seem to be a lot of discussion about this.


> Fixing that problem in std::vector is doable but not ideal. It's an
> allocation-related issue, we have an allocator, the fix should focus on the
> allocator.

Agree. I was addressing the topic of the orinal post, but there is a
bigger picture. However, the poster e-mailed me privately and said he
was specifically working in the context std::vector, so the bigger
picture may not be relevant to what he's working on, and was seeking
input on. Perhaps he can post here to elaborate.

> You work in a highly specialized domain.

I've got bills to pay :)

> Bringing an example from that niche
> to argue against a general-purpose facility is not a winning move. (Besides,
> I'm not sure I understand the logic. The post starts by telling people to
> trust std::vector and the standard allocation mechanisms, and ends by saying
> that in your work they turned out to be lacking and needed be replaced...)

It's too bad to don't value my input from personal experience. I wish
I had more to add, but I must limit my contributions to the scope of
what I know. Perhaps your experience is broader, and you could add
more.

My point was that std::vector should be the right thing by default,
until you measure otherwise. In the case where std::vector measured to
be lacking, I gave an example of how I addressed the issue in the
past. Does this clarify my argument?

> Andrei

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

"Mathieu Mazerolle" <mathieu.mazerolle@gmail.com> wrote in message
news:854db3d.0411140348.2dd3ee55@posting.google.com...
> As you said, your wish for expand_new() is motivated by performance,
> so let's debunk that first. What is stopping std::vector from using
> something like realloc() behind the scenes? First, trust your
> implementation and use std::vector. Secondly, measure performance.
> Third, perform a series of directed experitments to prove / disprove
> your hypothesis that std::vector is causing a bottleneck because it
> doesn't grow blocks in-place. If, and only if, you've proven the
> hypothesis, should you write a custom container that does exactly what
> you proposed.
>
> Given the very low probability of reaching that last step, I don't
> think your proposal is a good one.

Sorry, but this whole argument is completely misguided and mistaken.

It is a well-known and widely-discussed fact that C++'s memory primitives
have a problem that stems from the hallmark of bad design that realloc() is.
See for example http://www.armdevzone.com/EABI/malloc_helpers.htm.

> Also, your proposal is not a good
> one because it asks to make what should rightly be an implementation
> detail of std::vector a publicly accesible facility. It is so rare to
> need extra flexibility in the memory allocation system that I don't
> think it should be complicated any further.


Fixing that problem in std::vector is doable but not ideal. It's an
allocation-related issue, we have an allocator, the fix should focus on the
allocator.

> I do a lot of work on game consoles, where there is very limited
> memory and the applications have very demanding specifications. As a
> general rule, we only do one memory allocation per subsystem, which
> allocates a big block of memory to a custom allocator. So in my day to
> day work, new and delete are irrelevant when it comes to performance:
> they've been measured, found to be lacking, and replaced. There's not
> the slightest desire in my heart to add to the core language to
> rectify my problems, since what I do is not general purpose, just as
> expand_new is not general purpose.

You work in a highly specialized domain. Bringing an example from that niche
to argue against a general-purpose facility is not a winning move. (Besides,
I'm not sure I understand the logic. The post starts by telling people to
trust std::vector and the standard allocation mechanisms, and ends by saying
that in your work they turned out to be lacking and needed be replaced...)


Andrei


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

"Chris" <caj@cs.york.ac.uk> wrote in message
news:41901423.6070700@cs.york.ac.uk...
> Daniel Pfeffer wrote:
>
> > ""Pavel Vozenilek"" <pavel_vozenilek@yahoo.co.uk> wrote in message
> > news:2v83cpF2hilufU1@uni-berlin.de...
> >
> >>""Roger Orr"" wrote:
[ ... ]
> >>"Resized" data don't need to be constructed/destructed
> >>again and again.
> >
> >
> > This is not necessarily true. Any class whose copy constructor performs
more
> > than bitwise copying of the class data may behave in an undefined manner
> > when moved. Consider the following string class which uses an internal
> > buffer for small strings, but allocates memory on the heap for larger
> > strings:
> > ...
> >
> > How can instances of this class be safely copied by a bitwise "move"
> > operation? The only way to safely copy this class is to construct a
copy,
> > then destruct the original.
> >
> This is true, there are some classes for which a bitwise copy cannot be
> performed. However, I would imagine that it is possible to detect which
> classes can be copied bitwise (those with trivial copy constructor, and
> where each member also has a trivial copy constructor, etc?)
>
I think a special member function for the realloc operator should be added
to the
concept of a class. Maybe an optional one. So we would have constructors and
destructors for new/delete operators and some other special member function
for
realloc and perhaps for move. After all we do have special member functions
for
operators, adding a new one for realloc wouldn't be a big deal.

Timothy Madden
Romania


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

pavel_vozenilek@yahoo.co.uk ("Pavel Vozenilek") wrote in message news:<2vadf1F2hchtvU1@uni-berlin.de>...
> "Ron Natalie" wrote:
>
> [snip realloc using memory pages mapping]
>
> > The memory mapping games are limitted to things that don't change
> > the virtual address.   While realloc could use them to avoid actually
> > having to copy the data, it still won't work for C++.   You can't go
> > around changing the address of objects.
> >
> I do not understand. Playing with memory mapping won't change
> addresses of C++ objects - all can be done behind the courtain.
> /Pavel

Please discontinue this hardware-centric discussion in a standard C++
newsgroup. It is just wrong to be discussing language/std library
features that cannot be implemented by a large portion of hardware out
there such as embedded devices, game consoles, etc.  These devices
typically have no virtual memory and no memory mapping unit.

Let's just face it: if you move an object, you must assume that you
will need to destroy it and re-create it. Yes, on some kinds of PC
this may not be the case, but that's hardly a topic for this NG.

The only way around moving objects without zero cost is to impose an
execution environment (virtual machine, minimum hardware spec, etc) on
the language, and I don't think that will be very popular here. Java
solves that problem quite nicely, and is designed with the tradeoff of
garbage collection + relocatable objects versus slower execution time.

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

Mathieu Mazerolle wrote:
> pavel_vozenilek@yahoo.co.uk ("Pavel Vozenilek") wrote in message news:<2vadf1F2hchtvU1@uni-berlin.de>...
>
>>"Ron Natalie" wrote:
>>
>>[snip realloc using memory pages mapping]
>>
>>
>>>The memory mapping games are limitted to things that don't change
>>>the virtual address.   While realloc could use them to avoid actually
>>>having to copy the data, it still won't work for C++.   You can't go
>>>around changing the address of objects.
>>>
>>
>>I do not understand. Playing with memory mapping won't change
>>addresses of C++ objects - all can be done behind the courtain.
>>/Pavel
>
>
> Please discontinue this hardware-centric discussion in a standard C++
> newsgroup. It is just wrong to be discussing language/std library
> features that cannot be implemented by a large portion of hardware out
> there such as embedded devices, game consoles, etc.  These devices
> typically have no virtual memory and no memory mapping unit.
>
> Let's just face it: if you move an object, you must assume that you
> will need to destroy it and re-create it. Yes, on some kinds of PC
> this may not be the case, but that's hardly a topic for this NG.
>
> The only way around moving objects without zero cost is to impose an
> execution environment (virtual machine, minimum hardware spec, etc) on
> the language, and I don't think that will be very popular here. Java
> solves that problem quite nicely, and is designed with the tradeoff of
> garbage collection + relocatable objects versus slower execution time.
>

I apologise if the conversation appears to have got too deeply into
hardware specific details. The beginning (and I feel the main point) is
that the designers of C decided to introduce realloc because it performs
a commonly used operation and on some systems it provides the
possibility of very significant performance improvements. However, the
"vanilla" C realloc is not useful for C++ for various reasons. However
carrying the spirit of realloc over to C++ would allow for some (I agree
not all) systems to perform some significant improvements with (I
believe) no penality to those which cannot.

Do you agree?

Chris

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

caj@cs.york.ac.uk (chris) wrote in message news:<419648CB.3090803@cs.york.ac.uk>...
> Mathieu Mazerolle wrote:
> > pavel_vozenilek@yahoo.co.uk ("Pavel Vozenilek") wrote in message news:<2vadf1F2hchtvU1@uni-berlin.de>...
> I apologise if the conversation appears to have got too deeply into
> hardware specific details. The beginning (and I feel the main point) is
> that the designers of C decided to introduce realloc because it performs
> a commonly used operation and on some systems it provides the
> possibility of very significant performance improvements. However, the
> "vanilla" C realloc is not useful for C++ for various reasons. However
> carrying the spirit of realloc over to C++ would allow for some (I agree
> not all) systems to perform some significant improvements with (I
> believe) no penality to those which cannot.
>
> Do you agree?
>
> Chris

Hi Chris,

Obviously, if you're using objects, you should not be using realloc()
unless you've got some custom allocator that knows what it's doing
behind the scenes. So let's forget about realloc() unless we're
talking about C, and focus on your original expand_new() proposal.

As you said, your wish for expand_new() is motivated by performance,
so let's debunk that first. What is stopping std::vector from using
something like realloc() behind the scenes? First, trust your
implementation and use std::vector. Secondly, measure performance.
Third, perform a series of directed experitments to prove / disprove
your hypothesis that std::vector is causing a bottleneck because it
doesn't grow blocks in-place. If, and only if, you've proven the
hypothesis, should you write a custom container that does exactly what
you proposed.

Given the very low probability of reaching that last step, I don't
think your proposal is a good one. Also, your proposal is not a good
one because it asks to make what should rightly be an implementation
detail of std::vector a publicly accesible facility. It is so rare to
need extra flexibility in the memory allocation system that I don't
think it should be complicated any further.

I know what you're going to say: <gollum> "But I wantsssss it!"
</gollum>

I do a lot of work on game consoles, where there is very limited
memory and the applications have very demanding specifications. As a
general rule, we only do one memory allocation per subsystem, which
allocates a big block of memory to a custom allocator. So in my day to
day work, new and delete are irrelevant when it comes to performance:
they've been measured, found to be lacking, and replaced. There's not
the slightest desire in my heart to add to the core language to
rectify my problems, since what I do is not general purpose, just as
expand_new is not general purpose.

-- Matt

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

Mathieu Mazerolle wrote:

>
> Please discontinue this hardware-centric discussion in a standard C++
> newsgroup. It is just wrong to be discussing language/std library
> features that cannot be implemented by a large portion of hardware out
> there such as embedded devices, game consoles, etc.  These devices
> typically have no virtual memory and no memory mapping unit.
>

Actually, I disagree.  It is as topical as poinging out classes
of limitted hardware that CAN'T permit certain features.

We're not talking about moving objects.  I've explicitly pointed
out that MOVING objects requires the normal C++ copy paradigms
(which was the point I was trying to make to the virtual memory-assisted
remapping crowd).

The point that is still under discussion is whether the language can
support from a realloc capability to EXTEND allocations (which would
have to fail or use the normal C++ copy mechanisms).   I'm not
convinced that we do need such a feature, but I'm still open for
discussion.   I have a number is issues with the "can be stupidly
implemented on top of malloc" paradigm C++ is currently using, so
I can still be enlightened.

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

In article <41964d65$0$31293$9a6e19ea@news.newshosting.com>, Ron Natalie
<ron@sensor.com> writes
>The point that is still under discussion is whether the language can
>support from a realloc capability to EXTEND allocations (which would
>have to fail or use the normal C++ copy mechanisms).

I am not convinced that such extension of storage is prohibited as is.

--
Francis Glassborow      ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects

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

Francis Glassborow wrote:
> In article <41964d65$0$31293$9a6e19ea@news.newshosting.com>, Ron Natalie
> <ron@sensor.com> writes
>
>> The point that is still under discussion is whether the language can
>> support from a realloc capability to EXTEND allocations (which would
>> have to fail or use the normal C++ copy mechanisms).
>
>
> I am not convinced that such extension of storage is prohibited as is.
>
There's no way to express it in the normal dumber-as-malloc C++
allocator.   Even the standard allocators don't have any provision
that allows you to say "hey the allcoation I told you about earlier
is now bigger and no extension is required."

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

Ron Natalie wrote:
> Francis Glassborow wrote:
>
>> In article <41964d65$0$31293$9a6e19ea@news.newshosting.com>, Ron
>> Natalie <ron@sensor.com> writes
>>
>>> The point that is still under discussion is whether the language can
>>> support from a realloc capability to EXTEND allocations (which would
>>> have to fail or use the normal C++ copy mechanisms).
>>
>>
>>
>> I am not convinced that such extension of storage is prohibited as is.
>>
> There's no way to express it in the normal dumber-as-malloc C++
> allocator.   Even the standard allocators don't have any provision
> that allows you to say "hey the allcoation I told you about earlier
> is now bigger and no extension is required."

std::vector can detect when the implementation's own allocator is being
used, and take different actions, such as using extensions within that
allocator.

-- James

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

James Dennett wrote:

>
> std::vector can detect when the implementation's own allocator is being
> used, and take different actions, such as using extensions within that
> allocator.
>
>
And this is compliant with the current standard how?

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

In article <419a32a6$0$31276$9a6e19ea@news.newshosting.com>, Ron Natalie
<ron@sensor.com> writes
>James Dennett wrote:
>
>>  std::vector can detect when the implementation's own allocator is
>>being
>> used, and take different actions, such as using extensions within that
>> allocator.
>>
>And this is compliant with the current standard how?

More to the point, in what way is it not complying? Standard Library
elements are allowed to use 'magic'.


--
Francis Glassborow      ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects

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

Hello. I apologise that what am about to write is a) not that well
formed, and b) comes from discussions on the libstdc++ mailing list.

In C, there are 3 main functions involved with memory allocation,
malloc, realloc and free. For those who aren't familiar with it,
realloc(void* ptr, int new_size) takes the block of memory pointed to by
ptr and attempts to extend it to size "new_size". If this is not
possible it allocates a new block of memory of size new_size and copies
the old data into the new allocation. While it is standard-compliant to
simply ignore the "possibly extend block of memory",  it is often
possible to generate a more efficent implementation of it in 2 main ways:

1) A block of memory may have free memory after it. We can then extend
the current memory allocation almost for free.

2) In most modern operating systems the relationship between physical
memory and the memory layout a program sees is quite disjoint. This
means that it is sometimes possible to rearrange blocks of memory simply
by altering the order of pages, and not perform any physical copying of
memory.

In C++, memory allocation is done by users using new and delete (and
new[] and delete[]), and by containers using an allocator. Unfortunatly
none of these support a realloc-style function.

The main problem with using realloc in C++ code is that we cannot simply
copy many classes using memcpy (or similar bit-by-bit copying).
Therefore using realloc on a block of memory containing classes can be
highly dangerous realloc is unable to extend the current block of
memory. Also realloc cannot be used on memory created by new and delete.

Therefore I suggest the following extensions to C++ (which I admit are
under-specified)

template<typename T>
bool new_extend(T* ptr, int new_size)

Attempts to extend the memory allocated at ptr to size new_size. If the
memory block cannot be extended, then return false. It is
standards-compliant for this function to always return false.

template<typename T>
T* new_move(T* ptr, int new_size)

Basically operates the same as realloc, but if a new block of memory
must be allocated, will use copy-construction (but can obviously
optimise for those cases where T is a POD type). Is standard-compliant
to simply new a new block of memory, use std::copy to copy across the
items, and then delete the only block of memory.

Adding similar extensions to std::Allocators would I think also be
useful, but would be more complicated. There are various possible ways
in which allocators could be extended to allow this, the two most
obvious ways are:

make a class
template<typename T> struct extended_allocator { static const int
extended=0;} , which is overloaded for all allocators which support
these features

or make a class
template<typename T> struct extended_allocator { .. } which implements
simple versions of new_extend and new_move but which can be overloaded
by a specific allocator.


I do feel that these are areas where C++ memory handling is deficent in
comparison to C, espically now that many computers are 64-bit and
therefore have very, very large potential memory spaces.

Thank you for reading,

Chris Jefferson

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

caj@cs.york.ac.uk (chris) wrote in message news:<cltiq8$5ia$1@pump1.york.ac.uk>...
> Hello. I apologise that what am about to write is a) not that well
> formed, and b) comes from discussions on the libstdc++ mailing list.

[snip proposal]

What is the advantage of adding such functionality over the std::vector template?

Bob

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

Bob Bell wrote:
> caj@cs.york.ac.uk (chris) wrote in message news:<cltiq8$5ia$1@pump1.york.ac.uk>...
>
>>Hello. I apologise that what am about to write is a) not that well
>>formed, and b) comes from discussions on the libstdc++ mailing list.
>
>
> [snip proposal]
>
> What is the advantage of adding such functionality over the std::vector template?
>

Such functionality would be useful in the more efficent implementation
of the std::vector template. While in theory std::vector could be
implemented using these ideas without adding them to the standard, this
would require using implementation-specific details within the
std::vector template, which some people may not be happy with. However
there could also simply be a more efficent implementation of std::vector
as well, this is true and an option I had not considered.

Chris

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

Bob Bell wrote:
> caj@cs.york.ac.uk (chris) wrote in message news:<cltiq8$5ia$1@pump1.york.ac.uk>...
>
>>Hello. I apologise that what am about to write is a) not that well
>>formed, and b) comes from discussions on the libstdc++ mailing list.
>
>
> [snip proposal]
>
> What is the advantage of adding such functionality over the std::vector template?
>

Such functionality would be useful in the more efficent implementation
of the std::vector template. While in theory std::vector could be
implemented using these ideas without adding them to the standard, this
would require using implementation-specific details within the
std::vector template, which some people may not be happy with. However
there could also simply be a more efficent implementation of std::vector
as well, this is true and an option I had not considered.

Chris

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

"chris" <caj@cs.york.ac.uk> wrote in message
news:cltiq8$5ia$1@pump1.york.ac.uk...
> Hello. I apologise that what am about to write is a) not that well
> formed, and b) comes from discussions on the libstdc++ mailing list.
>
> In C, there are 3 main functions involved with memory allocation,
> malloc, realloc and free. For those who aren't familiar with it,
> realloc(void* ptr, int new_size) takes the block of memory pointed to by
> ptr and attempts to extend it to size "new_size". If this is not
> possible it allocates a new block of memory of size new_size and copies
> the old data into the new allocation. While it is standard-compliant to
> simply ignore the "possibly extend block of memory",  it is often
> possible to generate a more efficent implementation of it in 2 main ways:
>
> 1) A block of memory may have free memory after it. We can then extend
> the current memory allocation almost for free.
>
> 2) In most modern operating systems the relationship between physical
> memory and the memory layout a program sees is quite disjoint. This
> means that it is sometimes possible to rearrange blocks of memory simply
> by altering the order of pages, and not perform any physical copying of
> memory.
>
> In C++, memory allocation is done by users using new and delete (and
> new[] and delete[]), and by containers using an allocator. Unfortunatly
> none of these support a realloc-style function.
>
> The main problem with using realloc in C++ code is that we cannot simply
> copy many classes using memcpy (or similar bit-by-bit copying).
> Therefore using realloc on a block of memory containing classes can be
> highly dangerous realloc is unable to extend the current block of
> memory. Also realloc cannot be used on memory created by new and delete.

I seem to recall a discussion on this very matter in the "C++ Report" (a now
defunct journal) on the utility of a realloc<T> template. If such a template
is to be written in Standard C++, its requirements are as follows:

1. No resizing of an exisitng memory block is allowed (no class-compatible
functions exist in Standard C++).

2. When the existing memory block must be enlarged, it must be done as
follows:
    2.1 All the objects in the new memory block must be initialised with the
T() default constructor
    2.2 Any original objects must be copied with the operator =(const T &)
assignment operator.
    2.3 The original memory block must be released with the delete[]
operator.

3. When the existing memory block must be reduced, it must be done as
follows:
    3.1 All the objects in the new memory block must be initialised with the
T() default constructor
    3.2 Any original objects (up to the limit of the new memory block) must
be copied with the operator =(const T &) assignment operator.
    3.3 The original memory block must be released with the delete[]
operator.

If this template is mandated at the Standard library level, it is possible
that compilers may perform "magic" to create something closer to the
realloc() function. For example, a compiler can access the hidden
information regarding the size of a memory block, and perform operations
closer to those provided by the realloc() operation. This does not affect
the requirements for class T.

The requirements for class T are:

    1. Presence of a default constructor
    2. Presence of a copy constructor ("copy constructible")
    3. Presence of a destructor

These requirements sound remarkably similar to those for the vector<>
template class, which has the advantage that it does not leave dangling
pointers to memory (as is possible with raw memory pointers). Why not use
that?


Daniel Pfeffer


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

chris wrote:
> Bob Bell wrote:
>
>> caj@cs.york.ac.uk (chris) wrote in message
>> news:<cltiq8$5ia$1@pump1.york.ac.uk>...
>>
>>> Hello. I apologise that what am about to write is a) not that well
>>> formed, and b) comes from discussions on the libstdc++ mailing list.
>>
>>
>>
>> [snip proposal]
>>
>> What is the advantage of adding such functionality over the
>> std::vector template?
>>
>
> Such functionality would be useful in the more efficent implementation
> of the std::vector template. While in theory std::vector could be
> implemented using these ideas without adding them to the standard, this
> would require using implementation-specific details within the
> std::vector template, which some people may not be happy with. However
> there could also simply be a more efficent implementation of std::vector
> as well, this is true and an option I had not considered.
>

In order to provide a more efficient implementation of std::vector, we
might consider two possibile, non mutually exclusive, improvements of
the allocator interface:

   bool grow(pointer p, size_type n);

Semantic: if p is the result of a call to allocate(m) with the same
allocator try to extend the memory block at p in-place so that it can
store at least n elements. The first m*sizeof(T) bytes of the block
shall not be modified. Return true if successful, false otherwise.
[Note: it is conformant to always return false] [Note: if n <= m the
function should do nothing, i.e. the block is never shrunk]

The grow() method could be used when the vector grows in order to avoid
moving the elements already in the vector. Notice that allocators work
with raw memory, so grow() is not required to initialize the extra
memory. std::vector will initialize it if necessary.

   size_type actual_size(pointer p);

Semantic: if p is the result of a call to allocate(m) with the same
allocator, return the actual size n of the memory block at p or 0 if it
it's not possible to determine the actual size. [Note: it's conformant
to always return 0] [Note: if n > 0 then n will always be greater than
or equal to m]

The actual_size() method could be used to obtain a more precise value
for capacity() thereby exploiting the presence of any additional memory
that might be available after the requested block.

On a VC++ malloc-based allocator, both those function could be easily
implemented by using CRT specific functions like _expand and _msize. Of
course that doesn't mean that they can be implemented everywhere,
although the interface is designed in such a way that a dumb
implementation is always possible.

Comments?

Alberto

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

On Fri, 29 Oct 2004 17:21:18 GMT, caj@cs.york.ac.uk (chris) wrote:

>I do feel that these are areas where C++ memory handling is deficent in
>comparison to C, espically now that many computers are 64-bit and
>therefore have very, very large potential memory spaces.

The main purpose of providing realloc functionality is to allow for a
more efficient implementation of std::vector, and other resizeable
buffer classes (valarray, user containers, etc.). As such, I think you
could get away with simply adding some optional features to the
allocator requirements, and allow implementations to support these
features with std::allocator if they wish. Providing the feature at
the operator new level will cause problems for overloaded and
overridden operator new implementations.

Tom

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

"Alberto Barbati" wrote:


> On a VC++ malloc-based allocator, both those function could be easily
> implemented by using CRT specific functions like _expand and _msize. Of
> course that doesn't mean that they can be implemented everywhere,
>
On platforms that do not have expand() or equivalent the
grow() could always return 0. The check for this should
not have impact on performance.

The feature seems to be waiting to get used.

/Pavel




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

"Tom Widmer" <tom_usenet@hotmail.com> wrote in message
news:ttcco0psjqretelm3p2dba7n5uo3v1lgqm@4ax.com...
> On Fri, 29 Oct 2004 17:21:18 GMT, caj@cs.york.ac.uk (chris) wrote:
>
> >I do feel that these are areas where C++ memory handling is deficent in
> >comparison to C, espically now that many computers are 64-bit and
> >therefore have very, very large potential memory spaces.
>
> The main purpose of providing realloc functionality is to allow for a
> more efficient implementation of std::vector, and other resizeable
> buffer classes (valarray, user containers, etc.).

Since most implementations of std::vector already use an alogrithm of
increasing the size of a fresh allocation by a suitable scaling factor (eg
1.5)
I'm not sure how much realloc()-like functionality would add to efficiency.

Roger Orr
--
MVP in C++ at www.brainbench.com


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

""Roger Orr"" wrote:

> Since most implementations of std::vector already use an alogrithm of
> increasing the size of a fresh allocation by a suitable scaling factor (eg
> 1.5)
> I'm not sure how much realloc()-like functionality would add to
efficiency.
>
"Resized" data don't need to be constructed/destructed
again and again.

/Pavel


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

Pavel Vozenilek wrote:
> ""Roger Orr"" wrote:
>
>
>>Since most implementations of std::vector already use an alogrithm of
>>increasing the size of a fresh allocation by a suitable scaling factor (eg
>>1.5)
>>I'm not sure how much realloc()-like functionality would add to
>
> efficiency.
>
> "Resized" data don't need to be constructed/destructed
> again and again.
>
And adding things to vectors which have capacity doesn't need
to be constructed / destructed again.

Realloc only can operate in place when there is free space immediately
after the current block.   Otherwise it HAS to copy and it incurs the
same copy/destruction penalty as vector.  It's unlikely in the C++
environment, that realloc is going to just extend the end of the
allocation size (unless it does some random padding at the end of
allocations which is exactly te vector behavior again).

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

"Ron Natalie" wrote:

> Realloc only can operate in place when there is free space immediately
> after the current block.   Otherwise it HAS to copy and it incurs the
> same copy/destruction penalty as vector.  It's unlikely in the C++
> environment, that realloc is going to just extend the end of the
> allocation size (unless it does some random padding at the end of
> allocations which is exactly te vector behavior again).
>
Very large memory blocks may be allocated by different techniques
than small ones. These techniques may use OS memory mapping services.

I can imagine such allocator under Win32.

/Pavel


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

""Pavel Vozenilek"" <pavel_vozenilek@yahoo.co.uk> wrote in message
news:2v83cpF2hilufU1@uni-berlin.de...
>
> ""Roger Orr"" wrote:
>
> > Since most implementations of std::vector already use an alogrithm of
> > increasing the size of a fresh allocation by a suitable scaling factor
(eg
> > 1.5)
> > I'm not sure how much realloc()-like functionality would add to
> efficiency.
> >
> "Resized" data don't need to be constructed/destructed
> again and again.

This is not necessarily true. Any class whose copy constructor performs more
than bitwise copying of the class data may behave in an undefined manner
when moved. Consider the following string class which uses an internal
buffer for small strings, but allocates memory on the heap for larger
strings:


class OptimisedString {
public:

    /* other methods omitted */

    OptimisedString(const OptimisedString &src)
    {
        if (this != &src) {
            if (src.p_ == src.buf_) {
                std::strcpy(buf_,src.buf_);
                p_ = buf_;
            }
            else {         /* error checking omitted for clarity */
                p_ = new char[std::strlen(src.p_)+1];
                std::strcpy(p_,src.p_);
            }
        }
    }

private:
    char buf_[32];
    char *p_;
}


How can instances of this class be safely copied by a bitwise "move"
operation? The only way to safely copy this class is to construct a copy,
then destruct the original.


Daniel Pfeffer


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

Pavel Vozenilek wrote:

> Very large memory blocks may be allocated by different techniques
> than small ones. These techniques may use OS memory mapping services.
>
> I can imagine such allocator under Win32.
>
The memory mapping games are limitted to things that don't change
the virtual address.   While realloc could use them to avoid actually
having to copy the data, it still won't work for C++.   You can't go
around changing the address of objects.

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

 >Also [slightly OT, but not too much I don't think] note that under
some operating systems (I know this includes linux), calling realloc can
 >be much more efficent than alloc, copy, free because realloc can in
some cases call mremap, which simply "fiddles around" with the >virtual
memory table and doesn't do any actual copying. Doing this can make
extending a large vector which has been page aligned >essensially free.

That's fine for realloc...it avoids copying.   However, if the virtual
address changes, you've just
broken C++.

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

""Daniel Pfeffer"" wrote:

> > "Resized" data don't need to be constructed/destructed
> > again and again.
>
> This is not necessarily true. Any class whose copy constructor performs
more
> than bitwise copying of the class data may behave in an undefined manner
> when moved. Consider the following string class which uses an internal
> buffer for small strings, but allocates memory on the heap for larger
> strings:
> [example snipped]
>
> How can instances of this class be safely copied by a bitwise "move"
> operation? The only way to safely copy this class is to construct a copy,
> then destruct the original.
>
'C++ realloc' can and should be implemented so it won't move any
data.

It it is not possible to resize existing memory block it would return
with failure.

/Pavel


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

Ron Natalie wrote:
> Pavel Vozenilek wrote:
>
>> Very large memory blocks may be allocated by different techniques
>> than small ones. These techniques may use OS memory mapping services.
>>
>> I can imagine such allocator under Win32.
>>
> The memory mapping games are limitted to things that don't change
> the virtual address.   While realloc could use them to avoid actually
> having to copy the data, it still won't work for C++.   You can't go
> around changing the address of objects.
>
Well, you can if you are (for example) extending the length of a
std::vector and that the copy constructor of the class simply does a
bitwise copy, which would happen in a quite large number of cases I think.

Chris

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

Daniel Pfeffer wrote:

> ""Pavel Vozenilek"" <pavel_vozenilek@yahoo.co.uk> wrote in message
> news:2v83cpF2hilufU1@uni-berlin.de...
>
>>""Roger Orr"" wrote:
>>
>>
>>>Since most implementations of std::vector already use an alogrithm of
>>>increasing the size of a fresh allocation by a suitable scaling factor
>
> (eg
>
>>>1.5)
>>>I'm not sure how much realloc()-like functionality would add to
>>
>>efficiency.
>>
>>"Resized" data don't need to be constructed/destructed
>>again and again.
>
>
> This is not necessarily true. Any class whose copy constructor performs more
> than bitwise copying of the class data may behave in an undefined manner
> when moved. Consider the following string class which uses an internal
> buffer for small strings, but allocates memory on the heap for larger
> strings:
> ...
>
> How can instances of this class be safely copied by a bitwise "move"
> operation? The only way to safely copy this class is to construct a copy,
> then destruct the original.
>
This is true, there are some classes for which a bitwise copy cannot be
performed. However, I would imagine that it is possible to detect which
classes can be copied bitwise (those with trivial copy constructor, and
where each member also has a trivial copy constructor, etc?)

Chris

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

"Ron Natalie" wrote:

[snip realloc using memory pages mapping]

> The memory mapping games are limitted to things that don't change
> the virtual address.   While realloc could use them to avoid actually
> having to copy the data, it still won't work for C++.   You can't go
> around changing the address of objects.
>
I do not understand. Playing with memory mapping won't change
addresses of C++ objects - all can be done behind the courtain.
/Pavel


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

On Mon,  8 Nov 2004 15:01:44 GMT, ron@sensor.com (Ron Natalie) wrote:

>Pavel Vozenilek wrote:
>> ""Roger Orr"" wrote:
>>
>>
>>>Since most implementations of std::vector already use an alogrithm of
>>>increasing the size of a fresh allocation by a suitable scaling factor (eg
>>>1.5)
>>>I'm not sure how much realloc()-like functionality would add to
>>
>> efficiency.
>>
>> "Resized" data don't need to be constructed/destructed
>> again and again.
>>
>And adding things to vectors which have capacity doesn't need
>to be constructed / destructed again.
>
>Realloc only can operate in place when there is free space immediately
>after the current block.   Otherwise it HAS to copy and it incurs the
>same copy/destruction penalty as vector.  It's unlikely in the C++
>environment, that realloc is going to just extend the end of the
>allocation size (unless it does some random padding at the end of
>allocations which is exactly te vector behavior again).

That depends entirely on the allocator. Allocators do sometimes have
plenty of free space after an allocation, and that's why realloc often
works. And since you can replace the allocator in C++ (per container,
per class and globally), you could use an allocator that is generally
good at expanding the latest allocation if that helped your
application.

Finding the performance gains to be had or not would entail writing
such an allocator, and rewriting std::vector to take advantage of it.
Due to the exponential expansion of std::vector, gains are not going
to be measured in orders of magnitude, but you might conceivably get a
halving of the runtime of some programs.

Tom

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

Ron Natalie wrote:
>  >Also [slightly OT, but not too much I don't think] note that under
> some operating systems (I know this includes linux), calling realloc can
>  >be much more efficent than alloc, copy, free because realloc can in
> some cases call mremap, which simply "fiddles around" with the >virtual
> memory table and doesn't do any actual copying. Doing this can make
> extending a large vector which has been page aligned >essensially free.
>
> That's fine for realloc...it avoids copying.   However, if the virtual
> address changes, you've just
> broken C++.
>
Obviously you would not be able to use such a function indiscriminatly.
However there are many cases where you do want to do an alloc, bitwise
copy, free, and in these cases I argue using realloc can be much more
efficent.

Also, as you say, realloc can mess things up horribly, hence why it
would be useful to have a realloc variant which attempted to extend
allocation but on failure simply returned rather than executing an
alloc,copy,move.

Chris

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