realloc in c++
quik...@yahoo.com
Thank,
qk
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Francis Glassborow
"quik...@yahoo.com" <quik...@yahoo.com> writes
>For "malloc" in C, we have "new" in c++. For "realloc" in C, what we have in C++?
Well malloc and new do not implement the same concept. But in C++ you
also have realloc and if matter enough you can use that as long as you
also use malloc. However notice that realloc presupposes that you are
handling a dynamic array. In C++ you would use std::vector for such a
purpose. There is nothing to prevent an implementor from making memory
allocation as efficient as possible but that becomes a QoI issue.
--
Francis Glassborow ACCU
If you are not using up-to-date virus protection you should not be reading
this. Viruses do not just hurt the infected but the whole community.
Howard Hinnant
quik...@yahoo.com (quik...@yahoo.com) wrote:
> For "malloc" in C, we have "new" in c++. For "realloc" in C, what we have in
> C++?
vector<T>::resize(size_type, value_type);
-Howard
Maciej Sobczak
quik...@yahoo.com wrote:
> For "malloc" in C, we have "new" in c++. For "realloc" in C, what we have in C++?
std::vector<char> buf(100);
buf.resize(200);
or:
boost::scoped_array buf(new char[100]);
buf.reset(new char[200]);
Or, better yet, please write us what problem do you want to solve.
It is often the case that when the group is challenged with higher-level
question, the collective solution is much different (and usually much
better) than what the original poster initially thought.
--
Maciej Sobczak
Daniel Pfeffer
news:ead1f717.03100...@posting.google.com...
> For "malloc" in C, we have "new" in c++. For "realloc" in C, what we have
in C++?
In the general case, you don't. In order to implement a generic renew<T>,
you would have to ensure that every class is "copy constructible", or that
every class has an assignment operator. There are many cases in which the
existence of such operators is a bad idea.
If you require dynamic re-allocation of a vector of objects, I suggest that
you use the std::vector template.
HTH,
Daniel Pfeffer
WW
> For "malloc" in C, we have "new" in c++. For "realloc" in C, what we
> have in C++?
new bigger
copy
delete old
OR
write a language proposal what Bjarne Stroustrup will like to get a "renew"
or a new_in_place or something.
--
WW aka Attila
Aaron Bentley
> For "malloc" in C, we have "new" in c++. For "realloc" in C, what we have in C++?
Andrei Alexandrescu.
:-)
http://www.cuj.com/documents/s=7988/cujcexp1912alexandr/
One cute thing he points out is that realloc() is a complete replacement
for both malloc() and free()!
Aaron
--
Aaron Bentley
www.aaronbentley.com
Bjarne Stroustrup
> > For "malloc" in C, we have "new" in c++. For "realloc" in C, what we
> > have in C++?
>
> new bigger
> copy
> delete old
>
> OR
>
> write a language proposal what Bjarne Stroustrup will like to get a "renew"
> or a new_in_place or something.
Or simply use std::vector; it can expand using resize() or push_back()
- Bjarne Stroustrup; http://www.research.att.com/~bs
Joshua Lehrer
> One cute thing he points out is that realloc() is a complete replacement
> for both malloc() and free()!
>
I never understood why this surprised anyone. realloc changes a
pointer size from its original size to a new size. If the source size
is 0, and the new size is non zero, then, clearly, this has to do an
allocation (malloc). If the source size is non-zero, and the target
size is 0, then, clearly, this is a full deallocation (free).
To me, the interface only makes sense this way.
joshua lehrer
factset research systems
NYSE:FDS
WW
> > write a language proposal what Bjarne Stroustrup will like to get
> a "renew" > or a new_in_place or something.
>
> Or simply use std::vector; it can expand using resize() or push_back()
Do you also sometimes feel you are being watched? :-)
As I have given the above comment with the above poor attempt of humor as an
*alternative* to:
new bigger
copy
delete old
IMHO the vector is not really an alternative of possible in-place
reallocation of the stuff - since it does exaclty the above - unless it has
some optimization for PODs, and then agaon it will only attempt to "trick"
if it has a POD inside.
That "C++ realloc" would of course need a completely new feature. If we
wanted to base it on realloc we would still need some way to tell to
realloc: do *not* copy the stuff. Because it is unnecessary. In case the
reallocation happens in place we are fine. We just construct the new
elements in the new area.
Yet another attrocity to be committed in the name of optimization. Awaiting
for further correction. ;-)
--
WW aka Attila
Howard Hinnant
"WW" <wo...@freemail.hu> wrote:
> Bjarne Stroustrup wrote:
> > > write a language proposal what Bjarne Stroustrup will like to get
> > a "renew" > or a new_in_place or something.
> >
> > Or simply use std::vector; it can expand using resize() or push_back()
>
> Do you also sometimes feel you are being watched? :-)
>
> As I have given the above comment with the above poor attempt of humor as an
> *alternative* to:
>
> new bigger
> copy
> delete old
>
> IMHO the vector is not really an alternative of possible in-place
> reallocation of the stuff - since it does exaclty the above - unless it has
> some optimization for PODs, and then agaon it will only attempt to "trick"
> if it has a POD inside.
>
> That "C++ realloc" would of course need a completely new feature. If we
> wanted to base it on realloc we would still need some way to tell to
> realloc: do *not* copy the stuff. Because it is unnecessary. In case the
> reallocation happens in place we are fine. We just construct the new
> elements in the new area.
>
> Yet another attrocity to be committed in the name of optimization. Awaiting
> for further correction. ;-)
We need two things for vector to blow new/copy/delete out of the water:
1. Move semantics:
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1377.htm
2. Ability to expand in place:
http://www.armdevzone.com/EABI/malloc_helpers.htm
Both are technically feasible today. It just has to be standardized.
If these two proposals were standardized (plus a few other arcane but
fully backwards compatible details) the performance advantages of
vector<T, my_fast_allocator<T> > over a built-in array would be
insurmountable. And with the addition of a template alias:
template <class T>
using Vec = std::vector<T, my_fast_allocator<T> >;
( http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1489.pdf )
the use of customized allocators to faciliate expansion in place would
become quite practical. We would be in a position to say:
> If you do not use Vec<MyClass> instead of new/copy/delete MyClass, you are
> going to experience a serious performance hit.
-Howard
Gabriel Dos Reis
| Bjarne Stroustrup wrote:
| > > write a language proposal what Bjarne Stroustrup will like to get
| > a "renew" > or a new_in_place or something.
| >
| > Or simply use std::vector; it can expand using resize() or push_back()
|
| Do you also sometimes feel you are being watched? :-)
|
| As I have given the above comment with the above poor attempt of humor as an
| *alternative* to:
|
| new bigger
| copy
| delete old
|
| IMHO the vector is not really an alternative of possible in-place
| reallocation of the stuff - since it does exaclty the above - unless it has
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
You may be surprised by what your favorite implementation of the
standard library does with vector<T>::resize.
[...]
| That "C++ realloc" would of course need a completely new feature. If we
No, it would not. vector<T>::resize is sufficient.
| wanted to base it on realloc we would still need some way to tell to
| realloc: do *not* copy the stuff. Because it is unnecessary. In case the
| reallocation happens in place we are fine. We just construct the new
| elements in the new area.
Did you bother looking at existings implementation of vector<T>::resize?
-- Gaby
Francis Glassborow
>> Or simply use std::vector; it can expand using resize() or push_back()
>
>Do you also sometimes feel you are being watched? :-)
>
>As I have given the above comment with the above poor attempt of humor as an
>*alternative* to:
>
>new bigger
>copy
>delete old
>
>IMHO the vector is not really an alternative of possible in-place
>reallocation of the stuff - since it does exaclty the above - unless it has
>some optimization for PODs, and then agaon it will only attempt to "trick"
>if it has a POD inside.
But std::vector is a Standard Library template and so it CAN use special
handling. It can even 'know' if it is possible to extend the current
allocation regardless of the PODness of the elements.
What we shied away from (with good reason IMO) was trying to lay down
requirements about when memory should be extended in situ. BTW realloc
makes no such promise, and could always (when required to actually
provide memory rather than by a weird version of free) follow the
strategy:
malloc replacement
copy original
free original
all that vector does is to extend this strategy. Well it would if we
could force shrinkage. But that would be one step further than realloc
which can elect to do nothing if required memory is less than current
memory. I.e. realloc does not actually do the things that many people
seem to think it does.
--
Francis Glassborow ACCU
If you are not using up-to-date virus protection you should not be reading
this. Viruses do not just hurt the infected but the whole community.
WW
>> As I have given the above comment with the above poor attempt of
>> humor as an *alternative* to:
>>
>> new bigger
>> copy
>> delete old
>>
>> IMHO the vector is not really an alternative of possible in-place
>> reallocation of the stuff - since it does exaclty the above - unless
>> it has
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>
> You may be surprised by what your favorite implementation of the
> standard library does with vector<T>::resize.
I would be surprised. First of all I have no favoriute one. Second is the
ones I remember does exactly what I have described. Remember: I am not
talking about vectors of PODs!
> [...]
>
>> That "C++ realloc" would of course need a completely new feature.
>> If we
>
> No, it would not. vector<T>::resize is sufficient.
In your world. In mine doing twice the work just because there is no in
place realloc for non-PODs is not sufficient.
>> wanted to base it on realloc we would still need some way to tell to
>> realloc: do *not* copy the stuff. Because it is unnecessary. In
>> case the reallocation happens in place we are fine. We just
>> construct the new elements in the new area.
>
> Did you bother looking at existings implementation of
> vector<T>::resize?
Did you bother to read and try to understand what I wrote? I am getting
really tired of you turning everything back on me. In this thread as well
as in the lvalue thread. If you have something concrete to say: say it so.
If all you have is innuendos then I for one are not interested in them.
BTW just to check how justified are your questions I looked at the STL which
happens to be installed on my PC here. It does:
allocate new
copy old stuff
deallocate old
Just as I wrote. Instead of:
Try to increase in place
if worked use the new space
if not
allocate new
copy old stuff
deallocate old
--
WW aka Attila
WW
[SNIP]
> But std::vector is a Standard Library template and so it CAN use
> special handling. It can even 'know' if it is possible to extend the
> current allocation regardless of the PODness of the elements.
Yes. But unless there is C library support for this writers of portable
standard library implementations will be unable to provide this service
without significant effort.
> What we shied away from (with good reason IMO) was trying to lay down
> requirements about when memory should be extended in situ.
And it is not needed either. If it is possible (possible being
implementation defined but without the request of being documented) it will
be done. If not, it will be reported it is not:
void *attempt_extend( void*, size_t);
Returns 0 if it cannot extend, the same pointer if it did. Or it can return
a pointer to a new area, while *not* releasing the old (in case there was no
way to extend in place).
--
WW aka Attila
Hovik Melikyan
in C++?
>
Both vector<> resizing and realloc() are error-prone, since you may be
holdong a reference to memory being reallocated (or rather a ref to an
object which is a part of that memory chunk). It's not like with
free/delete, realloc-related errors are more subtle and dangerous. (And you
may feel safe with your vector<> only if you maintain pointers to objects
instead of objects themselves, but that's not a matter of the language
standard, but rather a programming technique.)
So if your goal is to have dynamic array functionality in C++ without having
a library of any kind (e.g. STL), then IMO it's not possible, because that
would lead to many changes in the language and finally to kind of 'lifting'
C++ to a higher level (and that would result in Java :).
--
Hovik Melikyan
Bjarne Stroustrup
> Bjarne Stroustrup wrote:
> > > write a language proposal what Bjarne Stroustrup will like to get
> > a "renew" > or a new_in_place or something.
> >
> > Or simply use std::vector; it can expand using resize() or push_back()
>
> Do you also sometimes feel you are being watched? :-)
>
> As I have given the above comment with the above poor attempt of humor as an
> *alternative* to:
>
> new bigger
> copy
> delete old
>
> IMHO the vector is not really an alternative of possible in-place
> reallocation of the stuff - since it does exaclty the above - unless it has
> some optimization for PODs, and then agaon it will only attempt to "trick"
> if it has a POD inside.
(1) realloc() does not guarantee not to move elements, and actually
often does move elements.
(2) std::vector often do expand without moving elements. In
particular, if you use reserve(N) the elements of the vector will not
be moved as the size of the vector increases until the size reaches N.
When you first use push_back() the vector implementations typically
reserve additional space so that elements need not be moved again
until the size of the vector has doubled. This is a very effective
heuristic - so effective that I have stopped using reserve in ordinary
code. Furthermore, a std::vector may be optimized so that it - like
typical realloc() implementations - doesn't move elements when you
expand a newly allocated vector; it simply expands into the free block
of memory in which its elements were allocated.
In other words std::vector *is* a realistic replacement for realloc.
> That "C++ realloc" would of course need a completely new feature. If we
> wanted to base it on realloc we would still need some way to tell to
> realloc: do *not* copy the stuff. Because it is unnecessary. In case the
> reallocation happens in place we are fine. We just construct the new
> elements in the new area.
>
> Yet another attrocity to be committed in the name of optimization. Awaiting
> for further correction. ;-)
Not autrocity is needed. std::vector provides what realloc() offers,
and more.
- Bjarne Stroustrup; http://www.research.att.com/~bs
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Jakob Bieling
news:blm8fv$b8s$1...@phys-news1.kolumbus.fi...
> Bjarne Stroustrup wrote:
> > > write a language proposal what Bjarne Stroustrup will like to get
> > a "renew" > or a new_in_place or something.
> >
> > Or simply use std::vector; it can expand using resize() or push_back()
>
> Do you also sometimes feel you are being watched? :-)
>
> As I have given the above comment with the above poor attempt of humor as
an
> *alternative* to:
>
> new bigger
> copy
> delete old
>
> IMHO the vector is not really an alternative of possible in-place
> reallocation of the stuff - since it does exaclty the above - unless it
has
> some optimization for PODs, and then agaon it will only attempt to "trick"
> if it has a POD inside.
>
> That "C++ realloc" would of course need a completely new feature. If we
> wanted to base it on realloc we would still need some way to tell to
> realloc: do *not* copy the stuff. Because it is unnecessary. In case the
> reallocation happens in place we are fine. We just construct the new
> elements in the new area.
I know I might get flamed for asking this, but this is not quite clear
to me:
What is wrong with using realloc on a non-POD? I am not saying I do
this. I do not use malloc, realloc or free at all. As I understand it, all
that realloc does (assuming it could not expand, which nobody seems to have
a problem with), is allocate the requested memory somewhere else, do a
byte-wise copy and free the old memory. Why would this be a problem? A class
does not rely on the memory location it is stored at, so I would have
thought it does not matter where it is stored. So what am I missing?
regards
--
jb
(replace y with x if you want to reply by e-mail)
Emil Dotchevski
implementation of std::vector is required to copy any elements when
resized.
For example, the target platform's virtual addressing may be used to
move the content of the vector to another physical address without
changing the virtual address of the elements.
Or, it may check whether it can expand the memory buffer without
having to copy the elements so that no unnecessary copy occurs.
Besides, a standard-conforming implementation of realloc is allowed to
copy the memory every time. With std::vector, you can use reserve(),
however my experience (dare I say the experience of anyone who has
used std::vector in real-life applications) is that reserve() is
rarely needed.
--Emil
Andrea Griffini
wrote:
>(1) realloc() does not guarantee not to move elements, and actually
>often does move elements.
I agree and I rarely if ever used realloc in my C programs;
what I did often was malloc-ing using a tecnique similar
to what std::vector currently does.
Sometimes I saw code using realloc for every element
added to dynamically allocated array... and *that* is
what I thought being horrible.
>(2) std::vector often do expand without moving elements. In
>particular, if you use reserve(N) the elements of the vector will not
>be moved as the size of the vector increases until the size reaches N.
>When you first use push_back() the vector implementations typically
>reserve additional space so that elements need not be moved again
>until the size of the vector has doubled. This is a very effective
>heuristic - so effective that I have stopped using reserve in ordinary
>code. Furthermore, a std::vector may be optimized so that it - like
>typical realloc() implementations - doesn't move elements when you
>expand a newly allocated vector; it simply expands into the free block
>of memory in which its elements were allocated.
>
>In other words std::vector *is* a realistic replacement for realloc.
I think the possibility of std::vector of expanding are
thin... even thinner than for realloc. And I've serious
doubts that even an attempt can be done with template
tricks only as global user defined allocators also come
into play... and can't be known until link phase is
complete if there is a global allocator or not.
My opinion is however that realloc is a non-issue (like
is a non-issue for C).
Andrea
Attila Feher
> (1) realloc() does not guarantee not to move elements, and actually
> often does move elements.
Yep. But when it does not it definitely does not. And the function I am
looking for is better off not moving anything, just preparing the ground.
> (2) std::vector often do expand without moving elements. In
> particular, if you use reserve(N) the elements of the vector will not
> be moved as the size of the vector increases until the size reaches N.
Sure. But I am only talking about the case when it does expand. To save
copying in that case - if it is possible.
> When you first use push_back() the vector implementations typically
> reserve additional space so that elements need not be moved again
> until the size of the vector has doubled. This is a very effective
> heuristic - so effective that I have stopped using reserve in ordinary
> code. Furthermore, a std::vector may be optimized so that it - like
> typical realloc() implementations - doesn't move elements when you
> expand a newly allocated vector; it simply expands into the free block
> of memory in which its elements were allocated.
In theory it can. But unless a standard function exists (attempt to expand
in place; if not, allocate new and return either the old/new or the new
pointer) it requires standard library implementors to go deep deep under the
C library allocator and either use OS memory allocation facilities or
non-standard elements of the C library allocator.
> In other words std::vector *is* a realistic replacement for realloc.
It could be. But in real life it seems it isn't. If I make a program, no
threads, and I start to read into a vector from somewhere. I have no idea
how much I will read, I cannot use reserve. So my vector will be
reallocated. But despite of the fact that there is space (no other thread,
I read in a loop, there is nothing else allocated on the heap) for in-place
expansion the vector will keep copying all the elements. I don't know much
what tricks can modern CPUs do with virtual memory, but since we always make
the vector 1.5 times or twice the size, it will never fit "before" the last
one in memory:
-
x--
xxx----
xxxxxxx--------
essentially ending up in fragmentation.
In case of in-place expansion:
-
--
----
--------
There is no fragmentation.
Of course it is quite probable that the in-place expansion is only possible
in very small amount of the cases. I do not have statistics for that.
However it seems to be reasonable to check if in-place expansion is
possible, before going on for copying all the elements to a new place.
>> Yet another attrocity to be committed in the name of optimization.
>> Awaiting for further correction. ;-)
>
> Not autrocity is needed. std::vector provides what realloc() offers,
> and more.
In theory it can. In practice - people are coming up with proposals on
proposals to make copying cheaper.
--
Attila aka WW
Gabriel Dos Reis
| Gabriel Dos Reis wrote:
| >> As I have given the above comment with the above poor attempt of
| >> humor as an *alternative* to:
| >>
| >> new bigger
| >> copy
| >> delete old
| >>
| >> IMHO the vector is not really an alternative of possible in-place
| >> reallocation of the stuff - since it does exaclty the above - unless
| >> it has
| > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| >
| > You may be surprised by what your favorite implementation of the
| > standard library does with vector<T>::resize.
|
| I would be surprised. First of all I have no favoriute one.
Ah. The important thing is that you have one ;-p
| Second is the ones I remember does exactly what I have described.
Consider bugging your suppliers or switch to an implementation that
does what you want.
| Remember: I am not talking about vectors of PODs!
Don't worry.
| > [...]
| >
| >> That "C++ realloc" would of course need a completely new feature.
| >> If we
| >
| > No, it would not. vector<T>::resize is sufficient.
|
| In your world. In mine doing twice the work just because there is no in
| place realloc for non-PODs is not sufficient.
Contrary to what you wrote earlier, vector<T>::resize in most
implementations try alternatives before allocating new storage. Look
at the GNU implementation for example; I'm pretty sure many vendors
out there do something similar.
| >> wanted to base it on realloc we would still need some way to tell to
| >> realloc: do *not* copy the stuff. Because it is unnecessary. In
| >> case the reallocation happens in place we are fine. We just
| >> construct the new elements in the new area.
| >
| > Did you bother looking at existings implementation of
| > vector<T>::resize?
|
| Did you bother to read and try to understand what I wrote?
Yes.
| I am getting really tired of you turning everything back on me.
In fact you're getting tired of your *believing* someone is turning
everything back on you. Free yourself of that idea and you'll see
the light (TM).
| In this thread as well as in the lvalue thread.
In which you've succeeded in turning questions directed to make clear
the difficulty of the issue into something you believe is directed
against you.
| If you have something concrete to say: say it so.
| If all you have is innuendos then I for one are not interested in them.
Another alternative is that you're trying to see things that are not.
| BTW just to check how justified are your questions I looked at the STL which
| happens to be installed on my PC here. It does:
I would be very helpful if you could name the vendor or the supplier
of that implementation.
| allocate new
| copy old stuff
| deallocate old
|
| Just as I wrote. Instead of:
|
| Try to increase in place
| if worked use the new space
| if not
| allocate new
| copy old stuff
| deallocate old
There are free implementations ought there that do try alternatives
before allocating new chuncks.
And more importantly, remember that realloc() is not obliged to
reallocate in place. It can return a pointer different from its
argument.
--
Gabriel Dos Reis
g...@integrable-solutions.net
Gabriel Dos Reis
| Francis Glassborow wrote:
| [SNIP]
| > But std::vector is a Standard Library template and so it CAN use
| > special handling. It can even 'know' if it is possible to extend the
| > current allocation regardless of the PODness of the elements.
|
| Yes. But unless there is C library support for this writers of portable
| standard library implementations will be unable to provide this service
| without significant effort.
Can you elaborate on why there would be a need of "C library support"?
--
Gabriel Dos Reis
g...@integrable-solutions.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Attila Feher
> Correct me if I'm wrong, but I don't think a standard-conforming
> implementation of std::vector is required to copy any elements when
> resized.
>
> For example, the target platform's virtual addressing may be used to
> move the content of the vector to another physical address without
> changing the virtual address of the elements.
>
> Or, it may check whether it can expand the memory buffer without
> having to copy the elements so that no unnecessary copy occurs.
Yes. But that forces the standard library implementors to go deep down into
OS memory access. They cannot build the vector implementation on top of a C
(like) standard library call.
> Besides, a standard-conforming implementation of realloc is allowed to
> copy the memory every time.
Sure. But then it is a QoI issue. However it is easier to get the C++
standard library to make something like this in-place expand if it can be
based on a rudimentary support (like malloc for allocations). Important to
note that it would most probably not be the realloc function, because it
does too much.
> With std::vector, you can use reserve(),
> however my experience (dare I say the experience of anyone who has
> used std::vector in real-life applications) is that reserve() is
> rarely needed.
It depends. We did need to use it at places wuite heavily, when we had to
convert vector A to vector B and B was expensive to default construct.
Think about a sort of adaptor.
--
Attila aka WW
Sergey P. Derevyago
> In other words std::vector *is* a realistic replacement for realloc.
can't be _directly_ used in "OO-environment".
On the other side the (absent) realloc_if_you_can() functionality would be of
a great value as it supports the famous zero-overhead rule.
PS Yet another example of an overloaded requrements: realloc() does two things
simultaneosly while we need only one.
--
With all respect, Sergey. http://cpp3.virtualave.net/
mailto : ders at skeptik.net
Attila Feher
> I know I might get flamed for asking this, but this is not quite
> clear to me:
Prepare, aim fire:
http://www.atwphoto.com/flame.htm
;-)
> What is wrong with using realloc on a non-POD?
It copies without using the copy-constructor and it fails to destroy the
originals.
> I am not saying I do this.
Phew. :-)
> I do not use malloc, realloc or free at all.
> As I understand it, all that realloc does
> (assuming it could not expand, which nobody
> seems to have a problem with),
Well, the only way to ensure it *can* expand is to know how much space you
need in advance... in which case you can use std::vector::reserve and be
done width it.
> is allocate the requested memory somewhere else,
> do a byte-wise copy and free the old memory. Why
> would this be a problem?
Because the class has to be copied using its copy constructor.
> A class does not rely on the memory location
> it is stored at, so I would have thought it does not matter where it
> is stored. So what am I missing?
A class usually does not store references to itself, but I have seen such
flawed designs as well:
template <class T>
struct point : std::pair<T,T> {
// stuff
point() : x(this->first), x(this->second) {;}
T &x;
T &Y;
};
This is just an example to show the idea. It may be full of (even syntax)
errors.
The more usual case is that "other places" know about the class. Meaning
that the class registers itself on creation by giving its this pointer away
or something similar.
So in general the only "legal" way (right now) to move an object is to
either copy (or assign if already constructed) it to the new place and
destroy the old one. If someone finds out a syntax to differentiate the
copy/move construction it might be then the move constructor. But it may
not be and does not need to be a bitwise copy.
--
Attila aka WW
Thomas Richter
> What is wrong with using realloc on a non-POD?
realloc does a very basic byte-wise copy in case it cannot grow the
memory region. Instead, it allocates a new region, and performs a raw
memory copy from the old to the freshly allocated memory.
Thus, it performs a shallow assignment (implicitly) that is likely to be
unsuitable for non-POD types. Even for PODs, this can cause problems in
case some other classes hold pointers to the objects to be re-alloced.
But then, classes that cannot be copied by shallow assignment should not
be designed as PODs in first place.
I think it more or less boils down to
"realloc is evil, use std::vector" (-;
Even in C, I look very suspicious at programs that use realloc() on
anything more than a vector of int. (-;
> Why would this be a problem? A class
> does not rely on the memory location it is stored at,
Uhoh, not so. Here's a simple example:
class List {
...
class Node {
List *Parent; // useful for effective removal/traversal...
..
public:
Node(List *parent)
: Parent(parent)
{ }
}...
...
};
Now, what happens if you perform a shallow copy of a list? Instead, this
class should have an assignment operator that "bents all the pointers back
in place". realloc() doesn't know that. The same would happen if List
would be (inapropriately, though) be a POD. A proper design cannot use PODs
here.
So long,
Thomas
Tim Rowe
wrote:
>"WW" <wo...@freemail.hu> :news1.kolumbus.fi>
>
> > > For "malloc" in C, we have "new" in c++. For "realloc" in C, what
we
> > > have in C++?
> >
> > new bigger
> > copy
> > delete old
> >
> > OR
> >
> > write a language proposal what Bjarne Stroustrup will like to get a
"renew"
> > or a new_in_place or something.
>
>Or simply use std::vector; it can expand using resize() or push_back()
Ok if it's a linear structure. If it's not -- if it's a
multi-dimensional array, for instance -- using std::vector always
seems very cumbersome. Maybe I'm missing something? How would you set
up a 3x3 array of doubles initialised to 1s on the major diagonal, 0s
off the diagonal using std::vector? Lets ignore the dynamic allocation
and how I'm planning to use it for the moment, just how we can easily
create and initialise the thing.
Gabriel Dos Reis
| Emil Dotchevski wrote:
| > Correct me if I'm wrong, but I don't think a standard-conforming
| > implementation of std::vector is required to copy any elements when
| > resized.
| >
| > For example, the target platform's virtual addressing may be used to
| > move the content of the vector to another physical address without
| > changing the virtual address of the elements.
| >
| > Or, it may check whether it can expand the memory buffer without
| > having to copy the elements so that no unnecessary copy occurs.
|
| Yes. But that forces the standard library implementors to go deep down into
| OS memory access. They cannot build the vector implementation on top of a C
| (like) standard library call.
Can you clarify the reasons for this insistance on having implementors
implement the standard library on top of "a (like) standard library call"?
--
Gabriel Dos Reis
g...@integrable-solutions.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
WW
>> In your world. In mine doing twice the work just because there is
>> no in place realloc for non-PODs is not sufficient.
>
> Contrary to what you wrote earlier, vector<T>::resize in most
> implementations try alternatives before allocating new storage. Look
> at the GNU implementation for example; I'm pretty sure many vendors
> out there do something similar.
What I was writing about *is* the GNU implementation. And at least the one
which I have here does not try to expand in place. If it runs out of
capacity it allocates new, copies and deletes old.
>> If you have something concrete to say: say it so.
>> If all you have is innuendos then I for one are not interested in
>> them.
>
> Another alternative is that you're trying to see things that are not.
Or may be not.
Can someone define lvaleue?/Can *you* define expression?
Vectors could benefit from possible in-place expansion./You only say that
because you have never seen a vector implementation.
> There are free implementations ought there that do try alternatives
> before allocating new chuncks.
Yeah. Apparently the GNU one. Which I was looking at (MingW 3.2).
> And more importantly, remember that realloc() is not obliged to
> reallocate in place. It can return a pointer different from its
> argument.
Yes. That is the reason that I have said another is needed.
--
WW aka Attila
WW
> "WW" <wo...@freemail.hu> writes:
>
>> Francis Glassborow wrote:
>> [SNIP]
>>> But std::vector is a Standard Library template and so it CAN use
>>> special handling. It can even 'know' if it is possible to extend the
>>> current allocation regardless of the PODness of the elements.
>>
>> Yes. But unless there is C library support for this writers of
>> portable standard library implementations will be unable to provide
>> this service without significant effort.
>
> Can you elaborate on why there would be a need of "C library support"?
I did. In at least 3 posts.
--
WW aka Attila
Gabriel Dos Reis
| On 4 Oct 2003 04:40:27 -0400, b...@research.att.com (Bjarne Stroustrup)
| wrote:
|
| >"WW" <wo...@freemail.hu> :news1.kolumbus.fi>
| >
| > > > For "malloc" in C, we have "new" in c++. For "realloc" in C, what
| we
| > > > have in C++?
| > >
| > > new bigger
| > > copy
| > > delete old
| > >
| > > OR
| > >
| > > write a language proposal what Bjarne Stroustrup will like to get a
| "renew"
| > > or a new_in_place or something.
| >
| >Or simply use std::vector; it can expand using resize() or push_back()
|
| Ok if it's a linear structure. If it's not -- if it's a
| multi-dimensional array, for instance -- using std::vector always
| seems very cumbersome. Maybe I'm missing something? How would you set
| up a 3x3 array of doubles initialised to 1s on the major diagonal, 0s
| off the diagonal using std::vector?
How do you currently do that with alternatives to std::vector?
--
Gabriel Dos Reis
g...@integrable-solutions.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Jerry Feldman
em...@collectivestudios.com (Emil Dotchevski) wrote:
> Besides, a standard-conforming implementation of realloc is allowed to
> copy the memory every time.
The C standard defines behavior not implementation. Many times Malloc(3)
will allocate much more than is requested. Most implementations only
perform copy operations when realloc(3) is unable to grow the block.
IMHO: malloc(3), realloc(3), calloc(3) and free(3) should be avoided in
C++ because they do not call constructors or (in the case of free)
destructors. This does not mean not to use them,, but they should be
used only in the context where the programmer understands the underlying
differences between these and the new/delete C++ operators.
--
Jerry Feldman <gaf-nospam-at-blu.org>
Boston Linux and Unix user group
http://www.blu.org PGP key id:C5061EA9
PGP Key fingerprint:053C 73EC 3AC1 5C44 3E14 9245 FB00 3ED5 C506 1EA9
Jerry Feldman
Thomas Richter <th...@cleopatra.math.tu-berlin.de> wrote:
> realloc does a very basic byte-wise copy in case it cannot grow the
> memory region. Instead, it allocates a new region, and performs a raw
> memory copy from the old to the freshly allocated memory.
>
> Thus, it performs a shallow assignment (implicitly) that is likely to
> be unsuitable for non-POD types. Even for PODs, this can cause
> problems in case some other classes hold pointers to the objects to be
> re-alloced.
Different implementations do it differently. As I mentioned, the C
standard defines a behavior. It is legal for a realloc implementation to
always perform a memory copy, but just as legal for it to perform a
memory copy only when it must allocate new memory in order to grow.
I fully agree with the fact that realloc(3) should not be used in C++
for the reasons that you pointed out.
--
Jerry Feldman <gaf-nospam-at-blu.org>
Boston Linux and Unix user group
http://www.blu.org PGP key id:C5061EA9
PGP Key fingerprint:053C 73EC 3AC1 5C44 3E14 9245 FB00 3ED5 C506 1EA9
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Emil Dotchevski
> OS memory access. They cannot build the vector implementation on top of a C
> (like) standard library call.
Without OS memory access, you can't even provide an implementation for
malloc. I fail to see why malloc can use the OS memory functions, and
std::vector can not. Clearly, an implementation of a standard library,
regardless if it is C or C++, is *not* platform independent. It is not
even portable between different compilers on the same platform!
> > Besides, a standard-conforming implementation of realloc is allowed to
> > copy the memory every time.
>
> Sure. But then it is a QoI issue. However it is easier to get the C++
> standard library to make something like this in-place expand if it can be
> based on a rudimentary support (like malloc for allocations). Important to
> note that it would most probably not be the realloc function, because it
> does too much.
Indeed. So, it turns out, you do need some support beyond what you get
from the standard C library. Which is my point precisely: either way,
it can not be based on a C standard function, therefore it is based on
some kind of non-standard OS functionality. If it is
platform-dependent solution anyway, then std::vector itself will be
optimal, would it not?
> > With std::vector, you can use reserve(),
> > however my experience (dare I say the experience of anyone who has
> > used std::vector in real-life applications) is that reserve() is
> > rarely needed.
>
> It depends. We did need to use it at places wuite heavily, when we had to
> convert vector A to vector B and B was expensive to default construct.
> Think about a sort of adaptor.
"Premature optimization is the root of all evil."
Are you saying that you tried with and without reserve(), and do you
have any hard data in support of your claim that you got a significant
performance boost out of using reserve()?
Note, I am not arguing that such cases do not exist; they definitely
do exist. I am questioning whether or not your decision to employ
reserve() was dictated by profiling data, or by your *assumption* that
it is necessary.
Also, a lot of times when resizing a vector is too costly, using
std::deque does the trick rather nicely. Yet another alternative to
using reserve().
--Emil
Emil Dotchevski
trying to make, which is:
The C++ standard does *not* mandate that resize() or push_back() do
*any* copying of elements. It only says that it *may*, but only if the
allocated reserve has been exhausted.
A perfectly conforming (dare I say straight-forward) implementation of
std::vector may use the virtual addressing features of the target
platform so that the elements are *never* copied around. There is no
need to change anything in the C++ standard or anywhere else in order
to allow compilers to do just that.
All of the above means that std::vector is at least as optimal as
realloc, with the added benefit that client code may reserve certain
amount of memory to ensure optimal performance. Which is why most
responders in this thread have recommended using std::vector::resize
instead of realloc, for PODs or anything else.
Now, I have the feeling you don't agree with some/most of the above.
If so, can you please be specific, and specify what other solutions do
you recommend? Do you propose a change in the C++ standard, do you
have recommendation to compiler vendors, in general, what is that bugs
you, I honestly don't understand...
--Emil
Gabriel Dos Reis
| Gabriel Dos Reis wrote:
| > "WW" <wo...@freemail.hu> writes:
| >
| >> Francis Glassborow wrote:
| >> [SNIP]
| >>> But std::vector is a Standard Library template and so it CAN use
| >>> special handling. It can even 'know' if it is possible to extend the
| >>> current allocation regardless of the PODness of the elements.
| >>
| >> Yes. But unless there is C library support for this writers of
| >> portable standard library implementations will be unable to provide
| >> this service without significant effort.
| >
| > Can you elaborate on why there would be a need of "C library support"?
|
| I did. In at least 3 posts.
It would be helpful if you could give references to such messages. I've
seen the above repeated assertions, but no reason for the need of a
"C library support".
--
Gabriel Dos Reis
g...@integrable-solutions.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Gabriel Dos Reis
| Gabriel Dos Reis wrote:
| >> In your world. In mine doing twice the work just because there is
| >> no in place realloc for non-PODs is not sufficient.
| >
| > Contrary to what you wrote earlier, vector<T>::resize in most
| > implementations try alternatives before allocating new storage. Look
| > at the GNU implementation for example; I'm pretty sure many vendors
| > out there do something similar.
|
| What I was writing about *is* the GNU implementation.
Then, you write wrong. The GNU implementation does not
uncondicationnaly do
allocate new
copy old stuff
deallocate old
[...]
| Vectors could benefit from possible in-place expansion./You only say that
| because you have never seen a vector implementation.
Quite possible. I'm maitaining one.
--
Gabriel Dos Reis
g...@integrable-solutions.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Samuel Krempp
>> In other words std::vector *is* a realistic replacement for realloc.
>
> It could be. But in real life it seems it isn't. If I make a program, no
> threads, and I start to read into a vector from somewhere. I have no idea
> how much I will read, I cannot use reserve. So my vector will be
> reallocated. But despite of the fact that there is space (no other
> thread, I read in a loop, there is nothing else allocated on the heap) for
> in-place
> expansion the vector will keep copying all the elements. I don't know
> much what tricks can modern CPUs do with virtual memory, but since we
> always make the vector 1.5 times or twice the size, it will never fit
> "before" the last one in memory:
you do realize that, if the allocated space is doubled by std::vecetor every
time it is required to grow,
let N be the final size of the vector,
let p be ceil(log(N)/log(2))
the final doubling will allocate for 2^p elements, and copy 2^(p-1) elements
so there will be a total of
1 + 2 + 4 + 8 + ... + 2^(p-1) = 2^p-1 < 2N copyings of elements.
and thus all the copying done will just result in the whole operation
causing at most 2N copyings. that wont have a tremendous impact on the
operation.
And this technique doesnt rely on any specificity of the platform, nor
particular current situation of the memory.
> -
> x--
> xxx----
> xxxxxxx--------
>
> essentially ending up in fragmentation.
>
> In case of in-place expansion:
> -
> --
> ----
> --------
>
> There is no fragmentation.
I don't understand. What do the x's stand for ? and what do you call
fragmentation here ? (the allocated memory of the vector is always
contiguous, what fragmentation could there be..)
> Of course it is quite probable that the in-place expansion is only
> possible
> in very small amount of the cases. I do not have statistics for that.
I dont know much about the workings of the virtual memory of my OS.
but I'd expect it very rarely has the luxury to prepare 800 MB of contiguous
memory addresses to a program asking for 400MB. so, for any decent size
vector expected to grow quite a bit, you'll probably end-up copying sooner
or later, and using OS specific allocation tricks just dont get you
anything more than what you have with clever vector growing scheme.
> However it seems to be reasonable to check if in-place expansion is
> possible, before going on for copying all the elements to a new place.
I suspect this eventuality is just too rare to really matter. (it might be
frequent for small sizes though, but then you don't care)
--
Samuel.Krempp
cout << "@" << "crans." << (is_spam ? "trucs.en.trop." : "" )
<< "ens-cachan.fr" << endl;
Falk Tannhäuser
>
> For "malloc" in C, we have "new" in c++. For "realloc" in C, what we have in C++?
However, take also a look at the article
http://www.moderncppdesign.com/publications/cuj-12-2001.php
for a proposition of an improved approach.
Falk
ka...@gabi-soft.fr
news:<8o02ov881en15teiq...@4ax.com>...
> >(1) realloc() does not guarantee not to move elements, and actually
> >often does move elements.
> I agree and I rarely if ever used realloc in my C programs; what I did
> often was malloc-ing using a tecnique similar to what std::vector
> currently does. Sometimes I saw code using realloc for every element
> added to dynamically allocated array... and *that* is what I thought
> being horrible.
I think that there is some history involved. Back when I started C,
dynamic memory wasn't used very much. If you were calling realloc, most
of the time, no one else would be allocating any memory between those
calls. And with the implementations I saw back then, sooner or later,
your block would have migrated to the end of the free space arena, and
copying would be rare.
Once you start using dynamic memory for several different things (and
it's hard to imagine a C++ program, of even a modern C program, which
doesn't), this stops working, and realloc starts copying a lot.
--
James Kanze GABI Software mailto:ka...@gabi-soft.fr
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
Thomas Richter
> A perfectly conforming (dare I say straight-forward) implementation of
> std::vector may use the virtual addressing features of the target
> platform so that the elements are *never* copied around. There is no
> need to change anything in the C++ standard or anywhere else in order
> to allow compilers to do just that.
Ok, realisticly speaking: How many compilers/libraries do you know
that do that? (Me: Zero ;-) Besides, MMU remapping has a certain
granularity, defined by the page size of the used MMU (typically, 4K
on today's systems), and you would need to align your data structures
to 4K boundaries to ensure that everything can be enlarged by MMU
usage. While all of the above sounds pretty nice in theory, I doubt it
has any relevance in practical implementations of realloc(), resize
and friends.
> All of the above means that std::vector is at least as optimal as
> realloc, with the added benefit that client code may reserve certain
> amount of memory to ensure optimal performance.
realloc() could use the very same trick if required. ANSI-C says nothing
about how the "physical memory layout" shall look like, except that realloc
shall return one larger "logical" chunk of memory.
> If so, can you please be specific, and specify what other solutions do
> you recommend? Do you propose a change in the C++ standard, do you
> have recommendation to compiler vendors, in general, what is that bugs
> you, I honestly don't understand...
As far as I'm concerned: "Don't do that. realloc() is evil." (-; Almost
the same holds for the vector operations; they are "sane" in the sense
that they do respect the language (unlike realloc() with its plain
dumb memory move attempt) but possibly still "expensive" in terms of
run-time or memory. In most situations I encountered, using
"intrinsically dynamic" structures like linked lists is a much easier
and straight solution to the problem.
So long,
Thomas
ka...@gabi-soft.fr
news:<m3wubir...@uniton.integrable-solutions.net>...
> Tim Rowe <tim@remove_if_not_spam.digitig.co.uk> writes:
> | Ok if it's a linear structure. If it's not -- if it's a
> | multi-dimensional array, for instance -- using std::vector always
> | seems very cumbersome. Maybe I'm missing something? How would you
> | set up a 3x3 array of doubles initialised to 1s on the major
> | diagonal, 0s off the diagonal using std::vector?
> How do you currently do that with alternatives to std::vector?
double a[ 3 ][ 3 ] = {
{ 1.0, 0.0, 0.0 },
{ 0.0, 1.0, 0.0 },
{ 0.0, 0.0, 1.0 } } ;
A bit simpler than with std::vector, I think.
--
James Kanze GABI Software mailto:ka...@gabi-soft.fr
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
ka...@gabi-soft.fr
news:<blrl5o$lmv$1...@newstree.wise.edt.ericsson.se>...
> > A class does not rely on the memory location it is stored at, so I
> > would have thought it does not matter where it is stored. So what am
> > I missing?
> A class usually does not store references to itself,
Perhaps not explicitly, but most implementations I've seen of virtual
base classes do use pointers within the class. And it isn't rare to
pass a pointer to the class to a member.
More generally (and this is a problem with std::vector as well), moving
things is dangerous, since others might have pointers to them.
--
James Kanze GABI Software mailto:ka...@gabi-soft.fr
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
WW
> It seems you are missing the point many people, including myself, are
> trying to make, which is:
>
> The C++ standard does *not* mandate that resize() or push_back() do
> *any* copying of elements. It only says that it *may*, but only if the
> allocated reserve has been exhausted.
I have never claimed it does.
> A perfectly conforming (dare I say straight-forward) implementation of
> std::vector may use the virtual addressing features of the target
> platform so that the elements are *never* copied around. There is no
> need to change anything in the C++ standard or anywhere else in order
> to allow compilers to do just that.
Virtual addressing features are (AFAIK) unable to do that, since all they do
is map virtual addresses to physical ones. But that is not the issue. The
issue is to use such services the standard library allocators will get
system specific and their implementors have to gain a lot of system specific
knowledge.
> All of the above means that std::vector is at least as optimal as
> realloc,
In theory. In practice people are looking for making copying (ehem, moving)
objects faster, even in language change proposals.
> with the added benefit that client code may reserve certain
> amount of memory to ensure optimal performance.
Yes. And I like it. I was not saying it is wrong. :-)
> Which is why most
> responders in this thread have recommended using std::vector::resize
> instead of realloc, for PODs or anything else.
Yes. And I have said that realloc is *not* appropriate for it. What I was
suggesting to *consider* a function along the lines of:
void *attempt_realloc( void *ptr, size_t newsize);
realloc does too much.
> Now, I have the feeling you don't agree with some/most of the above.
Not at all.
> If so, can you please be specific, and specify what other solutions do
> you recommend?
I was thinking about a C library function which attempts to expand (or
shrinks) memory in place. If it cannot, returns a 0 pointer. If such an
attempt (check if it fits) is feasible to do (fast), it seems to make sense
to consider such a function. IMHO if we have a layer for dynamic memory
allocation (the C layer) it makes sense to make it complete. realloc could
be defined in terms of the above function, malloc and copying.
> Do you propose a change in the C++ standard, do you
> have recommendation to compiler vendors, in general,
> what is that bugs you, I honestly don't understand...
Yes, it seems to be hard to understand since I guess many of those people
who have answered did not understand my point before answering. So we go 90
degrees differing directions. :-)
What I mean is that such a new "attempt_realloc" (and possibly a form of the
new operator based on it) could enable a "back door" to library
implementers. They would not need to know any special, platform dependent
"tricks" to take advantage of a possible in-place-expansion.
if (can expand in place) then
be happy
done
otherwise
be sad
allocate new
copy old
release old
done
Now this only makes sense if "if (can expand in place)" is "cheap enough".
I do not say it is a paramount issue. But realloc does too much, and making
vector (allocator) to know about how to expand in place is like asking my
car to know how to refine oil. At least it feels like it.
--
WW aka Attila
WW
>> What I was writing about *is* the GNU implementation.
>
> Then, you write wrong. The GNU implementation does not
> uncondicationnaly do
>
> allocate new
> copy old stuff
> deallocate old
If you have something to say, please say it.
The one implementation I have looked at (3.2 MingW) does it. If it runs out
of capacity (while calling insert), which was the context of this
discussion. At least the vector implementation I have followed in my
installation does that. If you think it does not, please post why and what
do you think what does it do. Otherwise I am giving up. I give you
concrete questions/answers. All I get back is vague statements that I say
something wrong. And they are about as concrete as the famous error
message: There was an error.
It is absolutely possible that what I say is wrong. What will not help me
to see where I am wrong is what you do.
--
WW aka Attila
WW
[SNIP]
> and thus all the copying done will just result in the whole operation
> causing at most 2N copyings. that wont have a tremendous impact on the
> operation.
> And this technique doesnt rely on any specificity of the platform, nor
> particular current situation of the memory.
If you are using push_back to add the elements make that 3N copying.
>> -
>> x--
>> xxx----
>> xxxxxxx--------
>>
>> essentially ending up in fragmentation.
>>
>> In case of in-place expansion:
>> -
>> --
>> ----
>> --------
>>
>> There is no fragmentation.
>
> I don't understand. What do the x's stand for ? and what do you call
> fragmentation here ? (the allocated memory of the vector is always
> contiguous, what fragmentation could there be..)
x is the old memory "freed". The "heap" is fragmented.
>> Of course it is quite probable that the in-place expansion is only
>> possible
>> in very small amount of the cases. I do not have statistics for
>> that.
>
> I dont know much about the workings of the virtual memory of my OS.
> but I'd expect it very rarely has the luxury to prepare 800 MB of
> contiguous memory addresses to a program asking for 400MB.
Where did I say it does?
> so, for
> any decent size vector expected to grow quite a bit, you'll probably
> end-up copying sooner or later,
You seem to think that copying will always involve copying. But here we
talk about copy construction and then destruction of the old elements. And
those may very well do more than just copy the memory.
> and using OS specific allocation
> tricks just dont get you anything more than what you have with clever
> vector growing scheme.
Because?
>> However it seems to be reasonable to check if in-place expansion is
>> possible, before going on for copying all the elements to a new
>> place.
>
> I suspect this eventuality is just too rare to really matter. (it
> might be frequent for small sizes though, but then you don't care)
I tend to believe that if anyone has ever measured it.
--
WW aka Attila
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Gabriel Dos Reis
| Gabriel Dos Reis <g...@integrable-solutions.net> wrote in message
| news:<m3wubir...@uniton.integrable-solutions.net>...
| > Tim Rowe <tim@remove_if_not_spam.digitig.co.uk> writes:
|
| > | Ok if it's a linear structure. If it's not -- if it's a
| > | multi-dimensional array, for instance -- using std::vector always
| > | seems very cumbersome. Maybe I'm missing something? How would you
| > | set up a 3x3 array of doubles initialised to 1s on the major
| > | diagonal, 0s off the diagonal using std::vector?
|
| > How do you currently do that with alternatives to std::vector?
|
| double a[ 3 ][ 3 ] = {
| { 1.0, 0.0, 0.0 },
| { 0.0, 1.0, 0.0 },
| { 0.0, 0.0, 1.0 } } ;
|
| A bit simpler than with std::vector, I think.
If you do it that way, i.e. your array "a" has fixed size, most
certainly, you don't do realloc. Do you?
For any useful purpose, I recall that my previous message was a query
for further information to a question (still present above) asked
after this suggestion"
# Or simply use std::vector; it can expand using resize() or push_back()
which itself was made after a question about realloc() in C++.
-- Gaby
Emil Dotchevski
> new operator based on it) could enable a "back door" to library
> implementers. They would not need to know any special, platform dependent
> "tricks" to take advantage of a possible in-place-expansion.
Do you propose a change to the C standard so that implementers are
required to supply attempt_realloc?
Do you propose a change to the C++ standard so that implementers are
required to supply attempt_realloc?
Neither of these two is feasable.
If you do not propose a change to any of the ANSI standards, then
attempt_realloc is non-standard (duh!), so it can not be used by any
of what you call "universal" standard libraries. Which makes them
dependent on a particular compiler/platform, which makes it possible
to use *any* feature available on that platform. If that's the case,
who cares how it works -- the important thing is that
std::vector::resize is -- in theory at least -- as fast as realloc.
And finally, there is no such thing as universal standard library.
Every C compiler comes with its own implementation of malloc, right?
Same thing with the standard C++ library. What comes with your
compiler is THE standard library. There are no others. The standard
library may even be "built-in" the compiler, without any external
source files.
--Emil
Gabriel Dos Reis
"WW" <wo...@freemail.hu> writes:
| Gabriel Dos Reis wrote:
| >> What I was writing about *is* the GNU implementation.
| >
| > Then, you write wrong. The GNU implementation does not
| > uncondicationnaly do
| >
| > allocate new
| > copy old stuff
| > deallocate old
|
| If you have something to say, please say it.
It was all there, awaiting you to read it.
Your assertion about the GNU implementation is wrong. Full stop.
| The one implementation I have looked at (3.2 MingW) does it. If it runs out
| of capacity (while calling insert), which was the context of this
^^^^^^^^
Please don't change your assertion.
The assertion that has been questioned so far is:
As I have given the above comment with the above poor attempt of
humor as an *alternative* to:
new bigger
copy
delete old
IMHO the vector is not really an alternative of possible in-place
reallocation of the stuff - since it does exaclty the above -
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
unless it has some optimization for PODs, and then agaon it will
only attempt to "trick" if it has a POD inside.
in response to Bjarne's suggestion:
> Or simply use std::vector; it can expand using resize() or push_back()
I invited you to have a look at existing implementation. You
mentioned the GNU implementation. But the *fact* is that the GNU
implementation does not do a reallocation unconditionally, i.e. it
does not do your "since it does exaclty the above".
In reality, in the GNU implementation, vector<T>::resize can realize
that it has enough memory left (from a previous allocation) and not do
any "new bigger; copy; delete old".
| discussion. At least the vector implementation I have followed in my
| installation does that. If you think it does not, please post why and what
| do you think what does it do. Otherwise I am giving up. I give you
| concrete questions/answers. All I get back is vague statements that I say
| something wrong. And they are about as concrete as the famous error
| message: There was an error.
|
| It is absolutely possible that what I say is wrong.
That is what many people, including myself, have been telling you.
| What will not help me to see where I am wrong is what you do.
Help yourself and the world will help you.
Your repeated untrue assertion is not my fault. I've invited you to
(carefully) look at existing pratice. You cited the GNU
implementation. Alas, that claim again is untrue. And that is NOT my
fault.
--
Gabriel Dos Reis
g...@integrable-solutions.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Attila Feher
>> What I mean is that such a new "attempt_realloc" (and possibly a
>> form of the new operator based on it) could enable a "back door" to
>> library implementers. They would not need to know any special,
>> platform dependent "tricks" to take advantage of a possible
>> in-place-expansion.
>
> Do you propose a change to the C standard so that implementers are
> required to supply attempt_realloc?
>
> Do you propose a change to the C++ standard so that implementers are
> required to supply attempt_realloc?
>
> Neither of these two is feasable.
Because?
--
Attila aka WW
Tim Rowe
<g...@integrable-solutions.net> wrote:
>Tim Rowe <tim@remove_if_not_spam.digitig.co.uk> writes:
>| Ok if it's a linear structure. If it's not -- if it's a
>| multi-dimensional array, for instance -- using std::vector always
>| seems very cumbersome. Maybe I'm missing something? How would you set
>| up a 3x3 array of doubles initialised to 1s on the major diagonal, 0s
>| off the diagonal using std::vector?
>
>How do you currently do that with alternatives to std::vector?
Syntactically in a similar way to the way I'd do it with vectors; I'd
set up an array of [ ]'s instead of a vector of vectors, then loop
over them to initialise them. But when I try to do it with vectors I
always seem to find myself creating an awful lot of temporary vectors
and elements, which I don't find myself doing when using [ ]s. Ok, it
doesn't matter much with a 3x3 of ints, but if it were a bigger array,
and the ints were instead classes that were expensive to construct --
am I missing an incantation that would let me do this without all
those temporaries?
Gabriel Dos Reis
| On 6 Oct 2003 18:47:50 -0400, Gabriel Dos Reis
| <g...@integrable-solutions.net> wrote:
|
| >Tim Rowe <tim@remove_if_not_spam.digitig.co.uk> writes:
|
| >| Ok if it's a linear structure. If it's not -- if it's a
| >| multi-dimensional array, for instance -- using std::vector always
| >| seems very cumbersome. Maybe I'm missing something? How would you set
| >| up a 3x3 array of doubles initialised to 1s on the major diagonal, 0s
| >| off the diagonal using std::vector?
| >
| >How do you currently do that with alternatives to std::vector?
|
| Syntactically in a similar way to the way I'd do it with vectors; I'd
| set up an array of [ ]'s instead of a vector of vectors, then loop
| over them to initialise them. But when I try to do it with vectors I
| always seem to find myself creating an awful lot of temporary vectors
| and elements, which I don't find myself doing when using [ ]s.
Ah, I see. Actually "realloc()" is not an issue in what you're
doing. If I understand you correctly, you just want to set the size
once, and later loop over the matrix. The following might do the trick
vector<vector<double> > matrix(3, 3);
for (int i = 0; i < 3; ++i)
for (int j = 0; i < 3; ++j)
matrix[i][j] = i == j;
The above, in principle, creates no temporary, it does
direct-initialization, followed by assignments.
| Ok, it
| doesn't matter much with a 3x3 of ints, but if it were a bigger array,
| and the ints were instead classes that were expensive to construct --
| am I missing an incantation that would let me do this without all
| those temporaries?
Try the above. Let me know if I misunderstood.
-- Gaby
Andrei Alexandrescu
news:m3pthat...@uniton.integrable-solutions.net...
> "Attila Feher" <attila...@lmf.ericsson.se> writes:
>
> | Emil Dotchevski wrote:
> | > Correct me if I'm wrong, but I don't think a standard-conforming
> | > implementation of std::vector is required to copy any elements when
> | > resized.
> | >
> | > For example, the target platform's virtual addressing may be used to
> | > move the content of the vector to another physical address without
> | > changing the virtual address of the elements.
> | >
> | > Or, it may check whether it can expand the memory buffer without
> | > having to copy the elements so that no unnecessary copy occurs.
> |
> | Yes. But that forces the standard library implementors to go deep down
into
> | OS memory access. They cannot build the vector implementation on top of
a C
> | (like) standard library call.
>
> Can you clarify the reasons for this insistance on having implementors
> implement the standard library on top of "a (like) standard library call"?
I guess that's the case with the default allocator, which at the end of the
day is required to grab memory with new[]. Right?
Andrei
Gabriel Dos Reis
The default allocator uses operator new(). Yes. So?
-- Gaby
Emil Dotchevski
> > required to supply attempt_realloc?
> >
> > Do you propose a change to the C++ standard so that implementers are
> > required to supply attempt_realloc?
> >
> > Neither of these two is feasable.
>
> Because?
It can not be added in the C++ standard, because malloc and free are C
functions, therefore anything that complements their functionality
belongs in the C standard.
Nobody will add something in the C standard just because it may make
it easier to write universal C++ standard library code.
--Emil
Tim Rowe
<dos...@cmla.ens-cachan.fr> wrote:
>Ah, I see. Actually "realloc()" is not an issue in what you're
>doing. If I understand you correctly, you just want to set the size
>once, and later loop over the matrix. The following might do the trick
>
> vector<vector<double> > matrix(3, 3);
>
> for (int i = 0; i < 3; ++i)
> for (int j = 0; i < 3; ++j)
> matrix[i][j] = i == j;
Hold on, I'm unconvinced again. Where did that (int, int) constructor
for vector<vector<int> > come from? It works in the first compiler I
tried, but I that;'s because it's matching
vector(
size_type _Count,
const Type& _Val
);
and the second integer is matching
vector(
size_type _Count
);
to do a cast from int to vector<int>. But the second compiler I tried
doesn't have that latter constructor. Instead it has
explicit vector(
size_type _Count
);
and sure enough your suggestion doesn't compile, because it can't do
the default conversion from int to vector<int>.
Gabriel Dos Reis
| On 9 Oct 2003 13:01:38 -0400, Gabriel Dos Reis
| <dos...@cmla.ens-cachan.fr> wrote:
|
| >Ah, I see. Actually "realloc()" is not an issue in what you're
| >doing. If I understand you correctly, you just want to set the size
| >once, and later loop over the matrix. The following might do the trick
| >
| > vector<vector<double> > matrix(3, 3);
| >
| > for (int i = 0; i < 3; ++i)
| > for (int j = 0; i < 3; ++j)
| > matrix[i][j] = i == j;
|
| Hold on, I'm unconvinced again. Where did that (int, int) constructor
| for vector<vector<int> > come from?
It comes from the template constructor
template<typename InputIterator>
vector(InputIterator first, InputIterator last);
which provides a best-match specialization
| It works in the first compiler I
| tried, but I that;'s because it's matching
| vector(
| size_type _Count,
| const Type& _Val
| );
No, this constructor cannot be used because in this case Type is
vector<int> and the constructor that could be called with a single
integer argument (to make the conversion) is explicit as you said.
That is why I remarked in my previous message that the above construct
creates no supererogatory temporaries.
| and the second integer is matching
| vector(
| size_type _Count
| );
| to do a cast from int to vector<int>. But the second compiler I tried
| doesn't have that latter constructor. Instead it has
| explicit vector(
| size_type _Count
| );
yes, this constructor is conforming.
| and sure enough your suggestion doesn't compile, because it can't do
| the default conversion from int to vector<int>.
Upgrade your compiler or library :-)
Here is an explanation of why your compiler should accept the
construct
vector<vector<double> > matrix(3, 3);
The arguments used in the object "matrix" construction are all the
same. Therefore, overload resolution selects the specialization of
the template constructor mentioned above (with InputIterator = int).
Now, there is an apparent embarassment because "int" is not an
iterator. The standard library requires (see 23.1.1/9) that, in such
situations, that instantiation should behave as if I wrote
vector<vector<double> > matrix(vector<vector<double> >::size_type(3),
static_cast<vector<double> >(3));
As you can se, the static_cast<> bypasses the "explicit"ness
# explicit vector(
# size_type _Count
# );
--
Gabriel Dos Reis
g...@integrable-solutions.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
John Potter
<tim@remove_if_not_spam.digitig.co.uk> wrote:
> On 9 Oct 2003 13:01:38 -0400, Gabriel Dos Reis
> <dos...@cmla.ens-cachan.fr> wrote:
> >Ah, I see. Actually "realloc()" is not an issue in what you're
> >doing. If I understand you correctly, you just want to set the size
> >once, and later loop over the matrix. The following might do the trick
> > vector<vector<double> > matrix(3, 3);
> > for (int i = 0; i < 3; ++i)
> > for (int j = 0; i < 3; ++j)
> > matrix[i][j] = i == j;
> Hold on, I'm unconvinced again. Where did that (int, int) constructor
> for vector<vector<int> > come from? It works in the first compiler I
> tried, but I that;'s because it's matching
> vector(
> size_type _Count,
> const Type& _Val
> );
No. It matches
template <class InputIterator>
vector (InputIterator first, InputIterator past)
When that constructor is matched by an integral type, it must have the
same effect as
vector (static_cast<size_type>(first), static_cast<value_type>(past))
See 23.1.1/9.
> and the second integer is matching
> vector(
> size_type _Count
> );
> to do a cast from int to vector<int>. But the second compiler I tried
> doesn't have that latter constructor. Instead it has
> explicit vector(
> size_type _Count
> );
> and sure enough your suggestion doesn't compile, because it can't do
> the default conversion from int to vector<int>.
It is not an implicit conversion, it is required to be an explicit
static_cast.
I'm guessing your second broken compiler does not support member
templates or the library is written to assume that it does not. The
code is valid as written. Much safer to write it explicitely because
it only works for two dimensions as shown.
vector<vector<double> > matrix(3, vector<double>(3));
That should keep your other compiler happy.
John
Attila Feher
>>> Do you propose a change to the C standard so that implementers are
>>> required to supply attempt_realloc?
>>>
>>> Do you propose a change to the C++ standard so that implementers are
>>> required to supply attempt_realloc?
>>>
>>> Neither of these two is feasable.
>>
>> Because?
>
> It can not be added in the C++ standard, because malloc and free are C
> functions, therefore anything that complements their functionality
> belongs in the C standard.
That does not mean it cannot be added. It only means it makes much more
sense to add it to the C standard.
> Nobody will add something in the C standard just because it may make
> it easier to write universal C++ standard library code.
Not necessarily. If the allocated stuff contains pointers into itself, it
is possible that C programmers could make a use of this function as well.
--
Attila aka WW
Andrei Alexandrescu
news:flsmm2y...@sel.cmla.ens-cachan.fr...
> | > Can you clarify the reasons for this insistance on having implementors
> | > implement the standard library on top of "a (like) standard library
call"?
> |
> | I guess that's the case with the default allocator, which at the end of
the
> | day is required to grab memory with new[]. Right?
>
> The default allocator uses operator new(). Yes. So?
No need to bring the heat from the past discussion on me. I did see the
light though :o). I guess "So?" really means "Well, the standard allocator
could be extended to offer more functions (such as expand), functions that
vector can know about, detect, and exploit. In that case, the entire
non-standard part would be in the library, and people can just use vector
and benefit of whatever advanced free store manipulation the implementation
provides".
That wouldn't be bad, however this state of affairs suffers of the "quod
licet Iovis, non licet bovis" syndrome: programmers don't have as much
ability to define an allocator as the standard library has, nor can they use
the extended functionality of the default allocator within the limits of the
standard.
So I do think a function that expands a chunk of memory in place would be
welcome and useful.
Andrei
Tim Rowe
<g...@integrable-solutions.net> wrote:
>| and sure enough your suggestion doesn't compile, because it can't do
>| the default conversion from int to vector<int>.
>
>Upgrade your compiler or library :-)
The library and compiler in question are Microsoft Visual C++ .net
version 2003. According to the error message, it fails specifically
because it's trying to match the constructor I quoted, and can't. Not
working with that compiler/library I consider a serious portability
issue, whatever the current standard says, as it's not a
compiler/library I'm likely to be able to ignore for some years to
come.
>iterator. The standard library requires (see 23.1.1/9) that, in such
>situations, that instantiation should behave as if I wrote
>
> vector<vector<double> > matrix(vector<vector<double> >::size_type(3),
> static_cast<vector<double> >(3));
Now, /that/ compiles on all the compilers/libraries I'm interested in!
Thanks.
Stephen Howe
> *any* copying of elements. It only says that it *may*, but only if the
> allocated reserve has been exhausted.
And if the allocated reserve has been exhausted? What then?
Can vector expand the size of the block of memory, in-situ?
It can't, because the allocator() interface is deficient.
What I would like to see as part of the allocator() interface is a member
function that resizes a previously allocated block via member function
allocate(). And unlike C's realloc() it would _NOT_ ever allocate new block,
copy the contents of the old block, free the old block. This member function
would only ever attempt to expand/shrink memory insitu. In this, it differs
from realloc()
Effectively resize() for a vector becomes :
(1) If new size is the same as old size, do nothing
(2) If new size is smaller than old size, erase surplus elements
(3) If new size is greater than old size, then
(4) If within capacity, construct new elements
(5) if capacity exceeded, call allocator resize() member function
(6) Did it succeed? Yes => construct new elements
(7) No => allocate new block, copy old elements, construct new
elements, swap blocks, destroy old elements, destroy old block.
Currently, it is steps (5) and (6) that are missing. And that means when the
capacity is exceeded, vector() is inefficient.
vector cannot go the last mile in terms of efficiency.
I would also like to see an operator renew [] and renew [] operator that
mirrors this and does exactly the same. Again, unlike realloc(), operator
renew would only ever expand/shrink a block insitu. shrink would be
guranteed to work. expand would not.
The renew [] operator would work on a previously new[]'ed block and would do
- if shrinking => call destructors
- if expanding =>
call operator renew []
if success, call default constructors
if failure,
call operator new []
if failure, throw bad_alloc
call copy constuctors, call default constructors
call destructors on old block
call operator delete [] on old block
> A perfectly conforming (dare I say straight-forward) implementation of
> std::vector may use the virtual addressing features of the target
> platform so that the elements are *never* copied around. There is no
> need to change anything in the C++ standard or anywhere else in order
> to allow compilers to do just that.
How? I don't see anything in the allocator() interface that allows vector to
do that.
> All of the above means that std::vector is at least as optimal as
> realloc...
I don't find either standard guarantees that vector or realloc() will be
efficient. They could be. But it is not guaranteed.
Underneath, for realloc() when expanding, it may be that a implementation
checks to see if memory either side of the currently allocated block is free
and in combination with the current block's size is sufficient to meet the
new memory size without asking the OS for more memory.
Stephen Howe
Shannon Barber
news:<blqu4r$hgd$06$1...@news.t-online.com>...
>
> I know I might get flamed for asking this, but this is not quite
clear
> to me:
>
> What is wrong with using realloc on a non-POD? I am not saying I
do
> this. I do not use malloc, realloc or free at all. As I understand it,
all
> that realloc does (assuming it could not expand, which nobody seems to
have
> a problem with), is allocate the requested memory somewhere else, do a
> byte-wise copy and free the old memory. Why would this be a problem? A
class
> does not rely on the memory location it is stored at, so I would have
> thought it does not matter where it is stored. So what am I missing?
The problem occurs when realloc has to move the buffer to a new spot
(reallocation was not possible, we have to malloc & copy). The
problem is that realloc does a bit blast /and/ frees the orginal
memory chunk. Now we can't copy construct the objects, because the
orignal memory space is gone. We would have to copy construct the
object ontop of itself, which is asking for trouble. It might work in
some cases, it might not in others.
Pointers to the objects themselves is no different than using vector
(or realloc) in the first place. "Iterators are invalidated". It's a
non-issue.
The next issue is self-pointing (which includes self-references).
Consider the copy ctor for such a class. It will construct the
self-pointers from the copied object - e..g it'll just work with the
ghost construction. Another non-issue.
The only trouble is things like memcpy, which are not gauranteed to
work on over-lapped memory.
Stephen Howe
> often does move elements.
But it would nice if there was a C memory allocation function that resized a
block allocated by malloc()/calloc() insitu or returned NULL if it could
not. With such a function, you could write realloc() using it. But this is
more topical in comp.lang.c.moderated :-)
> (2) std::vector often do expand without moving elements. In
> particular, if you use reserve(N) the elements of the vector will not
> be moved as the size of the vector increases until the size reaches N.
> When you first use push_back() the vector implementations typically
> reserve additional space so that elements need not be moved again
> until the size of the vector has doubled. This is a very effective
> heuristic - so effective that I have stopped using reserve in ordinary
> code. Furthermore, a std::vector may be optimized so that it - like
> typical realloc() implementations - doesn't move elements when you
> expand a newly allocated vector; it simply expands into the free block
> of memory in which its elements were allocated.
>
> In other words std::vector *is* a realistic replacement for realloc.
But what std::vector won't do is when the size() and capacity() are the same
and you wish to insert new elements, is to attempt to resize the underlying
allocated block insitu to try and avoid the copy construct-destruct cycle.
It is this extra "going the 2nd mile" step that I wish vector would do. And
if it fails, then it does do the copy construct-destruct cycle. It has run
out of options then.
Cheers
Stephen Howe
Gabriel Dos Reis
| "Gabriel Dos Reis" <dos...@cmla.ens-cachan.fr> wrote in message
| news:flsmm2y...@sel.cmla.ens-cachan.fr...
| > | > Can you clarify the reasons for this insistance on having implementors
| > | > implement the standard library on top of "a (like) standard library
| call"?
| > |
| > | I guess that's the case with the default allocator, which at the end of
| the
| > | day is required to grab memory with new[]. Right?
| >
| > The default allocator uses operator new(). Yes. So?
|
| No need to bring the heat from the past discussion on me. I did see the
I dot not intend to bring heat on you, but I'm glad you see the light :-p.
| light though :o). I guess "So?" really means "Well, the standard allocator
| could be extended to offer more functions (such as expand), functions that
| vector can know about, detect, and exploit. In that case, the entire
| non-standard part would be in the library, and people can just use vector
| and benefit of whatever advanced free store manipulation the implementation
| provides".
And I believe some implementations did that in the past.
More to the point, an implementation is free to add additional
parameter to allocator<T>::allocate that requires
in-place-expansion-or-nothing and use it (with some other
implementation-defined constructs).
It should probably be recalled that the member allocator<T>::allocate
already provides realloc()-like behaviour as far as raw memory is
concerned.
-- Gaby
Gabriel Dos Reis
| On 10 Oct 2003 15:41:57 -0400, Gabriel Dos Reis
| <g...@integrable-solutions.net> wrote:
|
|
| >| and sure enough your suggestion doesn't compile, because it can't do
| >| the default conversion from int to vector<int>.
| >
| >Upgrade your compiler or library :-)
|
| The library and compiler in question are Microsoft Visual C++ .net
| version 2003. According to the error message, it fails specifically
| because it's trying to match the constructor I quoted, and can't. Not
Then that is a bug in the compiler.
| working with that compiler/library I consider a serious portability
| issue, whatever the current standard says, as it's not a
it certainly becomes a portability issue for that compiler, but if
your description is accurate then it means that it has serious
issues with constructor templates and concersion.
| compiler/library I'm likely to be able to ignore for some years to
| come.
Nevertheless, you may probably consider submitting a bug report.
As any rate, that isn't a realloc issue.
-- Gaby
Andrei Alexandrescu
> | light though :o). I guess "So?" really means "Well, the standard
allocator
> | could be extended to offer more functions (such as expand), functions
that
> | vector can know about, detect, and exploit. In that case, the entire
> | non-standard part would be in the library, and people can just use
vector
> | and benefit of whatever advanced free store manipulation the
implementation
> | provides".
>
> And I believe some implementations did that in the past.
>
> More to the point, an implementation is free to add additional
> parameter to allocator<T>::allocate that requires
> in-place-expansion-or-nothing and use it (with some other
> implementation-defined constructs).
Cool. This doesn't, however, cure the Iovis/bovis syndrome which I noticed
in my previous post, which I'll repeat for completeness: "programmers don't
have as much ability to define an allocator as the standard library has, nor
can they use the extended functionality of the default allocator within the
limits of the standard."
> It should probably be recalled that the member allocator<T>::allocate
> already provides realloc()-like behaviour as far as raw memory is
> concerned.
Could you please expand on that?
Andrei
Gabriel Dos Reis
[...]
| > In other words std::vector *is* a realistic replacement for
realloc.
|
| But what std::vector won't do is when the size() and capacity() are
the same
| and you wish to insert new elements, is to attempt to resize the
underlying
| allocated block insitu to try and avoid the copy construct-destruct
cycle.
| It is this extra "going the 2nd mile" step that I wish vector would
do. And
| if it fails, then it does do the copy construct-destruct cycle. It has
run
| out of options then.
std::allocator<T>::allocate has been designed presumably to support
that style. Now, it may be a QoI.
--
Gabriel Dos Reis
g...@integrable-solutions.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Howard Hinnant
"Stephen Howe" <NOSPAM...@dial.pipex.com> wrote:
> But it would nice if there was a C memory allocation function that
resized a
> block allocated by malloc()/calloc() insitu or returned NULL if it
could
> not. With such a function, you could write realloc() using it. But
this is
> more topical in comp.lang.c.moderated :-)
<clears throat> Yup, I agree 100%. I posted this link eariler in this
thread but I don't think anyone followed it:
http://www.armdevzone.com/EABI/malloc_helpers.htm
This is an ARM-specific proposal to do just that: add to the
malloc/realloc/free interface in such a way as to find out if a chunk of
memory can be expanded in place. Except for the "__aeabi_" prefix, I
think it would be a good thing to drop this interface into standard
C/C++. Allocators (as in the policy class that is passed into vector)
could then write to this interface. And then vector could write to this
expanded allocator interface. And it can all be done in a backward
compatible fashion.
Yes, it is valuable to have the possibility for vector to be able to
expand in place even when size() == capacity().
> But what std::vector won't do is when the size() and capacity() are
the same
> and you wish to insert new elements, is to attempt to resize the
underlying
> allocated block insitu to try and avoid the copy construct-destruct
cycle.
> It is this extra "going the 2nd mile" step that I wish vector would
do. And
> if it fails, then it does do the copy construct-destruct cycle. It has
run
> out of options then.
Well said. This is a realistic goal. All of the technical pieces for
how to do this are in place. The major obstacles are now
standardization. And for that we need people like Stephen Howe, Attila
Feher and Andrei Alexandrescu to continue to stand up and say "Yes, we
want this!".
Thanks,
-Howard
Jerry Feldman
em...@collectivestudios.com (Emil Dotchevski) wrote:
> Every C compiler comes with its own implementation of malloc, right?
> Same thing with the standard C++ library. What comes with your
> compiler is THE standard library. There are no others. The standard
> library may even be "built-in" the compiler, without any external
> source files.
This statement is not entirely true. Some systems (mainly Unix systems)
supply the libraries but not the compilers. And in some cases. a third
party compiler may use the supplied libraries.
WRT: Standards. A standard defines behavior. An example of this (a bit
OT) might be the passing of parameters. The standards define the passing
of parameters as if they were pushed onto a stack. But, the calling
standard for several microprocessors use registers to pass parameters.
The Alpha assigns the first 6 parameters to registers, PA-RISC I believe
is 3, and MIPS I believe is 6. It is not the business of a standard to
impose implementation. The standard does not define the malloc technique
(power of 2, cartesian, etc). It also does not say anything about the
hidden head of a malloc block, which typically contains information such
as allocated size, pointers, and possibly some other information. The C
standard requires that the realloc behave as if a new block were
allocated, and the old block was copied to it and then freed. Some
versions of realloc did that regardless of what was requested. Most will
try to prevent the copy operation if possible.
--
Jerry Feldman <gaf-nospam-at-blu.org>
Boston Linux and Unix user group
http://www.blu.org PGP key id:C5061EA9
PGP Key fingerprint:053C 73EC 3AC1 5C44 3E14 9245 FB00 3ED5 C506 1EA9
Francis Glassborow
>But what std::vector won't do is when the size() and capacity() are the same
>and you wish to insert new elements, is to attempt to resize the underlying
>allocated block insitu to try and avoid the copy construct-destruct cycle.
Please give chapter and verse from the Standard if you believe this is
something that an implementation is not allowed to do. I doubt that
there is any such prohibition which means that it becomes a QoI issue.
--
Francis Glassborow ACCU
If you are not using up-to-date virus protection you should not be reading
this. Viruses do not just hurt the infected but the whole community.
Tim Rowe
<dos...@cmla.ens-cachan.fr> wrote:
>Tim Rowe <tim@remove_if_not_spam.digitig.co.uk> writes:
>
>| On 10 Oct 2003 15:41:57 -0400, Gabriel Dos Reis
>| <g...@integrable-solutions.net> wrote:
>|
>|
>| >| and sure enough your suggestion doesn't compile, because it can't do
>| >| the default conversion from int to vector<int>.
>| >
>| >Upgrade your compiler or library :-)
>|
>| The library and compiler in question are Microsoft Visual C++ .net
>| version 2003. According to the error message, it fails specifically
>| because it's trying to match the constructor I quoted, and can't. Not
>
>Then that is a bug in the compiler.
Care to point me to a 100% standard-compliant compiler (recalling a
recent thread?)
>Nevertheless, you may probably consider submitting a bug report.
Yes, I'll see if I can find out how to do that, though it seems to be
hard to be heard above the noise when reporting to Microsoft,
>As any rate, that isn't a realloc issue.
True -- I should have changed the message title, shouldn't I?
WW
> In article <3f8761fd$0$6632$cc9e...@news.dial.pipex.com>, Stephen
> Howe <NOSPAM...@dial.pipex.com> writes
>> But what std::vector won't do is when the size() and capacity() are
>> the same and you wish to insert new elements, is to attempt to
>> resize the underlying allocated block insitu to try and avoid the
>> copy construct-destruct cycle.
>
> Please give chapter and verse from the Standard if you believe this is
> something that an implementation is not allowed to do. I doubt that
> there is any such prohibition which means that it becomes a QoI issue.
Which is much easier to solve if you have a standard attempt_expand
function. Isn't it so?
--
WW aka Attila
Gabriel Dos Reis
| On 11 Oct 2003 20:15:28 -0400, Gabriel Dos Reis
| <dos...@cmla.ens-cachan.fr> wrote:
|
| >Tim Rowe <tim@remove_if_not_spam.digitig.co.uk> writes:
| >
| >| On 10 Oct 2003 15:41:57 -0400, Gabriel Dos Reis
| >| <g...@integrable-solutions.net> wrote:
| >|
| >|
| >| >| and sure enough your suggestion doesn't compile, because it can't do
| >| >| the default conversion from int to vector<int>.
| >| >
| >| >Upgrade your compiler or library :-)
| >|
| >| The library and compiler in question are Microsoft Visual C++ .net
| >| version 2003. According to the error message, it fails specifically
| >| because it's trying to match the constructor I quoted, and can't. Not
| >
| >Then that is a bug in the compiler.
|
| Care to point me to a 100% standard-compliant compiler (recalling a
| recent thread?)
This has nothing to do with a compiler being 100% standard-compiler.
And a 100% standard-compliant compiler is not necessarily useful.
The issue has just to do with compilers that accept commonly used and
useful constructs. You seem to have one, according to your previous
report.
--
Gabriel Dos Reis
g...@integrable-solutions.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Dhruv
> "Stephen Howe" <NOSPAM...@dial.pipex.com> writes:
>
> [...]
>
> | > In other words std::vector *is* a realistic replacement for
> realloc.
> |
> | But what std::vector won't do is when the size() and capacity() are
> the same
> | and you wish to insert new elements, is to attempt to resize the
> underlying
> | allocated block insitu to try and avoid the copy construct-destruct
> cycle.
> | It is this extra "going the 2nd mile" step that I wish vector would
> do. And
> | if it fails, then it does do the copy construct-destruct cycle. It has
> run
> | out of options then.
>
> std::allocator<T>::allocate has been designed presumably to support
> that style. Now, it may be a QoI.
I don't think so. Correct me if I'm wrong, but consider a vector. When a
vector needs to expand, it:
1. Allocates new memory (which could have been avoided by expanding the
currently used memory block if possibly).
2. Copies all the objects to the new memory. (This copy would also have
been avoided).
3. Destroys all the objects in the old chunk of memory. Again, avoid
destruction.
4. Frees old memory. Which potentially maay lead to fragmentation at a
later stage.
The memory usage of std::vector is such that it is bound to waste a lot of
memory, because:
1. It always acquires more memory before freeing the original.
2. The amount of memory acquired is usually (always) greater than the
memory that will be freed in the near future by the internal vector
representation.
So, the memory would look something like this:
Consider: X = Allocated; o = Free.
Initially:
oooooooooooooooooooooooooooooo
After vector contains say, 2 elements:
XXoooooooooooooooooooooooooooo
3*push_back:
ooXXXXXooooooooooooooooooooooo
5*push_back:
oooooooXXXXXXXXXoooooooooooooo
^^^^^^^
Useless free memory. After 'n' push_backs, suppose the vector needs to
grow, and there is enough physical/virtual memory available, but not after
the block occupied by the vector currenly, then vector will not be able to
expand, when in fact it should.
Regards,
-Dhruv.
Jerry Feldman
"Stephen Howe" <NOSPAM...@dial.pipex.com> wrote:
> > (1) realloc() does not guarantee not to move elements, and actually
> > often does move elements.
>
> But it would nice if there was a C memory allocation function that
> resized a block allocated by malloc()/calloc() insitu or returned NULL
> if it could not. With such a function, you could write realloc() using
> it. But this is more topical in comp.lang.c.moderated :-)
That would require a change to the standards.
IMHO, a generalized memory allocator is just that, general. One size
fits all. If these is a real need for specializing the allocator, the
application (or installation) could write their own specialized version.
For instance, I worked on a system that allocated and deallocated a
large number of small nodes in a multi-way tree. Since the malloc
overhead was very high, rather than using malloc to allocate each node,
we simply used malloc to allocate a block of nodes. I have also worked
on an (awful) implementation of C where all calls to malloc were calls
directly to the OS. And, if you failed to free any memory in that
application, the memory leak affected the entire session because the OS
treated the session as the process, and the application was a subtask.
(This was on an IBM mainframe running TSO under MVS).
Essentially, malloc(3), calloc(3), realloc(3) and free(3) are all pretty
much the same as they were before the C89 standard with some minor
details changed, such as returning a void pointer and free(3) not
returning a value.
--
Jerry Feldman <gaf-nospam-at-blu.org>
Boston Linux and Unix user group
http://www.blu.org PGP key id:C5061EA9
PGP Key fingerprint:053C 73EC 3AC1 5C44 3E14 9245 FB00 3ED5 C506 1EA9
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Gabriel Dos Reis
| > It should probably be recalled that the member allocator<T>::allocate
| > already provides realloc()-like behaviour as far as raw memory is
| > concerned.
|
| Could you please expand on that?
20.4.1.1
pointer allocate(size_type n, allocator<void>::const_pointer hint=0);
Notes: Uses ::operator new(size_t) (18.4.1)
Requires: hint either 0 or previously obtained from member allocate and
not yet passed to member deallocate. The value hint may be used by an
implementation to help improve performance 216) .
Returns: a pointer to the initial element of an array of storage of size
n * sizeof(T), aligned appropriately for objects of type T.
Note: the storage is obtained by calling ::operator new(size_t), but it
is unspecified when or how often this function is called. The use of
hint is unspecified, but intended as an aid to locality if an
implementation so desires.
Footnote 216 is:
In a container member function, the address of an adjacent element
is often a good choice to pass for this argument.
--
Gabriel Dos Reis
g...@integrable-solutions.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Howard Hinnant
Francis Glassborow <fra...@robinton.demon.co.uk> wrote:
> In article <3f8761fd$0$6632$cc9e...@news.dial.pipex.com>, Stephen
Howe
> <NOSPAM...@dial.pipex.com> writes
> >But what std::vector won't do is when the size() and capacity() are
the same
> >and you wish to insert new elements, is to attempt to resize the
underlying
> >allocated block insitu to try and avoid the copy construct-destruct
cycle.
>
> Please give chapter and verse from the Standard if you believe this is
> something that an implementation is not allowed to do. I doubt that
> there is any such prohibition which means that it becomes a QoI issue.
As a vendor of std::vector, I'm having trouble understanding how this is
a QoI issue. In general vector must stick to managing memory through
the allocator interface. That interface currently does not allow the
kinds of questions that we want to ask (i.e. can you expand this block
of memory in place).
It is possible that we could put special logic in place for vector<T,
std::allocator<T> >. But std::allocator<T> must eventually call new to
get memory. And new may be overridden by client code. So there isn't a
heck of a lot std::allocator<T> can do in the department of expanding a
block of memory in place.
Vendors are trying very hard to make the best vector possible. If it
were possible with the current language and allocator interface, you
would see this capability in today's libraries.
-Howard
Gabriel Dos Reis
Here is precisely where the parameter "hint" of
std::allocator<T>::allocate comes into play.
--
Gabriel Dos Reis
g...@integrable-solutions.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Gabriel Dos Reis
| Francis Glassborow wrote:
| > In article <3f8761fd$0$6632$cc9e...@news.dial.pipex.com>, Stephen
| > Howe <NOSPAM...@dial.pipex.com> writes
| >> But what std::vector won't do is when the size() and capacity() are
| >> the same and you wish to insert new elements, is to attempt to
| >> resize the underlying allocated block insitu to try and avoid the
| >> copy construct-destruct cycle.
| >
| > Please give chapter and verse from the Standard if you believe this
is
| > something that an implementation is not allowed to do. I doubt that
| > there is any such prohibition which means that it becomes a QoI
issue.
|
| Which is much easier to solve if you have a standard attempt_expand
| function. Isn't it so?
No, because the standard does not mandate useful implementations.
--
Gabriel Dos Reis
g...@integrable-solutions.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Andrei Alexandrescu
news:hinnant-3E1FE3...@syrcnyrdrs-03-ge0.nyroc.rr.com...
> In article <3f8761fd$0$6632$cc9e...@news.dial.pipex.com>,
> "Stephen Howe" <NOSPAM...@dial.pipex.com> wrote:
>
> > But it would nice if there was a C memory allocation function that
> resized a
> > block allocated by malloc()/calloc() insitu or returned NULL if it
> could
> > not. With such a function, you could write realloc() using it. But
> this is
> > more topical in comp.lang.c.moderated :-)
>
> <clears throat> Yup, I agree 100%. I posted this link eariler in
this
> thread but I don't think anyone followed it:
>
> http://www.armdevzone.com/EABI/malloc_helpers.htm
Looks cool, except that the realloc sample implementation is not
threadsafe,
which in a realistic system it must be.
> Well said. This is a realistic goal. All of the technical pieces for
> how to do this are in place. The major obstacles are now
> standardization. And for that we need people like Stephen Howe,
Attila
> Feher and Andrei Alexandrescu to continue to stand up and say "Yes, we
> want this!".
Actually, we already have this. In a very virtual sense of "already".
The
mythical YASLI defines, implements, and uses an improved interface for
allocators on systems that have an expand function.
Andrei
Andrei Alexandrescu
news:m3smlyw...@uniton.integrable-solutions.net...
That doesn't help much. It improves locality of allocation, but not in
the
least contiguity, and as such it is a topic orthogonal to the
discussion.
Andrei
Howard Hinnant
This interface is insufficient to ask all of the right questions.
vector needs to know:
1. Can you expand by X amount?
2. If not, what can you expand to?
3. What is the current size of this block (it may well be more than was
requested).
4. Can you allocate X amount, and if not, how much can you allocate?
Since vector routinely asks for more memory than it currently needs, it
makes a lot of sense for vector to be flexible in accepting less than it
asks for if that amount would suffice. This is especially true for
embedded systems where virtual memory may not be available.
Your interesting interpretation of the current allocator interface would
answer only question #1. And to the best of my knowledge, no
implementation is currently interpreting the allocator interface in this
manner, nor does the standard suggest this interpretation.
-Howard
Attila Feher
[SNIP]
>> Well said. This is a realistic goal. All of the technical pieces
>> for how to do this are in place. The major obstacles are now
>> standardization. And for that we need people like Stephen Howe,
>> Attila Feher and Andrei Alexandrescu to continue to stand up and say
>> "Yes, we want this!".
>
> Actually, we already have this. In a very virtual sense of "already".
> The mythical YASLI defines, implements, and uses an improved interface
> for allocators on systems that have an expand function.
/The mythical YASLI/
No one has ever seen it, but everyone talks about it. It is like Windows NT
4. ;-) We should rename it to SLANT. Standard Library Ace - Not Today. ;-)
Just teasing.
My whole point about this (now) imaginary attempt_expand is that if it is
standard and present (as a C library allocator, and possibly its C++ renew
counterpart) then (and IMO only then) it really becomes "easy" to implement
those allocators and a vector (string) which attempts to expand in place (in
case it runs out of capacity).
If attempt_realloc is present, we can really call it a QoI issue if library
implementors make it right or not.
Another thing, for clever people to think about. If we want the allocators
to do a good job, we should at least give some hints. If a vector (string)
could tell to the allocator (I mean the C library subsystem) that it will
grow, the allocator might be able to do a better job (QoI) to ensure it can
grow in place. Of course this is a bit tricky, since at some point of time
we might need to say: and now we are done. And nothing whatsoever is
present from this in the interfaces... not to mention that probably no one
has ever tried to implement something like this. Again this is something to
think about. Knee-jerk reactions like telling it is a non-issue, or it is
non-feasible are easy. Those I can do myself, no need to be a guru to tell
one of the thousand ways something cannot be done. ;-)
--
Attila aka WW
Howard Hinnant
"Andrei Alexandrescu" <SeeWebsit...@moderncppdesign.com> wrote:
> > http://www.armdevzone.com/EABI/malloc_helpers.htm
>
> Looks cool, except that the realloc sample implementation is not
> threadsafe,
> which in a realistic system it must be.
<nod> Perhaps you missed this disclaimer up near the front:
> This proposal does not address multithreaded issues. It is assumed that
> implementations will make these calls thread safe when and where necessary.
That being said, thread safety issues were certainly not ignored in
coming up with this specification.
> > Well said. This is a realistic goal. All of the technical pieces for
> > how to do this are in place. The major obstacles are now
> > standardization. And for that we need people like Stephen Howe,
> Attila
> > Feher and Andrei Alexandrescu to continue to stand up and say "Yes, we
> > want this!".
>
> Actually, we already have this. In a very virtual sense of "already".
> The
> mythical YASLI defines, implements, and uses an improved interface for
> allocators on systems that have an expand function.
If we can all agree on what that "improved allocator interface" looks
like (i.e. standardize it), then we can all write improved allocators
with a portable interface. Furthermore if we can agree on a common "C
level" interface, the implementation of those improved allocators can
also become portable.
-Howard
Tim Rowe
<g...@integrable-solutions.net> wrote:
>This has nothing to do with a compiler being 100% standard-compiler.
>And a 100% standard-compliant compiler is not necessarily useful.
>
>The issue has just to do with compilers that accept commonly used and
>useful constructs. You seem to have one, according to your previous
>report.
Yes, I have one that accepts it (gcc) and one that doesn't
(Microsoft's latest).
As far as I can tell, I have to pay Microsoft to be able to report the
bug to them. If anybody knows otherwise, could they please let me
know how to do it. I have sent an email to /a/ support address, but
I'm not sure it will get to an appropriate destination.
Andrea Griffini
<attila...@lmf.ericsson.se> wrote:
>Knee-jerk reactions like telling it is a non-issue, or it is
>non-feasible are easy. Those I can do myself, no need to be a guru to tell
>one of the thousand ways something cannot be done. ;-)
No idea if you're aiming at me or not. But saying that realloc
is non-issue does not mean that it can't be solved, but just
that can be solved in the C++ *program* and not in the library.
The standard library IMO should not try to solve all possible
problems, but just provide solutions for very common cases, and
tools for solving the rest *in your program*. The std::vector
reallocation logic works for a vast majority of situation;
if you need something else you can build whatever you want.
Why do you want your specific solution for a very very specific
marginal case to be the standard is something I do no understand
(yes... i think that in modern programs where a lot of dynamic
allocations are done in a lot of places by several concurrent
threads, in-place extension is IMO a very very fortunate case).
As even you noted there are a lot of details WRT memory
management, and no one is telling you should not address them;
au contraire... IMO you should address them as they're a very
important part of a program efficiency. Pretending the standard
solution must give to you exactly what you want is another issue.
Also I don't want to pay for the extra complexity if I don't
need it (no, nothing is free).
Just to draw a parallel IMO for example checking for
self-assignment when self-assignment would have worked
anyway is in most cases nonsense.
Andrea
Dhruv
Yes, but consider an allocator that does not have access to the internals
of the system VMM, and uses malloc to actually get the memory, and then
decides the allocation policy on it's own based on some scheme that it has
chosen. There is no way possible that it can reuse memory that has not yet
been freed, unless the allocator is super-smart and knows things that even
humans do not know!!! The fact is that vector allocators 2*capacity when
it runs out of space, and then frees the original memory. It cannot do
anything else, and remain a conforming implementation. So, the allocator
in turn also can not give memory having a lesser address than the current
address [assuming that the vector is the only thing that's using dynamic
memory is around]. See the diagram for what I'm talking about. What hint
can to at most is tell the allocator to allocate memory somewhere around
the current region AFAIK. It cannot tell the allocator to expand that
allocated block of memory. In fact, in my implementation of an allocator I
do make use of the hint argument. The base of the matter is that vector
allocates exponentially growing blocks of memory without freeing the
previously allocated blocks. And in such a case, only a directly VMM
mapped allocator can help. But, if there was a function such as
can_realloc (), then it would be great!!!
Regards,
-Dhruv.
Gabriel Dos Reis
| In article <9VsqRpBbvRi$Ew...@robinton.demon.co.uk>,
| Francis Glassborow <fra...@robinton.demon.co.uk> wrote:
|
| > In article <3f8761fd$0$6632$cc9e...@news.dial.pipex.com>, Stephen
| Howe
| > <NOSPAM...@dial.pipex.com> writes
| > >But what std::vector won't do is when the size() and capacity() are
| the same
| > >and you wish to insert new elements, is to attempt to resize the
| underlying
| > >allocated block insitu to try and avoid the copy construct-destruct
| cycle.
| >
| > Please give chapter and verse from the Standard if you believe this is
|
| > something that an implementation is not allowed to do. I doubt that
| > there is any such prohibition which means that it becomes a QoI issue.
|
| As a vendor of std::vector, I'm having trouble understanding how this is
|
| a QoI issue.
See below.
| In general vector must stick to managing memory through
| the allocator interface. That interface currently does not allow the
| kinds of questions that we want to ask (i.e. can you expand this block
| of memory in place).
|
| It is possible that we could put special logic in place for vector<T,
| std::allocator<T> >. But std::allocator<T> must eventually call new to
| get memory. And new may be overridden by client code.
so far so good. Here is a framework that could be elaborated to work
for the general standard std::allocator<T>.
template<class T>
T* std::allocator<T>::allocate(size_type n, const_pointer hint
bool try_expansion)
{
T* result = try_expansion ? pointer (hint) : 0;
typedef void* (*__opnew_t)(size_t, void*);
if (n > max_size())
throw std::bad_alloc();
// we can't do much if user replaces ::operator new
// or there is no storage left
if (!try_expansion
|| (static_cast<__opnew_t>(&::operator new)
!= __vendor__allocator_new)
|| !__resize_storage(hint, n))
result = pointer(::operator new(n, hint));
return result;
}
| So there isn't a
|
| heck of a lot std::allocator<T> can do in the department of expanding a
| block of memory in place.
On the contrary.
| Vendors are trying very hard to make the best vector possible. If it
they are not trying hard enough ;-)
--
Gabriel Dos Reis
g...@integrable-solutions.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Andrea Griffini
wrote:
>It is possible that we could put special logic in place for vector<T,
>std::allocator<T> >. But std::allocator<T> must eventually call new to
>get memory. And new may be overridden by client code.
IMO this realloc thing is not a serious issue... but I think
realloc-ing is hard but technical feasible with a bit compiler
magic; using that magic you may *know* there is no user defined
global allocator and so you may know tricks to try in-place
expansions if the allocator is the standard one and if there
is no global allocator replacement installed.
I also think this test must be done at run-time (because
at compile time it's impossible with the common C++
one-module-at-a-time visibility).
>Vendors are trying very hard to make the best vector possible. If it
>were possible with the current language and allocator interface, you
>would see this capability in today's libraries.
It's always a cost/return evaluation. I don't see the return
being that big... after all the waste is not such big IMO:
if you have problem without in-place reallocation then soon
you'll have problems even with it available... it's time to
think to a better data structure.
I think this situation it's a bit like having C++ unsigned
type used to represent size to be able to squeeze the last
bit (IMO a bad idea).
Andrea
Howard Hinnant
Gabriel Dos Reis <g...@integrable-solutions.net> wrote:
> Here is a framework that could be elaborated to work
> for the general standard std::allocator<T>.
>
> template<class T>
> T* std::allocator<T>::allocate(size_type n, const_pointer hint
> bool try_expansion)
> {
> T* result = try_expansion ? pointer (hint) : 0;
> typedef void* (*__opnew_t)(size_t, void*);
>
> if (n > max_size())
> throw std::bad_alloc();
>
> // we can't do much if user replaces ::operator new
> // or there is no storage left
> if (!try_expansion
> || (static_cast<__opnew_t>(&::operator new)
> != __vendor__allocator_new)
> || !__resize_storage(hint, n))
> result = pointer(::operator new(n, hint));
>
> return result;
> }
Very nice, and thank you for clearly stating your ideas. I think your
idea is a good one, especially the overridden new detection.
There are some things I would like to be able to do in addition to your
idea (and I believe all of the following things are doable):
1. I would like for ordinary users to be able to write allocators which
might allow inplace expansion. This would require either that the
committee standardize an allocator's expansion interface, or that user's
write to a proprietary interface (I prefer the former).
2. I would like for ordinary users to be able to implement their
expand-capable allocators in a portable fashion. This would require
some standardized lower-level functionality (e.g. a standardized
__resize_storage).
3. I would like for the interface of __resize_storage, and of
allocator, to have an interface that would allow a certain amount of
negotiation to take place between the allocator's client (e.g. vector)
and the allocator:
client: Can you expand this (100 byte) block to 200 bytes?
allocator: No, but I may be able to expand it to 150 bytes, do you want
me to try that?
client: Yes, 150 bytes will do.
or:
client: No thanks, just give me a new 200 byte buffer.
As vector usually and rather arbitrarily attempts to double its capacity
when it runs out, there may well be times when an inplace expansion of
only 50% is both feasible and desirable when the 100% inplace expansion
is not possible.
4. I would like for the interface of allocator, (and some underlying
supporting standard function) be able to report to the client how much
memory was actually delivered:
client: Please give me a 200 byte buffer.
allocator: Here you go, and by the way the buffer is actually 220 bytes.
client: Thanks, I'll just go ahead and add that extra 20 bytes to my
capacity (otherwise it is just wasted memory).
5. I would like for all of this to be workable on a platform which
lacks virtual memory. Indeed, I suspect that it is on such platforms
where this kind of efficiency is most badly needed.
I know I'm asking a lot. But as I said, I see no technical reason not
to make vector and other vector-like clients wicked fast and miserly
efficient. And I also see no reason to package this technology up in
such a way that only vector can benefit. I daresay that there are even
C applications that could greatly benefit from knowing the true size of
a buffer, or finding out the size to which an existing buffer could be
expanded or shrunk without the expense of a copy.
I believe the first step in achieving these goals is to standardize a "C
level" interface similar to that proposed at:
http://www.armdevzone.com/EABI/malloc_helpers.htm
The next step would be to standardize an allocator interface which would
allow the functionality I've proposed to shine through to allocator's
clients. And Gabriel's overridden-new-detection will even allow
std::allocator to enjoy the benefits of this technology. I had
previously thought that only a malloc_allocator would benefit.
-Howard
WW
> On 13 Oct 2003 08:02:20 -0400, "Attila Feher"
> <attila...@lmf.ericsson.se> wrote:
>
>> Knee-jerk reactions like telling it is a non-issue, or it is
>> non-feasible are easy. Those I can do myself, no need to be a guru
>> to tell one of the thousand ways something cannot be done. ;-)
>
> No idea if you're aiming at me or not.
No, I was not particulary aiming at any individual. Honest.
> But saying that realloc
> is non-issue does not mean that it can't be solved, but just
> that can be solved in the C++ *program* and not in the library.
IMO it is not feasible to force programmers to use non-standard tricks to
achieve this.
> The standard library IMO should not try to solve all possible
> problems, but just provide solutions for very common cases, and
> tools for solving the rest *in your program*.
This is a common case. An important part of the library is missing. IMHO
(and I am not alone) this is an embarrasment to be removed. Removing it is
fairly easy.
> The std::vector
> reallocation logic works for a vast majority of situation;
> if you need something else you can build whatever you want.
Yes. Based on that logic we would be still using C. Since it is possible
to write code equvivalent to C++ in C. The Comeau compiler is a good
example of this. Sarcasm aside: the fact that you do not meet this problem
in your coding does not mean that no one else does. I find it rather
tiresome to read over and over again that something is a non-issue while I
get 10 emails per day into my mailbox from people thinking otherwise. And
telling that they are afraid to back this up in the newsgroup, since last
time they have tried they have been run down and made look ridiculous. In
fact in comp.std.c++ I have got answers (few years back) which read: I am on
the C++ committee and if you ever come up with a proposal like this I will
vote against it. This essentially means: shut up. IMO this is not the way
to go.
If I combine the energy put into ridicule and defend this motion in this
newsgroup I believe that we have wasted enough. Enough to change the
standard(s) and to implement attempt_expand for at least 5 platforms
(including all Windows platforms as one of those).
> Why do you want your specific solution for a very very specific
> marginal case
Since this is the 3rd(?) time you state this is a marginal case I am forced
to ask you: prove it please!
> to be the standard is something I do no understand
> (yes... i think that in modern programs where a lot of dynamic
> allocations are done in a lot of places by several concurrent
> threads, in-place extension is IMO a very very fortunate case).
Yes. Especially since it is not supported at all, it should be. Sarcasm
aside again. There are freely available malloc replacement libraries (like
libHoard) which essentially create separate heaps for each thread. IMO due
to the poor perfomance of the native allocators truly dynamic systems cannot
be done without it.
> As even you noted there are a lot of details WRT memory
> management, and no one is telling you should not address them;
> au contraire... IMO you should address them as they're a very
> important part of a program efficiency. Pretending the standard
> solution must give to you exactly what you want is another issue.
> Also I don't want to pay for the extra complexity if I don't
> need it (no, nothing is free).
I see no need for added extra complexity.
> Just to draw a parallel IMO for example checking for
> self-assignment when self-assignment would have worked
> anyway is in most cases nonsense.
No one has asked for/forced the default standard allocators to
attempt_expand. But as long as this function is not there, they won't. And
as long as this function is not there it is unfeasable to write a user code
which does it.
So IMO if you state (as you seem to) that this is a marginal issue as well
as a non-issue it would be nice to give some hard facts. I mean nothing
personal: but the fact that it is marginal to you means only that, and not
more.
--
WW aka Attila
Andrei Alexandrescu
news:m3oewlq...@uniton.integrable-solutions.net...
> template<class T>
> T* std::allocator<T>::allocate(size_type n, const_pointer hint
> bool try_expansion)
> {
> T* result = try_expansion ? pointer (hint) : 0;
> typedef void* (*__opnew_t)(size_t, void*);
>
> if (n > max_size())
> throw std::bad_alloc();
>
> // we can't do much if user replaces ::operator new
> // or there is no storage left
> if (!try_expansion
> || (static_cast<__opnew_t>(&::operator new)
> != __vendor__allocator_new)
> || !__resize_storage(hint, n))
> result = pointer(::operator new(n, hint));
>
> return result;
> }
This code looks like complete bogus to me. Am I reading it wrong, or
allocate might return the hint pointer, which surely will be doubly deleted
later?
> | Vendors are trying very hard to make the best vector possible. If it
>
> they are not trying hard enough ;-)
Or users aren't trying hard enough to understand the semantics of 'hint'
:o). Hint, hint.
Andrei the Ruthless
David Abrahams
> Since vector routinely asks for more memory than it currently needs, it
> makes a lot of sense for vector to be flexible in accepting less than it
> asks for if that amount would suffice. This is especially true for
> embedded systems where virtual memory may not be available.
That seems like it would only be useful in an extremely limited set
of designs... basically, those that only use a single vector. What
can you do with another vector if the first vector sucks up the last
byte of memory? Wouldn't it be better to give users control over the
expansion factor?
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
Gabriel Dos Reis
[...]
| the current region AFAIK. It cannot tell the allocator to expand that
| allocated block of memory.
The Standard does give flexibility to implementors, but implementors
seem not to take advantage of that flexibility. For example, the
Standard explicitly allows implementors to add more parameters to
standard functions:
An implementation can declare additional non-virtual member function
signatures within a class:
-- by adding arguments with default values to a member function
signature;172) The same latitude does not extend to the
implementation of virtual or global or non-member functions,
however.
-- by replacing a member function signature with default values by
two or more member function signa-tures with equivalent behavior;
-- by adding a member function signature for a member function name.
In particular, an implementation is allowed to say
template<cass T>
struct allocator {
// ...
pointer allocate(size_type n, const_pinter hint = 0,
bool try_expansion = false);
};
if try_expansion == false, then the behaviour is that decribed by
the standard for the non-extended signature; otherwise it behaves
like realloc().
Such a specification is standard-compliant, and provides for
storage expansion. This is a QoI.
--
Gabriel Dos Reis
g...@integrable-solutions.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
WW
[SNIP]
> in such a case, only a directly VMM mapped allocator can help. But,
> if there was a function such as can_realloc (), then it would be
> great!!!
Actually attempt_expand would be better. In a multithreaded environment it
cannot be quaranteed that between the call of can_realloc and realloc noone
else will force that realloc to copy. IMO it has to be an "atomic"
operation, which also expands if it can.
--
WW aka Attila
Andrei Alexandrescu
news:c6hkov0ie5thd9nh8...@4ax.com...
> IMO this realloc thing is not a serious issue...
IAO it is... so what to do about that :o).
> >Vendors are trying very hard to make the best vector possible. If it
> >were possible with the current language and allocator interface, you
> >would see this capability in today's libraries.
>
> It's always a cost/return evaluation. I don't see the return
> being that big... after all the waste is not such big IMO:
> if you have problem without in-place reallocation then soon
> you'll have problems even with it available... it's time to
> think to a better data structure.
It's an optimization, not a principial problem. If optimization wouldn't be
a problem, we'd all program in <censored>.
> I think this situation it's a bit like having C++ unsigned
> type used to represent size to be able to squeeze the last
> bit (IMO a bad idea).
Comparisons and parallels are useless, and this is the second recent one in
this thread. But, if you want to take this route... mathematicians sure
didn't invent N just to save a bit in the representation of Z...
Andrei
Gabriel Dos Reis
[...]
| > In a container member function, the address of an adjacent element
| > is often a good choice to pass for this argument.
|
| That doesn't help much.
Sure it does. It means that the implementation
(*) can try contiguity as implementation of locality
Once (*) is implemented, the implementation can add a flag to request
realloc()-like behaviour or "speculative realloc" (meaning if storage
expansion can not be done no allocation is made). As you see,
technical infrastructures are already there. It is left to
implementors to do whatever they want, including supporting or not
storage expansion.
--
Gabriel Dos Reis
g...@integrable-solutions.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Gabriel Dos Reis
[...]
| > In a container member function, the address of an adjacent element
| > is often a good choice to pass for this argument.
|
| This interface is insufficient to ask all of the right questions.
and the questions you listed below are not necessarily the right ones
nor their answers required for implementing a std::vector<T>::resize
that attempts storage expansion.
| vector needs to know:
|
| 1. Can you expand by X amount?
| 2. If not, what can you expand to?
| 3. What is the current size of this block (it may well be more than was
|
| requested).
| 4. Can you allocate X amount, and if not, how much can you allocate?
Those questions are not necessary for std::vector<T>::resize to
implement something that behaves like realloc, but with semantics for
non POD.
All, it takes is an implementor takes seriously the suggestions made in
the standard.
First, if vector<T>::resize asks for a larger storage and the
allocator returns a pointer equals to the hint (which was the
one-past-end of the real vector storage), then it means then
vector<T>::resize surely can deduce the combination of the new
and ole storage is contiguous, thus avoid supererogatory copies.
Second, the standard text explicitly allows implementors to add more
"defaulted" parameters to a standard function. That means an
implementor is allowed to define an std::allocator<T>::allocate with
a third argument that specifies that a storage expansion should be
tried hard -- see my other posting.
| Since vector routinely asks for more memory than it currently needs, it
| makes a lot of sense for vector to be flexible in accepting less than it
|
| asks for if that amount would suffice. This is especially true for
| embedded systems where virtual memory may not be available.
well, that a "smart" std::vector<T>::resize would be beneficial for
systems with tight memory is not under dispute. But, it is a QoI.
| Your interesting interpretation of the current allocator interface would
|
| answer only question #1.
And that would suffice to implement a realloc-like std::vector<T>::resize.
| And to the best of my knowledge, no
| implementation is currently interpreting the allocator interface in this
|
| manner,
and that is precisely one of the issues ;-p
| nor does the standard suggest this interpretation.
that claim is at best wrong. See above.
--
Gabriel Dos Reis
g...@integrable-solutions.net
[ See http://www.gotw.ca/resources/clcm.htm for info about ]