std::vector reserve being more costly than expected

Question

So I need to manually handle the memory allocated by an std::vector for efficiency purposes. And I noticed that my program was slower than expected, so I added this idiom everywhere in my code base:

const uint new_edges_capacity = mesh.edges.size() + 6;
if(new_edges_capacity > mesh.edges.capacity())
    mesh.edges.reserve(new_edges_capacity * 2);

Originally I was simply doing:

const uint new_edges_capacity = mesh.edges.size() + 6; 
mesh.edges.reserve(new_edges_capacity * 2);

Well, that first snippet is orders of magnitude faster than the second. I don't understand, the official documentation seems to suggest that reserve should already be doing the same check I am. However, perf definitely marks std::reserve as the most expensive operation in my code, and indeed the modification shows that not calling reserve and relying on it to check for allocation is faster.

An example of a function where I am using this pattern:

template
void HMesh::SplitFace(uint face_id, HMesh& mesh)
{
    mesh.vertex_data.push_back({});
    mesh.verts.push_back({&mesh});
    HMesh::MVert& c = mesh.verts.back();

    const uint new_edges_capacity = mesh.edges.size() + 6;
    if(new_edges_capacity > mesh.edges.capacity())
        mesh.edges.reserve(new_edges_capacity * 2);
    mesh.edges.push_back({&mesh});
    HMesh::MEdge& n00 = mesh.edges.back();
    mesh.edges.push_back({&mesh});
    HMesh::MEdge& n01 = mesh.edges.back();
    mesh.edges.push_back({&mesh});
    HMesh::MEdge& n10 = mesh.edges.back();
    mesh.edges.push_back({&mesh});
    HMesh::MEdge& n11 = mesh.edges.back();
    mesh.edges.push_back({&mesh});
    HMesh::MEdge& n20 = mesh.edges.back();
    mesh.edges.push_back({&mesh});
    HMesh::MEdge& n21 = mesh.edges.back();

    const uint new_faces_capacity = mesh.faces.size() + 2;
    if(new_faces_capacity > mesh.faces.capacity())
        mesh.faces.reserve(new_faces_capacity * 2);
    mesh.faces.push_back({&mesh});
    HMesh::MFace& f1 = mesh.faces.back();
    mesh.faces.push_back({&mesh});
    HMesh::MFace& f2 = mesh.faces.back();

    auto& face = mesh.faces[face_id];

    HMesh::MFace& f0 = face;

    HMesh::MEdge& e0 = face.EdgeD();
    HMesh::MEdge& e1 = face.EdgeD().NextD();
    HMesh::MEdge& e2 = face.EdgeD().PrevD();

    HMesh::MVert& v0 = e0.VertD();
    HMesh::MVert& v1 = e1.VertD();
    HMesh::MVert& v2 = e2.VertD();

    ConnectFace(f0, n00, e0, n10);
    ConnectFace(f1, n11, e1, n21);
    ConnectFace(f2, n20, e2, n01);

    Pair(n00, n01);
    Pair(n10, n11);
    Pair(n20, n21);

    AttachVertices(n00, c, v0);
    AttachVertices(n11, c, v1);
    AttachVertices(n20, c, v2);

    c.Data({
        (v0.Data().position + v1.Data().position + v2.Data().position) / 3.0,
        (v0.Data().uv + v1.Data().uv + v2.Data().uv) / 3.0,
        {0,0,1}
    });
}

ShadowRanger · Accepted Answer

You're not reimplementing reserve, you're reimplementing the resize operation when capacity is exhausted. Problem is, if you do this every time you insert an item, you're resizing every time, making every operation O(n) (as it has to move all the items from the original backing storage to the new, larger, storage). If you ran this every time, building from an empty vector, you'd see a pattern of:

Size  Capacity  Reallocation needed?
1     14        Yes
2     16        Yes (16 > 14)
3     18        Yes (18 > 16)
4     20        Yes (20 > 18)
... reallocations continue forever ...

and each of those resizes would cause a new allocation, a move of all existing elements, and clean up of the old allocation (with destructors of the moved-from objects firing). You haven't saved anything, because you force new allocations every time, in an effort to avoid unnecessary allocations (which is clearly unhelpful).

In the case with the if test, since you test against a value half of what you reserve if the test fails, it reallocates much less frequently:

Size  Capacity  Reallocation needed?
1     14        Yes
2     14        No  (2 + 6 <= 14)
3     14        No  (3 + 6 <= 14)
4     14        No  (4 + 6 <= 14)
5     14        No  (5 + 6 <= 14)
6     14        No  (6 + 6 <= 14)
7     14        No  (7 + 6 <= 14)
8     14        No  (8 + 6 <= 14)
9     30        Yes  (9 + 6 > 14)
... very rare reallocations ...

As you can see, your test means far less resizing activity.

If you're just trying to guess at how much space you need, don't; let vector resize automatically on demand (doubling every time it's necessary might save you a little time over the default amortized growth schedule, but it also wastes a lot of memory). reserve is for when you know how much space you need; using it over and over is expensive.

std::vector reserve being more costly than expected

Answers (2)

Related Questions