Мы написали редактор для старой машины (имейте в виду, что это было некоторое время назад, около 1986 года, так что это по памяти, и с тех пор состояние техники могло несколько продвинуться), к которому нам удалось добраться развивайте производительность, используя фиксированные блоки памяти из самоуправляемых пулов.
У него было два пула, каждый из которых содержал фиксированное количество блоков определенного размера (один пул был для линейных структур, а другой для структур линейных сегментов). Это был в основном связанный список связанных списков.
Память была предварительно выделена (для каждого региона) из «malloc()» -подобного вызова, и мы использовали 65 535 блоков (от 0 до 65 534 включительно, номер блока 65 535 считался нулевым блоком, конец списка индикатор).
Это позволило использовать по 65, 535 строк (384 КБ или 512 КБ для дополненной версии) и около 1,6 ГБ размера файла (с 2 ГБ выделенного пространства), что было довольно большим в то время. Это был теоретический предел размера файла - я не думаю, что мы когда-либо приближались к этому в действительности, так как мы никогда не выделяли полный набор структур сегментов линии.
Отсутствие необходимости вызывать malloc() для каждого небольшого блока памяти дало нам огромное увеличение скорости, тем более что мы могли оптимизировать наши собственные процедуры выделения памяти для блоков фиксированного размера (включая вставку вызовов в окончательной оптимизированной версии).
Структуры в двух пулах были следующими: каждая строка представляла собой один байт):
Line structure (6/8 bytes) Line-segment structure (32 bytes)
+--------+ +--------+
|NNNNNNNN| |nnnnnnnn|
|NNNNNNNN| |nnnnnnnn|
|PPPPPPPP| |pppppppp|
|PPPPPPPP| |pppppppp|
|bbbbbbbb| |LLLLLLLL|
|bbbbbbbb| |LLLLLLLL|
|........| |xxxxxxxx|
|........| :25 more :
+--------+ : x lines:
+--------+
где:
- Строчные буквы, отличные от
x, указывают на пул сегмента линии.
- Буквы в верхнем регистре указывают на пул строк.
N был номером блока для следующей строки (ноль означает, что это была последняя строка в файле). P номер блока для предыдущей строки (ноль означает, что это была первая строка в файле). b был номером блока для первого сегмента линии в этой строке (ноль означает, что строка была пустой). . был зарезервирован для заполнения (для увеличения структуры до 8 байт). n был номером блока для следующего сегмента линии (ноль означает, что это был последний сегмент в строке). p был номером блока для предыдущего сегмента линии (ноль означает, что это был первый сегмент в строке). L - номер блока линейного блока сегмента. x - это 26 символов в этом отрезке.
Причина, по которой структура строки была дополнена, заключалась в том, чтобы ускорить преобразование номеров блоков в фактические ячейки памяти (смещение влево на 3 бита было намного быстрее, чем умножение на 6 в этой конкретной архитектуре, а используемая дополнительная память составляла всего 128 КБ, минимальное по сравнению к общему объему используемой памяти) хотя мы и предоставили более медленную версию для тех, кто больше заботился о памяти.
У нас также был массив из 100 16-битных значений, который содержал отрезок строки (и номер строки, чтобы мы могли быстро перейти к определенным строкам) примерно с таким процентом (так что массив [7] был строкой, которая была примерно 7 % в файл) и два свободных указателя для поддержки свободного списка в каждом пуле (это был очень простой односторонний список, где N или n в структуре указывали на следующий свободный блок и свободные блоки были выделены из, и вернуть в начало этих списков).
Не было необходимости вести подсчет символов в каждом сегменте строки, поскольку 0-байты были недопустимы в файлах. Каждому сегменту линии было разрешено иметь 0 байтов в конце, которые полностью игнорировались. Линии были сжаты (т.е. сегменты были объединены) всякий раз, когда они были изменены. Это позволило сохранить низкое использование блока (без редкой и длительной сборки мусора), а также значительно ускорило операции поиска и замены.
Использование этих структур позволило очень быстрое редактирование, вставку, удаление, поиск и навигацию по тексту, и именно здесь вы, скорее всего, получите большинство проблем с производительностью в простом текстовом редакторе.
Использование выделений (мы не реализовали это, так как это был редактор текстового режима, который использовал vi-подобные команды, такие как 3d, чтобы удалить 3 строки, или 6x, чтобы удалить 6 символов), можно реализовать, {line#/block, char-pos} кортеж, чтобы пометить позиции в тексте, и использовать два из этих кортежей для диапазона выделения.