| проще надо быть, понятней |
[Mar. 16th, 2018|07:18 am] |
вот сколько лет же говорят: практика — мерило теории! запомнить это надо, зазубрить!
это я о том, что если вообще повыкидывать всю сложную логику из реализации буфера для текстового редактора, и оставить добрую старую систему «root directory, subdirs, pages» (ниже поясню), то на процессинг ~264 мегабайт текста посимвольно (ради примера тупо считал количество '\n') уходит примерно полторы секунды. если то же самое делать постранично, то и вовсе меньше шестидесяти миллисекунд. все заморочки с деревьями для поиска позиций — нахуй лишние вообще. и с более сложной структурой буфера (как я пытался сделать раньше) — тоже.
конечно, перемещение «дырки» будет немного подтормаживать (пока не допилил нормальный код, чтобы проверить, но по прикидкам, передвинуть «дырку» с конца в начало, например, на тех же 264 — около ста миллисекунд). но! это совершенно неважно. во-первых, потому что файл размеров патологических; и то, что редактор вообще будет в состоянии его ворочать — само по себе достижение. (кстати, с какой скоростью такие файлы ворочает вим или имакс? и сколько надо памяти?) а во-вторых, большинство операций редактирования очень локализованы, и редкие «провисания» на сотню-другую миллисекунд, когда активная работа перемещается в очень далёкий кусок такого патологического текста — вполне терпимы. окупаются простотой кода (а, следовательно, отладки и сопровождения). локальные же перемещения «дырки» (в перделах нескольких сотен кб, например) — даже до миллисекунды не дотянут (при запасе как минимум в пару десятков миллисекунд).
обновление же кэша смещений строк для того же файла (122953 строки) — вообще даже половину миллисекунды не сжирает, так что кэш можно спокойно построить при загрузке (всё равно хотя бы количество строк там посчитать придётся — а тогда и смещения можно запомнить), а потом обновлять. то есть, код, ответственный за динамическое похеривание и перестраивание этого кэша (то, что сейчас делает egeditor) — тоже в мусорку. что хорошо, потому что в нём у меня было больше всего мелких ошибок.
да, посимвольная вставка чуть замедлится — ну и что? при вводе с клавиатуры времени всё ещё достаточно. а при вставке из клипборда (или файла/буфера) делать это посимвольно — тупо.
в общем, упрощай — и победишь. в возрастании мощностей техники есть некая прелесть.
теперь про «root directory, subdirs, pages»: эту идею я позаимствовал у файловых систем. всё выделение памяти всегда и безусловно идёт блоками одинаковых размеров (блок в четыре или восемь килобайт отлично работает). а чтобы выделять большие массивы, мы организуем двухуровневый каталог: в первом уровне каталога каждый блок просто последовательно хранит указатели на блоки данных. а блоки второго уровня хранят указатели на блоки первого уровня. то есть, чтобы найти байт со смещением mPos, надо сделать нечто такое:
immutable uint pgnum = mPos/PageSize;
void** pg1 = cast(void**)tbuf.mHugeDir[pgnum/RefsPerPage];
char* pg = cast(char*)pg1[pgnum%RefsPerPage];
return pg[mPos%PageSize];
зачем такая странная структура? а затем, что по условию мы не можем выделять/освобождать ничего другого кроме целого блока. в том числе у нас отсутствует и realloc, и какая-либо гарантия того, что блоки идут последовательно. поэтому тупо линейный массив указателей сделать не выйдет. да, многие файловые системы используют (или использовали) именно такую структуру вместо большой FAT (FAT вообще не лучшая идея). при размере блоков в четыре килобайта один блок «huge dir» достаточен, чтобы выделять массивы размером до четырёх гигабайт. мне хватит.
зачем такие драконовские ограничения для RAM? а чтобы избежать фрагментации памяти и overallocation. при буферах разных размеров рано или поздно и память будет нарезана на кусочки разного размера — это раз. во-вторых, в худшем случае ralloc требует как минимум 2x памяти для работы — и эта память может наличествовать, но опять-таки нарезаная на ленточки. это два. а при блочной схеме мы вообще не делаем realloc, и ленточки почти не нарезаем (нарезают другие части libc и прочих библиотек, но это маловажно в данном случае). таким образом, чтобы добавить пару десятков килобайт в текст при блочной организации — нам надо только выделить нужное количество блоков, и всё. а при «обычной», с линейными массивами — и изначально жестоко овераллокатить, и всё равно потом возникнет ситуация, когда надо для realloc найти свободный буфер размера «сколько есть плюс ещё сколько хотим».
вдобавок, освободившиеся блоки, например, можно сразу же отдавать undo-буферу (и наоборот), вследствие чего как минимум операция «переместить кусок текста из одного буфера в другой» магическим образом просто работает, не требуя дополнительной памяти вообще (за исключением одного-двух блоков на каталоги). то есть, undo/redo буфер становится очень дешёвым (да ещё и очень быстрым на больших фрагментах текста, которые можно передавать из буфера в буфер просто копируя указатель на страницу с данными). эту оптимизацию я вряд ли буду делать, но в принципе она несложная.
конечно, для 64-битного address space это всё не так важно: там блочную оптимизацию за нас сделает ядро, а address space можно нарезать до усёру — его много. так что если вы считаете 32 бита пережитком прошлого, то всё вышеописаное для вас имеет интерес скорее археологический, из разряда «как трудно жилось дидам, и как теперь хорошо нам». когда я буду окончательно вынужден перейти на 64 бита, я тоже это всё повыкидываю (наверное). а пока я хочу, чтобы редактор не давился и не тормозил на том, что есть. |
|
|
![[info]](http://lj.rossia.org/img/userinfo.gif){kind=small}