Проблема с реализацией "веревочной" структуры данных в C++

Question

Я пытаюсь сделать структуру данных веревки. Это тип двоичного дерева, то есть рекурсивная структура данных.

Назначение веревки состоит в том, что расщепление и конкатенация должны быть быстрыми, что означает, что вы избегаете копирования целых веревок.
Так, например, пользователь должен иметь возможность сказать rope1 + rope2 и ожидать результата в ~ логарифмическом времени.

Однако это представляет проблему:
Если веревка модифицирована, ее родители также изменяются косвенно.
Потому что моя цель состоит в том, чтобы сделать rope вставная замена для stringэто не приемлемо.

Мое решение это: всякий раз, когда есть какие- либо изменения в ropeЯ бы создал новый узел с небольшим изменением, оставив старые без изменений.

В теории, я думаю, что это будет работать довольно хорошо.

На практике, однако, это включает выделение кучи для (почти?) Каждой модификации строк.
Даже односимвольное изменение приведет к созданию нового объекта кучи, который не только сам по себе медленный, но и значительно уменьшает локальность памяти, что очень негативно влияет на производительность.

Как мне решить эту проблему?

Answer 1

Традиционный подход - копирование при записи: для этого вам необходимо пересчитать каждый выделенный узел.

Если измененный узел имеет refcount 1 (никто больше не ссылается на него), вам не нужно дублировать его.

Практическая проблема с этим заключается в том, чтобы с пользой отделить мутирование от немутатирующих операций:

    char& rope::operator[] (std::string::pos)

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

Этот подход был опробован для ранних реализаций std::string (где строка эквивалентна одноузловой веревке) iirc и выпала из фаворита; частично из-за проблемы мутации, а частично из-за того, что COW и требуемый пересчет становятся все более дорогостоящими, если вам приходится беспокоиться о многопоточности.

---

Как вы говорите, у веревки есть дополнительная проблема, если ваш узел содержит два независимых типа состояния: свою собственную строку и ссылки на свои дочерние узлы (поскольку это приводит к тому, что ссылочные мутации refcount/child распространяются вверх по дереву).

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

Получается ли полученная логарифмическая конкатенация, которую вы хотите? Возможно нет:

• Вы должны скопировать все неконечные узлы (и добавить новый корень), и число их - это число листьев.
• Вы также должны увеличивать пересчет листьев, хотя, линейный

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

Без этого вы получаете быстрые объединения, но произвольный доступ к символам может (непредсказуемо) выродиться в логарифмическое время, если им придется распространять операцию COW вверх по дереву.

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

Answer 2

На практике, однако, это включает выделение кучи для (почти?) Каждой модификации строк.

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

У Андрея Александреску отличный пример распределителя памяти в виде маленьких блоков в своей книге "Современный дизайн C++".