Цель проекта Boson — это разработка встроенного движка базы данных документов JSON, написанный на C++. Основные возможности: стандартное хранилище JSON-документов в формате ключ/значениями с постоянным хранением на диске. Размер документов до 4Gb. Быстрый поиск документов по ID с использованием индекса B+ дерева. Поддержка курсоров для линейного обхода записей. База данных в одном файле, без временных файлов. Простое, чистое и легкое в использовании API. Самодостаточный и не требующий настройки.

В предыдущих двух статьях мы прошли шаги от кэширования файлового ввода/вода (часть I) до построенного на его базе хранилища записей произвольной длины (часть II) с проверкой целостности, возможностью получения записей списком и повторным использованием свободного места. Теперь мы переходим к завершающей части и "сердцу" СУБД - индексу.

Зачем нужен индекс: предположим, что в базе есть 1 млрд не отсортированных записей документов, тогда поиск конкретного документа по ID потребует O(n) операций, то есть до 1 млрд операций в худшем случае. Однако, если бы документы в базе были бы отсортированы по ID, то поиск в сортированной базе, тем же бинарным поиском занял бы O(log n) занял бы 30 операций. Что, теоретически, на базе в 1 млрд записей будет в 33.3 млн раз быстрее.

В первой части статьи мы обсуждали разработку самого нижнего слоя СУБД Boson - CachedFileIO. Как упоминалось, статистика такого явления как Locality of Reference говорит о том, что в реальных приложениях ~95% запросов к данным локализованы в 10-15% базы данных. При этом среднее соотношение чтения/записи - 70%/30%. Это делает эффективным использование кэша (cache) работающего на основе алгоритма Least Recently Used (LRU). Реализовав его, мы получили 260%-600% прироста скорости чтения при 87%-97% cache hits.

Следующим после кэша слоем СУБД Boson является хранилище записей RecordFileIO. Это уже первый прообраз базы данных, который начинает приносить прикладную пользу. Сформулируем верхнеуровневую спецификацию требований:

После разработки виртуальной машины и компилятора в рамках хобби прошел год и захотелось попробовать реализовать ёмкий по алгоритмам проект по системному программированию.

Каждый разработчик "кровавого" enterprise в своей работе использует СУБД (SQL/NoSQL) и меня всегда искренне интересовало как они устроены в самом сердце, на самом низком уровне. Почитав документацию и исходный код SQLite и MongoDB, про используемые в индексах и интерпретаторах запросов алгоритмы, осознал, что несмотря на широкую распространенность и некую привычность, системы управления базами данных (СУБД) - это сложные программные продукты, реализация которых не всем под силу. Отлично - как раз то, что мне надо. С мотивацией разобрались, перейдем к делу.

Итак, для начала хорошо бы сформулировать высокоуровневую спецификацию требований. Boson - это легкая, встраиваемая документоориентированная база данных на С/С++

Для завершения реализации компилятора потребовалось около месяца времени (вечерами), чтобы на практике познакомиться с такими темами как BNF (Backus Naur Form), Abstract Syntax Tree (AST), Symbol Table, способами генерации кода, разработки самого компилятора (front-end, back-end), а также модификации виртуальной машины CVM. Ранее с этими темами был не знаком, но благодаря комментаторам погрузился. Хоть затрагиваемых тем много, постараюсь рассказать очень лаконично. Но обо всём по порядку.

По ходу разработки генератора кода для виртуальной машины понял, что виртуальная машина не готова к полноценным вызовам функций, с передачей аргументов и хранению локальных переменных функций. Поэтому её необходимо доработать. А именно, нужно определиться с Соглашением о вызовах (calling convention). Есть много разных вариантов, но выбор конечный за разработчиком. Главное - это обеспечить целостность стека, после вызова.

Соглашение о вызовах (calling convention) - это правила по которым при вызове функции передаются аргументы в вызываемую функцию (стек/регистры, порядок), кто и как очищает стек после вызова (вызывающий/вызываемый) и как возвращается результат функции в точку вызова (стек/регистр). Ко всему прочему, вызываемые функции могут создавать локальные переменные, которые будут хранится в стеке, что тоже необходимо учитывать, особенно, чтобы работала рекурсия.

На сегодняшний день, наиболее знакомое мне Соглашение о вызове (calling convention), регулирующее правила передачи аргументов функции, очистки стека после вызова, а также логика хранения локальных переменных - это C declaration (cdecl, x86/64) и pascal. Попробую применить эти знания с небольшими модификациями, а именно без прямого доступа программы к регистрам виртуальной машины (она же всё таки стековая, а не регистровая). Итак, логика будет следующая.

В первой части Разработка стековой виртуальной машины и компилятора под неё (часть I) сделал свою элементарную стековую виртуальную машину, которая умеет работать со стеком, делать арифметику с целыми числами со знаком, условные переходы и вызовы функций с возвратом. Но так как целью было создать не только виртуальную машину, но и компилятор C подобного языка, пришло время сделать первые шаги в сторону компиляции. Опыта никакого. Буду действовать по разумению.

Одним из первых этапов компиляции является лексический разбор исходного кода нашего "C подобного языка" (кстати, надо какое-то название дать как только он станет более формальным). Задача простая - "нарубить" массив символов (исходный код) на список классифицированных токенов, чтобы последующий синтаксический разбор и генерация кода не вызывали сложности.

Так сложилось, что за последние 18 лет, не приходилось писать на C/C++. На работе использовалась Java, да и ввиду должностей деятельность больше была связана с предпринимательством - переговоры, корпоративные продажи, выстраивание производственных операций и структурирование инвестиционных сделок. Захотелось в свободное от работы время восстановить навыки, размять часть мозга которую не напрягал все 18 лет и, естественно, начать с самых основ. Осталось придумать себе задачу.

В универе преподаватели, молодость которых приходилась на 70-80е годы, до объектно-ориентированного программирования убивались по теме разработке собственных языков (интерпретаторов, компиляторов) под предметные области. Всё это казалось мне невостребованным "старьём", но появление новых языков за последнее десятилетие (Go, Kotlin и множества других) повысили мой интерес к этой теме.

Решил в качестве хобби написать 32-bit стековую виртуальную машину и компилятор C подобного языка под неё, чтобы восстановить базовые навыки. Такая классическая Computer Science задачка для заполнения вечеров с пивом. Как предприниматель, я четко понимаю, что она никому не нужна, но такая практика нужна мне для эстетического инженерного удовольствия. Плюс когда об этом рассказываешь сам понимаешь глубже. С целью и мотивами определился. Начнём.

Так как это виртуальная машина, мне нужно определиться с её характеристиками:

CPU: 32-bitный набор команд, так как машина стековая, в основном операнды команд храним в стеке, из регистров только IP (Instruction Pointer) и SP (Stack Pointer), пока работаем с целыми числами со знаком (__int32), позже добавим остальные типы данных.

RAM: пусть памяти пока будет 65536 ячеек по 32-bit`а. Которую организуем просто. С нижних адресов в верх будут идти код (code/text) и данные (data, heap), а с верхних адресов вниз будет расти стек (stack). Дёшево и сердито.

Разрабатывая игровой движок для Android, я был уверен, что нативный код C/C++ будет исполняться быстрее чем аналогичный код на Java. Это утверждение справедливо, но не для последних версий Android. Чтобы проверить почему так происходит, решил провести небольшое исследование.

Для теста использовался Android Studio 4.1.3 - для Java Android SDK (API 30), для C/C++ Android NDK (r21, компилятор CLang). Тест довольно тупой, который выполняет арифметические операции над массивом int в двух вложенных циклах. Ничего осмысленного и специфичного.