speed issues with resize() and POD
Paul Rosen
std:vector<unsigned char>
I have an object of this type that is used over and over. Conceptually
it is kind of like this (NOTE: the following is trivial code, don't take
the exact code seriously.):
std:vector<unsigned char> Coll;
while (lots of times through)
{
int iSize = SizeThisTime();
Coll.resize(iSize);
Process(Coll);
}
Now, my profiler is showing that the resize() function is taking up a
lot of time, but it theoretically wouldn't have to. I stepped through it
and can see that it is going through the elements one by one, which is
unnecessary in this case because the object contains POD.
What I'd like resize() to do in this case is:
1) if the new size is less than the capacity, just set the size.
2) else do the normal stuff.
Very quickly Coll would reach a maximum size and would hum along really
fast.
In my implementation (the STL that comes with MSVC 7.1), I think I could
just set the variable Coll._Mylast if I'm changing the size to something
under the capacity, but that is unportable and just seems wrong.
Does anyone have a better solution?
I don't really want to create my own vector class since I pass it around
to other routines that shouldn't know about any of this.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
mzdude
> std:vector<unsigned char> Coll;
> while (lots of times through)
> {
> int iSize = SizeThisTime();
> Coll.resize(iSize);
> Process(Coll);
>}
>Now, my profiler is showing that the resize() function is taking up a
>lot of time, but it theoretically wouldn't have to.
Rather than resize and passing the entire container to Process, use
iterators to mark the boundries
while( lots of times through )
{
int iSize = SizeThisTime();
if( i > Coll.size() )
Coll.resize( iSize );
Process( col.begin(), col.begin()+iSize);
andys...@runbox.com
vectors are often implemented as wrappers around a single array so if
there is not enough space to grow the array in place a new array must
be allocated and all the contents copied over.
the dequeue class has a very similar protocol but is often implemented
as a series of arrays, if the dequeue needs to grow it can just
allocate some more memory without having to copy the whole data
structure.
Forgive me if this is not helpful as I am fairly new to cpp.
Tony Delroy
If your STL isn't doing what you want, then you've provided the logical
solution in your question, and you can implement it yourself in code:
std:vector<unsigned char> Coll;
int largest_size = 0;
while (lots of times through)
{
int iSize = SizeThisTime();
if (iSize > largest_size)
{
largest_size = iSize;
Coll.resize(iSize);
}
Process(Coll);
}
Anyway, I guess the STL implementation's iteration/empty-destructor
calls should be optimised away if you set your optimisation level
appropriately.
Cheers, Tony
Carlos Moreno
> I have a vector like this:
>
> std:vector<unsigned char>
>
> I have an object of this type that is used over and over. Conceptually
> it is kind of like this (NOTE: the following is trivial code, don't take
> the exact code seriously.):
>
> std:vector<unsigned char> Coll;
>
> while (lots of times through)
> {
> int iSize = SizeThisTime();
> Coll.resize(iSize);
> Process(Coll);
> }
>
> Now, my profiler is showing that the resize() function is taking up a
> lot of time, but it theoretically wouldn't have to. I stepped through it
> and can see that it is going through the elements one by one, which is
> unnecessary in this case because the object contains POD.
>
> What I'd like resize() to do in this case is:
>
> 1) if the new size is less than the capacity, just set the size.
> 2) else do the normal stuff.
>
> Very quickly Coll would reach a maximum size and would hum along really
> fast.
>
> In my implementation (the STL that comes with MSVC 7.1), I think I could
> just set the variable Coll._Mylast if I'm changing the size to something
> under the capacity, but that is unportable and just seems wrong.
>
> Does anyone have a better solution?
How about don't resize unless the object is growing?
> I don't really want to create my own vector class since I pass it around
> to other routines that shouldn't know about any of this.
This should not be a valid argument -- your other routines should not be
attached (tightly coupled) to the fact that you're using one particular
container. If you make those templates, or have them receive iterators
(which would mean template as well), that would solve both problems:
you don't have to resize the vector, since you only have to pass a pair
of iterators specifying the sequence (so, you pass the second iterator
pointing where you know the end should be, but without making that the
end).
If your other functions are not up for negotiation, then perhaps you're
out of luck -- you could try raising the optimization level and see if
the compiler inlines and optimizes away the do-nothing destructor?
HTH,
Carlos
--
Paul Rosen
> Paul Rosen said
>
>>std:vector<unsigned char> Coll;
>>while (lots of times through)
>>{
>>int iSize = SizeThisTime();
>>Coll.resize(iSize);
>>Process(Coll);
>>}
>>Now, my profiler is showing that the resize() function is taking up a
>>lot of time, but it theoretically wouldn't have to.
>
>
> Rather than resize and passing the entire container to Process, use
> iterators to mark the boundries
>
> while( lots of times through )
> {
> int iSize = SizeThisTime();
> if( i > Coll.size() )
> Coll.resize( iSize );
> Process( col.begin(), col.begin()+iSize);
> }
That's a possibility, but I'd prefer to just pass one parameter. A
really nice feature of using vector instead of a plain old unsigned
char* and a length is that the vector is a single parameter for a single
concept.
If I were to propagate the parameter change all the way through the
Process() routine and everything it called, I'd be tempted to just go
back to C:
unsigned char* puc = new unsigned char[MAX_BUFF];
while( lots of times through )
{
int iSize = SizeThisTime();
Process(puc, iSize);
}
delete [] puc;
ka...@gabi-soft.fr
> I have a vector like this:
> std:vector<unsigned char>
> I have an object of this type that is used over and
> over. Conceptually it is kind of like this (NOTE: the
> following is trivial code, don't take the exact code
> seriously.):
> std:vector<unsigned char> Coll;
> while (lots of times through)
> {
> int iSize = SizeThisTime();
> Coll.resize(iSize);
> Process(Coll);
> }
> Now, my profiler is showing that the resize() function is
> taking up a lot of time, but it theoretically wouldn't have
> to. I stepped through it and can see that it is going through
> the elements one by one, which is unnecessary in this case
> because the object contains POD.
> What I'd like resize() to do in this case is:
> 1) if the new size is less than the capacity, just set the size.
> 2) else do the normal stuff.
> Very quickly Coll would reach a maximum size and would hum
> along really fast.
I'm not sure I understand. Technically, this is the required
behavior of resize() -- it is not allowed to invalidate
iterators, and thus cannot deallocate any memory. The only
thing it would normally do in addition to just setting the new
size is 1) call destructors on removed objects, and 2) call
constructors on added objects. In the former case, a good
compiler will detect that the loop in the code doesn't do
anything, and surpress it. In the second, that is part of the
specification of the container (all containers) -- a container
never contains an uninitialized object, POD or no.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Maxim Yegorushkin
> I have a vector like this:
>
> std:vector<unsigned char>
>
> I have an object of this type that is used over and over. Conceptually
> it is kind of like this (NOTE: the following is trivial code, don't take
> the exact code seriously.):
>
> std:vector<unsigned char> Coll;
>
> while (lots of times through)
> {
> int iSize = SizeThisTime();
> Coll.resize(iSize);
> Process(Coll);
> }
>
> Now, my profiler is showing that the resize() function is taking up a
> lot of time, but it theoretically wouldn't have to. I stepped through it
> and can see that it is going through the elements one by one, which is
> unnecessary in this case because the object contains POD.
It does not do that for PODs. For PODs it uses memcpy/memmove to copy
and memset to initialize new elements. Check the sources carefully.
> What I'd like resize() to do in this case is:
>
> 1) if the new size is less than the capacity, just set the size.
This is what happens for PODs.
> 2) else do the normal stuff.
>
> Very quickly Coll would reach a maximum size and would hum along really
> fast.
[]
> Does anyone have a better solution?
>
> I don't really want to create my own vector class since I pass it around
> to other routines that shouldn't know about any of this.
I experienced a similar problem. I used a vector<char> as a buffer for
reading data from a socket. Having profiled my server under heavy load
it turned out that 30% of its runtime was spent in zeroing out buffer
when I grew it (vector::resize) to read data in.
I threw std::vector<> away and wrote my own low cholesterol
pod_vector<> and have been happy ever since.
Greg Herlihy
> I have a vector like this:
>
> std:vector<unsigned char>
>
> I have an object of this type that is used over and over. Conceptually
> it is kind of like this (NOTE: the following is trivial code, don't take
> the exact code seriously.):
>
> std:vector<unsigned char> Coll;
>
> while (lots of times through)
> {
> int iSize = SizeThisTime();
> Coll.resize(iSize);
> Process(Coll);
> }
>
> Now, my profiler is showing that the resize() function is taking up a
> lot of time, but it theoretically wouldn't have to. I stepped through it
> and can see that it is going through the elements one by one, which is
> unnecessary in this case because the object contains POD.
>
> What I'd like resize() to do in this case is:
>
> 1) if the new size is less than the capacity, just set the size.
> 2) else do the normal stuff.
>
> Very quickly Coll would reach a maximum size and would hum along really
> fast.
>
>
You should "preflight" this operation by first calling
std::vector::reserve() to increase Coll's capacity to some reasonably
large number that is unlikely to be exceeded for the duration of this
function. Reserving memory for the vector's contents up front ensures
that resizing the vector to any size smaller than the vector's capacity
will not entail reallocating and copying the vector's contents. It's
the reallocations and copying of the vector's elements as its size
gradually increases that is almost certainly the cause of the poor
performance.
Note that if SizeThisTime() returns a value that exceeds Coll's
capacity, then the routine should double the amount of memory Coll has
in reserve and do the same on all such future occurrences (of course if
Coll's initial capacity was well chosen, having to increase it
subsequently should not be a frequent event).
Greg
Howard Hinnant
Paul Rosen <pro...@fte.com> wrote:
Fwiw, the Freescale implementation of vector<unsigned char> does what
you suggest, except instead of:
2) else do the normal stuff.
It is more like:
2) expand using memset to "construct" the new elements.
That being said, this is not a clear-cut case. A major question is
whether such optimizations are desirable or not in the face of
allocator::construct and allocator::destroy which may have side effects
beyond those listed in the standard.
I.e. Are allocator::construct/destroy convenience functions or
customization points?
I believe the standard is less than clear on this issue. And
furthermore I believe the "right" answer is less than clear as well.
The Freescale implementation currently has a hybrid approach (for better
or worse):
1. allocator::construct is consistently used as long as the contained
type has a non-trivial copy constructor, else it is not.
2. allocator::destroy is consistently used as long as the contained
type has a non-trivial destructor, else it is not.
Although I do not do this (yet), it would be possible to further
specialize these optimizations on whether or not std::allocator was
being used. But then my customers using vector<char,
my_allocator<char>> may rightly complain that vector slows to a crawl
with their allocator but not with std::allocator.
This is a classic performance / functionality tradeoff, and as you note,
the performance hit can be significant. So we do not want to dictate
this functionality if it is not needed.
-Howard
Ivan Vecerina
news:BYFRe.5139$9i4....@newsread2.news.atl.earthlink.net...
>I have a vector like this:
> std:vector<unsigned char> Coll;
>
> while (lots of times through)
> {
> int iSize = SizeThisTime();
> Coll.resize(iSize);
> Process(Coll);
> }
>
> Now, my profiler is showing that the resize() function is taking up a
> lot of time, but it theoretically wouldn't have to. I stepped through it
> and can see that it is going through the elements one by one, which is
> unnecessary in this case because the object contains POD.
Unfortunately, without compiler support, the library code cannot
automatically determine if a template parameter is POD or not.
Some library implementations would have a default specialization
for built-in types, in release mode at least. Maybe not the one you use?
> What I'd like resize() to do in this case is:
>
> 1) if the new size is less than the capacity, just set the size.
> 2) else do the normal stuff.
>
> Very quickly Coll would reach a maximum size and would hum along really
> fast.
>
> In my implementation (the STL that comes with MSVC 7.1), I think I could
> just set the variable Coll._Mylast if I'm changing the size to something
> under the capacity, but that is unportable and just seems wrong.
>
> Does anyone have a better solution?
Question: do you need to preserve the contents of Coll between
iterations of the loop?
If not, you could try using the pair of calls:
Coll.resize(0);
Coll.resize(iSize);
This will save std::vector from copying the previous contents of
the collection when it needs to allocate a larger memory block.
You could also call vector::reserve initially with a
"reasonable" size guess.
I hope this helps,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Ivan Vecerina
...
: > Rather than resize and passing the entire container to Process,
use
: > iterators to mark the boundries
: >
: > while( lots of times through )
: > {
: > int iSize = SizeThisTime();
: > if( i > Coll.size() )
: > Coll.resize( iSize );
: > Process( col.begin(), col.begin()+iSize);
: > }
:
: That's a possibility, but I'd prefer to just pass one parameter. A
: really nice feature of using vector instead of a plain old unsigned
: char* and a length is that the vector is a single parameter for a
single
: concept.
variable]
: If I were to propagate the parameter change all the way through the
: Process() routine and everything it called, I'd be tempted to just
go
: back to C:
:
: unsigned char* puc = new unsigned char[MAX_BUFF];
:
: while( lots of times through )
: {
: int iSize = SizeThisTime();
: Process(puc, iSize);
: }
:
: delete [] puc;
Yes but this is not exception-safe.
You can pass a buffer the C-way while retaining the safety and
convenience of std::vector:
std::vector<unsigned char> buf(MAX_SIZE_GUESS);
while( lots of times through )
{
unsigned const size = SizeThisTime();
if( size > buf.size() ) buf.resize( size );
Process( &buf.front(), size );
}
Iterators, as suggested by mzdude, give you more flexibility, but you
can use the 'good old way' if you know you won't have to bother with
non-contiguous storage.
Cheers,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact
form
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Greg Herlihy
Certainly callng vector::resize() will deallocate memory and invalidate
the vector's iterators when called to resize the vector beyond its
current capacity. How could it avoid doing so? And what would be the
benefit from not doing so? A quick check of vector::resize()'s
implementation from two different compiler vendors shows that in both
libraries, calling vector::resize() will reallocate memory if
necessary.
Here's a another suggestion in response to the original post. If the
initialization of the elements when resizing the vector turns out to be
time consuming, then eliminate the resize call altogether (but still
call reserve() so that the vector has some sufficiently large
capacity). Then just have the routine push_back() the items as they are
being added to the vector.
Greg
Maxim Yegorushkin
andys...@runbox.com wrote:
> vectors are often implemented as wrappers around a single array so if
> there is not enough space to grow the array in place a new array must
> be allocated and all the contents copied over.
Then what is the "rare" implementation which does not wrap a single
array?
Ivan Vecerina
message news:df9nlr$vtu$1...@news.hispeed.ch...
: Question: do you need to preserve the contents of Coll between
: iterations of the loop?
: If not, you could try using the pair of calls:
: Coll.resize(0);
: Coll.resize(iSize);
: This will save std::vector from copying the previous contents of
: the collection when it needs to allocate a larger memory block.
it probably won't do much as the new contents
will still have to be "initialized" individually.
[ although it might save read-access to the original
data, but this isn't likely to do much ].
Sorry for the confusion,
Ivan
James Kanze
> "Paul Rosen" <pro...@fte.com> wrote in message
> news:BYFRe.5139$9i4....@newsread2.news.atl.earthlink.net...
>>I have a vector like this:
> ...
>>std:vector<unsigned char> Coll;
>>while (lots of times through)
>>{
>>int iSize = SizeThisTime();
>>Coll.resize(iSize);
>>Process(Coll);
>>}
>>Now, my profiler is showing that the resize() function is
>>taking up a lot of time, but it theoretically wouldn't have
>>to. I stepped through it and can see that it is going through
>>the elements one by one, which is unnecessary in this case
>>because the object contains POD.
> Unfortunately, without compiler support, the library code
> cannot automatically determine if a template parameter is POD
> or not. Some library implementations would have a default
> specialization for built-in types, in release mode at
> least. Maybe not the one you use?
It doesn't really matter. If resize increases the size of the
array, the standard requires that the new elements be
initialized.
>>What I'd like resize() to do in this case is:
>>1) if the new size is less than the capacity, just set the size.
>>2) else do the normal stuff.
>>Very quickly Coll would reach a maximum size and would hum
>>along really fast.
>>In my implementation (the STL that comes with MSVC 7.1), I
>>think I could just set the variable Coll._Mylast if I'm
>>changing the size to something under the capacity, but that is
>>unportable and just seems wrong.
>>Does anyone have a better solution?
> Question: do you need to preserve the contents of Coll between
> iterations of the loop?
> If not, you could try using the pair of calls:
> Coll.resize(0);
> Coll.resize(iSize);
> This will save std::vector from copying the previous contents
> of the collection when it needs to allocate a larger memory
> block.
He specifically said that after a short time, the largest size
would be reached, so reallocation isn't a problem. Unless the
implementation of resize() is also reducing capacity; this isn't
allowed by the standard, but I think earlier versions were less
clear about this, and some older implementations may have done
this.
What is certain is
1) If resize reduces the size of the array, the implementation
must call the destructors of the objects removed from the
array. In the case of a POD, this should result in an empty
loop, which the compiler *should* be able to optimize out.
2) If resize increases the size of the array, the
implementation must call the copy constructor for the new
objects. Even for a POD, the copy constructor is *not*
empty, and cannot be optimized out.
In theory, the compiler could recognize that all of the
values used are assigned to before use, and suppress the
unneeded initialization. Doing that for the elements in an
array, however, is way beyond the abilities of any optimizer
I've ever heard of.
I think that Hymen offered the best proposal: don't call resize
except if it is necessary to increase the size. The vector will
very quickly reach its maximum size, and from that point on, the
fact that resize is too slow is irrelevant, since it won't be
called. On the other hand, this means that you cannot use
vector::size() to determine exactly how many elements are really
in the array; you need to maintain this information separately.
Which could be a real pain.
--
James Kanze mailto: james...@free.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34
Howard Hinnant
"Greg Herlihy" <gre...@pacbell.net> wrote:
> Certainly callng vector::resize() will deallocate memory and invalidate
> the vector's iterators when called to resize the vector beyond its
> current capacity. How could it avoid doing so? And what would be the
> benefit from not doing so? A quick check of vector::resize()'s
> implementation from two different compiler vendors shows that in both
> libraries, calling vector::resize() will reallocate memory if
> necessary.
This is a true statement in the context of today's standard. However I
just wanted to point out that there is room for improvement here. It
could be possible for vector::resize() to not reallocate even when
size() threatens to exceed capacity().
There is a proposal before the C committee to expand the
malloc/realloc/free interface to allow for expanding in place, without
the threat of automatically moving the memory block (as realloc does):
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1085.htm
Given this improved interface at the C level, it would become practical
to expand the C++ allocator interface to also include analogous
capability:
template <class T>
class custom_allocator
{
public:
// ... allocator interface as today, plus ...
typedef std::version_type<custom_allocator, 2> version;
size_type size(pointer p) const throw();
pointer allocate(size_type n, size_type& size_received);
pointer request(size_type size_requested,
size_type& size_received) throw();
int resize(pointer p, size_type size_requested,
size_type& size_received) throw();
int expand(pointer p, size_type min_size, size_type preferred_size,
size_type& size_received) throw();
};
A new specification for std::vector could detect a "version 2"
allocator, and use its augmented interface to attempt an in-place
expansion when size() threatens to exceed capacity().
I have prototyped such a malloc, such a custom allocator, and such a
vector. The measured performance improvements in some cases are
significant.
-Howard
Marc Mutz
<snip>
> I experienced a similar problem. I used a vector<char>
> as a buffer for reading data from a socket. Having
> profiled my server under heavy load it turned out that
> 30% of its runtime was spent in zeroing out buffer when
> I grew it (vector::resize) to read data in.
Maybe range-insert at the end would have helped you, too.
Marc
James Kanze
> "Paul Rosen" <pro...@fte.com> wrote in message
> news:0a2Se.5977$FW1....@newsread3.news.atl.earthlink.net...
> ...
> > > Rather than resize and passing the entire container to
> > > Process, use iterators to mark the boundries
> > > while( lots of times through )
> > > {
> > > int iSize = SizeThisTime();
> > > if( i > Coll.size() )
> > > Coll.resize( iSize );
> > > Process( col.begin(), col.begin()+iSize);
> > > }
> > That's a possibility, but I'd prefer to just pass one
> > parameter. A really nice feature of using vector instead of
> > a plain old unsigned char* and a length is that the vector
> > is a single parameter for a single concept.
> [NB: boost.org has classes to wrap iterator ranges into a
> single variable]
For that matter, wrapping the array yourself with an STL
compatible interface would seem to be a reasonable solution: in
fact, you use your abstraction, not std::vector, but of course,
your abstraction uses std::vector in its implementation.
(Having said that, I think that Boost's classes, here, are a
very good solution.)
> > If I were to propagate the parameter change all the way through the
> > Process() routine and everything it called, I'd be tempted to just go
> > back to C:
> > unsigned char* puc = new unsigned char[MAX_BUFF];
> > while( lots of times through )
> > {
> > int iSize = SizeThisTime();
> > Process(puc, iSize);
> > }
> > delete [] puc;
> Yes but this is not exception-safe.
Boost has an array_ptr which would make it so. On the other
hand, this solution means reimplementing most of the growth
logic present in std::vector.
--
James Kanze mailto: james...@free.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Maxim Yegorushkin
Howard Hinnant wrote:
[]
> There is a proposal before the C committee to expand the
> malloc/realloc/free interface to allow for expanding in place, without
> the threat of automatically moving the memory block (as realloc does):
>
> http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1085.htm
Is not it what glibc malloc already does? realloc() expands the memory
block by coalescing following memory blocks if there are some,
otherwise it does usual malloc-memcpy-free.
I exploited that fact in my pod_vector.
Maxim Yegorushkin
Marc Mutz wrote:
> Maxim Yegorushkin wrote:
> <snip>
> > I experienced a similar problem. I used a vector<char>
> > as a buffer for reading data from a socket. Having
> > profiled my server under heavy load it turned out that
> > 30% of its runtime was spent in zeroing out buffer when
> > I grew it (vector::resize) to read data in.
> <snp>
>
> Maybe range-insert at the end would have helped you, too.
range-insert what? I read data directly into my pod_vector<> to avoid
memory copy. To use range-insert I would have to read data in some
intermediate buffer then copy (insert) it into my container. This is no
go.
ka...@gabi-soft.fr
[...]
> > > Very quickly Coll would reach a maximum size and would hum
> > > along really fast.
> > I'm not sure I understand. Technically, this is the
> > required behavior of resize() -- it is not allowed to
> > invalidate iterators, and thus cannot deallocate any memory.
> > The only thing it would normally do in addition to just
> > setting the new size is 1) call destructors on removed
> > objects, and 2) call constructors on added objects. In the
> > former case, a good compiler will detect that the loop in
> > the code doesn't do anything, and surpress it. In the
> > second, that is part of the specification of the container
> > (all containers) -- a container never contains an
> > uninitialized object, POD or no.
> Certainly callng vector::resize() will deallocate memory and
> invalidate the vector's iterators when called to resize the
> vector beyond its current capacity.
Of course. But as the original poster indicated: "Very quickly
Coll would reach a maximum size." Although I didn't make it
clear, I was speaking about using resize() in the context where
new allocation would not be necessary.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Howard Hinnant
"Maxim Yegorushkin" <maxim.ye...@gmail.com> wrote:
> Howard Hinnant wrote:
>
> []
>
> > There is a proposal before the C committee to expand the
> > malloc/realloc/free interface to allow for expanding in place, without
> > the threat of automatically moving the memory block (as realloc does):
> >
> > http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1085.htm
>
> Is not it what glibc malloc already does? realloc() expands the memory
> block by coalescing following memory blocks if there are some,
> otherwise it does usual malloc-memcpy-free.
>
> I exploited that fact in my pod_vector.
That's great for your pod_vector. But in general, std::vector doesn't
have that option because there is no allocator interface with which to
do it. std::vector must work strictly through its allocator.
Also a key difference between N1085 and the existing realloc, is that
the proposed:
int resize_alloc(void* ptr, size_t size_requested,
size_t* size_received);
int negotiate_alloc(void* ptr, size_t min_size,
size_t preferred_size, size_t* size_received);
_do_not_ do the malloc-memcpy-free dance. That means that
vector<not_a_pod> can also take advantage of the expand-in-place
technology. If it can expand in place it will. If it can't, then it
need not worry that realloc is going to memcpy its non-pods about.
-Howard
Marc Mutz
<snip>
> range-insert what?
the std::vector::insert() that takes an iterator range as
parameter.
> I read data directly into my
> pod_vector<> to avoid memory copy. To use range-insert I
> would have to read data in some intermediate buffer then
> copy (insert) it into my container. This is no go.
Depending on the source of the data, you could use an
istreambuf_iterator, or write such a thing yourself. If
you're only using fwrite(), then that's a bit harder,
indeed.
Marc
Paul Rosen
They fall into the following categories:
1) The compiler should recognize that resize() isn't doing anything and
optimize it away.
I wish that were true, but that doesn't appear to be true for my
compiler (MSVC 7.1), and my STL (the one that ships with it.)
Perhaps there is some compiler switch that I'm not seeing, but I'm not
seeing it.
2) Don't resize when it's smaller. Therefore the routines that get the
vector passed to them can't rely on size().
That is unacceptable because that just seems like a maintenance nightmare.
3) Pass either a pair of iterators or the size along with the vector.
Well, that would work, but I've got a number of routines downstream that
are passed a vector as a parameter and they'd all have to change. Since
everything works (its just slow), I'd like to make a localized change if
possible.
4) Some suggestions concentrated on reallocing memory, which is not the
slow part, instead of calling lots of constructors and destructors
unnecessarily.
---
I am really tempted to go with the non-portable solution:
void quick_resize(std::vector<unsigned char>& coll, size_type new_size)
{
unsigned char* pNewLast = coll._Myfirst + new_size;
if (pNewLast > coll._Myend)
coll.resize(new_size);
else
coll._Mylast = pNewLast;
}
If we change STL implementations, I'll probably have to revisit the
performance anyway.
That brings up something that I was curious about. Why is _Myfirst, etc.
declared public?
If I were designing that class, I'd want to declare them private just so
no one could monkey around with them like I just did.
The only items I'd declare public would be the routines that are
documented in the standard.
Also, is there some #define I could use to see which version of the STL
I'm using? For instance, this would be safer:
#ifdef DINKUMWARE_STL_7_1 // does some define like this exist?
void quick_resize ... as above
...
#else
void quick_resize(std::vector<unsigned char>& coll, size_type new_size)
{
coll.resize(new_size);
}
#endif
mzdude
want to. One of the powerful liabilities of C / C++ is you can do
anything you want to :)
Only you can determine if deviating from accepted convention is worth
it. That's what they pay you (big bucks) for.
Keep in mind the future maintainer of the code. Will the type ever be
non POD? Suppose someone who doesn't understand your code, your
reasoning or C++ as well as you, sees this performance enhancement and
decides it will benefit them. But their vector is non POD. OOPS memory
leaks. With every compiler update, you will now have to peruse the STL
implementation of vector to make sure this continues to give the
requested performance.
There have been articles by people (forget who) about compile time
testing for POD types. This would have no run time impact. I would
throw some of those test in your quick_resize(). I don't think comments
will be enough.
Maxim Yegorushkin
> >
> > []
> >
> > > There is a proposal before the C committee to expand the
> > > malloc/realloc/free interface to allow for expanding in place, without
> > > the threat of automatically moving the memory block (as realloc does):
> > >
> > > http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1085.htm
> >
> > Is not it what glibc malloc already does? realloc() expands the memory
> > block by coalescing following memory blocks if there are some,
> > otherwise it does usual malloc-memcpy-free.
> >
> > I exploited that fact in my pod_vector.
>
> That's great for your pod_vector. But in general, std::vector doesn't
> have that option because there is no allocator interface with which to
> do it. std::vector must work strictly through its allocator.
Well, I see std::allocator::allocate() has void* hint paramater. So,
when expanding a std::vector, why not pass as hint the pointer to the
current array, so that if the allocator can expand it inplace it
returns the same pointer, or another pointer if new memory has been
allocated? Am I missing something?
Carl Barron
Maxim Yegorushkin <maxim.ye...@gmail.com> wrote:
>
> Well, I see std::allocator::allocate() has void* hint paramater. So,
> when expanding a std::vector, why not pass as hint the pointer to the
> current array, so that if the allocator can expand it inplace it
> returns the same pointer, or another pointer if new memory has been
> allocated? Am I missing something?
>
Simply put this has the same essential problems of realloc.
see comp.std.c++ for a dissusion of extending allocator, etc
to handle in place allocations. Revised Allocator Proposal is the
thread.
Maxim Yegorushkin
Carl Barron wrote:
[]
> Simply put this has the same essential problems of realloc.
What are those problems?
> see comp.std.c++ for a dissusion of extending allocator, etc
> to handle in place allocations. Revised Allocator Proposal is the
> thread.
I failed to find 'hint' and 'realloc' words in the thread.
Carl Barron
Maxim Yegorushkin <maxim.ye...@gmail.com> wrote:
> Carl Barron wrote:
>
> []
>
> > Simply put this has the same essential problems of realloc.
>
> What are those problems?
>
> > see comp.std.c++ for a dissusion of extending allocator, etc
> > to handle in place allocations. Revised Allocator Proposal is the
> > thread.
>
> I failed to find 'hint' and 'realloc' words in the thread.
>
int *p = 0;
int n = 2;
do
{
p = realloc(p,n);
n += 2;
} while(p);
if there is not enough memory to move the data, or the data is
moved the old memory leaks. It is possible to avoid the problem,
but it is too easy to create the problem, using the same function to
move or allocate. A better approach is a test of extensibliy of current
allocation and then extend the memory or not via different functions.
Since the allocation problem is being solved again, it is best to avoid
the problems of the older solution. The 'realloc solution' is not
enough.
Maxim Yegorushkin
Carl Barron wrote:
[]
> > I failed to find 'hint' and 'realloc' words in the thread.
> >
> int *p = 0;
> int n = 2;
> do
> {
> p = realloc(p,n);
> n += 2;
> } while(p);
>
> if there is not enough memory to move the data, or the data is
> moved the old memory leaks.
I'm sorry, I'm slow. I don't see how memory could leak here, provided
the code is rewritten correctly to test the realloc() return value
before assigning it to the pointer. Could you please elaborate?
> It is possible to avoid the problem,
> but it is too easy to create the problem, using the same function to
> move or allocate. A better approach is a test of extensibliy of current
> allocation and then extend the memory or not via different functions.
The is a race condition between the test and the actual reallocation.
The test does not guarantees that the following call to a reallocation
function succeed.
Allan W
> > int *p = 0;
> > int n = 2;
> > do {
> > p = realloc(p,n);
> > n += 2;
> > } while(p);
> >
> > if there is not enough memory to move the data, or the data is
> > moved the old memory leaks.
Maxim Yegorushkin wrote:
> I'm sorry, I'm slow. I don't see how memory could leak here, provided
> the code is rewritten correctly to test the realloc() return value
> before assigning it to the pointer. Could you please elaborate?
But that was exactly Carl's point -- there's a LOT of code out
there that doesn't test the realloc() return value before assigning
it to the pointer, such as in Carl's example. (I'm almost certain
that Carl's example wasn't real-world... but it's not that far off.)
So that when realloc() fails, the only pointer to the original
memory is set to null, causing the leak.
The fact that realloc can return null is only obvious if you read
the documentation -- and far too many so-called programmers do not
read documentation.
Maxim Yegorushkin
Allan W wrote:
> > Carl Barron wrote:
> > > int *p = 0;
> > > int n = 2;
> > > do {
> > > p = realloc(p,n);
> > > n += 2;
> > > } while(p);
> > >
> > > if there is not enough memory to move the data, or the data is
> > > moved the old memory leaks.
>
> Maxim Yegorushkin wrote:
> > I'm sorry, I'm slow. I don't see how memory could leak here, provided
> > the code is rewritten correctly to test the realloc() return value
> > before assigning it to the pointer. Could you please elaborate?
>
> But that was exactly Carl's point -- there's a LOT of code out
> there that doesn't test the realloc() return value before assigning
> it to the pointer, such as in Carl's example. (I'm almost certain
> that Carl's example wasn't real-world... but it's not that far off.)
> So that when realloc() fails, the only pointer to the original
> memory is set to null, causing the leak.
Well, the proposed solution is much worse, since it complicates the
interface and gives false feel of safety to a naive programmer. As I
said there is a race between the two calls and the latter realloc call
can still return 0 leaving you back with the original problem.
> The fact that realloc can return null is only obvious if you read
> the documentation -- and far too many so-called programmers do not
> read documentation.
Do you think those programmers would read the docs for the new
interface?
Howard Hinnant
"Maxim Yegorushkin" <maxim.ye...@gmail.com> wrote:
> > That's great for your pod_vector. But in general, std::vector doesn't
> > have that option because there is no allocator interface with which to
> > do it. std::vector must work strictly through its allocator.
>
> Well, I see std::allocator::allocate() has void* hint paramater. So,
> when expanding a std::vector, why not pass as hint the pointer to the
> current array, so that if the allocator can expand it inplace it
> returns the same pointer, or another pointer if new memory has been
> allocated? Am I missing something?
I've seen that suggestion before, and it is a good one. However I think
it is sufficiently suboptimal as to warrant a more drastic change.
Consider vector::push_back(const T&):
When size() == capacity() the vector must grow its capacity
geometrically in order to meet complexity requirements. This means that
capacity will double, or grow by 1.5, or perhaps something in between.
With your proposed interface the vector can ask for the doubled (for
example) capacity, and the allocator can either expand the existing
memory block by the requested amount, or allocate a new one. There are
only those two choices, nothing else.
It would be so much better for the vector to be able to request of the
allocator: Try to double (for example) my buffer, but failing that try
to expand the buffer as much as you can, at least enough for just one
more element (remember this is under push_back).
By accepting a far lower expansion, you greatly increase the odds that
your in-place expansion will work. And you still meet your complexity
requirements even though the capacity is no longer guaranteed to grow
geometrically. If the allocator is unable to expand the buffer by one
more element you can still allocate a new buffer with a geometrically
larger capacity. The interface I propose is rich enough for this
negotiation to take place. The reuse of hint is not (afaict).
-Howard
Maxim Yegorushkin
Howard Hinnant wrote:
> > Well, I see std::allocator::allocate() has void* hint paramater. So,
> > when expanding a std::vector, why not pass as hint the pointer to the
> > current array, so that if the allocator can expand it inplace it
> > returns the same pointer, or another pointer if new memory has been
> > allocated? Am I missing something?
>
> I've seen that suggestion before, and it is a good one. However I think
> it is sufficiently suboptimal as to warrant a more drastic change.
But it's a piece of cake to implement right now, and I am disappointed
it was not done so years ago, without waiting until it's ratified by
the committee in the next decade.
Howard Hinnant
"Maxim Yegorushkin" <maxim.ye...@gmail.com> wrote:
> Howard Hinnant wrote:
>
>>> Well, I see std::allocator::allocate() has void* hint paramater. So,
>>> when expanding a std::vector, why not pass as hint the pointer to the
>>> current array, so that if the allocator can expand it inplace it
>>> returns the same pointer, or another pointer if new memory has been
>>> allocated? Am I missing something?
>>
>> I've seen that suggestion before, and it is a good one. However I think
>> it is sufficiently suboptimal as to warrant a more drastic change.
>
> But it's a piece of cake to implement right now, and I am disappointed
> it was not done so years ago, without waiting until it's ratified by
> the committee in the next decade.
No matter how simple or complicated proposals are at this point for
extended functionality, nothing will be ratified until C++0X, with the
hope that X is 9. Committee work is glacially slow (and this is
actually a good thing). Quick fixes can correct bugs (e.g. defect
reports), but not extend functionality. You get one chance every 10
years (or so) to better a standard. Put your best foot forward.
-Howard