19 октября 2013 в 16:46

Организация памяти в текстовом редакторе

Каждый, кто пытался запрограммировать хотя бы простейший редактор текста на низком уровне, сталкивался с задачей организации памяти для хранения редактируемого текста. Структура данных для хранения текста должна удовлетворять следующим требованиям:
  1. иметь малые накладные расходы по памяти. Большая часть доступной памяти должна использоваться для хранения текста, а не служебной информации;
  2. допускать эффективную вставку и удаление в произвольном месте текста.

Удовлетворить эти требования одновременно непросто. Если рассмотреть широкоизвестные структуры данных, такие как массивы, списки, деревья, стеки, очереди, кольцевые буфера — то такой структуры, которая бы позволила эффективно выполнить оба требования, не встречается. В случае массива имеем незначительные накладные расходы по памяти, но операция вставки имеет сложность O(n), где n — размер редактируемого текста. В случае списка сложность вставки и удаления составляет O(1), однако накладные расходы по памяти в несколько раз превышают размер собственно текста. Деревья, кучи, кольцевые буфера, ассоциативные массивы и прочие структуры и вовсе неприменимы для хранения текста в редакторе.

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

Предлагаю вашему вниманию эффективную структуру данных для хранения редактируемого текста, которая проста в реализации, имеет константные накладные расходы по памяти и быструю вставку/удаление в произвольном месте. Также она позволяет эффективно редактировать файлы, которые целиком не умещаются в оперативную память.

Несмотря на то, что эта структура данных была открыта давно и использовалась в текстовых редакторах на старых ЭВМ в 8-битную эпоху, это тайное знание предков было в значительной мере утеряно и в современных редакторах встречается редко. Попробуйте открыть файл, состоящий из одной строки мегабайт на 10, в Notepad или Far. Вставка и удаление символов будет длиться секундами.

Описание


Берем блок памяти фиксированного размера (в старых 8-битных ЭВМ под этот блок берется вся свободная память) и размещаем в начале этого блока редактируемый текст до курсора, а в конце блока — текст после курсора. Текст хранится в памяти двумя непрерывными кусками, а в промежутке между ними находится вся доступная для текста свободная память. В процессе редактирования текста поддерживаем этот инвариант: в начале буфера находится текст до курсора, а в конце — текст после курсора. Всё!

Такая структура данных называется в английской терминологии Gap Buffer. Русское название мне неизвестно, встречается только термин «буферное окно» в русской Википедии. Не знаю, правда, доверять такому переводу термина или нет.

Анализ


  • Операции вставки и удаления — дешевые: O(1) как при вставке отдельного символа, так и их группы (например, вставка из буфера обмена).
  • Накладные расходы по памяти — низкие: O(1). Нужно хранить только положение курсора и общий размер буфера.
  • Операция поиска элемента по индексу — дешевая: O(1).
  • Операция копирования участка содержимого (например, для копирования в буфер обмена или сохранения текста на диск) — O(n), где n — размер копируемого участка. Сложность такая же, как для массива.

Иными словами, для перечисленных операций удалось реализовать все те преимущества, какие дает массив.

При использовании Gap Buffer в текстовом редакторе появляются расходы на перемещение курсора. Ведь для обеспечения инварианта приходится копировать текст из нижнего заполненного участка буфера в верхний или наоборот. Сложность перемещения курсора — O(n), где n — расстояние, на которое перемещается курсор. При перемещениях из начала в конец текста может проявиться ощутимая пользователем задержка. Однако перемещения из начала в конец текста — относительно редкая операция при его редактировании. Чаще встречаются перемещения на символ, строку или страницу вперед или назад, и тогда приходится перемещать лишь небольшой участок текста. Задержка будет незаметна даже для 8-битных ЭВМ.

Таким образом, Gap Buffer эксплуатирует то свойство процесса редактирования текста, что операции вставки и удаления всегда происходят в том месте, где находится курсор; в свою очередь, перемещения курсора обычно бывают невелики.

Вариации


1. Теневой курсор записи

В своей базовой реализации Gap Buffer все же может вызывать нежелательные задержки. Например, при поиске текста или использовании закладок могут происходить значительные перемещения курсора. Также не всякое перемещение курсора по тексту сопровождается редактированием. Отсюда решение: ввести невидимый пользователю «курсор записи», который соответствует разрыву в Gap Buffer. Этот курсор перемещается только тогда, когда пользователь начинает вставку или удаление текста. При простых же перемещениях видимого курсора по тексту или замене (то есть когда общий размер текста не меняется) курсор записи не перемещать. Тем самым устраняются задержки при любых случайных перемещениях видимого курсора при просмотре текста, использовании закладок, поиска и т.д.

2. Редактирование файлов, которые не умещаются в оперативную память

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

С помощью Gap Buffer можно эффективно реализовать редактирование файлов, размер которых превышает размер оперативной памяти компьютера. Можно заметить, что Gap Buffer фактически представляет собой два стека, один из которых хранит данные до курсора, а второй — после курсора. Первый из стеков растет вверх, а второй — вниз. Отсюда идея: реализовать оба стека в виде файлов, при этом храня в оперативной памяти только те их участки, которые находятся ближе к вершине.

Стек в памяти может расти вверх или вниз, а стек, реализованный в виде файла, может расти только вверх. Только к концу файла мы можем дописывать данные или наоборот, удалять их оттуда. Если вернуться теперь к операциям с памятью и рассмотреть стеки, растущие в разные стороны — то видно, что в стеке, растущем вверх, данные располагаются в прямом порядке по отношению к последовательности помещения их на стек, а в стеке, растущем вниз — в обратном порядке. Так что, если мы хотим реализовать Gap Buffer в виде двух стеков, растущих вверх — нам придется поменять порядок элементов во втором стеке, который хранит текст после курсора. Поэтому тот временный файл, который содержит данные после курсора, должен их содержать в обратном порядке, задом наперед.

Во временных файлах мы будем хранить не все содержимое стеков, а только их нижнюю часть. Верхняя часть будет располагаться в оперативной памяти, образуя как бы «локальный» Gap Buffer и позволяя пользователю, как и прежде, быстро редактировать текст и перемещаться по нему в некоторых пределах. При перемещениях курсора по тексту за пределы загруженного в память участка, его часть, наиболее далекая от курсора, будет сохраняться в один из временных файлов, а из другого будет подгружаться недостающая часть.

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

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

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

Реализованное описанным способом редактирование текста без полной его загрузки в память имеет, таким образом, умеренные накладные расходы по дисковому пространству: для временных файлов требуется место, равное размеру текста.

Интересно, что даже если текст большого объема в принципе влезает в оперативную память, при использовании редактора, который не загружает его целиком, такой документ будет быстрее открываться. Снова-таки повышение удобства для пользователя.

Заключение


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

Благодарности


Об описываемой структуре данных я впервые узнал от пользователя ESL в теме на форуме zx.pk.ru. Там тоже обсуждался вопрос организации памяти для текстового редактора применительно именно к ЭВМ с ограниченными ресурсами, таким как ZX Spectrum.
Михаил Борисов @MichaelBorisov
карма
87,2
рейтинг 0,1
Самое читаемое Разработка

Комментарии (55)

  • +29
    Tехнологии, разработанные для старых компьютеров с ограниченными возможностями, оказываются в наше время забытыми
    Сейчас у нас куча новых компьютеров с ограниченными возможностями — это смартфоны и планшеты. Но погроммисты, видимо, расчитывают, что если их программа не работает из-за нехватки памяти, то через полгода Самсунг выпустит новый смартфон, в котором будет в два раза больше оперативки.
    • +3
      > Сейчас у нас куча новых компьютеров с ограниченными возможностями — это смартфоны и планшеты…

      Даже первые WP7 были с 512М памяти, это как бы порядочно больше тех «640Кбайт, которых хватит на все случаи жизни».

      Вспомнилось, делал в 90х простой текстовый редактор на ASM, так там была одна страница 64k, текст в которой делился на две части: от начала до курсора хранилось в начале блока 64k, а остальной текст — в конце блока. Ограничение размера текста 65536 байт.

      PS: Прочел, оказывается я как обычно открыл ранее открытое ))))
      • +10
        Памяти не бывает много. К примеру, в аппсторах полно программ для редактирования фоточек, фильтры там, кроп, демотиватор сделать. Когда мне нужно было обрезать фотки с 16-мегапиксельного фотоаппарата, загрузить джипег-фотку не смогла НИ ОДНА ПРОГРАММА включая платные, включая адобовские. Все падали при загрузке. Как-то выкрутился открывая фотки штатным просмотрщиком и делая скриншоты — скриншоты уже обрезал и постил в бложик. Ещё можно было послать фотки самому себе по почте — почтовая программа предлагала при отправке уменьшить фотки, причём реально посылать было не обязательно — достаточно поставки на отправку, потом можно было вытащить уменьшенные фотки из неушедших писем в «Исходящих».
      • 0
        Почитайте ради интереса про, например, открытие картинок на android'е.

        Одному приложению/потоку выделяется много меньше, чем вся память, если не ошибаюсь, 16 мб. на процесс вроде. Так что открытие большой картинки или большого числа данных одним куском превращается если не в хитрый, то уж точно в не банальный код «открыли и поехали».
        • +1
          48MB стандартно, 128MB если android:largeHeap=true.

          Так что всё должно бы влазить, но нужно с этой памятью очень аккуратно распоряжаться. У современных программистов так не принято.
          • 0
            Да, могу путать размеры. Другое дело, String Builder'ом я «в лоб» ~14 мб. текста в сумме, падало нафиг после 12 мб… Хотя очень может быть, что я чего-то не понял.

            Вот не зря выше упоминается (правда, не адроид) что с картинками проблемы — а там видимо происходит следующее: картинку в 16мб в Jpeg пытается програмка расжать, а 16 мб. сжатого в виде несжатого битмапа скорее всего мнооого больше весит.

            Не то что бы не принятно, а нынче «быстрее, быстрее выпустить продукт», поэтому многие действия делаются безхитростно, даже наверное не думаю — работает, с нормальной скоростью — и ладно. Мысли появляются только при возникновении проблем и поисках пути оптимизации. Плохо ли это? Возможно.
          • +11
            Ну а как ей можно аккуратно распорядиться, когда неизвестна не то что разрядность, но даже архитектура процессора (x86 или arm), сам код выполняется на Dalvik-машине с её непредсказуемым сборщиком мусора, а в фоне висит ещё N процессов, которые так или иначе могут влиять на работу нашего?
            Всё очарование старых машин было основано на том, что там не было такой уж зверской фрагментации (во времена digger'а даже таймеры на тактовую частоту процессора завязывали!), а вся система, от портов ввода-вывода и прерываний до самой последней ячейки памяти была под полным и абсолютным контролем программиста, без 100500 слоёв абстракции и прочей виртуальщины.
            Когда же программисты погрязли во фрагментации и виртуализации, то все эти старые трюки стали восприниматься грязными хаками, которые потенциально снижают переносимость. Поэтому никто не будет их специально искать. Проблема решается как можно проще, идеально — «прямо в лоб». Ну а если чуток тормозит, так и не страшно: главное, что вообще хоть как-то работает на всём зоопарке устройств и прошивок, тут уж не до мелких тормозов.
            • –2
              Да что ж вы всех всякими ужасами пугаете? Всё уже украдено до нас. Было бы желание. И нет проблем ни в непредсказуемостью сборщика мусора, ни с архитектурой процессора. Но да, желанию-то как раз часто и нету.
  • +5
    У меня интересный вопрос: а как в такой структуре с поиском/заменой регулярных выражений? Кроме того, если вы берёте какой‐либо редактор с встроенным API для расширений на каком‐либо языке, то вы наверняка встретитесь как с возможностью вставки текста в любом месте, а не только в месте нахождения курсора, так и с дополнениями, которые хотят эту возможность использовать. Поиск/замена является частным случаем возможности вставки/удаления в произвольном месте.
    • –1
      Очевидно, в этих случаях базовая версия Gap Buffer оказывается неэффективной. Но возможны вариации на его основе. Например, хранение текста в цепочке из нескольких Gap Buffer, с распределением свободной памяти между ними. Каждый такой буфер имеет свой «теневой курсор», и сложность вставки и удаления в пределах каждого из них не превышает O(n), где n — размер каждого буфера.
    • +8
      И для полного эффекта можно вспомнить sublime text, с возможностью сделать себе кучу курсоров сразу :)
  • +1
    GC решает проблему фрагментации не хуже, чем это можно сделать руками.

    Я бы вообще делал какое-нибудь immutable-дерево. Получил бы бесплатное undo, и возможность пускать всякие операции типа индексирования, подсветки, сохранения и проверки орфографии в отдельном потоке.
    • 0
      Если писать редактор на иммутабельных структурах данных, надо смотреть на zipper. Кстати, принцип во многом похож на gap buffer — эффективность копирования с изменением обеспечивается за счёт привязки зиппера к конкретной точке в тексте (обычно — место последнего изменения).
  • +2
    Делал на ZX Spectrum совершенно иначе, текст непрерывным куском, редактируемая строка (или её часть) держится в спец буфере (ограниченного размера), по мере заполнения буфера или смены строки, буфер скидывается в текст. Опять же сюда хорошо вписалась и загрузка текста частями (с дискеты).
  • 0
    Интересное решение. Undo/redo реализуемо несложными модификациями. Rich text editing тоже можно придумать как реализовать. Чуствую, что подстава всё же есть. Видимо, самый простой пример, как уже написали, find&replace. Но всё равно интересно.

    Для длинных текстов и Rich Text можно такую оптимизацию сделать: разбить текст на блоки, и оперировать как отдельными блоками, так списком блоков по изложенному алгоритму. Кажется, такой вариант не описывался в статье.

    Спасибо, статья заставляет думать.
  • +12
    А ещё специально для тектовых редакторов придумана такая структура данных как Rope. (И это дерево.)

    И мне кажется в вашей статье слишком много пафоса.
    • +4
      За ссылку на Rope — спасибо.

      Насчет пафоса — не понял. Что в статье вам показалось пафосным?
  • +4
    Я в своём редакторе использовал комбинацию Gap Buffer и Ropes. Представлял текст в виде AVL-дерева, каждый узел которого хранил immutable-подстроку текста и количество символов в поддеревьях для поиска символа по индексу (наподобие Rope, но в моей реализации значения могли содержать не только листья, но и узлы). Если пользователь начинал редактировать подстроку данного узла дерева, она динамически подменялась GapBuffer-строкой. Затем, если строка долго не изменяется, она заменяется обратно immutable-версией для экономии памяти.
    Получалось довольно эффективно.
    Минус полностью immutable-деревьев — создание log(N) нодов на каждую операцию изменения текста.
    • +1
      По-моему, этот минус (если он так уж беспокоит) преодолим посредством «выворачивания» дерева в месте последней модификации на манер finger tree. Я подумывал скомбинировать органицацию набора блоков приличной длины (а не по несколько символов, как если бы finger tree использовалось в лоб для хранения массива символов) с выворачиванием, а ещё рассматривал забавную идею immutable блока с гэп-буфером: давайте контрольную запись (указатель на блок плюс индексы краёв гэпа) хранить отдельно от самого блока. Тогда при добавлении символов на краях гэпа блок клонировать не надо — создаются новые контрольные записи с обновленными индексами краёв гэпа (гэп сужается) — старые контрольные записи продолжают оставаться в том же состоянии (immutable), указывая на тот же блок!
  • 0
    Со временными файлами, на мой взгляд, заморачиваться не надо.
    mmap()-ируйте файл любого размера. Операционная система сама разберётся, что держать в памяти, а что нет.

    Сооружение собственного свопа на уровне приложения, как правило, неоправданно (лишнее время, никакой пользы).
    • +7
      mmap()-ируйте файл любого размера.
      Ммм… У вас какой-то странный mmap, однако. Мой технологией вставки пары байт в середину как-то не обладает…
      • 0
        А remap_file_pages() сюда никак не получится присобачить?

        Upd: сорри, не заметил, что это Linux-specific call.
        • +1
          remap_file_pages не передвинет данные в файле, только их представление в памяти. И только размерами кратными странице.
  • 0
    А как выбирать рамзер окна? Переполнение окна ведь приведет к копированию остатка, а заводить просто так значительных размеров окно — расход памяти.
    И как-то мне не очевидно как сделать undo-redo для всех этих случаев.

    Не проще ли в целом сделать какую-то «карту» файла который редактируется, в которой хранилися бы список блоков текста, к примеру в таком виде: файл в котором текст, адрес начала блока в файле и адрес конца блока.

    При открытии файла для редактирования — создается один блок, файл = тот самый файл который открыли, адрес начала = 0, адрес конца = размер файла. При вставке внутри блока он разбивается на два блока до и после места вставки, + между ними добавляется третий блок с вставляемым содержимым — который можно хранить в новом временном файле. Удаление с начала или конца блока просто перемещает указатель начала/конца блока. Чтоб уменьшить фрагментацию, можно держать изменения в буффере пока они происходят в рамках одного нового блока.
    При сохранении все это можно собрать в один файл пройдясь по списку блоков.
    Undo/redo реализуется тоже элементарно — присваивать блокам не только номера порядка следования в результирующем тексте, но и номера порядка их создания. И удалять/возвращать из/в списка блоков последний блок по порядку создания.
    Вроде могло бы работать.
  • +2
    Деревья, кучи, кольцевые буфера, ассоциативные массивы и прочие структуры и вовсе неприменимы для хранения текста в редакторе

    B-дерево очень даже применимо.
    • +2
      Я бы даже сказал, любые сбалансированные деревья очень даже применимы, при условии, что хранить мы будем не символы, а подстроки исходного текста.
      • +3
        А потом кому-нибудь приспичит окрыть XML-документ на пару мегабайт из одной строки и вся ваша машинерия станет раком. Обидно когда старые древние emacs и vim отлично работают с многосотмегабайтными файлами, а новомодные игрушки начинают тормозить на файлах, которые и на дискету бы влезли!
        • +1
          Scintilla (Notepad++, TexnicCenter), например, тормозит по-чёрному.
        • +5
          Как раз, древовидное представление файла никак не завязано на то, сколько символов содержится в строке.
          Проблема современных редакторов не в том, как они хранят текст, а в том, как они его отображают. Если у вас есть стомегабайтный файл, записанный в одну строку, редактор должен рассчитать ширину всей строки в пикселях, как минимум, для того, чтобы правильно рассчитать максимальное значение горизонтального скроллбара. Это легко сделать в случае моноширинных шрифтов, но если вы выставили пропорциональный шрифт, всё сильно усложняется.
          Скажем, проскроллили мы на миллион пикселей вправо. Какой символ нужно отобразить первым слева? У vim и emacs таких проблем не возникает, потому что они используют моноширинные шрифты — делим миллион на ширину символа в пикселях, вот и наш индекс. В случае пропорциональных шрифтов необходимо сложить ширину всех символов вплоть до того, который даст результат равный миллиону.
          Конечно, всё это можно оптимизировать, но главный вопрос — зачем? Часто ли вы редактируете многомегабайтные файлы, записанные в одну строку?
          • +6
            У Vim огромные проблемы с подсветкой таких файлов. Кроме того, как вы в Vim проскроллите на миллион пикселей вправо? Горизонтальной полосы прокрутки в нём отродясь не было.

            И ещё: с какой стати в моноширинном шрифте ширина всех символов одинакова? Это не так. В моноширинном шрифте символ «A» занимает ровно две ячейки (это относится ко всем символам, которые имеют свойство east_asian_width равное ́«F» (и, кажется, «W»), а иногда также и «A» (последнее зависит от шрифта и настроек терминала)). А три символа «а́݅» (русская «а» и два диакритических знака) занимают одну ячейку. Я не говорю уже о том, что для отрисовки текста с некоторой позиции нужен индекс байта, а не символа.

            Моноширинные шрифты дают преимущество в смысле, что не нужно запускать рендерер, чтобы узнать, насколько текст широк. Но оно не настолько велико, как вы здесь описываете. Складывать ширину всех символов нужно всегда. Просто с моноширинными шрифтами не нужно рендерить глифы, чтобы её узнать.
            • +3
              Просто с моноширинными шрифтами не нужно рендерить глифы, чтобы её узнать.
              Данное утверждение тоже, кстати, не всегда верно. Современные системы отображения текста умеют брать отсутствующие глифы из шрифтов, где они присутствуют. Если основной шрифт моноширинный, и при том отображающая шрифт программа расчитывает на определённые размеры символа, то это приводит к различным глюкам отображения, так как символ из другого шрифта имеет другие размеры.
              • +1
                Согласен с каждым пунктом =) Я в своём сообщении сделал обобщение «моноширинный шрифт» == «консольное приложение», имея в виду что в консольных редакторах не нужно измерять ширину текста. Конечно, это упрощение не работает в GIU-редакторах.

                По поводу символов типа "A" — я проверял шрифты Consolas, Lucida Console и другие, и все глифы в них имеют одинаковую ширину. Только что ради интереса открыл Sublime Text (который по умолчанию использует Consolas) и вставил туда этот символ. Закономерно, он заменился символом из другого шрифта. Все GUI-редакторы разделяют текст на spans (не знаю, как правильно перевести), каждый спан имеет свои атрибуты форматирования, в том числе шрифт. Я думаю, Sublime просто создаёт отдельный спан для таких символов. Так вот, ширина строки текста складывается из ширины отдельных спанов, и их можно посчитать только один раз, если текст внутри спана не меняется.
                • +1
                  Дело в том, что все эмуляторы консоли, которые я проверял, считают глифы из других шрифтов имеющими размеры символа данного шрифта, не зависимо от реального размера глифа. Но для FULLWIDTH символов и терминал, и Vim считают ширину равной двум. Я, правда, не смог найти ни одного моноширинного шрифта, в котором fontforge показал бы наличие глифов для данных символов. А я‐то считал (из‐за отсутствия обычных проблем с отображением, обычно отличающих отсутствующие глифы) «A» присутствующей в шрифте.

                  Эмуляторы терминала со спанами явно не заморачиваются: слишком широкий символ из другого шрифта в зависимости от расположения звёзд может либо перекрываться другим символом, либо двигать все прочие символы. Причём состояние «перекрывается»/«двигает» может меняться даже без изменения отображаемого текста (например, при выделении).
        • +3
          Хочу заметить, сугубо практически, что у xapi (компонента XenServer) база данных хранится в виде xml-файла. Разумеется, в одну строку.

          Работать в vim'е с такой строкой (в 40-50Мб в размере) невозможно, даже при отключении подстветки синтаксиса.
          • +1
            У vim память, кажется, выделяется блоками на N≥1 строк. Целых строк. Кроме того, даже если найдётся кто‐то, кто перепишет memline.c, чтобы работать с большими строками, средства навигации по таким строкам практически отсутствуют. И вывод на экран тоже под такие строки не рассчитан. Но я не работаю с настолько большими файлами в одну строку, так что у меня всё почти всегда упирается в подстветку синтаксиса.

            Я бы эту проблему решал с помощью пары фильтров: xmllint --format - при чтении и xmllint --noblanks - при записи.
  • +2
    К слову, в последней стабильной ветке ядра Linux (3.11) добавили новый флаг для системного вызова open(), позволяющий безопасно создавать и использовать временные файлы — O_TMPFILE.
    kernelnewbies.org/LinuxChanges
  • +1
    Думаю, что в контексте обсуждения структуры данных Gap Buffer, надо обязательно упомянуть и про текстовый движок Scintilla (и редактор SciTE), который как раз на нем основан. В свое время мне довелось тесно с ним работать. Из недостатков Gap Buffer отмечу, что притормаживает при работе с большими объемами текста. По теме, могу порекомендовать к прочтению отличную работу
  • 0
    Идея интересная, но я со скрипом представляю себе отработку поиска-и-замены в такой конструкции. Если у нас искомая подстрока встречается в каждой сотой строке, то вместо того, чтобы потревожить 1% строк, мы будем вынуждены перетягивать все 100%.

    В студенческое время мы над этой проблемой думали (благо, компьютеры на базе 386sx стимулировали думать о производительности) и самой компромиссной версией, которая тогда придумалась, звучала как «список строк, указывающий на список массивов внутри строки». Этакое line->buffer.current[c]. Фрагментация легко устраняется с помощью SLAB-подобного аллокатора и выделения буффера одного из фиксированных размеров (а так же наличия в каждом буфере указания «откуда-докуда» текст).

    При этом возникают накладные расходы на обновление всяких счётчиков, типа «сколько символов в буфере, сколько символов в строке», но они O(1) для больших текстов.
  • 0
    Сложности возникают при переходах в начало/в конец больших файлов. Если файл не вмещается в буфер, то стеки приходится хранить во временных файлах, и для больших перемещений приходится переносить содержимое одного стека в другой, да ещё и задом наперёд. Когда на «Ямахах» приходилось редактировать большие (больше 32 килобайт) файлы, то действия «открыть файл — вставить строчку — пойти в конец» приводили к задержкам в несколько минут. И с большой вероятностью места на дискете не хватало — нужно было свободное место, вдвое большее, чем редактируемый файл.
  • +1
    Действительно, а попробуйте на VPS в 128mb отредактировать SQL-дамп на пару-тройку гигов :)
    В таких случаях очень спасает все тот олдовый редактор, который из покон веков умеет бибикать и все портить ( vi :)
  • 0
    Наш редактор использует представление документа в виде списка объектов, каждый из которых соответствует одному абзацу текста. В этом случае вставка абзаца в середину документа — это просто вставка еще одного объекта в список. Т.к. абзацы длиной 10 МБ встречаются крайне редко (я бы даже сказал, никогда не встречаются), а вот документы длиной по 50-100 тысяч абзацев — вполне реальны (объем «наибольшего» редактируемого файла в наших реалиях достигает примерно 150 МБ). И редактор прекрасно с такими объемами справляется. При этом удобно на объекты-абзацы навесить еще и дополнительную логику (т.е. объект хранит не только сам текст, но и стили (жирность, курсив), выделение цветом и т.п.).
    • 0
      А как вы определяете, какой абзац рендерить при изменении вертикального смещения ViewPort-а?
      • +1
        Если объяснять упрощенно, поверх каждого внутреннего объекта-абзаца с содержимым создается еще объект «отображаемый абзац», который отвечает за просчет размеров и отрисовку исходного абзаца. Если меняется ширина ViewPort'а, то высоты всем отображаемых абзацев считаются невалидными. Реальный пересчет высот в этот момент выполнять не обязательно, т.к. при изменении ширины ViewPort'а отображаемые на экране абзацы на должны поехать, т.е. отображаться всё равно будут они. А вот при скроллинге уже выполняется пересчет всех невалидных высот от начала документа (ну на самом деле не всегда от начала :) ), пока не дойдем до текущей позиции скроллинга. При открытии документа для определения «максимальной позиции» (диапазона) скроллинга просчитать все высоты один раз все равно придется.
        • 0
          То есть, получается, если верхняя координата ViewPort`а «указывает» на последнюю строку очень длинного абзаца, то при увеличении ширины ViewPort`а, эта строка может пропасть с экрана, вследствие того, что в этом абзаце может уменьшится количество строк?
          И еще вопрос: если вы не пересчитываете высоту всех абзацев при изменении ширины, как вы понимаете максимальное значение вертикального скролла?
          (Я сам сейчас делаю небольшой редактор, и пришёл к такому же выводу, что производить полный word-wrap всего документа на каждое изменение ширины — слишком накладно, но если просто помечать высоты как невалидные, со скроллом возникают некоторые проблемы. Хотелось бы узнать мнение людей, которые уже прошли через этот этап =) )
          • 0
            >>если верхняя координата ViewPort`а «указывает» на последнюю строку очень длинного абзаца, то при увеличении ширины ViewPort`а, эта строка может пропасть с экрана, вследствие того, что в этом абзаце может уменьшится количество строк?
            Да, так оно сейчас и происходит. Но на самом деле это мало кого беспокоит, т.к. изменение ширины окна в процессе редактирования относительно редкая операция, обычно окно либо не разворачивают, либо разворачивают сразу, до начала редактирования.

            >>если вы не пересчитываете высоту всех абзацев при изменении ширины, как вы понимаете максимальное значение вертикального скролла?
            Со скроллом отдельная история :). Пересчитывать высоты отображаемых абзацев по всему документу при изменении ширины окна нереально — это очень медленно, поэтому скролл у нас считается в количестве абзацев и умеет позиционироваться только на начало абзаца (имею в виду тот скролл, который выполняется вертикальным скроллером). Это может приводить к «скачкообразному» пролистыванию, например, если в абзаце есть рисунок на половину страницы. А для более точного позиционирования по строкам длинных абзацев используется скроллинг стрелками вверх-вниз и PageUp/PageDown на клавиатуре и скроллинг колесом мыши. В целом позиция скроллирования задается в виде пары (номер абзаца, номер строки). Когда нажимаем стрелку вниз на клавиатуре, увеличивается номер строки, а если он выходит за количество строк текущего отображаемого абзаца — то номер абзаца.
            • 0
              Спасибо, интересное решение.
    • +1
      Т.к. абзацы длиной 10 МБ встречаются крайне редко (я бы даже сказал, никогда не встречаются)
      Я так понял, вы под «абзацами» понимаете «строки текста»? Если да, то один из любимых примеров: XML в одну строку. Мне, правда, никогда не доводилось редактировать XML, который обязан занимать одну строку, что позволяло пользоваться xmllint, но других люди говорят: им нужно. Собственно, эта необходимость упоминается фактически в каждой теме, где кто‐то говорит, что «обратка длинных строк не нужна».

      Если нет, то как вы определяете границы абзаца?
      • 0
        Я говорю об RTF-представлении документа (не конкретно об RTF-формате, а просто о представлении текста в виде набора абзацев с оформлением). Аналогичное представление имеем в форматах Doc, RTF, WordML, ODT). Абзац — это некоторый набор символов, завершающийся признаком конца абзаца (при этом в том же Word'е абзац визуально может быть разбит на неколько строк, если он не влезает в ширину листа, но физически это один абзац). Если говорить о чисто текстовых файлах, то да, абзац — это строка, заканчивающая признаком конца строки (символами 13, 10 в Windows или только 13 в Linux).
        • 0
          Если говорить о чисто текстовых файлах, то да, абзац — это строка, заканчивающая признаком конца строки (символами 13, 10 в Windows или только 13 в Linux).
          Обычно строка — это строка. А абзац — это либо внутренняя терминология редактора (вроде «абзац — это набор строк, ограниченных строками, не содержащими не пробельных символов, либо началом/концом файла» (основное определение для Vim)), либо терминология того формата данных, в котором записан текстовый файл (свои абзацы есть и в FB2, и в *TeX), либо терминология отображающей программы (читалки при чтении текстовых файлов обычно имеют своё представление о том, как текст должен биться на абзацы, причём зачастую он бьётся совершенно не по строкам).
      • 0
        Т.е. видимо нужно уточнить, наш редактор работает с «высокоуровневым» представлением документа (полученным на основе чтения формата RTF или WordML), а не с исходным «чисто текстовым» файлом. Т.е. XML на 10 МБ в одну строку нашим редактором «напрямую» действительно не отредактируешь, наш редактор не предназначен для этого.
  • +2
    А я порекоменду книгу Craig A. Finseth — The Craft of Text Editing.
    В этой книге рассказывается о том, как написать текстовый редактор: реализация, алгоритмы, организация данных и прочее (автор правда подводит к мысли, что EMACS — это лучший и надо ориентироваться на него).
    Метод, Buffer Gap там также упоминается, см. главу 6.
  • +1
    Просто ради полноты. Эта структура данных была описана в книжке А.Г. Кушниренко и Г.В. Лебедева «Программирование для математиков» (1988) и использовалась в широко известном в узких кругах текстовом редакторе «Микромир».
  • 0
    Вот здесь предлагается использовать B-tree для текстового редактора для работы с большими файлами, которые не помещаются в память: www.chiark.greenend.org.uk/~sgtatham/tweak/btree.html. Как я понял, B-tree куда круче вашего подхода (по скорости), хотя, признаюсь, читал ваш пост невнимательно
    • 0
      Люблю Хабр! Как раз сейчас думаю, как наиболее эффективно организовать работу с большими файлами в моём редакторе. Сейчас использую immutable AVL tree, но чем дальше, тем больше понимаю, что, возможно, не самая удачная структура для редактора. Спасибо.
      • 0
        Кстати, было бы интересно услышать мнение людей, занимающихся текстовыми редакторами: насколько эффективно динамически подменять структуры хранения данных в зависимости от текущих условий.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.