Pre allocation of memory
-
In setting up vector or other data structures, is there really any benefit to pre-allocating the memory?
-
Yes. It saves you some memory copy operations.
-
Are you talking about "reserve()":http://doc.trolltech.com/latest/qvector.html#reserve member function of QVector or std::vector?
If yes, then the answer is you could get some benefits in speed if you use reserve instead calling many times push_back() or any other way repeatedly resize the vector and cause multiple allocations (potentially copy data, deallocation of old memory)
-
not potentially, it serves some allocations.
Not each push results in a new, ther is always some pre allocation, but ich you want to add many items, it definitly makes sense if you already know the amount of items.
Otherwise you reallocate memory and free memory often, which fragemnts the memory more than needed. You have to move the elements of the vector on each reallocation.
And if you call reserve, the memory is allocated en block and then placement new is used to create the object. placement new is used to call the constructor of a class on an already allocated block of memory. This is the way how STL does this pre allocation.
The current vector implementations always grow (reserve) dependant on the current size if all allocated memory is in use, so they are already a bit optimized for multiple push operations, but reserve is always a good idea.
-
Like Gerolf said the important question is if you know the amount of items. You don't want to "reserve" much more memory than you will need and avoiding reallocating memory can't hurt.
from the "documentation":http://doc.qt.nokia.com/4.7/qvector.html#reserve:
bq. Attempts to allocate memory for at least size elements. If you know in advance how large the vector will be, you can call this function, and if you call resize() often you are likely to get better performance. If size is an underestimate, the worst that will happen is that the QVector will be a bit slower. The sole purpose of this function is to provide a means of fine tuning QVector's memory usage. In general, you will rarely ever need to call this function. If you want to change the size of the vector, call resize().
-
Ok! So this leads me into a slightly more involved question.
I have created a graph data structure that holds pointers to the node and edge objects that make up the graph. I am wondering if perhaps my implementation is not as efficient as it could be. The data for the graph is read in from an XML file and as the reader comes to each new node the following code runs:
@
//Determine if the node already exists in the graph ... skip is yes.
if( !NodeExists(name, heuristic) )
nodeList.push_back(new GraphNode(name, heuristic, m_iNodeIndex));//Advance the Node index. m_iNodeIndex++;@
NodeList is a vector of pointers. Based on your responses, it seems that each new graph node will be created on the heap in a random location. Is that correct? If so, would it be better to store the node itself rather than a pointer to the node in the NodeList vector?
Edges are created in roughly the same manner except pointers to each edge are stored in a vector or edge pointers that are a part of each node.
Or, is this a difference of programming style?
Laurence -
-
It depends what you do with the objects later on.
From pure creational view, It could be better to store objects than pointers. But that also leads to other implications. If you store the pointers (or use the pointers) somwhere else and the modify the vector, the pointer might be invalid.
So it can't be answered generally.
-
How could an object be rendered invalid?!? That almost seems counter-intuitive. If I create and object and then pass a pointer reference to some other part of the program, even if the data in the object is changed, it should not invalidate the object itself.
After a little more reading, my question should be, are you referring the possibility that the vector may have to re-allocate and move the underlying objects around thus invalidating the pointers? If so, I am not sure that I have to worry about this possibility. The graph's nodes and edges are fixed in number.
-
An std::vector (and also a QVector) is a C - array. SO if you have 20 elements in and need to reallocate the vector, the old content MUST be moved in memory, so pointers to the old (unchanged) array would definitly get invalid.
If you can preallocate the vector and do not resize it, than you can also give pointers out of it. Think of it like a C-style array. If you have no space left and want to add elements, you have to move all elements to a new array which is bigger.
Both vectors have just a bit more comfort, like moving, adding, preallocating, but in general, they are C-style arrays.
-
Not sure if this helps, since I don't like arrays, never used them and would not know how they compare to a vector, just giving another angle to the discussion.
I think a std::vector is contiguous through out its life. When the allocated memory block for a vector is exhausted during a growth, the entire vector gets copied into a larger block, and whatever is contained gets copied with it. Any type of data can be accessed in this vector as before the copy took place.
The catch is when the vector is created at run time and is filled with a horde of pointers and needs to be destructed, than all those pointers in the vectors need to be destroyed as well and at programming time you don't know which one's will be created and where - you are stuck or it's time for smart pointers.
Bottom line? I practise and test stuff to the hilt. If the vector works the way I want it, it's end of story.
-
I believe that I understand now. Coming from the Visual Basic and C# universes, I was shielded (to an extent) from this sort of thing. Is there a way to check if a pointer assignment is still valid?
Laurence -
-
@ cazador7907
That is more or less a save pointer.
Hopefully I will not get shot down showing a link to the competition, but I learned so much from those guys. -
But unique_ptr ist no solution here. A unique_ptr implies that you own the object pointed to and
that the lifetime of the object and the unique_ptr are (more or less) identical. So you should know if its valid, regardless of the use of unique_ptr.In fact there is no way no ensure, that a pointer points to an object that has not been deleted.
-
My humblest apologies.
The pointer style in my previous link does work in std::vectors, and those vectors that had been moved(copied). The topic is about effectively using vectors, and I added information to that.And sure, no smart/save pointer is a direct answer to cazador7907 question, but the topic is about vectors; that's why I wrote 'That is more or less ...' , I assumed his/her question was in context to the topic, since we all agreed that to allocate space for a vector is a good idea, and what left to figgure out is what to do with its contents. :)
