Лучший способ представить форматированный текст в памяти? C++
Я пишу простой текстовый редактор, ну, на самом деле это блок управления редактированием, в котором я хочу написать код, числовые значения и выражения для моей основной программы.
В настоящее время я делаю так, чтобы строки символов вводились в элемент управления редактирования. В элементе управления редактирования у меня есть класс, который разбивает строку на "глифы", такие как слова, числа, разрывы строк, табуляции, маркеры форматирования и т. Д. Например, глифы слов содержат строку, представляющую буквальное слово, и короткое целое число, которое представляет количество конечных пробелов. Глифы также содержат информацию, необходимую для рисования текста и вычисления переноса строк.
Например, текстовая строка "Меня зовут Карл" будет равна связанному списку глифов, например: NewLineGlyph → WordGlyph ("My", 1 пробел) → WordGlyph ("name", 1 пробел) → WordGlyph ("is", 1 пробелы) → WordGlyph ("Карл", 0 пробелов) → NULL.
Таким образом, вместо того, чтобы хранить строку в памяти как непрерывный блок символов (или WCHAR), она хранится небольшими порциями с потенциально большим количеством небольших выделений и освобождений.
Мой вопрос я должен быть обеспокоен фрагментацией кучи, делая это таким образом? Есть ли у вас какие-либо советы, как сделать это более эффективным? Или совершенно другой способ сделать это?:)
PS. Я работаю в C++ на Win7.
2 ответа
Стоит ли беспокоиться о фрагментации? Вероятно, ответ зависит от размера ваших документов (например, количества слов), объема редактирования и характера этих изменений. Подход, который вы обрисовали в общих чертах, может быть разумным для статического (только для чтения) документа, в котором вы можете "разобрать" документ один раз, но я полагаю, что за кулисами будет достаточно работы, чтобы сохранить ваши структуры данных в правильном состоянии, поскольку пользователь вносит произвольные изменения. Кроме того, вам придется решить, что такое "слово", что не всегда очевидно / непротиворечиво в каждом случае. Например, "трудолюбивый" одно слово или два? Если он один, значит ли это, что вы никогда не будете переносить слова через дефис? Или рассмотрим случай, когда "слово" не помещается на одной строке. В этом случае, вы просто усечете или захотите разбить слово между строк?
Моя рекомендация - хранить текст в виде блока и сохранять разрывы строк отдельно (как смещения в текстовом блоке), а затем пересчитывать разрывы строк по мере необходимости при каждом изменении. Если вас беспокоит фрагментация и минимизация количества выделений / освобождений, вы можете выделить блоки фиксированного размера, а затем сами управлять памятью внутри этих блоков. Вот что я сделал в прошлом:
Текст хранится в виде блока символов, но вместо того, чтобы иметь один непрерывный блок для всего документа, я поддерживаю связанный список блоков, которые всегда выделяются 4 КБ (т. Е. Либо 4 КБ однобайтовых символа, либо 2 КБ WCHAR). Другими словами, текст хранится в виде связанного списка массивов, где каждому массиву присваивается постоянный размер.
Каждый блок отслеживает, сколько места (то есть символов) используется / свободно в этом блоке.
При вставке одного или нескольких символов, если в текущем блоке есть место, я могу просто переместить память в этом блоке (выделение / освобождение не требуется). Если в текущем блоке нет свободного места, но в соседнем блоке есть свободное место, то я снова могу просто сместить память между существующими блоками (выделение / освобождение не требуется). Если оба блока заполнены, только тогда я могу выделить новый блок 4 КБ и добавить в соответствующую позицию в связанном списке.
При удалении одного или нескольких символов мне просто нужно сместить память (не более 4 КБ), а не весь текст документа. Мне также, возможно, придется освободить и удалить любые блоки, которые становятся полностью пустыми.
Я также делаю некоторую "сборку мусора", чтобы объединить свободное пространство в подходящее время. Это довольно просто и включает перемещение символов из одного блока в другой, так что некоторые блоки становятся пустыми и могут быть удалены.
С точки зрения операционной системы и / или библиотеки времени выполнения, все распределения / выделения имеют одинаковый размер (4 КБ), поэтому фрагментации нет. И так как я управляю содержимым этой памяти, я могу избежать фрагментации в своем выделенном пространстве, сдвигая содержимое памяти, чтобы устранить потерянное пространство. Другое преимущество состоит в том, что он минимизирует количество вызовов alloc/dealloc, что может быть проблемой производительности в зависимости от того, какой распределитель вы используете. Итак, это оптимизация как по скорости, так и по размеру - как часто это происходит?:-)
Я не буду беспокоиться о фрагментации кучи; современный менеджер кучи довольно хорошо справляется с этим.
Я мог бы беспокоиться о плохой локализации данных, хотя. С каждым глифом в качестве отдельного выделения в связанном списке (особенно в неинвазивном списке, таком как std::list), любой вид прохода по документу будет перепрыгивать через всю память потенциально без использования кэша.
Текстовые редакторы сложнее, чем кажутся на первый взгляд. Существует множество специализированных структур данных для представления блоков текста и структурированных документов. Каждый из них оптимизирует для различных типов операций. Я рекомендую поискать их объяснения, а затем рассмотреть типы операций, которые вам придется выполнять чаще всего.
Эта статья старая, но в ней много полезной информации: http://www.cs.unm.edu/~crowley/papers/sds.pdf