CODEWITHSUNDEEP
c++pointersc++11optimizationcontainers
Pietro
Pietro

Reputation: 13222

Performance of container of objects vs performance of container of pointers

class C { ... };
std::vector<C> vc;
std::vector<C*> pvc;
std::vector<std::unique_ptr<C>> upvc;

Depending on the size of C, either the approach storing by value or the approach storing by pointer will be more efficient.

Is it possible to approximately know what this size is (on both a 32 and 64 bit platform)?

Upvotes: 3

Views: 1063

Answers (3)

jschultz410
jschultz410

Reputation: 2899

For a Plain Old Data (POD) type, a vector of that type is always more efficient than a vector of pointers to that type at least until sizeof(POD) > sizeof(POD*).

Almost always, the same is true for a POD type at least until sizeof(POD) > 2 * sizeof(POD*) due to superior memory locality and lower total memory usage compared to when you are dynamically allocating the objects at which to be pointed.

This kind of analysis will hold true up until sizeof(POD) crosses some threshold for your architecture, compiler and usage that you would need to discover experimentally through benchmarking. The above only puts lower bounds on that size for POD types.

It is difficult to say anything definitive about all non-POD types as their operations (e.g. - default constructor, copy constructors, assignment, etc.) can be as inexpensive as a POD's or arbitrarily more expensive.

Upvotes: -1

Thomas Matthews
Thomas Matthews

Reputation: 57749

Let's look at the details of each example before drawing any conclusions.

Vector of Objects

A vector of Objects has first, initial performance hit. When an object is added to the vector, it makes a copy. The vector will also make copies when it needs to expand the reserved memory. Larger objects will take more time to copy, as well as complex or compound objects.

Accessing the objects is very efficient - only one dereference. If your vector can fit inside a processor's data cache, this will be very efficient.

Vector of Raw Pointers

This may have an initialization performance hit. If the objects are in dynamic memory, the memory must be initialized first (allocated).

Copying a pointer into a vector is not dependent on the object size. This may be a performance savings depending on the object size.

Accessing the objects takes a performance hit. There are 2 deferences before you get to the object. Most processors don't follow pointers when loading their data cache. This may be performance hit because the processor may have to reload the data cache when dereferencing the pointer to the object.

Vector of Smart Pointers

A little bit more costly in performance than a raw pointer. However, the items will automatically be deleted when the vector is destructed. The raw pointers must be deleted before the vector can be destructed; or a memory leak is created.

Summary

The safest version is to have copies in the vector, but has performance hits depending on the size of the object and the frequency of reallocating the reserved memory area. A vector of pointers takes performance hits because of the double dereferencing, but doesn't incur extra performance hits when copying because pointers are a consistent size. A vector of smart pointers may take additional performance hits compared to a vector of raw pointers.

The real truth can be found by profiling the code. The performance savings of one data structure versus another may disappear when waiting for I/O operations, such as networking or file I/O.

Operations with the data structures may need to be performed a huge amount of times in order for the savings to be significant. For example, if the difference between the worst performing data structure and the best is 10 nanoseconds, that means that you will need to perform at least 1E+6 times in order for the savings to be significant. If a second is significant, expect to access the data structures more times (1E+9).

I suggest picking one data structure and moving on. Your time developing the code is worth more than the time that the program runs. Safety and Robustness are also more important. An unsafe program will consume more of your time fixing issues than a safe and robust version.

Upvotes: 8

ezaquarii
ezaquarii

Reputation: 1916

Yes, it is possible - benchmark it. Due to how CPU caches work these days, things are not simple anymore.

Check out this lecture about linked lists by Bjarne Stroustrup: https://www.youtube.com/watch?v=YQs6IC-vgmo

Here is an excelent lecture by Scott Meyers about CPU caches: https://www.youtube.com/watch?v=WDIkqP4JbkE

Upvotes: 8

Related Questions