8

In this case the question scenario is a game, so all resources are allocated at the beginning then iterated over for a level.

The objects being stored in the vector are instances of complex classes, and of course the actual copying them into the vector at load-time is time-consuming, but of low-concern.

But if my main concern is the speed of iteration over the class objects at runtime, would I be better to store the class objects themselves in the vector, rather than just pointers to the class objects as is traditionally recommended?

I am not worried about memory management in this example, only speed of iteration.

metamorphosis
  • 1,972
  • 16
  • 25
  • 6
    If you're talking about an already-built vector, the performance difference will be marginal, but *could* favor the vector-of-objects, as one indirection level is eliminated. And as always, *profile both* and see for yourself. – WhozCraig Mar 28 '14 at 03:35
  • 1
    But wouldn't the data being contiguous - in the vector-of-objects scenario - inherently make for faster iteration? – metamorphosis Mar 28 '14 at 03:55
  • 1
    Are they all the same type? If not then you must use pointers to avoid slicing. – Retired Ninja Mar 28 '14 at 03:56
  • 2
    @metamorphosis among other reasons, yes. but chances are your "object" also has dynamic members of it own (most do; strings, other vectors, etc). If its a true POD-type and small enough to have a nice load in the data cache, there is little doubt a vector-of-objects will perform better, again assuming we're talking about an already-built vector. But like I said, **profile** it. – WhozCraig Mar 28 '14 at 04:11
  • 1
    Thanks WhozCraig, that's pretty much the answer I was trying to find. – metamorphosis Mar 28 '14 at 04:14
  • Using a vector of objects could help make tight loops over the data more [cache friendly](http://stackoverflow.com/a/16699282/2507444), but as @WhozCraig pointed out, profiling is definitely a tool you should use to figure out what the actual performance impact is in your application. I've made multiple games (student projects admittedly) that have used vectors of points in many places and have that has never been the bottle neck for me. There are certainly situations where it can be, but as with most issues regarding optimization it is best to profile. – Peter Clark Mar 28 '14 at 04:33
  • 2
    Also note that if it were an issue, the array of pointers could be made more cache friendly by providing a custom allocator to the vector so that the objects are allocated from a memory pool of contiguous memory. – Peter Clark Mar 28 '14 at 04:35

3 Answers3

9

I'm answering this question late, but the performance aspect is important and the answers online so far have been purely theoretical and/or focusing exclusively on the memory-management aspects. So here is some actual benchmarking info on three related scenarios I recently tried. Your results may be different but at least there's some idea of how things pan out in a practical application.

The class A referenced here has about 10 member fields, half of which are primitives and the other half are std::string, std::vector<int>, and other dynamically sized containers. The application has already been fairly optimized and thus we would like to see which architecture now gives us the fastest looping over the collection of A. The values of any of A object's member fields may be changing over the application lifetime, but the number of A objects in the vector do not change over the many repeated iterations we perform (this continual iterating constitutes about 95% of this application's execution time). In all scenarios, looping was performed with the typical std::iterator or std::const_iterator. Each enumerated A object has at least several member fields accessed.

Scenario 1 — Vector Of Object Pointers

Although the simplest, this architecture of std::vector<A*> ended being slightly slower than the others.

Scenario 2 — Vector Of Object Pointers, Objects Are Allocated Using Placement New

The idea behind this approach is that we can improve the locality of caching by forcing our objects to be allocated into contiguous memory space. So the std::vector<A*> of object pointers is guaranteed to be contiguous by the std::vector implementation and the A objects themselves will also be contiguous on the heap because we've used the placement new idiom. I used the same approach outlined in this answer; more info on placement new can be found here.

This scenario was 2.7% faster than Scenario 1.

Scenario 3 — Vector Of Objects

Here we use std::vector<A> directly. The std::vector implementation guarantees our A objects will be contiguous in memory. Note that a std::vector of objects does involve considerations of the move and copy constructors of A. To avoid unnecessary moving and/or reconstruction, it is best to std::vector.reserve() the maximum possibly needed size in advance (if possible) and then use std::vector.emplace_back() (instead of push_back()) if at all possible. Looping over this structure was the fastest because we are able to eliminate one level of pointer indirection.

This approach was 6.4% faster than Scenario 1.

A related answer to a different question also shows that plain objects (as class members) can be quite faster than the respective pointers (as class members).

Community
  • 1
  • 1
Special Sauce
  • 5,338
  • 2
  • 27
  • 31
1

The first thing is pointers should be used for storing bulky things . Because if you use array of objects if would be creating n bulky objects and copy each one everytime its stored(it is also a big cost) And the second thing if you are using vectors(STL)The vectors size grows every time its gets full of memory. The main cost is copying the data of first in second and this is actually the main cost i.e copying. Also this cost is minimal cost that would be incured if use built in.

Gauri
  • 11
  • 3
  • 1
    This doesn't answer my question. This is the 'standard' answer, relevant to memory management but not speed of iteration. – metamorphosis Mar 28 '14 at 04:12
  • "if you are using vectors(STL)The vectors size grows as twice every time its gets full of memory" -- I don't know where you got that information from, but the standard does not specify anything like that. Implementations are allowed to have any kind of algorithm for reallocating and choosing a new bigger size. – Shoe Mar 28 '14 at 04:14
  • You are right it was my mistake its not growing twice everytime – Gauri Mar 28 '14 at 05:01
1

No, She is not wrong, she is absolutely right, though you are asking only about fast iteration, but that has alot of link with Memory... More the memory stack slower will be the access...

I have a live demo...

#include <iostream>
#include <string>
#include <vector>
#include "CHRTimer.h"

struct Items
{
    std::string name;
    int id;
    float value;
    float quantity;
};

void main()
{

    std::vector<Items> vecItems1;
    for(int i = 0; i < 10000; i++)
    {
        Items newItem;
        newItem.name = "Testing";
        newItem.id = i + 1;
        newItem.value = 10.00;
        newItem.quantity = 1.00;

        vecItems1.push_back(newItem);
    }

    CHRTimer g_timer;
    g_timer.Reset();
    g_timer.Start();
    for(int i = 0; i < 10000; i++)
    {
        Items currentItem = vecItems1[i];
    }
    g_timer.Stop();
    float elapsedTime1 = g_timer.GetElapsedSeconds();
    std::cout << "Time Taken to load Info from Vector of 10000 Objects -> " << elapsedTime1 << std::endl;

    std::vector<Items*> vecItems;
    for(int i = 0; i < 100000; i++)
    {
        Items *newItem = new Items();
        newItem->name = "Testing";
        newItem->id = i + 1;
        newItem->value = 10.00;
        newItem->quantity = 1.00;

        vecItems.push_back(newItem);
    }

    g_timer.Reset();
    g_timer.Start();
    for(int i = 0; i < 100000; i++)
    {
        Items *currentItem = vecItems[i];
    }
    g_timer.Stop();
    float elapsedTime = g_timer.GetElapsedSeconds();
    std::cout << "\nTime Taken to load Info from Vector of 100000 pointers of Objects -> " << elapsedTime;
}
Kamal Singla
  • 11
  • 1