Выделение кучи против std :: vector

Question

Мне нужно создать мульти-дерево в критической части моего кода. Стандартный способ - использовать что-то вроде:

struct node{ // or class
   ... data ...
  std::unordered_set<node*> children
};

node* root;

Важным моментом является то, что после создания узла он не будет удален, пока не будет удалено все дерево.

очевидный способ - использовать операторы new и delete для управления этими данными в куче. Готово.

Мне интересно, стоит ли изучать производительность использования std :: vector вместо new / delete напрямую:

struct node{ // or class
   ... data ...
  std::unordered_set<uint_32> children
};

std::vector<node> tree;
uint_32 root; // probably always 0, fist element of vector

Удаление дерева будет простым сделано с tree.clear();

Есть ли шанс, что это будет быстрее для больших (или огромных) деревьев?

Answer 1

Я предполагаю, что у вас есть дерево размером примерно в 10 миллионов + элементов (или, по крайней мере, примерно в 100k + элементов), которое нужно учитывать.

Тогда все зависит от того, как используются ваши данные и дерево. Обычно вызывает беспокойство пространственность данных, но это не очевидно, если это ваш случай. Если дерево много пересекается после построения (в некоторой степени противоположно частому изменению) и только немного изменяется, тогда имеет смысл попытаться организовать данные таким образом, чтобы они повторялись непрерывно (как обычно std::vector) . В этом случае вы не хотите иметь такие указатели или, скорее, не хотите использовать один элемент new / delete наверняка, поскольку это почти гарантировано ошибка (поскольку вы не можете рассчитывать на то, что элементы размещаются в памяти непрерывно), но все зависит от вашего варианта (ов) использования.

Простой метод и радикально иной подход будут be:

std::vector< std::pair<PathInTree, Node> > tree;

Затем сделайте его отсортированным таким образом, чтобы Node отображались в том порядке, в котором вы повторяете дерево. Это несколько крайнее решение и имеет недостатки, в том числе то, что теперь вставка может стать дорогостоящей, если происходит много случайных вставок. Также я не упомянул, как реализовать Path в дереве, но обычно это должна быть какая-то последовательность (например, в структуре файловой системы).

Answer 2

Учитывая, что каждый экземпляр std::unordered_set<uint_32> по-прежнему будет приводить как минимум к еще одному выделению памяти в куче (внутренне), реально достижимая экономия жестко ограничена. Вы собираетесь сэкономить менее 50% необходимого распределения кучи.

Важно то, что после создания узла он не будет удален, пока не будет удалено все дерево.

Перераспределение все еще происходит в std::vector по мере его роста. В отличие от неподвижных выделений в куче, это дополнительно включает перемещение уже выделенных узлов. В зависимости от того, какие другие атрибуты имеют ваши элементы node, это может быть еще дороже. Вам также необходимо убедиться, что ваш класс node совместим с семантикой перемещения.

Поскольку std::unordered_set также выделяется в куче, вы также не сможете избежать возникающей фрагментации памяти.

В общем, если вы не ожидаете, что будете ограничены производительностью распределения кучи или у вас нет варианта использования для обхода дерева, независимого от порядка, сжатие node экземпляров, вероятно, не будет стоить усилий.

Потенциально разумной оптимизацией будет замена std::unordered_set<node*> на std::unordered_set<node>. Если вам не нужно это косвенное обращение в этом месте (внешние указатели?), Это сэкономит вам столько же, сколько и ваша собственная попытка, без ущерба для возможностей отладки.

Реализация необходимой функции ha sh и оператора равенства для node обычно легко.

Если производительность вызывает реальную озабоченность, и у вас также есть (разумная) верхняя граница количества дочерних узлов на узел, вы можете подумать о замене std::unordered_set<uint_32> children на std::array<uint_32, n> children вместо использования std::find() для обнаружения коллизий.

Причина этого довольно проста: node становится TriviallyCopyable , что внутренне сокращает перераспределение до простого memcpy. Примерно для 16 детей это будет нейтральным с точки зрения потребления памяти, но все же быстрее.