10 Replies - 670 Views - Last Post: 22 September 2011 - 03:47 PM Rate Topic: -----

#1 bluebear1608  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 82
  • Joined: 03-June 08

What performance difference does initially setting size of vector make

Posted 22 September 2011 - 01:58 AM

Hi,

I have to write a report analyzing the performance of a program, and one of the questions is "What performance difference does initially setting the size of the vector make". I could not find any information on this, can anyone point me in the right direction? i have done a lot of googling but have not found anything useful.
Is This A Good Question/Topic? 0
  • +

Replies To: What performance difference does initially setting size of vector make

#2 PlasticineGuy  Icon User is offline

  • mov dword[esp+eax],0
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,436
  • Joined: 03-January 10

Re: What performance difference does initially setting size of vector make

Posted 22 September 2011 - 02:37 AM

The reason vectors might have increased performance from resizing is that the vector only allocates so much space on its first push. It allocates more when you exceed this, and continues as you push. This means it might have to do many more deallocation, allocation and copying routines than it otherwise might.
Was This Post Helpful? 0
  • +
  • -

#3 bluebear1608  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 82
  • Joined: 03-June 08

Re: What performance difference does initially setting size of vector make

Posted 22 September 2011 - 02:52 AM

just to clarify, you are saying that by initially setting the size of the vector, it would decrease the performance if you need to add more than that initial size because it has to deallocate, allocate and copy.
So how would you use a vector if you dont initially set the size? would you have to allocate more memory to the vector each time an element is added? In a situation where you KNOW you will not exceed that initial size, it would be faster to initially set the size of the vector because you wont need to spend time resizing the vector every time an element is added?
Was This Post Helpful? 0
  • +
  • -

#4 PlasticineGuy  Icon User is offline

  • mov dword[esp+eax],0
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,436
  • Joined: 03-January 10

Re: What performance difference does initially setting size of vector make

Posted 22 September 2011 - 04:15 AM

It allocates the extra memory automatically. Forcing it to a specific size helps it speed up because it doesn't need to guess how much memory you need.

Allocating and freeing dynamic memory is a fairly expensive operation, and can be quite slow.
Was This Post Helpful? 0
  • +
  • -

#5 bluebear1608  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 82
  • Joined: 03-June 08

Re: What performance difference does initially setting size of vector make

Posted 22 September 2011 - 04:51 AM

so my understanding is that it is generally better to initially set the size or at lease reserve memory for the vector. In a situation where the size is unknown, vector::reserve() could be used to reserve memory for the vector, rather than setting it to a specific size (number of elements). vector::reserve() doesn't affect the size of the vector and allows the vector to grow. If the vector grows to a point where it exceeds the reserved memory, reserve() can be called again to allocate more memory. In a situation where the size of the vector is known, the size of the vector can be initially set.
If a vector is used without having its size set or memory allocated, automatic memory allocation will occur and this may be costly.
Is this correct?
Was This Post Helpful? 0
  • +
  • -

#6 jimblumberg  Icon User is offline

  • member icon


Reputation: 3987
  • View blog
  • Posts: 12,300
  • Joined: 25-December 09

Re: What performance difference does initially setting size of vector make

Posted 22 September 2011 - 05:58 AM

Quote

If a vector is used without having its size set or memory allocated, automatic memory allocation will occur and this may be costly.

A vector normally allocates more memory for the vector than is initially required. For small vectors there maybe no further allocation required. If you know how large the vector will be you can reserve or set the size of the vector to the desired value, but in this case you may want to consider std::array. Always "reserving" or "manually sizing" your vector may actually take more time or use too much memory.

The only reliable way to know if you are having speed issues when using a vector is to profile and test your code.

Jim
Was This Post Helpful? 0
  • +
  • -

#7 bluebear1608  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 82
  • Joined: 03-June 08

Re: What performance difference does initially setting size of vector make

Posted 22 September 2011 - 06:19 AM

Generally speaking though, for a rather large vector, with over 10,000,000 elements, when the size of a vector is known, what is the best thing to do (just thinking about performance, not space)? is it best to use reserve(), to initialize the vector with a size, or just create an empty vector and rely on automatic memory allocation?
And when the size is unknown, what is the best thing to do?
Was This Post Helpful? 0
  • +
  • -

#8 jimblumberg  Icon User is offline

  • member icon


Reputation: 3987
  • View blog
  • Posts: 12,300
  • Joined: 25-December 09

Re: What performance difference does initially setting size of vector make

Posted 22 September 2011 - 07:06 AM

Quote

Generally speaking though, for a rather large vector, with over 10,000,000 elements, when the size of a vector is known, what is the best thing to do (just thinking about performance, not space)?


If you know that the "vector" will have a known size you may want to look at std::array. If you don't need the dynamic aspects of the vector then maybe vector is not the correct container.

Quote

is it best to use reserve(), to initialize the vector with a size, or just create an empty vector and rely on automatic memory allocation?

The difference between reserve() and size() is that reserve only reserves the memory, it does not add any elements. Size adds the elements and possibly initializes these elements, when using size() the system will usually reserve more memory than what is actually required.

Also remember if you are using user defined data types in your vector, and are concerned about speed, insure your constructors are as clean as possible, use initialization lists to initialize your class to avoid possible copy constructor calls.

Quote

And when the size is unknown, what is the best thing to do?

Again unless you know you have a performance issue I would let the vector do it's thing.

Also remember that the vector may not be the best choice for your container. If you only worry about how long it takes to create/populate your container and never consider how this container is used you may find that your "speed" problem is not in the creation, but in how you are using the data.

Jim
Was This Post Helpful? 0
  • +
  • -

#9 bluebear1608  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 82
  • Joined: 03-June 08

Re: What performance difference does initially setting size of vector make

Posted 22 September 2011 - 07:19 AM

i understand what you are saying, but this is for an assignment and i need to use vectors in my program, as well as discuss the performance implications of having to initially set a size for a vector. the questions just ask "What performance difference does initially setting size of vector make" so im trying to understand what the best thing to do in each situation (known size vs. not known size).
Was This Post Helpful? 0
  • +
  • -

#10 CodeGrappler  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 41
  • View blog
  • Posts: 120
  • Joined: 29-November 10

Re: What performance difference does initially setting size of vector make

Posted 22 September 2011 - 07:43 AM

If you know your std::vector is going to have a large amount of elements then you should always reserve as many "spaces" as you can.

std::vector only uses contiguous memory unlike std::deque. So every time the std::vector runs out of usable spaces it needs to allocate a new chunk of memory large enough to hold everything it had plus some amount more. Then it has to copy the old data to the new memory and delete the old memory.

If you know the size is going to be 1,000,000 then reserve 1,000,000.

If you don't know the exact size but you can guess that it will be over X then you should reserve X or even X + N.

The less memory allocation your std::vector has to do, the better.
Was This Post Helpful? 0
  • +
  • -

#11 bluebear1608  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 82
  • Joined: 03-June 08

Re: What performance difference does initially setting size of vector make

Posted 22 September 2011 - 03:47 PM

so my understanding is that if you know the size of a vector, it is still better to use reserve() instead of vector<type>(size) because the later creates a vector and initializes all the elements to the default value, which takes more time, also, it always allocates extra memory to the vector which is not needed if you know the exact size.
is this right?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1