Компиляторы *

Введение

Регулярные выражения — широко используемый способ задания конечных автоматов для поиска текста. Применяются они с давних времён и повсеместно. Они удобны тем, что их запись весьма краткая и лаконичная. Но обратной стороной их удобства является достаточно низкая производительность конечных автоматов, построенных по регулярным выражениям. Проблема в том, что в большинстве реализаций этот конечный автомат строится на лету — во время исполнения программы, что весьма ограничивает скорость его работы.

Возникает вопрос — как можно ускорить построение конечных автоматов по регулярным выражениям? У меня как-то раз возникла идея, как это можно сделать — для этого можно применить настоящий компилятор, который может генерировать максимально эффективный машинный код. Эту идею я решил опробовать на практике, используя библиотеку LLVM как компилятор/оптимизатор для регулярных выражений. Что из этого вышло, будет изложено ниже в данной статье.

Иногда возникает задача парсинга произвольного DSL для дальнейшей работы с ним на уровне PHP кода. И я хочу поделиться опытом решения этой приблемы с помощью регулярок с примерами.

Большинство из нас в повседневной жизни постоянно сталкивается с различными компьютерными системами: процессорами общего назначения (general-purpose, в основном x86) в ноутбуках и рабочих станциях, их мощными многоядерными версиями в датацентрах, мобильными процессорами в телефонах, многочисленными контроллерами в бытовой технике и на транспорте. Но помимо всех упомянутых вариантов есть ещё одно важное, хотя и редко упоминаемое семейство: цифровые сигнальные процессоры, чаще именуемые Digital Signal Processors или просто DSP.

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

В этой статье будет кратко изложена история DSP, их отличие от процессоров общего назначения, особенности их архитектуры, а также будет подробно рассказано о способах оптимизации кода.

Прошу прощения за заголовок, похожий на желтые СМИ, и странный эпиграф, который я объясню ниже. Речь пойдет не о том, как увеличить скорость процессора или емкость диска на порядок, а всего лишь о разновидности данных, которые могут быть включены в исполняемый модуль формата EXE. Эти данные, на мой взгляд, не совсем удачно названы (или же зря буквально переведены) как «ресурсы».

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

В эпоху Windows EXE-формат еще усложнился, и закономерно появилась возможность хранить в нем как неотъемлемую часть не только команды и простые данные, но и, например, картинки или элементы интерактивного диалога. В самом деле, если Ваша программа рисует красивый курсор в виде какой-нибудь стрелочки «выточенной из стали», неудобно же таскать вместе с программой еще и отдельный файл с изображением этой стрелки. Гораздо удобнее поместить изображение прямо внутрь EXE-файла, указав, что это не просто картинка, а именно курсор. Кстати, при создании ярлыка программы, Windows ищет в ресурсах EXE-файла элемент типа «иконка» и высвечивает его как значок ярлыка по умолчанию.

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

© Платон «Государство», книга 7: Миф О Пещере

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

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

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

Команда Rust рада сообщить о выпуске новой версии — 1.53.0. Rust — это язык программирования, позволяющий каждому создавать надёжное и эффективное программное обеспечение.

Если вы установили предыдущую версию Rust средствами rustup, то для обновления до версии 1.53.0 вам достаточно выполнить следующую команду:

rustup update stable

Если у вас ещё не установлен rustup, вы можете установить его с соответствующей страницы нашего веб-сайта, а также посмотреть подробные примечания к выпуску на GitHub.

Что было стабилизировано в 1.53.0

Этот выпуск содержит несколько новых возможностей языка и ещё больше — стандартной библиотеки, включая долгожданную реализацию IntoIterator для массивов. Смотрите подробные примечания к выпуску, чтобы узнать о других изменениях, не представленных в данном анонсе.

Всем привет! На связи Антон Баширов, разработчик из ИТ-кластера «Ростелекома». Импортозамещение набирает обороты, а российский софт всё глубже проникает в нашу повседневную ИТ-шную сущность бытия. Процессоры Эльбрус и Байкал становятся более востребованными, комьюнити расширяется, но мысли о необходимости портировать весь наш любимый технологический стек на неизведанную архитектуру E2K звучат страшнее рассказов про горящий в пламени production-кластер.

Работая в команде по внедрению Эльбрусов, мне довелось в прямом и переносном смысле пощупать наши отечественные процессоры, поэтому я хочу поделиться полученным опытом, рассказать о том, какой болевой порог нужен, чтобы выдержать портирование NoSql native базы данных и не сойти с ума, а еще познакомить разработчиков с миром Эльбруса и его обитателями.

Создать компилятор JS с высокой производительностью означает сделать больше, чем разработать сильно оптимизированный компилятор, например TurboFan, особенно это касается коротких сессий, к примеру, загрузки сайта или инструментов командной строки, когда большая часть работы выполняется до того, как оптимизирующий компилятор получит хотя бы шанс на оптимизацию, не говоря уже о том, чтобы располагать временем на оптимизацию. Как решить эту проблему? К старту курса о Frontend-разработке делимся переводом статьи о Sparkplug — свече зажигания под капотом Chrome 91.

Представьте себе, что вы студент, изучающий современные фичи C++. И вам дали задачу по теме concepts/constraints. У преподавателя, конечно, есть референсное решение "как правильно", но для вас оно неочевидно, и вы навертели гору довольно запутанного кода, который всё равно не работает. (И вы дописываете и дописываете всё новые перегрузки и специализации шаблонов, покрывая всё новые и новые претензии компилятора).

А теперь представьте себе, что вы — преподаватель, который увидел эту гору, и захотел помочь студенту. Вы стали упрощать и упрощать его код, и даже тупо комментировать куски юнит-тестов, чтобы оно хоть как-то заработало... А оно всё равно не работает. Причём, в зависимости от порядка юнит-тестов, выдаёт разные результаты или вообще не собирается. Где-то спряталось неопределённое поведение. Но какое?

Сперва преподаватель (то есть, я) минимизировал код вот до такого: https://gcc.godbolt.org/z/TaMTWqc1T

enum class ABCD : std::uint64_t { A = 0x1012, B = 0x405324, };

constexpr std::uint64_t value = std::to_underlying(ABCD::A); 

В первой части Разработка стековой виртуальной машины и компилятора под неё (часть 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). Дёшево и сердито.

• Низкий порог входа и естественное ограничение уровня сложности в течение длительного времени даже при условии постоянного развития самого языка.
• Возможность писать код программы как в декларативной, так и в императивной парадигме с использованием процедурного, модульного и объектно-ориентированного подхода.

Мы рады объявить третью редакцию языка Rust — Rust 2021, которая выйдет в октябре. Rust 2021 содержит несколько небольших изменений, которые, тем не менее, значительно улучшат удобство использования Rust.

Что такое Редакция?

Релиз Rust 1.0 установил "стабильность без застоя" как основное правило Rust. Начиная с релиза 1.0, это правило звучало так: выпустив функцию в стабильной версии, мы обязуемся поддерживать её во всех будущих выпусках.

Однако есть случаи, когда возможность вносить небольшие изменения в язык бывает полезной — даже если у них нет обратной совместимости. Самый очевидный пример — введение нового ключевого слова, которое делает недействительными переменные с тем же именем. Например, в первой версии Rust не было ключевых слов async и await. Внезапное изменение этих слов на ключевые слова в более поздних версиях привело бы к тому, что, например код let async = 1; перестал работать.

Редакции — механизм, который мы используем для решения этой проблемы. Когда мы хотим выпустить функцию без обратной совместимости, мы делаем её частью новой редакции Rust. Редакции опциональны и должны прописываться явно, поэтому существующие пакеты не видят эти изменения, пока явно не перейдут на новую версию. Это означает, что даже последняя версия Rust по-прежнему не будет рассматривать async как ключевое слово, если не будет выбрана версия 2018 или более поздняя. Этот выбор делается для каждого пакета как части Cargo.toml. Новые пакеты, созданные cargo new, всегда настроены на использование последней стабильной редакции.

int sum(int count)
{
  int result = 0;

  for (int j = 0; j < count; ++j)
    result += j*j;

  return result;
}

sum(int):
        test    edi, edi
        jle     .LBB0_1
        lea     eax, [rdi - 1]
        lea     ecx, [rdi - 2]
        imul    rcx, rax
        lea     eax, [rdi - 3]
        imul    rax, rcx
        shr     rax
        imul    eax, eax, 1431655766
        add     eax, edi
        shr     rcx
        lea     ecx, [rcx + 2*rcx]
        lea     eax, [rax + rcx]
        add     eax, -1
        ret
.LBB0_1:
        xor     eax, eax
        ret

Команда Rust рада сообщить о выпуске новой версии — 1.52.0. Rust — это язык программирования, позволяющий каждому создавать надёжное и эффективное программное обеспечение.

Если вы установили предыдущую версию Rust средствами rustup, то для обновления до версии 1.52.0 вам достаточно выполнить следующую команду:

rustup update stable

Если у вас ещё не установлен rustup, вы можете установить его с соответствующей страницы нашего веб-сайта, а также посмотреть подробные примечания к выпуску на GitHub.

Что было стабилизировано в 1.52.0

Самое значительное изменение этого выпуска не касается самого языка или стандартной библиотеки. Это улучшения в Clippy.

Ранее запуск cargo clippy после cargo check не запускал Clippy: кэширование в Cargo не видело разницы между ними. В версии 1.52 это поведение было исправлено, а значит, теперь пользователи будут получать то поведение, которое ожидают, независимо от порядка запуска этих команд.