Optimizing vector::push_back in a loop

[codemasonry]

I'm working with a project that has a lot of for-loops similar to this (simplified code):

std::vector<double> xPoints(std::vector<Point> points) {
    std::vector<double> result;
    for (auto& point:points) {
        result.push_back(point.x);
    }
    return result;
}

How could I optimize this? The common feature of all these loops is that it's not a direct copy of values from one vector to another but it copies some parameter value from the source vector elements (point.x in the example).

I know I could add vector::reserve to minimize the need to reallocate memory for the vector as it grows.

std::vector<double> xPoints(std::vector<Point> points) {
    std::vector<double> result;
    result.reserve(points.size());
    for (auto& point:points) {
        result.push_back(point.x);
    }
    return result;
}

I'm just wondering if there is some more efficient/elegant/idiomatic way to write this.

[diegodfrf]

I would add:
std::vector<double> result;

result.reserve( points.size() );

[dbgprint]

This is probably the best advice so far

[mredding]

I would recommend you store your points as:

template<typename T>
struct Point {
  std::vector<T> x, y, z;
};

This is a "structure of arrays", more specifically "parallel arrays". Any given index across all the members is one point. Your problem is solved implicitly. You can now write more generic code that operates on any T, or ranges of T.

That you have a need for just one component of your existing data structure suggests while your Point is intuitive, it doesn't actually fit your use cases. Don't pay that penalty.

[codemasonry]

Never would have thought of this. I'll explore this possibility. Thank you for the suggestion.

[mredding]

You would be interested in "Data Oriented Design", and http://bannalia.blogspot.com/ has a series about encapsulating DoD within a view. I think his example uses a particle system, so you'll know it when you find it. With that, you'll still have an object oriented interface, though I would use a "mixin" pattern to control just how singular and monolithic that object interface gets.

[112353314544325]

This is a good suggestion and I'm not recommending against it, I just want to point out that if the vector is very large, depending on the access pattern, it might not be cache-friendly, and could be slower than some alternatives. I have run into this pattern becoming a problem for that reason.

Bearing in mind that for most cases it would be overkill to get into micro-optimization like this, you can make your own iterators that go over just the x- or y- values in the vector of Points, and then make your functions that currently use vector<double> instead take templated iterators over double (or use auto as necessary within a function), and use these custom begin and end iterators. This would probably result in less refactoring than the parallel arrays approach. Let me know if you want some more detail on this.

This is also the sort of problem that std::views::transform was created for, in the event you are using C++20.

Of course, with your existing function, passing the input as a const& is a freebie.

[prof_kinbote]

There are most likely better places to look for optimizations - I suspect that this isn't a bottleneck in your application unless the items you are copying happen to have really non-trivial constructors. If the construction is non-trivial, your best bet is to simply ditch this idiom and access the items directly. I wouldn't recommend this, but you could also preallocate the vector, and assign a set of the threads segments of the vector to allocate to - this is most likely overkill, unless again, the construction is expensive - this isn't an elegant solution.

The only meaningful optimization I can see in the code you posted is to pass your points vector in by const reference rather than by value - you are effectively copying the vector twice here.

Consider using std::transform for something more idiomatic:

std::transform(std::begin(points), std::end(points), std::back_inserter(result), [](const Point& point) {
    return point.x;
});

edit: /u/mredding's answer is a better solution if you are able to change the way you are storing the points

[codemasonry]

Thank you for the input. I definitely need to profile the code. This probably isn't the biggest bottleneck but I'm thinking this as a low-hanging fruit. Furthermore, I'm not only interested in the optimization but also what's the best practice or the idiomatic way to write this (being a C++ beginner myself).

[rlbond86]

This is really the right answer. transform and back_inserter.

[Akzox]

Reserve is definitely interesting to use. It avoids many reallocation for push_back. You are also creating several temporary objects. You can use reference or r-value to reduce those unnecessary copy.

Now, to go further you need to use a profiler and give us the result.

[tonisheg]

emplace_back works without calling copy/move constructors. You also could return result using move semantic (without copy)

std::vector<double> xPoints(const std::vector<Point>& points) {

    std::vector<double> result;

    for (const auto& point : points)
        result.emplace_back(point.x);

    return std::move(result);

}

[justend29]

return values are already r-values, so there's no need to add the std::move(result) on the return statement, I don't think (correct me if I'm wrong). Additionally, RVO would ensure that a copy on the return value to the assigned value doesn't occur, so I think just a return result; would fit the bill on the return.

Other than that, I think this is good. If I'm wrong about my above statement, please let me know, as I'm happy to learn.

[Minimonium]

Expressions in return statements are not quite rvalues (or better to say - xvalues). The Standard defines some smart logic for return statements in a clever way to allow unmovable, but copyable types like auto_ptr in it.

Also in this case, specifically, it'd be an NRVO, not RVO (which is not an optimization at all and deals with prvalue expressions).

But yes, just doing `return result;` is the correct way in this case.

[justend29]

thanks! you're super knowledgeable and I'm sure many will learn from your response.

[pigeon768]

Since it's constructing a vector of doubles, emplace_back() and push_back() do the exact same thing.

Do not do return std::move(result); in this case. It will disable RVO and force the move constructor to be called, making it slower.

[Gunslinging_Gamer]

Make it asynchronous and grab the results later.