Лучший способ представить форматированный текст в памяти?C ++

Question

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

Способ, которым я сейчас занимаюсь, заключается в том, что я передаю строки символов в элемент управления редактирования. В элементе управления редактирования у меня есть класс, который разбивает строку на «глифы», такие как слова, числа, разрывы строк, табуляции, маркеры форматирования и т. Д. Например, глифы слов содержат строку, представляющую буквальное слово, и короткое целое число, которое представляет количество конечных пробелов. Глифы также содержат информацию, необходимую для рисования текста и вычисления переноса строк.

Например, текстовая строка «Меня зовут Карл» будет равна связанному списку глифов: NewLineGlyph → WordGlyph («Мой», 1 пробел) → WordGlyph («имя», 1 пробел) → WordGlyph («есть», 1 пробел) → WordGlyph («Карл», 0 пробел) → NULL.

Таким образом, вместо того, чтобы хранить строку в памяти как непрерывный блок символов (или WCHAR), она хранится небольшими порциями с потенциально большим количеством небольших выделений и освобождений.

Мой вопрос; я должен быть обеспокоен фрагментацией кучи, делая это таким образом? Есть ли у вас какие-либо советы, как сделать это более эффективным? Или совершенно другой способ сделать это? :)

PS. Я работаю в C ++ на Win7.

Answer 1

Стоит ли беспокоиться о фрагментации?Вероятно, ответ зависит от размера ваших документов (например, количества слов), объема редактирования и характера этих изменений.Подход, который вы обрисовали в общих чертах, может быть разумным для статического (только для чтения) документа, в котором вы можете «разобрать» документ один раз, но я полагаю, что будет достаточно работы, которая должна выполняться за кулисами, чтобы сохранить ваши структуры данныхв правильном состоянии, поскольку пользователь вносит произвольные изменения.Кроме того, вам придется решить, что такое «слово», что не всегда очевидно / непротиворечиво в каждом случае.Например, "трудолюбивый" одно слово или два?Если он один, значит ли это, что вы никогда не будете переносить слова через дефис?Или рассмотрим случай, когда «слово» не помещается на одной строке.В этом случае, вы просто урежете или вы хотите принудительно разбивать слово по строкам?

Моя рекомендация - хранить текст как блок и сохранять разрывы строк отдельно (как смещения в тексте).блок), затем пересчитывайте разрывы строк по мере необходимости при каждом изменении.Если вы беспокоитесь о фрагментации и минимизации количества распределений / освобождений, вы можете выделить блоки фиксированного размера, а затем сами управлять памятью внутри этих блоков.Вот что я делал в прошлом:

• Текст хранится в виде блока символов, но вместо того, чтобы иметь один непрерывный блок для всего документа, я поддерживаю связанный списокблоки, которым всегда выделяется 4 КБ (т. е. либо 4 КБ однобайтовых символа, либо 2 КБ WCHAR).Другими словами, текст хранится в виде связанного списка массивов, где каждый массив имеет постоянный размер.

• Каждый блок отслеживает, сколько места (т. Е. Символов)используются / свободны в этом блоке.

• При вставке одного или нескольких символов, если в текущем блоке есть место, я могу просто переместить память в этом блоке (выделение / освобождение не требуется).Если в текущем блоке нет свободного места, а в соседнем блоке есть свободное место, то я снова могу просто переместить память между существующими блоками (выделение / освобождение не требуется).Если оба блока заполнены, только тогда я могу выделить новый блок размером 4 КБ и добавить в соответствующую позицию в связанном списке.

• При удалении одного или нескольких символов мне просто нужно сдвинутьпамять (не более 4 КБ), а не весь текст документа.Мне также, возможно, придется освободить и удалить любые блоки, которые становятся полностью пустыми.

• Я также делаю некоторую «сборку мусора», чтобы объединить свободное пространство в подходящее время.Это довольно просто и включает перемещение символов из одного блока в другой, так что некоторые блоки становятся пустыми и могут быть удалены.

С точки зрения ОС и / или библиотеки времени выполнения, все распределения/ dellocations имеют одинаковый размер (4 КБ), поэтому фрагментации нет.И так как я управляю содержимым этой памяти, я могу избежать фрагментации в своем выделенном пространстве, сдвигая содержимое памяти, чтобы устранить потерянное пространство.Другое преимущество заключается в том, что он минимизирует количество вызовов alloc / dealloc, что может быть проблемой производительности в зависимости от того, какой распределитель вы используете.Итак, это оптимизация для скорости и размера - как часто это происходит ?: -)

Answer 2

Я бы не беспокоился о фрагментации кучи;Современный диспетчер кучи справляется с этим довольно хорошо.С каждым глифом в качестве отдельного выделения в связанном списке (особенно в неинвазивном списке, таком как std :: list), любой вид прохода по документу будет перепрыгивать через всю память потенциально без использования кэша.

Текстовые редакторы сложнее, чем кажутся на первый взгляд.Существует много специализированных структур данных для представления блоков текста и структурированных документов.Каждый из них оптимизирует для различных типов операций.Я рекомендую поискать их объяснения, а затем рассмотреть типы операций, которые вам придется выполнять чаще всего.

Эта статья старая, но в ней много полезной информации: http://www.cs.unm.edu/~crowley/papers/sds.pdf