Ответ 1
Мы написали редактор для старой машины (имейте в виду, что это было совсем недавно, примерно в 1986 году, так что это из памяти, а современное состояние, возможно, несколько продвинулось с тех пор), которому нам удалось добраться до кричать вместе, производительность разумно, используя фиксированные блоки памяти из самоуправляемых пулов.
В нем было два пула, каждый из которых содержал фиксированное количество блоков определенного размера (один пул был для линейных структур, другой для структур линейного сегмента). Это был связанный список связанных списков.
Память была предварительно выделена (для каждой области) из вызова 'malloc()', и мы использовали 65 535 блоков (от 0 до 65534 включительно, номер кадра 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был номером блока для следующей строки (значение null означало, что это была последняя строка в файле). -
Pномер блока для предыдущей строки (значение null означает, что это была первая строка в файле). -
bбыл номером блока для первого сегмента строки в этой строке (значение null означает, что строка пуста). -
.было зарезервировано дополнение (чтобы уменьшить структуру до 8 байтов). -
N- номер блока для следующего сегмента строки (значение null означает, что это был последний сегмент в строке). -
Pбыл номером блока для предыдущего сегмента строки (значение null означало, что это был первый сегмент в строке). -
Lбыл номером блока для блока сегментной строки. -
x- это 26 символов в этом сегменте.
Причина, по которой структура строки была дополнена, заключалась в том, чтобы ускорить преобразование номеров блоков в фактические ячейки памяти (сдвиг влево на 3 бита был намного быстрее, чем умножение на 6 в этой конкретной архитектуре, а дополнительная используемая память была только 128 КБ, минимальная сравниваемая к общей используемой памяти), хотя мы предоставили более медленную версию тем, кто больше заботился о памяти.
Мы также имели массив из 100 16-битных значений, которые содержали сегмент линии (и номер строки, чтобы мы могли быстро перейти к конкретным строкам) примерно в таком проценте (так что массив [7] был линией, которая была примерно 7 % в файл) и два бесплатных указателя для поддержки бесплатного списка в каждом пуле (это был очень простой список в один конец, где N или N в структуре указано, что следующий свободный блок и свободные блоки были выделены, и верните назад, в начало этих списков).
Не нужно было содержать количество символов в каждом сегменте линии, так как 0-байты не были действительны в файлах. Каждому сегменту линии было разрешено иметь 0-байты в конце, которые были полностью проигнорированы. Линии были сжаты (то есть, сегменты линий были объединены), когда они были изменены. Это уменьшало использование блоков (без редкой и длительной сборки мусора), а также значительно ускорило операции поиска и замены.
Использование этих структур позволило очень быстро редактировать, вставлять, удалять, искать и навигация вокруг текста, в котором вы, вероятно, получите большую часть своих проблем с производительностью в простом текстовом редакторе.
Использование выборов (мы не реализовали это, так как это был редактор текстового режима, который использовал vi-подобные команды, такие как 3d, чтобы удалить 3 строки или 6x, чтобы удалить 6 символов) можно было реализовать, если a {line#/block, char-pos}, чтобы пометить позиции в тексте и использовать два из этих кортежей для диапазона выбора.