Как избежать ненужных копий с рекурсивной структурой XML `boost::variable`

Question

Позвольте мне обратиться к следующему примеру из урока повышения духа о разборе структуры данных "мини-XML". Мой вопрос не имеет ничего общего с духом, он на самом деле о boost::variantи создание эффективных "рекурсивных" вариантов конструкций.

Вот код:

struct mini_xml;

typedef
    boost::variant<
        boost::recursive_wrapper<mini_xml>
      , std::string
    >
mini_xml_node;

struct mini_xml
{
    std::string name;                           // tag name
    std::vector<mini_xml_node> children;        // children
};

В этом уроке они показывают, как "адаптировать" struct mini_xml за boost::fusion, а затем написать спиртовые грамматики, которые загружают в него данные.

Однако недавно мне пришло в голову, что в этом примере есть тонкая проблема, которая может привести к значительным накладным расходам.

Проблема в том, что variant тип, mini_xml_nodeв этом примере не является ходом без броска. Причина в том, что он содержит boost::recursive_wrapper, recursive_wrapper<T>всегда представляет выделенный в куче экземпляр Tи не имеет пустого состояния. Когдаvariant содержащий recursive_wrapper перемещен, новое динамическое распределение сделано и новый Tэто движение построено из старого T - мы не можем просто взять на себя ответственность за старое Tпотому что это оставило бы старый вариант в пустом состоянии. (Я изучил это только после того, как попытался реализовать свой собственный тип варианта - это действительно то, что boost::variant делает afaict, и это действительно не ход без броска конструктивно в этом примере.)

Так как mini_xml_node не без ходу, конструктив, контейнер std::vector<mini_xml_node> children будет на "медленном пути" - когда он использует std::move_if_noexcept, он выберет копировать элементы, а не перемещать их. Это происходит, например, каждый раз, когда емкость вектора увеличивается. И когда мы копируем mini_xml_nodeКопируем всех своих детей.

Так, например, если я хочу разобрать с диска дерево XML, которое имеет глубину d и фактор ветвления bЯ считаю, что в конечном итоге мы будем копировать каждый лист дерева о d * log b раз, так как отодвигая назад в вектор b времена вызывает перераспределение о log b раз, и это произойдет для каждого предка листа.

У меня сейчас нет реального приложения, где я забочусь об этих накладных расходах, но мне легко представить, что я могу. Например, я мог бы захотеть написать высокопроизводительный синтаксический анализатор, использующий Spirit, для какой-нибудь небольшой служебной программы, которая проверит, например, имеет ли файл данных определенную форму, или посчитает некоторую статистику этого или что-то еще. И тогда вполне может быть, что время синтаксического анализа доминирует в общем времени выполнения утилиты, поэтому эти копии могут быть критичными для производительности.

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

1. Быстро и грязно: напишите класс-оболочку, который содержит mini_xml_node но конструктор перемещения явно помеченnoexceptхотя это не совсем noexcept, Это вызовет завершение, если выдается исключение, но это должно быть довольно редко...

2. Используйте альтернативу std::vector это не использует std::move_if_noexcept, а вместо этого просто использует move, Если я правильно понимаю, boost::vector Является ли это. Компромисс в том, что он не имеет строгой безопасности исключений, но не ясно, действительно ли это проблема здесь.

3. (Этот на самом деле не работает.) Добавить boost::blank как один из вариантов mini_xml_node,

когда blank является одним из типов значений, boost::variant имеет специальный код, который адаптирует его поведение - он будет использоватьblank как естественное пустое состояние при построении по умолчанию и при назначении с изменением типа.

Тем не менее, кажется, что положить blank в boost::variant не заходит так далеко, как позволяет мне без ходов построить вариант, даже если он содержит boost::recursive_wrapper тип. Проверено на колиру с бустом 1.63:

http://coliru.stacked-crooked.com/a/87620e443470b70c

(Может быть, это было бы полезно для boost::variant в будущем? Я хотел бы, чтобы конструктор перемещения передавал владение рекурсивно обернутому парню, переводил старый вариант в пустое состояние и помечал конструктор перемещения как noexcept.)