Уменьшение выделения памяти Переполнение стека
У меня возникли проблемы при разработке хорошей стратегии по сокращению выделения памяти для следующей проблемы:
Я строю дерево. При запуске у меня есть только рут, который содержит некоторые данные (список (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();
}
Решение
Если каждый узел должен поддерживать динамический сам список, тогда вы можете использовать std::vector::reserve() прежде чем позвонить всем этим push_back()s.
Однако, если вся длина определяется после того, как вы настроили корень, и этот начальный вектор остается неизменным, а затем вы просто «разделяете его» между каждым узлом, то сами узлы могут просто содержать указатели на данные внутри исходного вектора — тем самым устраняя почти все распределения вокруг этой структуры данных.
Другие решения
В основном, если вы не можете reserve векторы, основанные на некоторой эвристике, вы становитесь жертвой Алгоритм Шлемеля (более мягкая версия, потому что геометрический рост обеспечивает O (n) сложность времени на 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, Несмотря на то, что вам приходится повторять индексы дважды, тяжелая работа (геометрические вычисления) выполняется исключительно в первом цикле.