减少内存分配C++

Question

我很难想出一个好的策略来减少以下问题的内存分配：

我正在建造一棵树。开始时，我只有包含一些数据的根(索引列表(std::vector((。我分成两部分，其中一部分索引归左边的孩子，另一部分归右边的孩子。我不知道有多少人会向左/向右走。一旦我完成了根的处理，我不再需要为它存储索引。事实上，我只对那些叶子感兴趣。此外，每次拆分时都可以添加其他数据！因此，如果根有 20 个元素，那么拆分后左边的根可能有 12 个元素，右边的根可能有 10 个元素。

在每个节点中，我保留一个包含这些索引的std::vector。当我添加元素时，我push_back()导致许多内存分配的元素。

保持指数的好策略是什么？

该问题与SBVH数据结构的生成有关。

法典：

struct Node {
     std::vector<unsigned> indices_;
     // ... some other stuff here
}
void partition(Node* node) {
    Node* left = new Node();
    Node* right = new Node();
    float axis = findSplitPosition(node);
    for(size_t i = 0; i < node->indices_.size(); ++i) {
        if (index is strictly left on axis) {
            left->indices_.push_back(node->indices_[i]);
        } else if(index is strictly right on axis) {
            right->indices_.push_back(node->indices_[i]);
        } else {
            // it intersects the axis -> add to left and right
            left->indices_.push_back(node->indices_[i]);
            right->indices_.push_back(node->indices_[i]);
        }
    }
    // root indices no longer needed
    node->indices_.clear();
}

Answer 1

如果每个节点本身都必须维护一个动态列表，那么您可以在调用所有这些push_back()之前使用 std::vector::reserve()。

但是，如果在设置根后确定了整个长度，并且初始向量保持不变，然后只需在每个节点之间"拆分"它，那么节点本身可以简单地保留指向初始向量内数据的指针，从而消除围绕此数据结构的几乎所有分配。

Answer 2

基本上，如果你不能根据一些启发式方法reserve向量，你就会成为施莱米尔算法的受害者(虽然是一个温和的版本，因为几何增长确保了n连续插入而不是 O(n^2((的时间复杂度(。

但是，如果您

首先浏览节点的索引并记录给定的索引是否应该转到左侧子节点，右侧子节点或两者，则可以获得恒定数量的分配。还要跟踪左/右子节点的索引计数：

struct Foo {
    bool goesIntoLeft;
    bool goesIntoRight;
};
std::vector<Foo> foo;
foo.reserve(node->_indices.size());
int leftCount = 0;
int rightCount = 0;
for (auto i = 0; i < node->_indices.size(); ++i) {
    if (index goes into left) {
        foo.push_back({ true, false });
        ++leftCount;
    } else if (index goes into right) {
        foo.push_back({ false, true });
        ++rightCount;
    } else { // goes into both
        foo.push_back({ true, true });
        ++leftCount;
        ++rightCount;
    }
}
std::vector<Node> leftNodes;
leftNodes.reserve(leftCount);
std::vector<Node> rightNodes;
rightNodes.reserve(rightCount);
for (auto i = 0; i < node->_indices.size(); ++i) {
    if (foo[i].goesIntoLeft) leftNodes.push_back(nodes._indices[i]);
    if (foo[i].goesIntoRight) rightNodes.push_back(nodes._indices[i]);
}

这样你只做 3 个分配，即 foo、leftNodes、rightNodes 。尽管您必须遍历索引两次，但繁重的工作(几何计算(仅在第一个循环中完成。