efficiency of vector of pointers.

[smp]

Does anyone know why making a vector of pointers is so much less efficient
than a vector of objects? For a simple example:

int num = 20;
vector<int*> v_int_ptr;
v_int_ptr.reserve(num);

for(int i = 0; i < num; i++)
{
int* my_int_ptr = new int;
*my_int_ptr = i;
v_int_ptr.push_back(my_int_ptr);
}

takes a long time and uses up pretty much all the memory when num is
large. However, the functionally equivalent:

int num = 20;
vector<int> v;
v.reserve(num);
for(int i = 0; i < num; i++)
{
double my_int = i;
v.push_back(myint);
}

runs very fast under the same conditions that bogged down the former. And
by the way, I'm trying to avoid using arrays.
Finally, what is the best way to deallocate the memory here? Does one need
to iterate through the vector deleting each block in turn?

Thanks in advance,
SMP

 

[Zilla]

Does anyone know why making a vector of pointers is so much less efficient
than a vector of objects? For a simple example:

int num = 20;
vector<int*> v_int_ptr;
v_int_ptr.reserve(num);

for(int i = 0; i < num; i++)
{
int* my_int_ptr = new int;
*my_int_ptr = i;
v_int_ptr.push_back(my_int_ptr);
}

takes a long time and uses up pretty much all the memory when num is
large. However, the functionally equivalent:

int num = 20;
vector<int> v;
v.reserve(num);
for(int i = 0; i < num; i++)
{
double my_int = i;
v.push_back(myint);
}

runs very fast under the same conditions that bogged down the former. And
by the way, I'm trying to avoid using arrays.
Finally, what is the best way to deallocate the memory here? Does one need
to iterate through the vector deleting each block in turn?

Thanks in advance,
SMP

new() and delete() functions take a lot of real time. Depending on
your compiler, pointer sizes may be big, hence, a memory hog too. To
deallocate, use v.clear().

 

[Ian Collins]

Does anyone know why making a vector of pointers is so much less
efficient than a vector of objects? For a simple example:

int num = 20;
vector<int*> v_int_ptr;
v_int_ptr.reserve(num);

for(int i = 0; i < num; i++)
{
int* my_int_ptr = new int;
*my_int_ptr = i;
v_int_ptr.push_back(my_int_ptr);
}

takes a long time and uses up pretty much all the memory when num is
large. However, the functionally equivalent:

int num = 20;
vector<int> v;
v.reserve(num);
for(int i = 0; i < num; i++)
{
double my_int = i;
v.push_back(myint);
}

runs very fast under the same conditions that bogged down the former.
And by the way, I'm trying to avoid using arrays.

Well what do you expect? The first example calls new each time round
the loop. It's not what goes in the vector, its how that object is
created. Now consider the case where the object stored in the vector is
expensive to copy and compare that with a vector of pointers to said
objects.

Finally, what is the best way to deallocate the memory here? Does one
need to iterate through the vector deleting each block in turn?

In the first case, yes, the every new requires a delete rule applies.
This is one reason smart pointer types are often stored in standard
containers.

 

[Kai-Uwe Bux]

new() and delete() functions take a lot of real time. Depending on
your compiler, pointer sizes may be big, hence, a memory hog too. To
deallocate, use v.clear().

v.clear() will _not_ deallocate the elements of the vector. It will just
call the trivial destructor for each int* stored. Consequently, a call to
v.clear() without going through v and calling delete on all the pointers
will leak memory big time.

Moreover, v.clear() is not guaranteed to deallocate any memory allocated by
the vector v. In particular, v.capacity() may or may not change.


Best

Kai-Uwe Bux

 

[er]

v.clear() will _not_ deallocate the elements of the vector. It will just
call the trivial destructor for each int* stored. Consequently, a call to
v.clear() without going through v and calling delete on all the pointers
will leak memory big time.

Moreover, v.clear() is not guaranteed to deallocate any memory allocated by
the vector v. In particular, v.capacity() may or may not change.

Best

Kai-Uwe Bux

if your vector grows sequentially, reallocation will occur. in this
case, ptrs might be preferable if each element is big (unlike your
example), unless, of course, you know in advance how many elements
will be inserted (reserve).

this point was made earlier:
http://groups.google.com/group/comp...2f6d6dae52?lnk=st&q=&rnum=19#639d782f6d6dae52

 

[James Kanze]

new() and delete() functions take a lot of real time. Depending on
your compiler, pointer sizes may be big, hence, a memory hog too.

In one case, each element uses sizeof(int) memory, period. In
the other, each element in the vector is sizeof(int*), but
there's also the int which is pointed to, plus the additional
overhead associated with dynamic allocation (at least 8 bytes on
most machines, often more). So in a best case analysis, where
both pointers and int's are four bytes, vector<int*> will use 4

To
deallocate, use v.clear().

That won't deallocate anything.

 

[James Kanze]

[...]

v.clear() will _not_ deallocate the elements of the vector. It will just
call the trivial destructor for each int* stored. Consequently, a call to
v.clear() without going through v and calling delete on all the pointers
will leak memory big time.

Moreover, v.clear() is not guaranteed to deallocate any memory allocated by
the vector v. In particular, v.capacity() may or may not change.

v.clear() is guaranteed by the standard to not reduce the
capacity(), and so in practice will never deallocate memory
allocated by the vector itself.

 

[Kai-Uwe Bux]

[...]

v.clear() will _not_ deallocate the elements of the vector. It will just
call the trivial destructor for each int* stored. Consequently, a call to
v.clear() without going through v and calling delete on all the pointers
will leak memory big time.

Moreover, v.clear() is not guaranteed to deallocate any memory allocated
by the vector v. In particular, v.capacity() may or may not change.

v.clear() is guaranteed by the standard to not reduce the
capacity(), and so in practice will never deallocate memory
allocated by the vector itself.

Where would I find that in the standard? I only found that the semantics of
clear() is defined as erase( begin(), end() ). Regarding erase(), I did not
find any statement in the standard as to how it may or may not affect the
capacity. The closest provision I found is that erase does not invalidate
iterators before the erased range and hence it will generally not cause
reallocation (however, that is vacuous when all elements are erased). Or is
it just by absence: it is not mentioned in the Effects clause that the
capacity could change, therefore it cannot change?


Best

Kai-Uwe Bux

 

[Daniel T.]

Does anyone know why making a vector of pointers is so much less efficient
than a vector of objects? For a simple example:

int num = 20;
vector<int*> v_int_ptr;
v_int_ptr.reserve(num);

for(int i = 0; i < num; i++)
{
int* my_int_ptr = new int;
*my_int_ptr = i;
v_int_ptr.push_back(my_int_ptr);
}

takes a long time and uses up pretty much all the memory when num is
large. However, the functionally equivalent:

int num = 20;
vector<int> v;
v.reserve(num);
for(int i = 0; i < num; i++)
{
double my_int = i;
v.push_back(myint);
}

runs very fast under the same conditions that bogged down the former. And
by the way, I'm trying to avoid using arrays.
Finally, what is the best way to deallocate the memory here? Does one need
to iterate through the vector deleting each block in turn?

We can see that the first code sample allocates a block of memory that
is sizeof( int* ) * 20 then allocates 20 blocks that are each sizeof(
int ), while the second code sample only allocates a single sizeof( int
) * 20 block. If sizeof( int* ) == sizeof( int ) [not necessarily true]
then one can see that the first sample allocates at least twice as much
total ram as the second, and 20 more blocks than the second. These two
facts alone account for all of the speed and memory difference.

 

[Lance Diduck]

Does anyone know why making a vector of pointers is so much less efficient
than a vector of objects? For a simple example:

int num = 20;
vector<int*> v_int_ptr;
v_int_ptr.reserve(num);

for(int i = 0; i < num; i++)
{
int* my_int_ptr = new int;
*my_int_ptr = i;
v_int_ptr.push_back(my_int_ptr);
}

takes a long time and uses up pretty much all the memory when num is
large. However, the functionally equivalent:

int num = 20;
vector<int> v;
v.reserve(num);
for(int i = 0; i < num; i++)
{
double my_int = i;
v.push_back(myint);
}

runs very fast under the same conditions that bogged down the former. And
by the way, I'm trying to avoid using arrays.
Finally, what is the best way to deallocate the memory here? Does one need
to iterate through the vector deleting each block in turn?

Thanks in advance,
SMP

new and delete for very small objects is typically inefficient, vector
or not. Assuming that your new/delete is pointing to a general purpose
heap allocator underneath the hood (typically malloc ) why is this?
1. each call to new requires scanning free blocks looking for enough
space. This is typically and O(log n) search (where 'n' is the number
of free blocks)
2. In addition to the sizeof(int) memory required, you allocator is
going to add its own bookkeeping, usually sizeof(a few pointers). Plus
the minimum size chunk it is going to make is typically 16 bytes.
Since int only needs four, you've just claimed about 20 bytes extra
3. On an MT system, new/delete is going to cost you a mutex lock
4. delete is typically an O(n) operation (n being the number of times
you called new). If you ran your program through a very good profiler,
you would consistently find that "delete" operation take up way more
time than "new" (This is one reason that people find throwing an
exception very costly - as it is unwinding the stack, it is calling a
bunch of destructors, and dtor is where you find a lot of "deletes" )
5. There is no guarantee that the memory returned by successive calls
to "new" is placed anywhere near each other in memory. So your
processors cache keeps getting flushed and reloaded. Also, recall
that a typical L1 cache line is 16 bytes. Well, we just observed that
memory returned by new is going to take up about 20 odd bytes minimum.
So each 4 byte int needs an entire cache line. Ouch
6. the memory returned by new has maximum alignment, no matter what
type you are actually newing. No optimization can be performed based
on the fact that int does not always need maximum alignment.

OK so what does vector do? It just keeps one big contiguous chunk of
ints. So all of the observations above are amortized over many many
ints (in your example everything is done in reserve() and dtor), and
your cache likes it because all these ints are perfectly aligned and
jammed right next to each other.
You may also want to consider using deque if you are doing a lot of
insertions like your example. See http://www.codeproject.com/vcpp/stl/vector_vs_deque.asp

The moral of the story: only use container of pointers when
a) you need the object shared by other containers or some other object
b) the object is expensive to copy (large or complicated objects), or
is not copyable at all
c) you are making a container of abstract classes (you have no other
choice but use a pointer
Excessive calls to new is often a problem seen in C++ programs written
by Java developers. The Java allocator is completely different, and
the language itself accounts for this difference (one reason there are
no dtors in Java). Typically in Java, calls to new are constant time
(not including time to call objects ctor) and deallocation is behind
the scenes, outside of normal program flow. Of course, Java systems
developers are always struggling with Java's deallocation problems,
but that is a different story.

For delete, the easiest way is to use a shared_ptr . But if you have
performance worries now, using shared_ptr for a vector of int* is even
worse. This is how I do it
template<class T>struct deleteme{
void operator()(T t){delete t;}
};
std::for_each(mycontainer.begin(),mycontainer.end(),deleteme<int*>());

Lance

 

[James Kanze]

[...]

v.clear() will _not_ deallocate the elements of the vector. It will just
call the trivial destructor for each int* stored. Consequently, a call to
v.clear() without going through v and calling delete on all the pointers
will leak memory big time.
Moreover, v.clear() is not guaranteed to deallocate any memory allocated
by the vector v. In particular, v.capacity() may or may not change.

v.clear() is guaranteed by the standard to not reduce the
capacity(), and so in practice will never deallocate memory
allocated by the vector itself.

Where would I find that in the standard?

Spread out all over the place, and specified very indirectly.
It's designed so that you'll miss it.

I only found that the semantics of clear() is defined as
erase( begin(), end() ). Regarding erase(), I did not find
any statement in the standard as to how it may or may not
affect the capacity. The closest provision I found is that
erase does not invalidate iterators before the erased range
and hence it will generally not cause reallocation (however,
that is vacuous when all elements are erased). Or is it just
by absence: it is not mentioned in the Effects clause that the
capacity could change, therefore it cannot change?

Sort of. In general, a function cannot do other things that
what is specified in its effects clause: you won't find anything
in the standard that directly forbids vector::clear() from
modifying some other vector, as well as the one its called on,
either. This is more or less implicite.

Now consider something like the following:

std::vector< int > v ;
for ( int i = 0 ; i < 10 ; ++ i ) {
v.push_back( i ) ;
}
v.reserve( 100 ) ;
v.clear() ;
for ( int i = 0 ; i < 10 ; ++ i ) {
v.push_back( i ) ;
}
std::vector< int >::iterator it = v.begin() ;
v.push_back( 100 ) ;

I would contend that that last line cannot invalidate it. The
fact that capacity is tightly linked to iterator validity, at
least when inserting, means that not modifying capacity except
when explicitly allowed is a very, very important guarantee in
the standard. Managing the validity of iterators is already
hard enough as is.

 

[Ye Gu]

new and delete for very small objects is typically inefficient, vector
or not. Assuming that your new/delete is pointing to a general purpose
heap allocator underneath the hood (typically malloc ) why is this?
1. each call to new requires scanning free blocks looking for enough
space. This is typically and O(log n) search (where 'n' is the number
of free blocks)
2. In addition to the sizeof(int) memory required, you allocator is
going to add its own bookkeeping, usually sizeof(a few pointers). Plus
the minimum size chunk it is going to make is typically 16 bytes.
Since int only needs four, you've just claimed about 20 bytes extra
3. On an MT system, new/delete is going to cost you a mutex lock
4. delete is typically an O(n) operation (n being the number of times
you called new). If you ran your program through a very good profiler,
you would consistently find that "delete" operation take up way more
time than "new" (This is one reason that people find throwing an
exception very costly - as it is unwinding the stack, it is calling a
bunch of destructors, and dtor is where you find a lot of "deletes" )
5. There is no guarantee that the memory returned by successive calls
to "new" is placed anywhere near each other in memory. So your
processors cache keeps getting flushed and reloaded. Also, recall
that a typical L1 cache line is 16 bytes. Well, we just observed that
memory returned by new is going to take up about 20 odd bytes minimum.
So each 4 byte int needs an entire cache line. Ouch
6. the memory returned by new has maximum alignment, no matter what
type you are actually newing. No optimization can be performed based
on the fact that int does not always need maximum alignment.

OK so what does vector do? It just keeps one big contiguous chunk of
ints. So all of the observations above are amortized over many many
ints (in your example everything is done in reserve() and dtor), and
your cache likes it because all these ints are perfectly aligned and
jammed right next to each other.
You may also want to consider using deque if you are doing a lot of
insertions like your example. Seehttp://www.codeproject.com/vcpp/stl/vector_vs_deque.asp

The moral of the story: only use container of pointers when
a) you need the object shared by other containers or some other object
b) the object is expensive to copy (large or complicated objects), or
is not copyable at all
c) you are making a container of abstract classes (you have no other
choice but use a pointer
Excessive calls to new is often a problem seen in C++ programs written
by Java developers. The Java allocator is completely different, and
the language itself accounts for this difference (one reason there are
no dtors in Java). Typically in Java, calls to new are constant time
(not including time to call objects ctor) and deallocation is behind
the scenes, outside of normal program flow. Of course, Java systems
developers are always struggling with Java's deallocation problems,
but that is a different story.

For delete, the easiest way is to use a shared_ptr . But if you have
performance worries now, using shared_ptr for a vector of int* is even
worse. This is how I do it
template<class T>struct deleteme{
void operator()(T t){delete t;}};

std::for_each(mycontainer.begin(),mycontainer.end(),deleteme<int*>());

Lance

I'm just having some similar problem regarding this issue. As Lance
stated, " a) you need the object shared by other containers or some
other object ", I do in my current project, in which every object
contains 3 pointers to other objects in the same container and in two
other containers. However I have about three vectors each of which
contains 100,000 items. And it takes forever to do the deallocation.
Do you have any good suggestion when I have to reference(using pointer
or other means) the object in a container? Is it possible to store the
object in the vector directly and reference them through the pointer
by codes such as:
v[7000].myPtrV=&v[9991];

Thanks!
coo

 

[James Kanze]

[...]

I'm just having some similar problem regarding this issue. As Lance
stated, " a) you need the object shared by other containers or some
other object ", I do in my current project, in which every object
contains 3 pointers to other objects in the same container and in two
other containers. However I have about three vectors each of which
contains 100,000 items. And it takes forever to do the deallocation.
Do you have any good suggestion when I have to reference(using pointer
or other means) the object in a container? Is it possible to store the
object in the vector directly and reference them through the pointer
by codes such as:
v[7000].myPtrV=&v[9991];

You can, but be careful. The address will be invalided by the
same operations which may invalidate a pointer (in a vector, at
least).

If you're dealing with lots of little, short lived objects, you
should investigate using garbage collection. That's the sort of
scenario where it really shines. (Execution time for memory
management with manual allocation and deallocation is usually a
function of the number of allocations/deallocation you do.
Execution time for memory management with the most typical
garbage collection algorithms depends on the amount of memory in
actual use when the collector is called.) Failing that, it's
pretty simple to use class specific allocators, implementing
either a garbage collection algorithm for them, or even
something simpler, if they have long, more or less scoped
lifetimes.

 

[Ye Gu]

On Oct 19, 7:26 pm, smp <[email protected]> wrote:

[...]

I'm just having some similar problem regarding this issue. As Lance
stated, " a) you need the object shared by other containers or some
other object ", I do in my current project, in which every object
contains 3 pointers to other objects in the same container and in two
other containers. However I have about three vectors each of which
contains 100,000 items. And it takes forever to do the deallocation.
Do you have any good suggestion when I have to reference(using pointer
or other means) the object in a container? Is it possible to store the
object in the vector directly and reference them through the pointer
by codes such as:
v[7000].myPtrV=&v[9991];

You can, but be careful. The address will be invalided by the
same operations which may invalidate a pointer (in a vector, at
least).

If you're dealing with lots of little, short lived objects, you
should investigate using garbage collection. That's the sort of
scenario where it really shines. (Execution time for memory
management with manual allocation and deallocation is usually a
function of the number of allocations/deallocation you do.
Execution time for memory management with the most typical
garbage collection algorithms depends on the amount of memory in
actual use when the collector is called.) Failing that, it's
pretty simple to use class specific allocators, implementing
either a garbage collection algorithm for them, or even
something simpler, if they have long, more or less scoped
lifetimes.

--
James Kanze (GABI Software) email:[email protected]
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

Thank you. Since my objects have long lifetimes, I've solved the
problem by using vector::reserve and carefully calculating the number
of items.

Best,
coo