Побеждаем компилятор в скорости при помощи ассемблера

в 13:00, , рубрики: AArch64, abi, ruvds_переводы, ассемблерная вставка, оптимизация кода, производительность, язык ассемблера

Побеждаем компилятор в скорости при помощи ассемблера - 1


В наше время все знают, что писать ассемблерный код — занятие для дураков. Компиляторы — это результат буквально человеко-веков разработки, и они понимают процессор гораздо лучше, чем вы.

Тем не менее, иногда до нас доносятся слухи.

Написанные в древних томах, подслушанные в тайных покоях, начертанные на стенах разрушенных храмов, упоминаемые в загадочных текстах, они рисуют чёткую картину:

Компиляторы плохо справляются с генерацией кода для интерпретаторов, и можно превзойти их, написав интерпретатор на языке ассемблера.


Недавно я написал быстрый интерпретатор для Uxn CPU — стековой архитектуры с 256 опкодами. Интерпретатор — это простой цикл, считывающий байт из ОЗУ, а затем выбирающий соответствующую команду:

impl Uxn {
    /// Выполняет VM с указанного адреса, пока она не завершит выполнение
    #[inline]
    pub fn run<D: Device>(&mut self, dev: &mut D, mut pc: u16) {
        loop {
            let op = self.ram[usize::from(pc)];
            pc = pc.wrapping_add(1);
            let Some(next) = self.op(op, dev, pc) else {
                break;
            };
            pc = next;
        }
    }

    /// Выполняет одну операцию
    #[inline]
    fn op<D: Device>(&mut self, op: u8, dev: &mut D, pc: u16) -> Option<u16> {
        match op {
            0x00 => op::brk(self, dev, pc),
            0x01 => op::inc::<0b000>(self, dev, pc),
            0x02 => op::pop::<0b000>(self, dev, pc),
            0x03 => op::nip::<0b000>(self, dev, pc),
            0x04 => op::swp::<0b000>(self, dev, pc),
            0x05 => op::rot::<0b000>(self, dev, pc),
            0x06 => op::dup::<0b000>(self, dev, pc),
            0x07 => op::ovr::<0b000>(self, dev, pc),
            0x08 => op::equ::<0b000>(self, dev, pc),
            0x09 => op::neq::<0b000>(self, dev, pc),
            0x0a => op::gth::<0b000>(self, dev, pc),
            0x0b => op::lth::<0b000>(self, dev, pc),
            0x0c => op::jmp::<0b000>(self, dev, pc),
            0x0d => op::jcn::<0b000>(self, dev, pc),
            0x0e => op::jsr::<0b000>(self, dev, pc),
            // ... и т.д.
        }
    }
}

В результате все реализации опкодов оказываются мономорфизированными и встроенными в тело Uxn::run(..), а компилятор достаточно умён, чтобы хранить значения ключей в регистрах. Благодаря этому он относительно быстр: по моим данным, он на 10-20% превосходит по скорости эталонную реализацию.

Давайте рассмотрим ассемблерный код и разберёмся, что делает компилятор, а ещё подумаем, можно ли как-то улучшить ситуацию. Для контекста: Uxn CPU имеет четыре разных типа памяти:

  • Стек данных, имеющий формат [u8; 256] с индексом u8.
  • Стек возвратов, имеющий тот же формат.
  • ОЗУ в формате [u8; 65535].
  • Память устройства, которую мы пока не будем рассматривать (вместе с аргументом D: Device).

В процессе вычислений мы также отслеживаем счётчик программ pc (u16), используемый для индексации в ОЗУ. В каждом цикле мы загружаем байт из ОЗУ, а затем вызываем соответствующий опкод. Некоторые опкоды также могут выполнять чтение и запись в ОЗУ, так что можно писать самомодифицируемый код!

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

; INC
0x100002d4c: ldrb w8, [x25]     ; считываем текущий индекс стека данных
0x100002d50: ldrb w9, [x24, x8] ; считываем байт из стека данных
0x100002d54: add w9, w9, #1     ; выполняем инкремент этого байта
0x100002d58: strb w9, [x24, x8] ; записываем этот байт обратно в стек
0x100002d5c: b 0x100002d1c      ; переходим обратно к циклу диспетчеризации

Из этого ассемблерного кода мы узнали следующее:

  • x25 — это адрес индекса стека данных (не его значение!);
  • x24 — адрес массива стека данных;
  • w9 используется как временный регистр.

Аналогично, команда INCr (инкремент верхнего значения стека возвратов) даёт нам понять, что x22 и x23 — это адреса данных и индекса стека возвратов.

JMP показывает нам, что счётчик программ хранится в w27:

; JMP
0x100002eac: ldrb w8, [x25]      ; считываем текущий индекс стека данных
0x100002eb0: ldrsb w9, [x24, x8] ; считываем смещение перехода со знаком из стека данных
0x100002eb4: sub w8, w8, #1      ; выполняем декремент индекса стека данных
0x100002eb8: strb w8, [x25]      ; записываем обратно индекс стека данных
0x100002ebc: add w27, w27, w9    ; применяем переход к нашему счётчику программ
0x100002ec0: b 0x100002d1c       ; переходим обратно к циклу диспетчеризации

Наконец, стоит исследовать сам цикл диспетчеризации:

0x100002d1c: and x10, x27, #0xffff          ; маскируем PC в u16
0x100002d20: ldr x8, [x20, #256]            ; загружаем базовый адрес ОЗУ из *mut Uxn
0x100002d24: ldrb w10, [x8, x10]            ; загружаем байт опкода из ОЗУ
0x100002d28: add w27, w27, #1               ; выполняем инкремент PC
0x100002d2c: adr x11, #-96                  ; загружаем базовый адрес для перехода
0x100002d30: ldrh w12, [x27, x10, lsl  #1]  ; загружаем величину перехода на опкод
0x100002d34: add x11, x11, x12, lsl #2      ; вычисляем местоположение перехода
0x100002d38: br x11                         ; переходим к реализации опкода

Компилятор сгенерировал таблицу переходов 256 смещений (каждое является двухбайтным значением, на которое указывает lsl #1). Он считывает значение для конкретного опкода из этой таблицы, чтобы вычислить местоположение перехода, а затем выполняет косвенное ветвление, чтобы перейти к реализации опкода.

Можно запустить код в отладчике и сдампить саму таблицу переходов:

(lldb) disas -p -c3
raven-cli`raven_uxn::Uxn::run::had9dba0d7d1b5105:
->  0x100002d30 <+236>: ldrh   w12, [x27, x10, lsl  #1]
    0x100002d34 <+240>: add    x11, x11, x12, lsl #2
    0x100002d38 <+244>: br     x11
(lldb) reg read x27
     x27 = 0x0000000100170b10
(lldb) memory read -s2 -fu -c256 0x0000000100170b10
0x100170b10: 2923
0x100170b12: 31
0x100170b14: 36
0x100170b16: 40
0x100170b18: 44
0x100170b1a: 52
0x100170b1c: 28
0x100170b1e: 64
0x100170b20: 70
0x100170b22: 78
0x100170b24: 86
0x100170b26: 94
0x100170b28: 119
0x100170b2a: 102
0x100170b2c: 110
0x100170b2e: 125
; и т.д.

Именно так я и сгенерировал листинг команд для каждого опкода.

Изучив ассемблерный код, можно заметить два потенциально неэффективных момента:

  • Некоторые критически важные значения (индексы стеков, базовые адреса ОЗУ) хранятся в памяти, а не в регистрах; например, у INC есть дополнительная операция загрузки для получения текущего индекса стека данных.
  • Цикл диспетчеризации выполняет одно косвенное ветвление к реализации опкода. Это значит, что ветвление будет практически непредсказуемым!

При профилировании кода выясняется, что самые «горячие» команды находятся в цикле диспетчеризации; больше трети общего времени выполнения занимает ldrh!

Побеждаем компилятор в скорости при помощи ассемблера - 2

Я не уверен, что в данном случае профилировщик соотносит время с правильной командой, но тенденции определённо указывают на то, что диспетчеризация — это затратный процесс.

LuaJIT — это быстрый интерпретатор (с большим отрывом от других), написанный на ассемблере. Майк Пэлл называет двумя главными причинами высокой скорости хранение состояний в регистрах и косвенное сшивание; надёжным образом это можно реализовать только на ассемблере.

Так как заставить компилятор генерировать чётко определённые паттерны сложно, давайте начнём писать собственный ассемблерный код. Дома я работаю на M1 Macbook, поэтому весь ассемблерный код будет для AArch64. В реализации применяются регистры общего назначения; имейте в виду, что w* и x* обозначают 32-битный и 64-битный режимы одного и того же регистра.

▍ Назначение регистров

Нашей первой оптимизацией будет хранение всех важных данных в регистрах, чтобы избежать ненужных загрузок и сохранений. В конечном итоге в моей реализации используются 9 регистров (x0-x8), а также несколько scratch-регистров:

; x0 - указатель стека (&mut [u8; 256])
; x1 - индекс стека (u8)
; x2 - указатель стека возвратов (&mut [u8; 256])
; x3 - индекс стека возвратов (u8)
; x4 - указатель ОЗУ (&mut [u8; 65536])
; x5 - счётчик программ (u16), смещение следующего значения в ОЗУ
; x6 - указатель VM (&mut Uxn)
; x7 - указатель дескриптора устройства (&DeviceHandle)
; x8 - указатель таблицы переходов
; x9-15 - scratch-регистры

Соглашение о вызове AArch64 предоставляет лишь 8 входных аргументов, так что мы не можем вызывать функцию напрямую со всеми этими значениями в регистрах; нам понадобится точка входа в стиле C ABI (её мы рассмотрим ниже).

▍ Косвенное сшивание

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

Опкоды хранятся как единичные байты в ОЗУ VM с базовым адресом x4. Я создам отдельную таблицу переходов указателей функций, а затем передам её адрес в регистре x8. На стороне Rust таблица будет выглядеть так:

extern "C" {
    fn BRK();
    fn INC();
    fn POP();
    fn NIP();
    fn SWP();
    fn ROT();
    fn DUP();
    fn OVR();
    fn EQU();
    // ... и т.д.
}

const JUMP_TABLE: [unsafe extern "C" fn(); 256] = [
    (BRK as unsafe extern "C" fn()),
    (INC as unsafe extern "C" fn()),
    (POP as unsafe extern "C" fn()),
    (NIP as unsafe extern "C" fn()),
    (SWP as unsafe extern "C" fn()),
    (ROT as unsafe extern "C" fn()),
    (DUP as unsafe extern "C" fn()),
    (OVR as unsafe extern "C" fn()),
    (EQU as unsafe extern "C" fn()),
    (NEQ as unsafe extern "C" fn()),
    // ... и т.д.
];

В ассемблерном коде мы хотим считать текущий байт из ОЗУ VM (x4), использовать его для выбора адреса в таблице переходов (x8), а затем перейти по этому адресу. Я написал макрос для выполнения этой диспетчеризации:

.macro next
    ldrb w9, [x4, x5]          ; загружаем байт из ОЗУ
    add x5, x5, #1             ; выполняем инкремент счётчика программ
    and x5, x5, #0xffff        ; заворачиваем счётчик программ
    ldr x10, [x8, x9, lsl #3]  ; загружаем адрес реализации опкода
    br x10                     ; переходим к реализации опкода
.endm

Обратите внимание, что это макрос, а не функция; мы добавим в конец каждого опкода next, что будет развёрнуто в этот текст.

Например, вот INC:

.global _INC
_INC:
    ldrb w9, [x0, x1]   ; считываем байт из вершины стека
    add w9, w9, #1      ; выполняем его инкремент
    strb w9, [x0, x1]   ; записываем его обратно
    next                ; переходим к следующему опкоду

В отличие от LuaJIT, здесь нет этапа декодирования для команд; аргументы регистров отсутствуют, а однобайтный опкод уникальным образом определяет поведение программы.

▍ Реализация

Реализация остальных 255 опкодов — достаточно монотонная задача, здесь нет ничего особо экзотического, простой ассемблер без затей.

Во многих случаях я использовал вспомогательный макрос, чтобы генерировать код для группы команд:

.macro binary_op op
    ldrb w10, [x0, x1]  ; считываем верхнее значение из стека данных
    pop                 ; выполняем декремент индекса стека данных (это макрос!)
    ldrb w11, [x0, x1]  ; считываем следующее значение из стека данных
    op w10, w11, w10   ; выполняем саму математическую операцию
    strb w10, [x0, x1]  ; записываем результат в стек данных
    next
.endm

.global _ADD
_ADD:
    binary_op add

.global _SUB
_SUB:
    binary_op sub

.global _MUL
_MUL:
    binary_op mul

.global _DIV
_DIV:
    binary_op udiv

Вся реализация уместилась примерно в 2400 строк. Кажется, что это много, но на самом деле уникальна только примерно половина: у большинства опкодов есть два типа (с флагом RET и без него), различающихся только по используемому стеку.

▍ Оболочки C

Разумеется, программа не полностью написана на ассемблере. Нам нужно как-то вызывать нашу ассемблерную функцию из остальной реализации (на Rust). Это похоже на функцию entry (Rust), которая выполняет вызов точки aarch64_entry (ассемблер) (совместимой с C ABI):

Побеждаем компилятор в скорости при помощи ассемблера - 3

Как же нам передавать aarch64_entry? Состояние слишком велико, чтобы передавать его в регистрах аргументов функции (x0-x7), поэтому я определил вспомогательный объект, который содержит всё необходимое нам:

#[repr(C)]
pub(crate) struct EntryHandle {
    stack_data: *mut u8,
    stack_index: *mut u8,
    ret_data: *mut u8,
    ret_index: *mut u8,
    ram: *mut u8,
    vm: *mut core::ffi::c_void,  // *Uxn
    dev: *mut core::ffi::c_void, // *DeviceHandle
}

struct DeviceHandle<'a>(&'a mut dyn Device);

DeviceHandle необходимо потому, что &mut dyn Device — это толстый указатель (fat pointer), а потому его небезопасно передавать в функцию C. Как и во всех компьютерных задачах, мы решим эту добавлением ещё одного уровня косвенности: поместим &mut dyn Device в DeviceHandle, а затем передадим уже его адрес.

Для вызова ассемблерного кода достаточно заполнить объект EntryHandle, а затем выполнить ветвление в опасную зону:

// Объявление нашей точки входа, написанной на ассемблере
extern "C" {
    pub fn aarch64_entry(
        h: *const EntryHandle,
        pc: u16,
        table: *const unsafe extern "C" fn(),
    ) -> u16;
}

pub fn entry(vm: &mut Uxn, dev: &mut dyn Device, pc: u16) -> u16 {
    let mut h = DeviceHandle(dev);
    let mut e = EntryHandle {
        stack_data: vm.stack.data.as_mut_ptr(),
        stack_index: &mut vm.stack.index as *mut _,
        ret_data: vm.ret.data.as_mut_ptr(),
        ret_index: &mut vm.ret.index as *mut _,
        ram: (*vm.ram).as_mut_ptr(),
        vm: vm as *mut _ as *mut _,
        dev: &mut h as *mut _ as *mut _,
    };

    // БЕЗОПАСНОСТЬ: ты мне доверяешь?
    unsafe {
        aarch64::aarch64_entry(&mut e as *mut _, pc, JUMP_TABLE.as_ptr())
    }
}

aarch64_entry — это самописная точка входа в ассемблерный код. Она жонглирует регистрами, чтобы подготовить всё необходимое для наших опкодов, а затем начинает исполнение при помощи обычного макроса next:

.global _aarch64_entry
_aarch64_entry:
    sub sp, sp, #0x200  ; подготавливаем место в стеке
    stp   x29, x30, [sp, 0x0]   ; сохраняем стек и указатель фрейма
    mov   x29, sp

    // Выполняем распаковку из EntryHandle в регистры
    mov x5, x1 ; копируем PC (перед перезаписью x1)
    mov x8, x2 ; таблица переходов (перед перезаписью x2)
    ldr x1, [x0, 0x8]  ; указатель индекса стека
    ldr x2, [x0, 0x10] ; возвращаем указатель данных
    ldr x3, [x0, 0x18] ; возвращаем указатель индекса
    ldr x4, [x0, 0x20] ; указатель ОЗУ
    ldr x6, [x0, 0x28] ; *mut Uxn
    ldr x7, [x0, 0x30] ; *mut DeviceHandle
    ldr x0, [x0, 0x00] ; указатель данных стека (перезаписывает *EntryHandle)

    ; Выполняем преобразование из указателей индексов в значения индексов в w1 / w3
    stp x1, x3, [sp, 0x10]      ; сохраняем указатели индекса стека
    ldrb w1, [x1]               ; загружаем индекс стека
    ldrb w3, [x3]               ; загружаем индекс возвратов

    ; Переходим в список команд
    next

Далее при выходе (с помощью опкода BRK) нам нужно обновить данные и индексы стека возвратов, скопировав значения из регистров в соответствующие адреса памяти:

.global _BRK
_BRK:
    ; Записываем значения индекса обратно через указатели индекса
    ldp x9, x10, [sp, 0x10]     ; восстанавливаем указатели индекса стека
    strb w1, [x9]               ; сохраняем индекс стека данных
    strb w3, [x10]              ; сохраняем индекс стека возвратов

    ldp   x29, x30, [sp, 0x0]   ; восстанавливаем стек и указатель фрейма
    add sp, sp, #0x200          ; откатываем смешение стека

    mov x0, x5 ; возвращаем PC из функции
    ret

▍ Ввод-вывод устройства

Опкоды DEI и DEO выполняют «ввод-вывод устройства», что позволяет подсоединять к системе произвольную периферию. Самый популярный набор периферии — это система Varvara,
добавляющая всё необходимое для превращения CPU в настоящий компьютер: экран, ввод с клавиатуры и мыши, звук и так далее.

Чтобы реализация Uxn оставалась обобщённой, я определил для устройства трейт:

/// Трейт для совместимого с Uxn устройства
pub trait Device {
    /// Выполняет операцию `DEI` для указанного устройства
    ///
    /// Эта функция должна записать свой выходной байт в `vm.dev[target]`; затем
    /// цикл вычислений CPU скопирует это значение в стек.
    fn dei(&mut self, vm: &mut Uxn, target: u8);

    /// Выполняет операцию `DEO` для указанной цели
    ///
    /// Перед вызовом этой функции входной байт будет записан в `vm.dev[target]`, после чего считывается этой функцией.
    ///
    /// Возвращает `true`, если CPU должен продолжать исполнение, `false`, если должен
    /// выполнить выход.
    #[must_use]
    fn deo(&mut self, vm: &mut Uxn, target: u8) -> bool;
}

Реализация опкода получает &mut dyn Device, то есть что-то, реализующее этот трейт, и вызывает для него методы трейта:

pub fn deo<const FLAGS: u8>(
    vm: &mut Uxn,
    dev: &mut dyn Device,
    pc: u16,
) -> Option<u16> {
    let mut s = vm.stack_view::<FLAGS>();
    let i = s.pop_byte();
    let mut run = true;
    match s.pop() {
        Value::Short(v) => {
            let [lo, hi] = v.to_le_bytes();
            let j = i.wrapping_add(1);
            vm.dev[usize::from(i)] = hi;
            run &= dev.deo(vm, i);
            vm.dev[usize::from(j)] = lo;
            run &= dev.deo(vm, j);
        }
        Value::Byte(v) => {
            vm.dev[usize::from(i)] = v;
            run &= dev.deo(vm, i);
        }
    }
    if run {
        Some(pc)
    } else {
        None
    }
}

Однако эта функция несовместима с C ABI — она и обобщённая, и получает объект трейта, так что её нельзя вызывать напрямую из опкода DEO на ассемблере.

Чтобы мои опкоды могли вызывать функции DEO и DEI, я снова написал несколько оболочек (shim):

#[no_mangle]
extern "C" fn deo_entry(vm: &mut Uxn, dev: &mut DeviceHandle) -> bool {
    vm.deo::<0b000>(dev.0, 0).is_some()
}

#[no_mangle]
extern "C" fn deo_2_entry(vm: &mut Uxn, dev: &mut DeviceHandle) -> bool {
    vm.deo::<0b001>(dev.0, 0).is_some()
}

#[no_mangle]
extern "C" fn deo_r_entry(vm: &mut Uxn, dev: &mut DeviceHandle) -> bool {
    vm.deo::<0b010>(dev.0, 0).is_some()
}

// и так далее, 16 функций для всех вариаций DEI / DEO

Полный путь функции выглядит примерно так:

Побеждаем компилятор в скорости при помощи ассемблера - 4

Со стороны ассемблера есть один тонкий момент: во время обычной обработки опкодов мы храним значения данных и индекса стека возвратов в x1 и x3 (оставляя исходные значения в &mut Uxn неизменными). Нам нужно записать эти регистры обратно в соответствующие адреса памяти в &mut Uxn до вызова функции, ожидающей, что эти значения будут корректными.

Вот ассемблерный код для вызова наших функций-оболочек:

.global _DEI
_DEI:
    ; Нам нужно записать указатели индекса стека обратно в &mut Uxn
    ldp x11, x12, [sp, 0x10] ; восстанавливаем указатели индекса стека
    strb w1, [x11]   ; изменяем указатель индекса стека
    strb w3, [x12]   ; изменяем указатель индекса стека возврата

    ; Мы используем сохранённые вызванной стороной регистры, так что нужно создать их резервные копии
    stp x0, x1, [sp, #0x20] ; сохраняем состояние регистра
    stp x2, x3, [sp, #0x30]
    stp x5, x4, [sp, #0x40]
    stp x6, x7, [sp, #0x50]
    str x8,     [sp, #0x60]

    ; подготавливаем наши аргументы, а затем вызываем функцию-оболочку:
    mov x0, x6 ; x0 = указатель Uxn
    mov x1, x7 ; x1 = указатель DeviceHandle
    bl _dei_entry

    ldp x0, x1, [sp, #0x20] ; восстанавливаем состояние регистра
    ldp x2, x3, [sp, #0x30]
    ldp x5, x4, [sp, #0x40]
    ldp x6, x7, [sp, #0x50]
    ldr x8,     [sp, #0x60]

    ; Операция DEO могла изменить указатели стека, так что мы обновляем их 
    ldp x11, x12, [sp, 0x10]
    ldrb w1, [x11]  ; обновляем указатель индекса стека
    ldrb w3, [x12]  ; обновляем указатель индекса стека возвратов
    next

▍ Производительность

Для тестирования производительности интерпретатора я использовал две рабочие нагрузки, активно задействующие CPU:

  • модифицированную fib.tal, выводящую первые 35 чисел ряда Фибоначчи;
  • mandelbrot.tal со значением %SCALE, равным #0020 (рендеринг изображения 672 × 512)

Обе эти программы выполняют все свои вычисления при запуске, поэтому я добавил оснастку для вывода времени, проведённого в векторе входа (по адресу 0x100).

Здесь тестировались четыре разные реализации:

  • Эталонная реализация uxnemu, выполняемая нативно на моём ноутбуке.
  • Исходный интерпретатор raven-uxn, выполняемый нативно на моём ноутбуке.
  • Оптимизированный интерпретатор raven-uxn (написан вручную на ассемблере), выполняемый нативно на моём ноутбуке.
  • Исходный интерпретатор raven-uxn, выполняемый в браузере (скомпилирован в WebAsembly).

А вот те показатели производительности, которых вы ждали:

Интерпретатор Целевая платформа Fibonacci Mandelbrot
uxnemu (эталонный) AArch64 1,57 с 2,03 с
raven-uxn (исходный) AArch64 1,38 с 1,56 с
raven-uxn (ассемблерный) AArch64 1,00 с 1,10 с
raven-uxn (исходный) wasm32 2,54 с 2,82 с

Заметны три чётких тренда:

  • Исходный интерпретатор raven-uxn (написанный на безопасном Rust) быстрее, чем эталонная реализация; мы уже знали это из предыдущей статьи.
  • Ассемблерная реализация примерно на 30% быстрее исходной!
  • По сравнению с исходной реализацией WebAssembly добавляет замедление примерно в 1,8 раза.

▍ Тестирование

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

Мы можем легко протестировать последнее, изменив макрос next:

.macro next
    b next_dispatch
.endm
next_dispatch:
    ldrb w9, [x4, x5]
    add x5, x5, #1
    and x5, x5, #0xffff
    ldr x10, [x8, x9, lsl #3]
    br x10

Добавив эти новые результаты в таблицу (с обозначением «ассемблерный*»), я увидел следующее:

Интерпретатор Целевая платформа Fibonacci Mandelbrot
raven-uxn (исходный) AArch64 1,38 с 1,56 с
raven-uxn (ассемблерный) AArch64 1,00 с 1,10 с
raven-uxn (ассемблерный*) AArch64 1,34 с 1.41 с

Централизованная диспетчеризация сильно снижает скорость, почти до скорости исходного интерпретатора!

Всё это показывает, что не стоит дразнить алгоритм предсказания ветвления.

▍ То, что не сработало

Я провёл несколько экспериментов, никак не ускоривших работу:

  • Расширил ОЗУ так, чтобы в ней хранились и пользовательские байты, и цели для перехода (то есть превратив ОЗУ в [u64; 65536]). Пользовательский байт хранится в битах 48-54 указателя, поскольку они не используются, и я добавил маскирование + сдвиг в зависимости от того, используем ли мы компонент данных или указателя. Это было существенно медленнее, вероятно, из-за меньшего удобства для кэширования (512 КиБ вместо 64 КиБ + 1 КиБ таблицы переходов).
  • Сделал все реализации опкодов одного размера (заполняя опкоды до самой большой реализации опкода при помощи .balign 256), а затем полностью избавился от таблицы переходов. Это тоже было медленнее и тоже, вероятно, из-за неудобства для кэша: общий размер реализаций опкодов увеличился с 16,6 КиБ до 64 КиБ.

▍ Заключение

К моей радости, написание интерпретатора на ассемблере оказалось и увлекательным, и полезным для производительности процессом!

Вот стратегии, которые можно использовать для получения схожего уровня производительности в языках высокого уровня: использование вычисленных goto и Massey Meta Machine.

Однако ни одну из них невозможно применить в Rust; цитата из великолепной статьи:

На данный момент не существует портируемого способа создания вычисленных goto или оптимизации хвостовых вызовов в скомпилированном из Rust машинном коде.

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

Весь код проекта выложен на Github с фичей native. Исполняемые файлы uxn-cli и uxn-gui принимают флаг --native, позволяющий выбирать бэкенд ассемблерного интерпретатора.

Автор: ru_vds

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js