RFC-020: Динамические модули и интеграция FFI

⚠️ Устарел: данный документ устарел, его содержимое объединено с RFC-026: FFI основной механизм.

Ссылки:

• RFC-001: Модель spawn и система обработки ошибок
• RFC-008: Модель параллелизма Runtime и разделение проектирования планировщика
• RFC-018: AOT-компилятор LLVM и проектирование прозрачного параллелизма L3
• RFC-021: Расширение FFI на основе библиотек и поддержка кросс-языковых вызовов

Резюме

Данный документ, основываясь на RFC-001, 008, 018, дополнительно детализирует и расширяет модель параллелизма YaoXiang, чтобы охватить практические сценарии, такие как загрузка динамических модулей, внешний интерфейс функций (FFI) и более точная оптимизация планирования. Основные аспекты проектирования:

1. Контракт метаданных динамического модуля: предоставление описания зависимостей на этапе компиляции для динамических библиотек, написанных на одном языке, позволяющее основной программе статически строить DAG при сохранении прозрачного параллелизма.
2. Семантика планирования FFI: внешние функции по умолчанию выступают в DAG как узлы @block, могут быть интегрированы в параллельное планирование через аннотации (инструментарий FFI подробно описан в RFC-021).
3. Оптимизация на основе контекста вызова: вместо статического порогового отката, компилятор интеллектуально принимает решение о встраивании или планировании как отдельного узла на основе фактической роли функции в DAG (количество потребителей, побочные эффекты и т.д.).
4. Механизм слияния потока управления и DAG: посредством Phi-узлов и динамического развёртывания, динамические структуры, такие как if, loop, естественно интегрируются в граф потоков данных.
5. Оптимизация памяти и производительности планировщика Runtime: уточняется управление жизненным циклом узлов, региональное выделение памяти, очереди без блокировок и другие реализации абстракций с низкими накладными расходами.

Целью документа является совершенствование языковой спецификации, обеспечение того, чтобы модель параллелизма YaoXiang могла справляться как со статическим анализом всей программы, так и с гибкой обработкой динамики и внешнего взаимодействия, сохраняя при этом высокую производительность и удобство разработки.

Мотивация

Недостатки существующего проектирования

RFC-001/008/018 построили элегантную модель прозрачного параллелизма, но всё ещё имеют слепые зоны при столкновении с потребностями реального мира:

• Динамические модули: когда программа поддерживает плагины или динамически компонуемые библиотеки, основная программа не может узнать на этапе компиляции о внутренних отношениях вызовов и зависимостях модуля, что приводит к сбою построения глобального DAG.
• FFI-вызовы: внешние функции (такие как библиотеки C) являются полностью чёрным ящиком, их внутренняя часть может содержать параллелизм, блокировки или побочные эффекты, прямое рассмотрение их как обычных узлов нарушит безопасность параллелизма.
• Затраты на планирование малых функций: предложенный в RFC-001 «автоматический откат L1» использует статический порог (количество инструкций <50), это неявное правило затрудняет разработчикам предсказание поведения и не адаптируется к сложному контексту вызовов.
• Слияние потока управления и DAG: представление динамических структур, таких как if, loop в DAG, всё ещё неясно и может повлиять на точность анализа зависимостей.
• Контроль накладных расходов Runtime: с ростом количества узлов DAG, необходимо уточнить проектирование управления памятью и оптимизации производительности планировщика, чтобы избежать их превращения в узкое место.

Цели

• Сохраняя основную философию прозрачного параллелизма, обеспечить ясную, безопасную, постепенную поддержку динамических модулей и FFI.
• Преобразовать оптимизацию планирования из «неявных глобальных правил» в «интеллектуальные решения на основе контекста», повышая предсказуемость и производительность.
• Усовершенствовать представление динамических потоков управления в DAG, обеспечивая естественную интеграцию всех программных структур в модель потоков данных.
• Уточнить стратегии управления памятью и оптимизации производительности планировщика, реализуя абстракции с низкими накладными расходами.

Предложение

1. Контракт метаданных динамического модуля

1.1 Содержание контракта

Каждая динамическая библиотека, скомпилированная с помощью YaoXiang (.yxo / специфичная для платформы динамическая библиотека), должна сопровождаться файлом описания метаданных (.yxmeta), содержащим:

• Список экспортируемых функций: полная сигнатура типа каждой функции (параметры, возвращаемое значение, метки ресурсов).
• Метки побочных эффектов: автоматически выводимые компилятором @pure / @io (разработчик также может явно переопределить).
• Зависимости ресурсов: является ли каждый параметр типом ресурса (например, File), содержит ли возвращаемое значение новые ресурсы.
• Сводка графа вызовов (опционально): ID других экспортируемых функций, которые может вызывать данная функция, для обнаружения циклических зависимостей между модулями.
• Информация о владении: семантика владения параметрами (заимствование/перемещение), владение возвращаемым значением.
• Безопасность параллелизма: автоматически выведенный результат соответствия Send/Sync.

Формат метаданных использует бинарный или структурированный текст (например, MessagePack) для обеспечения эффективности разбора.

1.2 Обработка на этапе компиляции

При компиляции основной программы, при обнаружении вызова функции динамического модуля:

1. Чтение соответствующего файла .yxmeta модуля.
2. Создание заполняющего узла в глобальном DAG, регистрирующего зависимости ввода-вывода, метки побочных эффектов и т.д., полученные из метаданных.
3. Заполняющий узел участвует в анализе зависимостей как обычный узел, планировщик может заранее планировать порядок выполнения.

1.3 Привязка во время выполнения

При загрузке динамического модуля:

• Runtime проверяет, соответствует ли фактическая сигнатура функции метаданным (предотвращение несоответствия версий).
• Привязывает заполняющий узел к фактическому указателю функции.

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

1.4 Гарантии безопасности

• Если динамический модуль нарушает контракт (например, заявляет @pure, но модифицирует глобальное состояние), последствия ложатся на разработчика (аналогично границе unsafe в FFI). Но поскольку это один и тот же язык, безопасность может быть усилена посредством проверок во время выполнения (таких как изоляция памяти), но это увеличит накладные расходы.
• Циклические зависимости между модулями: если модуль A вызывает B, а B вызывает A, и в метаданных уже объявлены отношения вызовов, компилятор может это обнаружить и сообщить об ошибке; если не объявлено, во время выполнения может произойти взаимоблокировка, планировщик обнаружит её и вызовет panic.

2. Семантика планирования FFI в DAG

Полная поддержка инструментария FFI (загрузка динамических библиотек, генерация привязок, преобразование типов, владение памятью) определена в RFC-021. Данный раздел описывает только поведение FFI-вызовов в планировании DAG.

2.1 Поведение планирования по умолчанию

Внешние функции (объявленные через native("symbol")) по умолчанию выступают в DAG как узлы @block:

• Не участвуют в параллельном планировании DAG, выполняются синхронно в текущем потоке.
• Во время выполнения планировщик не вмешивается во внутренний параллелизм.
• Возвращаемое значение доступно, но сам вызов не создаёт рёбер зависимостей.

2.2 Опциональные аннотации параллелизма

Разработчик может использовать аннотации для интеграции FFI-вызовов в планирование DAG (подробности см. в RFC-021 §2.2):

• @pure: рассматривается как обычный узел DAG, может выполняться параллельно с другими узлами без зависимостей.
• @io: участвует в анализе зависимостей ресурсов, множественные вызовы к одному ресурсу автоматически сериализуются.

2.3 Влияние на планировщик

FFI-узлы в планировщике используют ту же структуру TaskNode, что и обычные узлы, отличие только в том, что effect помечен как Block. При обнаружении узла Block планировщик пропускает параллельное планирование и выполняет его синхронно.

3. Оптимизация на основе контекста вызова

Вместо статического порога «автоматического отката L1» в RFC-001, используется интеллектуальное решение компилятора на основе фактического контекста каждой точки вызова в DAG.

3.1 Основания для принятия решения об оптимизации

Компилятор анализирует каждый узел вызова функции:

• Количество потребителей: сколько нижестоящих узлов используют результат данного узла. Если 1, то он является кандидатом на встраивание; если больше 1, он должен остаться отдельным узлом для совместного использования результата.
• Побочные эффекты: если узел имеет побочный эффект @io, он должен остаться отдельным узлом для обеспечения порядка.
• Оценка объёма вычислений: всё ещё может ссылаться на эвристики, такие как количество инструкций, но не как жёсткий порог, а только для оценки выгоды от встраивания.
• Зависимости ресурсов: если узел задействует переменные ресурсов (например, File) и эти переменные передаются между вышестоящими и нижестоящими узлами, встраивание может разрушить цепочку зависимостей, требуется осторожность.

3.2 Операция встраивания

Если принято решение о встраивании:

• Вычислительная логика узла напрямую встраивается в код его единственного нижестоящего узла.
• Узел удаляется из DAG, его входы напрямую становятся входами нижестоящего узла.
• При окончательной генерации кода встроенная функция не создаёт независимую единицу планирования.

3.3 Ограничения встраивания

• Рекурсивные функции или вызовы внутри тела цикла обычно не встраиваются, чтобы предотвратить бесконечное развёртывание.
• Функции через границы модулей (динамические модули, FFI) не встраиваются.
• Разработчик может использовать аннотацию @noinline для принудительного запрета встраивания, или @forceinline для указания компилятору попытаться выполнить встраивание.

3.4 Наблюдаемость

Компилятор должен генерировать отчёт об оптимизации (можно включить через --emit-optimization-report), содержащий следующую информацию:

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

Формат вывода отчёта может быть текстовым или JSON для удобства разбора инструментами.

4. Слияние потока управления и DAG

4.1 Обработка условного ветвления (if)

Введение Phi-узлов (заимствовано из формы SSA) для представления точек слияния ветвей:

• На этапе компиляции для каждого выражения if строится:
  • Два под-DAG ветвей (соответствующие then и else).
  • Один Phi-узел, входы которого включают переменную условия и выходы двух ветвей.
• Семантика Phi-узла: когда переменная условия готова, выход соответствующей ветви выбирается в качестве собственного выхода на основе значения условия.
• Во время выполнения Phi-узел зависит от переменной условия; после того как условие готово, он динамически добавляет себя в список нижестоящих узлов выбранной ветви и ожидает результат этой ветви.

Пример DAG:

        cond
       /    \
  then DAG  else DAG
       \    /
        Phi
         |
      Последующие узлы

4.2 Обработка циклов (loop/while)

Цикл рассматривается как под-DAG с обратными рёбрами, развёртывается по требованию во время выполнения:

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

Сложный пример: условие цикла зависит от переменной, обновляемой внутри тела цикла

let mut x = 0
while x < 10 {
    x = compute(x)  // x обновляется внутри тела цикла
}

В этом шаблоне узел условия x < 10 зависит от x, обновлённого после каждой итерации. DAG представлен следующим образом:

• Шаблон цикла содержит переменную состояния x с начальным значением 0.
• Каждая итерация: сначала выполняется узел условия (зависящий от текущего x), если истинно, выполняется x = compute(x) и генерируется новое x, затем снова входит в узел условия.
• Runtime динамически развёртывает по описанному выше процессу до тех пор, пока условие не станет ложным.

Зависимости между итерациями естественно формируют поток данных через переменные состояния, зависимые итерации автоматически сериализуются, независимые итерации могут выполняться параллельно (например, map).

4.3 Особая обработка бесконечных циклов

Одиночный бесконечный цикл выполняется напрямую синхронно как основной DAG (без затрат на планирование); несколько бесконечных циклов выступают как фоновые DAG, параллельно выполняемые посредством срезов времени планировщика.

5. Оптимизация памяти и производительности планировщика Runtime

5.1 Управление жизненным циклом узлов

• Каждый узел поддерживает счётчик ссылок (атомарная переменная), представляющий количество потребителей, зависящих от его результата.
• После завершения выполнения узла и передачи результата всем нижестоящим узлам, счётчик ссылок обнуляется, память узла может быть освобождена.
• Само значение результата также использует подсчёт ссылок (Arc<T>), но может быть оптимизировано: если результат используется только одним потребителем, владение перемещается напрямую, избегая затрат на подсчёт.

5.2 Региональное выделение памяти (Arena)

Для динамически генерируемых узлов с коротким жизненным циклом (таких как итерации цикла) используется региональный аллокатор:

• Выделение области памяти для одного развёртывания цикла.
• Узлы внутри области выделяются последовательно, освобождаются целиком, уменьшая фрагментацию и затраты на освобождение.
• При завершении области вся память узлов освобождается за один раз.

5.3 Структуры данных без блокировок

• Счётчики зависимостей: используют AtomicUsize, атомарное уменьшение через fetch_sub.
• Очереди готовности: используют двустороннюю очередь Chase-Lev (локальная очередь каждого потока + кража работы), уменьшая конкуренцию за блокировки.
• Списки нижестоящих узлов: только для чтения после создания, избегая параллельных модификаций.

5.4 Адаптивное планирование

• Если в системе только один бесконечный цикл, он выполняется напрямую синхронно с нулевыми затратами на планирование.
• В зависимости от гранулярности задач и нагрузки системы, динамически регулируется степень параллелизма (например, путём мониторинга длины очереди для регулировки количества рабочих потоков).

5.5 Принцип абстракций с низкими накладными расходами

Все затраты на планирование пропорциональны количеству задач, дополнительные затраты каждой задачи (создание, постановка в очередь, обработка зависимостей) контролируются на уровне десятков наносекунд. Для задач со сверхмелкой гранулярностью оптимизация встраивания (см. раздел 3) позволяет избежать планирования.

Детальное проектирование

6.1 Формат метаданных динамического модуля (проект)

// Структура файла метаданных (упрощённая)
struct Metadata {
    version: u32,
    functions: Vec<FuncMeta>,
}

struct FuncMeta {
    name: String,
    signature: TypeSignature,
    effects: EffectTag,      // Pure | IO | Block
    resource_params: Vec<usize>, // Список индексов параметров, указывающих какие параметры являются типами ресурсов
    calls: Vec<String>,       // Имена других вызываемых экспортируемых функций (опционально)
    ownership: OwnershipInfo,
    send_sync: SendSync,      // Удовлетворяет ли Send/Sync
}

6.2 Основные структуры данных планировщика

struct TaskNode {
    id: TaskId,
    deps: Vec<TaskId>,                // Вышестоящие зависимости
    remaining_deps: AtomicUsize,
    inputs: Vec<Option<Value>>,
    result: Option<Value>,
    func: Executable,
    downstream: Vec<TaskId>,           // Нижестоящие узлы (только для чтения после создания)
    effect: EffectTag,
    arena_id: Option<ArenaId>,         // Принадлежность к области (опционально)
}

struct Scheduler {
    ready_queues: PerThreadQueue<TaskId>, // Локальная очередь каждого потока
    global_work_stealer: WorkStealer,
    arenas: ArenaAllocator,               // Региональный аллокатор
}

6.3 Анализ оптимизации на основе контекста

Компилятор выполняет следующие шаги на уровне MIR:

1. Построение глобального графа вызовов и графа зависимостей данных.
2. Для каждого узла вызова функции вычисление его исходящей степени (количество потребителей).
3. Если исходящая степень равна 1, и функция не имеет побочных эффектов (@pure), и не является рекурсивной, она помечается как «кандидат на встраивание».
4. В сочетании с эвристиками (такими как количество инструкций) оценивается выгода от встраивания, принимается решение о встраивании.
5. При встраивании код узла вызова встраивается в его нижестоящий узел, обновляются отношения зависимостей.

6.4 Представление узлов потока управления

enum NodeKind {
    Normal(FuncId),
    Phi { cond: TaskId, then_branch: TaskId, else_branch: TaskId },
    LoopTemplate { cond: FuncId, body: FuncId, state_var: VarId },
    // ...
}

При динамическом развёртывании во время выполнения LoopTemplate генерирует серию экземпляров Normal.

Компромиссы

Преимущества

• Безопасная интеграция динамических модулей: контракт метаданных позволяет динамическим библиотекам беспрепятственно совместно использовать модель параллелизма с основной программой, сохраняя целостность статического DAG.
• Постепенная интеграция FFI: разработчики могут постепенно добавлять аннотации к внешним функциям, переходя от безопасной деградации к эффективному параллелизму.
• Предсказуемость оптимизации: решения на основе контекста заменяют неявные пороги, поведение прозрачно, разработчики могут понять оптимизацию с помощью инструментов.
• Естественная интеграция потока управления: Phi-узлы и динамическое развёртывание позволяют DAG представлять все программные структуры без специального синтаксиса.
• Масштабируемая производительность: проектирование регионального выделения, очередей без блокировок и т.д. гарантирует, что планировщик может справляться с крупномасштабным параллелизмом.

Недостатки

• Контракт метаданных увеличивает сложность компиляции: требуется генерация и разбор метаданных для динамических библиотек, инструментарий должен это поддерживать.
• FFI-аннотации зависят от корректности разработчика: неправильная разметка может привести к гонкам данных, необходимо снижать риски посредством документации и подсказок инструментов.
• Анализ оптимизации на основе контекста отнимает время: глобальный анализ может увеличить время компиляции, но может быть смягчён посредством инкрементальной компиляции.
• Динамическое развёртывание увеличивает накладные расходы Runtime: развёртывание цикла требует динамического создания узлов, но может быть смягчено региональным выделением.

Стратегия реализации

Разделение на этапы (с предложениями по приоритету)

Предложения по приоритету реализации: в начальном периоде не обязательно стремиться к идеальной реализации, сначала можно использовать простые решения для запуска системы, а затем постепенно оптимизировать. Например:

• Подсчёт ссылок может напрямую использовать Arc.
• Очереди без блокировок могут использовать зрелые библиотеки (например, deque из crossbeam).
• Региональное выделение может сначала использовать простой bump allocator, с последующей оптимизацией.

Этап 1: Базовая поддержка (v0.7)

• [ ] Реализация деградации FFI по умолчанию до @block.
• [ ] Добавление аннотаций @pure, @io для использования в FFI.
• [ ] Реализация типов-обёрток ресурсов (таких как File) и их базовых методов.

Этап 2: Метаданные динамических модулей (v0.8)

• [ ] Проектирование формата метаданных, модификация компилятора для генерации .yxmeta для динамических библиотек.
• [ ] Реализация чтения метаданных и создания заполняющих узлов при компиляции основной программы.
• [ ] Реализация механизма привязки во время выполнения.

Этап 3: Оптимизация на основе контекста (v0.9)

• [ ] Реализация анализа графа вызовов, вычисление исходящей степени узлов.
• [ ] Добавление поддержки решений о встраивании и генерации кода.
• [ ] Реализация вывода отчёта об оптимизации (включая точки встраивания, причины и т.д.).

Этап 4: Слияние DAG потока управления (v0.10)

• [ ] Реализация представления Phi-узлов и условного ветвления на этапе компиляции.
• [ ] Реализация шаблонов циклов и динамического развёртывания в Runtime.
• [ ] Усовершенствование фонового планирования бесконечных циклов.

Этап 5: Оптимизация производительности (v1.0)

• [ ] Реализация регионального аллокатора.
• [ ] Оптимизация очередей без блокировок и кражи работы.
• [ ] Бенчмарки и настройка.

Связь с другими RFC

• RFC-001: расширяет обработку побочных эффектов и уровни параллелизма, использует оптимизацию на основе контекста вместо автоматического отката.
• RFC-008: дополняет поддержку Runtime для динамических модулей и FFI, сохраняя разделение проектирования планировщика.
• RFC-018: детализирует построение DAG и реализацию планировщика, добавляет Phi-узлы и динамическое развёртывание.

Приложение: Записи о проектных решениях

Решение	Принятое решение	Дата	Автор
Предоставление контракта метаданных динамическими модулями	Использование файла метаданных + привязка во время выполнения	2026-03-14	Чэньсюй
Деградация FFI по умолчанию до @block	Да, разработчик может постепенно аннотировать	2026-03-14	Чэньсюй
Оптимизация на основе контекста вместо статического порога	Интеллектуальные решения на основе исходящей степени, побочных эффектов и т.д.	2026-03-14	Чэньсюй
Введение Phi-узлов для обработки условного ветвления	Заимствовано из SSA, динамический выбор ветви	2026-03-14	Чэньсюй
Динамическое развёртывание циклов	Инстанцирование итераций по требованию, поддержка сериализации зависимостей	2026-03-14	Чэньсюй
Региональное выделение для узлов с коротким жизненным циклом	Повышение эффективности памяти и локальности кэша	2026-03-14	Чэньсюй

Ссылки

• RFC-001: Модель spawn и система обработки ошибок
• RFC-008: Модель параллелизма Runtime и разделение проектирования планировщика
• RFC-018: AOT-компилятор LLVM и проектирование прозрачного параллелизма L3
• RFC-021: Расширение FFI на основе библиотек и поддержка кросс-языковых вызовов
• SSA-форма и Phi-функции
• Двусторонняя очередь Chase-Lev