Привет.
Поскольку t.me/swarmsync стал англоязычным, создаю русскоязычную версию.

Опрос имел вполне жизненную подоплёку, тем не менее. В C++ реализации RON используется ragel http://www.colm.net/open-source/ragel
С его помощью сделаны парсеры UTF8, RONt, JSON, RFC3986 URI, HTTP. Что, кстати, заняло не очень большое время. На подходе wikitext и CSV. Причём Ragel в ванильной конфигурации парсит только регулярные языки, поэтому для JSON он используется скорее как лексер.
В любом случае, ragel использует что-то вроде алгоритма Томпсона и потому всегда парсит за линейное время https://swtch.com/~rsc/regexp/regexp1.html
PCRE, которое используется везде (и в js), делает бэктрекинг, из-за чего может потребовать экспоненциального времени на выполнение. Я сталкивался с таким в проде, и не только я. То есть, Томпсон всяко круче?
Увы, обратная сторона Томпсона - комбинаторный взрыв в парсере из-за того, что возможно 2**n суперпозиций состояний.
Так вот, при написании парсера вики-разметки такая проблема и возникла. Ибо вики разметка не имеет чётких границ элементов, поэтому парсер держит в уме сложные суперпозиции.
Взрыв получался, если в парсер вики разметки включить парсер URI. Грамматика URI сложна и 2**n резко бабахает.
Такая вот занимательная химия.

Полный деплатформинг в 24 часа без каких либо судов и вообще бумаг!
Альтернатива децентрализации – цифровой тоталитаризм. Информационные супермонополии располагают невообразимым количеством информации и контролируют её циркуляцию. Каких-либо сдержек и противовесов не осталось.

Можно поздравить IPFS
https://brave.com/brave-integrates-ipfs/

IPFS в Brave работает возможно чуть медленней HTTP, но работает вполне себе децентрализовано, в peer-to-peer режиме.
Единственно, в сети неизбежно полная вакханалия, соединения на множество адресов для скачивания/раздачи и постоянные разговоры с DHT хостами. В строгой корпоративной сети это лучше не запускать.

bluesky работают потихоньку
выпустили обзор технологий дец веба
https://twitter.com/bluesky/status/1352302821140549632?s=20

BitCoin это очень злая шутка над людьми. Демонически злая. Валюта устроена так, что её капитализация - это примерная оценка энергии, потраченной на "майнинг". Изначально заявленные цели - популярная криптовалюта, анонимизация и отсутствие посредников - оказались пшиком, и это было прекрасно понятно и 10 лет назад https://web.archive.org/web/20110724171749/http://www.pds.ewi.tudelft.nl/~victor/bitcoin.html. Зато инцентивизация и спекулятивный компонент удались на славу.
Уже раздаются голоса за насильственное уничтожение BitCoin https://medium.com/the-capital/green-hackers-around-the-world-lets-destroy-bitcoin-725700434a8f
В этой связи, инвестиция Tesla в BitCoin расставляет точки над i. Tesla - это про зелёное будущее или про силу интернет мемов? Конечно, второе.
Кстати, когда у основателя DeLorean пошатнулись дела, он занялся контрабандой кокаина, но был пойман (1982). Самая крутая тачка того периода, если кто помнит "Назад в будущее". Такая вот параллель.

На прошедшем в выходные FOSDEM был трек про распределенный Веб, были интересные докладчики https://fosdem.org/2021/schedule/track/beyond_blockchain_distributed_web/
Доклад от IPFS при этом шёл в треке "Open Research Tools and Technologies" https://fosdem.org/2021/schedule/event/open_research_filecoin_ipfs/ Видимо, IPFS интересна и другая аудитория, помимо энтузиастов крипты и децентрализации :) Что ж, это очень зрелый подход.

Теперь про RON. В системе PLS/DaRWiN добрый старый markdown в реализации commonmark.org был заменен на свой собственный минималистичный диалект *с формальной грамматикой*, названный StrictMark http://doc.replicated.cc/%5EWiki/strictmark.sm
Такой дерзкий подход был, тем не менее, с интересом принят сообществом CommonMark :)

RON, DaRWiN и diff'ы по Майерсу

Одно из демо-приложений RON это система контроля версий DaRWiN. На данный момент эта система хранит документацию RON, ну и понятно, работает подопытным кроликом. Мерж там, понятное дело, бесконфликтный, на основе CRDT (CT Chronofold).

Поскольку система реал-таймовая, то контроль версий, неизбежно, посимвольный. Исторические diff и patch, и всё что их использует (git, например), отслеживают изменения построчно (есть нюансы). Во многом это из-за того, что сложность алгоритма у diff это O(ND), где N размер текстов и D количество изменений. Понятно, что при посимвольном разборе N будет больше, да и D тоже. На глазок, раз в 60-70 :) Исторически, вероятно, компьютеры не тянули столько. Тем более, есть вероятность, что какой-нибудь маньяк засунет в систему не только Войну и Мир (все 2.5MB), но и какой-нибудь CSV файл с результатами всекитайской переписи.

Вторую проблему DaRWiN решает просто: CSV это другой тип данных и diff для него другой, не посимвольный. DaRWiN хранит структуры данных (текст, таблица), а не буковки.

А первую проблему интересно было проверить. Поэтому я взял Войну и Мир и все запятые там заменил на точки с запятой. Это максимально неприятный сценарий, 30тыс изменений и нельзя отрезать неизменные голову и хвост, упростив задачу. Что ж, некоторое время алгоритму пришлось подумать. Но не так долго.

Вывод? Нет причин не использовать посимвольные diff'ы в DaRWiN. Это сильно упрощает вычитку и коррекцию текста. Это позволяет показать нормальные diff-ы после re-wrap'а текста. И это работает в реальном времени.

Но если вам не нравятся запятые у Льва Толстого, то, конечно, придётся медленно вдохнуть и выдохнуть.

Толстой против Майерса

Вчера было интересно. Меня немного занесло и я сделал скриптовый язык поверх RON. То есть, весь парсинг и типы RON'ом уже решены, так что добавить нужно было немного. Тем более что язык сам прорастал через асфальт, разные тулзы уже использовали свои маленькие микроязычки команд. А конкретно сейчас меня подтолкнул маленький случай кодогенерации на awk, который выглядел, как плевок. Все эти грязные сепараторы и липкая пунктуация... нехорошо.
За день работы язык научился выполнять заклинания вроде
for id string in 'ron/status.ron', write _1 _2;
где большая часть слов, технически, 128 битные UUID-ы в Base64 записи, но это станет заметно только тогда, когда мы попытаемся объявить переменную с именем длиннее 20 символов. Чем такой язык лучше awk и прочих? В первую очередь, типизацией. Все переменные это туплы RON из RON атомов (UUID, INT, STRING, FLOAT). Вся обычная возня с парсингом уходит, данные ощущаются скорее как Excel, чем как командная строка UNIX.
Назвал Drone (произносится "дрын").
Для простой кодогенерации пока достаточно, развивать буду по мере необходимости.

# B-tree, LSM tree и хэш таблицы

Весь мир баз данных покоится на двух китах: B-trees и LSM-trees. Это две структуры данных, которые позволяют хранить значения упорядоченно и находить значение по ключу за O(logN). B-деревья мутабельны и представляют из себя просто дерево с большим раздувом. Новые значения просто вписываются в свободную ячейку. LSM-деревья иммутабельны и представляют из себя набор "кирпичей" с отсортированными значениями, которые периодически мержатся. Но есть классический контейнер, который в базах данных не популярен - хэш-таблица. Хотя она и позволяет читать значения по ключу за O(1), в хэш-таблице невозможны range scans, так как значения не упорядочены. Теперь допустим, что вам не нужны range scans. Вы просто пишете и читаете точечные значения. Что получается? А получается довольно интересно.

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

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

Пожалуй, следующий логоческий шаг - обобщить до hash set. Если в наивном хэшмапе есть "ключ" и "значение", желательно одинаковой длины, то в hash set есть просто entries, для которых определены хэш-функция и равенство (ключей). В hash set уже можно складывать всякие забавные entries, например по 32 бита, где 31 бит это ключ и 1 бит это значение.
Получившаяся структура данных чем-то напоминает автомат ППШ - могучее оружие, собранное на коленке из говна и палок.

Примечания.
Ода хэш-таблице написана, пока фаззилась её очередная итерация. Объём кода - 350 строк (это cpp шаблон). Под "говном и палками" я подразумевал "штамповка без фрезеровки" :)