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_in t_ptr;
v_int_ptr.reser ve(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<intv;
v.reserve(num);
for(int i = 0; i < num; i++)
{
double my_int = i;
v.push_back(myi nt);
}

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]

On Oct 19, 7:26 pm, smp <spear...@stude nt.ucr.eduwrote :

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_in t_ptr;
v_int_ptr.reser ve(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<intv;
v.reserve(num);
for(int i = 0; i < num; i++)
{
double my_int = i;
v.push_back(myi nt);
}

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]

smp wrote:

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_in t_ptr;
v_int_ptr.reser ve(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<intv;
v.reserve(num);
for(int i = 0; i < num; i++)
{
double my_int = i;
v.push_back(myi nt);
}

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.

--
Ian Collins.

[Kai-Uwe Bux]

Zilla wrote:

On Oct 19, 7:26 pm, smp <spear...@stude nt.ucr.eduwrote :

>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_in t_ptr;
v_int_ptr.reser ve(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<intv;
v.reserve(num);
for(int i = 0; i < num; i++)
{
double my_int = i;
v.push_back(myi nt);
}

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().

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]

On Oct 19, 10:34 pm, Kai-Uwe Bux <jkherci...@gmx .netwrote:

Zilla wrote:

On Oct 19, 7:26 pm, smp <spear...@stude nt.ucr.eduwrote :

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_in t_ptr;
v_int_ptr.reser ve(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<intv;
v.reserve(num);
for(int i = 0; i < num; i++)
{
double my_int = i;
v.push_back(myi nt);
}

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().

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....9d782f6d6dae52

[James Kanze]

On Oct 20, 1:44 am, Zilla <zill...@bellso uth.netwrote:

On Oct 19, 7:26 pm, smp <spear...@stude nt.ucr.eduwrote :

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_in t_ptr;
v_int_ptr.reser ve(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<intv;
v.reserve(num);
for(int i = 0; i < num; i++)
{
double my_int = i;
v.push_back(myi nt);
}

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?

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
times more memory than vector<int>.

To
deallocate, use v.clear().

That won't deallocate anything.

--
James Kanze (GABI Software) email:ja******* **@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[James Kanze]

On Oct 20, 4:34 am, Kai-Uwe Bux <jkherci...@gmx .netwrote:

[...]

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.

--
James Kanze (GABI Software) email:ja******* **@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[Kai-Uwe Bux]

James Kanze wrote:

On Oct 20, 4:34 am, Kai-Uwe Bux <jkherci...@gmx .netwrote:

[...]

>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.]

smp <sp******@stude nt.ucr.eduwrote :

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_in t_ptr;
v_int_ptr.reser ve(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<intv;
v.reserve(num);
for(int i = 0; i < num; i++)
{
double my_int = i;
v.push_back(myi nt);
}

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]

On Oct 19, 7:26 pm, smp <spear...@stude nt.ucr.eduwrote :

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_in t_ptr;
v_int_ptr.reser ve(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<intv;
v.reserve(num);
for(int i = 0; i < num; i++)
{
double my_int = i;
v.push_back(myi nt);
}

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(m ycontainer.begi n(),mycontainer .end(),deleteme <int*>());

Lance