| worse is better, или регресс прогресса |
[Apr. 5th, 2017|06:22 pm] |
вообще, я хотел детально рассказать про дизайн egedit, но передумал. нет там ничего, о чём стоило бы детально рассказывать. а недетально сейчас напишу.
1. текст хранится в тупом массиве байтов. для редактирования используется gap buffer.
2. для подсветки массив байтов сопровождается теневым массивом ushort'ов. то есть, каждый байт имеет теневой ushort. сам редактор с ними не делает ничего.
3. редактор делает кэш, в котором указывает позицию начала каждой строки. при добавлении/удалении текста счётчик общего количества строк правится на основе количества добавленых/удалённых '\n'. при изменении строки n кэш для неё и всех последующих строк инвалидатится, а при запросе «хочу позицию строки с номером хер» тупо обновляется до строки «хер» (если надо). преобразование из позиции в номер строки — то же самое, только кэш обновляется до тех пор, пока не дорастёт до нужной позиции. поиск '\n' — тупой memchr. вся эта механика работает на удивление быстро, и преобразования позиция-в-номер-строки — O(log n), потому что двоичный поиск.
собственно, всё: это весь редактор. в таком виде он вполне справляется с файлами на 210 мегабайт, например. читает мгновенно, навигация мгновенная, поиск-и-замена по регулярке — примерно три-четыре секунды на 98000 замен. меня устраивает.
если добавить раскраску синтаксиса — то переход на конец файла становится несколько хуже: секунды две с половиной занимает покрасить весь файл. красит весь для того, чтобы не рисовать хуйню, как редакторы, которые смотрят «на сто линий от текущей», и в результате фэйлят с раскраской каментов или строк. это можно значительно ускорить, сделав только определение того, какие строки должны быть исследованы на предмет сложной раскраски (мультистрочный комментарий, мультистрочный строковый литерал), а непосредственно красить только то, что видно, но мне лениво. файлы в 210 мегов я туда сую почти никогда, а 300-400 кб (максимальный исходник, который мне надо было чинить) обрабатывается мгновенно.
мда. чего-то вышло детальней, чем думалось.
теперь к заголовку поста. у меня есть движок на piece chains, где для преобразований position-в-chain используется немного модифицированное red-black tree. чисто теоретически этот движок лучше. линейное сканирование чуть медленней, если кусков много (но не так уж и), зато блягодаря тому, что все структуры можно сделать immutable — совершенно халявное undo. в принципе, в дерево можно вмонтировать не только информацию о позициях, но и счётчик строк, так что оно ещё и автоматически будет поддерживать поиск строки по позиции и наоборот, тоже за O(log n). в целом будет быстрее gap buffer (egedit при вставке первого символа в 210мб ощутимо тормозит, пока двигает дырку в начало файла).
я вполне серьёзно планировал всё переделать на этот движок. потому что из-за бага egedit при каждом удалении двигал дырку в конец файла, а потом на нужное место, и это дико тормозило (всё те же 210мб с поиском-и-заменой не справились и за несколько минут). однако баг починился, и переделывать я передумал. потому что хуле, мощностей много, скорость удовлетворительная — нафига?
вот это и есть регресс прогресса: с увеличением тупой мощности красивые алгоритмы заменяются на тупые. потому что работает же, хуле. с одной стороны — мне это нравится, потому что проще писать и отлаживать. а с другой — немного грустно: меньше мест чтобы выебнуться. ну, я бы первый спросил: «а нахера ты ебался с деревьями, если gap buffer на практике не хуже, зато сильно проще?»
извините, пожалуйста, за ошибки. перечитывать никаких сил нет пока. |
|
|