memmove in C++ code

[Himanshu81]

I am working on a C++ application which uses STL vectors heavily. When I profile the code using gprof it shows that 21% of the time is spent during memmoves. The code itself does not have any explicit memove calls.

(portion of flat profile produced using gprof)

% cumulative self self total
time seconds seconds calls s/call s/call name
21.17 52.23 21.21 memmove

(portion of call graph produced using gprof)

<spontaneous>
[8] 20.0 20.17 0.00 memmove [8]


It seems that memmove calls arise due to dynamic memory allocation. But its not clear how to exactly pinpoint which (STL) operations in the code are responsible for this. Any ideas on how to locate the cause of memmoves or which STL operations might cause memmoves.

Thanks,
Himanshu

[Banfa]

The problem is the vectors. A vector keeps a contiguous block of memory (very much like an array), what this means is that if you insert or delete data anywhere except the end of the vector it has to move the following data to make room for the new item (or move all the data to overwrite the old item).

If you are using a vector and making a lot of these type of insertion/deletion then prehaps you should consider a different type of STL container, say a list.

[Himanshu81]

The problem is the vectors. A vector keeps a contiguous block of memory (very much like an array), what this means is that if you insert or delete data anywhere except the end of the vector it has to move the following data to make room for the new item (or move all the data to overwrite the old item).

If you are using a vector and making a lot of these type of insertion/deletion then prehaps you should consider a different type of STL container, say a list.

Hi there,

Actually, I take care to NOT insert or delete elements from anywhere expect the ends of a vector. The operations that I use on vectors are reserve, resize, push_back, range insert at the end, clear, swap.

Can the above functions lead to memmoves?

Thanks,
Himanshu

[Banfa]

Hi there,

Actually, I take care to NOT insert or delete elements from anywhere expect the ends of a vector. The operations that I use on vectors are reserve, resize, push_back, range insert at the end, clear, swap.

Can the above functions lead to memmoves?

Thanks,
Himanshu

They can, anything that causes a resize of the vectors memory will cause a memmove. If you push_back and the vector needs 1 extra slot to hold the new sized vector then it allocates a block of memory that is the current size + 1 and copies the current contents to the new block of memory. Using resize helps to reduce this by automatically sizing the vectors memory to the right size before doing several push_backs but you will still end up with some memmoves.

vectors inherently have this feature because the have to maintain a contiguous block of memory. If you don't need that specific feature then don't use a vector.

[Himanshu81]

They can, anything that causes a resize of the vectors memory will cause a memmove. If you push_back and the vector needs 1 extra slot to hold the new sized vector then it allocates a block of memory that is the current size + 1 and copies the current contents to the new block of memory. Using resize helps to reduce this by automatically sizing the vectors memory to the right size before doing several push_backs but you will still end up with some memmoves.

vectors inherently have this feature because the have to maintain a contiguous block of memory. If you don't need that specific feature then don't use a vector.

Thanks for answering to my post. Based on your suggestion I looked at stl_vector.h. Most of the routines there call unitialized_copy which in turn calls memmove. I reduced some of the vector related operations (in a critical loop) and that did lead to reduction in the time spent in memmoves.