性病:病媒储备比预期成本更高

Question

因此，为了提高效率，我需要手动处理由std：：向量分配的内存。我注意到我的程序比预期的慢，所以我在代码库中到处添加了这个成语：

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

最初我只是在做：

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

嗯，第一个片段比第二个片段快几个数量级。我不明白，官方文件似乎表明储备应该已经在做同样的检查了但是，perf肯定将std::reserve标记为代码中最昂贵的操作，而且修改确实表明，不调用保留并依赖它检查分配速度更快。

使用此模式的函数示例：

template<typename V>
void HMesh<V>::SplitFace(uint face_id, HMesh<V>& mesh)
{
    mesh.vertex_data.push_back({});
    mesh.verts.push_back({&mesh});
    HMesh<V>::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<V>::MEdge& n00 = mesh.edges.back();
    mesh.edges.push_back({&mesh});
    HMesh<V>::MEdge& n01 = mesh.edges.back();
    mesh.edges.push_back({&mesh});
    HMesh<V>::MEdge& n10 = mesh.edges.back();
    mesh.edges.push_back({&mesh});
    HMesh<V>::MEdge& n11 = mesh.edges.back();
    mesh.edges.push_back({&mesh});
    HMesh<V>::MEdge& n20 = mesh.edges.back();
    mesh.edges.push_back({&mesh});
    HMesh<V>::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<V>::MFace& f1 = mesh.faces.back();
    mesh.faces.push_back({&mesh});
    HMesh<V>::MFace& f2 = mesh.faces.back();

    auto& face = mesh.faces[face_id];

    HMesh<V>::MFace& f0 = face;

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

    HMesh<V>::MVert& v0 = e0.VertD();
    HMesh<V>::MVert& v1 = e1.VertD();
    HMesh<V>::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}
    });
}

Answer 1

您没有重新实现reserve，而是在容量耗尽时重新实现大小调整操作。问题是，如果每次插入项时都这样做，那么每次都要调整大小，使每个操作都是O(n) (因为它必须将所有项从原始备份存储移动到新的、更大的存储中)。如果您每次都从空的vector中运行此模式，您将看到以下模式：

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 ...

而每一个调整大小都会导致新的分配，所有现有元素的移动，以及旧分配的清理(使用已移动对象的析构函数触发)。您没有保存任何东西，因为每次都强制进行新的分配，以避免不必要的分配(这显然是没有帮助的)。

在if测试的情况下，如果测试失败，根据reserve值的一半进行测试，因此重新分配的频率要低得多：

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 ...

如您所见，您的测试意味着调整活动的大小要少得多。

如果您只是想猜测您需要多少空间，不要；让vector按需自动调整大小(必要时加倍可能会比默认的摊销增长计划节省一点时间，但也浪费了大量内存)。reserve用于当您知道您需要多少空间时，反复使用它是很昂贵的。

Answer 2

你根本不需要预约。用索引就行。

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

    const uint n = mesh.edges.size();
    mesh.edges.push_back({&mesh});
    mesh.edges.push_back({&mesh});
    mesh.edges.push_back({&mesh});
    mesh.edges.push_back({&mesh});
    mesh.edges.push_back({&mesh});
    mesh.edges.push_back({&mesh});
 
    auto & n00 = mesh.edges[n + 0];
    auto & n01 = mesh.edges[n + 1];
    auto & n10 = mesh.edges[n + 2];
    auto & n11 = mesh.edges[n + 3];
    auto & n20 = mesh.edges[n + 4];
    auto & n21 = mesh.edges[n + 5];

    const uint f = mesh.faces.size();
    mesh.faces.push_back({&mesh});
    mesh.faces.push_back({&mesh});

    auto& f0 = mesh.faces[face_id];
    auto& f1 = mesh.faces[f + 0];
    auto& f2 = mesh.faces[f + 1];

    auto& e0 = f0.EdgeD();
    auto& e1 = f0.EdgeD().NextD();
    auto& e2 = f0.EdgeD().PrevD();

    auto& v0 = e0.VertD();
    auto& v1 = e1.VertD();
    auto& 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}
    });
}