CODEWITHSUNDEEP
c++vector
Fadecomic
Fadecomic

Reputation: 1268

Returning copies of vector elements vs returning pointers to vector elements

I have an object like this:

class Node {
    float x, y, z;
    size_t tag;
    bool isFree;
    std::vector<size_t> connections; // Usually ~10-100 in length
};

Just to give you an idea of size. There is list of these node objects containing millions of instances, which I'll call std::vector<Node> masterNodes. I have a function elsewhere that returns a container of these objects, such as this one:

std::vector<Node> find_nodes()
{
    std::vector<Node> nodes;
    // copy some elements from masterNodes that meet our conditions
    return nodes;
}

My question is would it be more efficient to return a vector of Node* instead, or is my compiler going to optimize this enough that the gain would be minimal for objects like mine? E.g.

std::vector<Node*> find_nodes()
{
    std::vector<Node*> nodes;
    // point to some elements from masterNodes that meet our conditions
    return nodes;
}

I've seen some replies (such as this one) that suggest copies might be nearly as efficient as returning a pointer, acknowledging the danger of returning pointers to vector elements.

Upvotes: 4

Views: 142

Answers (4)

Felix Glas
Felix Glas

Reputation: 15524

Locality of reference

Real-life performance is very much dependant on hardware and if you know how to use it, much can be gained.

One of the biggest hardware induced performance gains can be made when utilizing locality of reference. This means that working with data located in close proximity, both in time and space, can make better use of the built-in CPU cache which is much faster than using the main memory (RAM).

This is why copying data, to allow contiguous local access, can give you a performance boost.

The opposite of this is using indirection. Indirection is the ability to access memory using a reference or pointer instead of the value itself. This allows you to avoid copying things, BUT you can not make good use of the CPU cache when the hardware has to fetch every bit of data from different places in main memory all the time.

Performance must be tested

Basically, copying big things will incur a one-time performance penalty but if you will work a lot with the data you can make up for this using locality of reference.

However, you have to test it yourself to know what works best for you. It might be that in your case the cost of copying the data will incur a bigger performance penalty than better use of the CPU cache will make up for.

Upvotes: 1

srdjan.veljkovic
srdjan.veljkovic

Reputation: 2548

It would it be more efficient to return a vector of Node*, because your nodes is a vector of copies of Nodes from masterNodes, and your Node is much bigger than a pointer. Nothing like Return Value Optimisation or move-semantics can help with the fact that you have (and return) a vector of copies.

BTW, you may return a vector<vector<Node>::iterator> instead ofvector<Node*>. It is as efficient as Node*, at least in the release build, but usually has some integrated checks in the debug build, which could help.

Upvotes: 1

Raydel Miranda
Raydel Miranda

Reputation: 14360

You should try std::copy_if algorithm, according to the reference:

In practice, implementations of std::copy avoid multiple assignments and use bulk copy functions such as std::memmove if the value type is TriviallyCopyable.

You can make your Node implementation match the requirements to be considered TriviallyCopyable (use std::array, instead std::vector for connections), so using std::copy_if should be very fast.

On the other hand, copying nodes is limited by the memory, if you don't have enough memory, you could get an out of memory error, if you are sure you never will return more that 100 nodes, well, you have this controlled.

And if you work with pointers, the application would have to manage the memory, this decrease the ammount of memory used, but can encrease the time needed due memory management.

But the best answer you will get, is your test both options.

Upvotes: 0

cradondy
cradondy

Reputation: 1

When you use std::vector<Node> as method return, you duplicate all data and that takes time. Using std::vector<Node*> allows you to only have addresses of data and no duplication is done. But if you use this choice, you have to be careful with modifications of data because modifications are done in your masterNodes.

Upvotes: 0

Related Questions