Thread: Good Idea to Reserve Memory for Vectors?

  1. #1
    Registered User
    Join Date
    Mar 2011
    Posts
    61

    Good Idea to Reserve Memory for Vectors?

    Say I had a program like the following:

    Code:
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <string>
    
    using namespace std;
    
    int main()
    {
    	vector<string> words;
    	vector<string>::iterator it;
    	string temp;
    
    	cout << "Enter a series of words separated by spaces and terminated with [Enter]:" << endl;
    
    	do
    	{
    		cin >> temp;
    		words.push_back(temp);
    	}
    	while (cin.get() != '\n');
    
    	sort(words.begin(), words.end());
    	
    	cout << "\n\nYou entered (sorted): ";
    	for (it = words.begin(); it != words.end(); it++)
    	{
    		cout << *it << " ";
    	}
    
    	cin.get();
    	return 0;
    }
    and I knew that there was going to be at least ten words entered. Would it be better to call words.reserve() to reserve that space and eliminate the need to allocate more memory each time push_back() is called? I know it costs performance when the entire vector has to be copied to a new location, but if it is just allocating more memory (without copying) does it make a difference?

  2. #2
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Since you are planning on such a small number of words, I wouldn't reserve any memory. Typically vector implementations preallocate an array to start with anyway, so even if you reserve it would make no difference.

  3. #3
    Registered User
    Join Date
    Oct 2006
    Posts
    3,445
    if I know how many elements are going to be put in the vector, I often reserve space, especially if I know it's going to be a lot of elements.

  4. #4
    Registered User
    Join Date
    Mar 2011
    Posts
    61
    Obviously I wouldn't bother with it if I only had 10 items, this was just an example program.

    My question was more of whether or not it costs performance to allocate more memory if movement of the vector is unnecessary and, as a result, if it is wise to to reserve memory if you have a general idea, but don't know exactly, how much memory needs to be allocated.

  5. #5
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    I'm not aware of any implementation that actually is capable of reallocating in place. If you have to reallocate, it's going to be a performance hit, but it's not worse than reallocating anything else. You probably won't feel it unless the n in O(n) for linear copying is very large: on the order of thousands for really big, contained objects that eat memory.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by LyTning94
    My question was more of whether or not it costs performance to allocate more memory if movement of the vector is unnecessary and, as a result, if it is wise to to reserve memory if you have a general idea, but don't know exactly, how much memory needs to be allocated.
    If you are using reserve as an optimisation rather than to avoid invalidation of iterators due to reallocation, then the general optimisation guideline applies: measure to be sure.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Mar 2011
    Posts
    61
    Quote Originally Posted by whiteflags View Post
    I'm not aware of any implementation that actually is capable of reallocating in place. If you have to reallocate, it's going to be a performance hit, but it's not worse than reallocating anything else. You probably won't feel it unless the n in O(n) for linear copying is very large: on the order of thousands for really big, contained objects that eat memory.
    So...you're saying that if a vector had adjacent unallocated memory, and you pushed a value into the vector which exceeded its reserved size, it couldn't just allocate some of the adjacent memory for the new value, but instead has to reallocate memory for the entire thing and copy the vector?

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by LyTning94
    So...you're saying that if a vector had adjacent unallocated memory, and you pushed a value into the vector which exceeded its reserved size, it couldn't just allocate some of the adjacent memory for the new value, but instead has to reallocate memory for the entire thing and copy the vector?
    Yes, at least with the standard allocator used by a "typical" vector implementation.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by laserlight View Post
    Yes, at least with the standard allocator used by a "typical" vector implementation.
    Is it possible...to implement it otherwise?
    How would the allocator know what is occupied memory and what isn't, out of the piece reserved?

  10. #10
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by manasij7479 View Post
    Is it possible...to implement it otherwise?
    How would the allocator know what is occupied memory and what isn't, out of the piece reserved?
    Realloc, or simmilar OS specific functions could make it work. The problem is, the standard containers wouldn't know to call such a function, since it's not part of the allocator "interface".
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  11. #11
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    It isn't possible to implement with a stateless allocator. Nevertheless, with a stateful allocator, it is possible. That is to say, if the allocator remembers if it has previously allocated memory, it can probably deduce that the container wants to reallocate. Care needs to be taken care of, but certainly it's possible.

    Quote Originally Posted by manasij7479 View Post
    Is it possible...to implement it otherwise?
    How would the allocator know what is occupied memory and what isn't, out of the piece reserved?
    Every operating system typically uses virtual memory and hence gives functions to manipulate said thing. Windows, for example, allows you to allocate and reserve and even query the status of virtual pages. This allows you to see if an adjacent page is used or not.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #12
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > I know it costs performance when the entire vector has to be copied to a new location,
    > but if it is just allocating more memory (without copying) does it make a difference?
    This smacks of premature optimisation disease.
    Yes, there is likely a performance hit.

    But the elephant in the room is still likely to be your file I/O. Modern processors execute millions of instructions in the time it takes a hard disk to do a sector seek (and there will be a lot of those in a large file). Plenty of time to relocate your data structure before anything else has a chance to notice.

    It MIGHT be worth doing after you've finished the program and done some decent profiling with real data.
    Before then - it's just a distraction from you getting it finished and working.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Reserve a range in virtual memory at link time
    By pheres in forum Windows Programming
    Replies: 11
    Last Post: 12-10-2009, 11:15 AM
  2. a good idea
    By luoyangke in forum C Programming
    Replies: 6
    Last Post: 12-02-2009, 12:03 PM
  3. Are namespaces a good idea?
    By Crilston in forum Game Programming
    Replies: 6
    Last Post: 06-24-2005, 06:30 PM
  4. Is my career idea good?
    By face_master in forum A Brief History of Cprogramming.com
    Replies: 26
    Last Post: 08-06-2002, 01:01 PM
  5. Good idea, bad idea.
    By sean in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 06-15-2002, 12:26 PM