Чудеса nightly, часть 1: на чём тайком держится stable Rust

Привет!

Заверните обычный File в структуру из одного поля и пробросьте чтение внутрь. Пара строк, логика не поменялась. А теперь скопируйте через io::copy файл на 64 мегабайта: голый File справлялся за два системных вызова, обёртка сделает больше шестнадцати тысяч.

Ошибки в коде нет, вы просто выпали из специализации, которой в стабильном Rust официально не существует. Зато в стандартной библиотеке на ней висит больше сотни функций, и такая фича там не одна: даже NonNull хранит адрес в типе, который на stable объявить нельзя.

Чем глубже копаешь, тем веселее. Та же специализация ускоряет collect и умеет заставить код без единого unsafe читать освобождённую память, а итератор, написанный как обычная функция, превращается в идеальный ассемблер и почему-то отказывается векторизоваться. Материала набралось на четыре-пять статей, это первая, и в ней пять фич: gen-блоки, pattern types, специализация, become и #[loop_match].

Итератор, который пишется как функция

Кто хоть раз писал Iterator руками для чего-то сложнее счётчика, помнит этот квест. Локальные переменные переезжают в поля структуры, цикл рассыпается на флаги, а next при каждом вызове вспоминает, где мы остановились в прошлый раз. Через полгода никто уже и не скажет, какой флаг за что отвечает.

gen-блок заберет всю эту возню себе. Слово gen зарезервировали в редакции 2024, так что без --edition 2024 пример не соберётся:

#![feature(gen_blocks)]

gen fn evens(limit: u32) -> u32 {
    let mut i = 0;
    while i < limit {
        if i % 2 == 0 {
            yield i;
        }
        i += 1;
    }
}

Тип u32 после стрелки описывает то, что уходит через yield, а наружу функция отдаёт impl Iterator<Item = u32>. evens(5) выдаёт 0, 2 и 4, дальше None сколько ни зови, и никакой паники.

С этим impl Iterator связаны две неприятные штуки.

Сам gen-блок реализует FusedIterator: gen { yield 1u32; } спокойно проходит в функцию с ограничением I: FusedIterator. Отдайте туда же evens(3) и получите E0277, потому что непрозрачный тип из gen fn обещает только Iterator, а про остальные трейты вызывающий код ничего не знает.

Вторая проблема уже в памяти. size_hint у такого итератора всегда (0, None), компилятор не пытается угадать, сколько раз сработает yield. Поэтому collect из evens(2000) выдаёт вектор на 1000 элементов с capacity 1024 и серией переаллокаций по дороге, а (0..2000).step_by(2).collect() сразу выделяет ровно 1000. Если размер известен заранее, палочка выручалочка тут Vec::with_capacity и extend.

Откуда растут такие ограничения, видно, только если заглянуть внутрь.

Что прячется внутри gen-блока

Компилятор превращает блок в корутину, а корутину в перечисление, где на каждую точку yield заведён свой вариант. Какие переменные туда попадут, он решает сам, и подсмотреть это решение можно флагом -Zprint-type-sizes. Возьмём итератор с массивом на килобайт, который нужен только до первого yield:

#![feature(gen_blocks)]

pub fn before_only(n: u64) -> impl Iterator<Item = u64> {
    gen move {
        let big = [7u8; 1024];
        let s: u64 = big.iter().map(|&b| b as u64).sum();
        yield s;
        let mut acc = 0u64;
        for i in 0..n {
            acc += i;
            yield acc;
        }
    }
}

Вывод компилятора, из которого я выкинул строки с захваченным n (оно лежит в каждом варианте):

print-type-size type: `{gen block@sizes.rs:4:5: 4:13}`: 40 bytes, alignment: 8 bytes
print-type-size     discriminant: 1 bytes
print-type-size     variant `Unresumed`: 8 bytes
print-type-size     variant `Suspend0`: 8 bytes
print-type-size     variant `Suspend1`: 32 bytes
print-type-size         local `.acc`: 8 bytes
print-type-size         local `.iter`: 16 bytes
print-type-size     variant `Returned`: 8 bytes
print-type-size     variant `Panicked`: 8 bytes

В Unresumed блок сидит, пока его ни разу не запускали. Suspend0 и Suspend1 соответствуют двум yield, и во втором сохраняются счётчик acc и сам диапазон 0..n на 16 байт. Returned и Panicked отмечают конец и падение. Массива в раскладке нет вовсе, итератор весит 40 байт.

Теперь поменяем в цикле одну строку на acc += i + big[i as usize % 1024] as u64. Массив начинает жить через yield, попадает и в Suspend0, и в Suspend1, и итератор раздувается до 1064 байт. Тысяча таких в векторе займёт мегабайт вместо сорока килобайт, и всё из-за одного обращения к массиву.

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

gen {
    let v = vec![10, 20, 30];
    for x in &v {
        yield *x;
    }
}

error[E0626]: borrow may still be in use when `gen` block yields
  |
  |         for x in &v {
  |                  ^^
  |             yield *x;
  |             -------- possible yield occurs here

Метод next принимает &mut self без Pin. Значит, итератор имеют право передвинуть в памяти между вызовами, и ссылка из одного поля автомата на другое после переезда смотрела бы на старый адрес. У async-блоков этой беды нет, потому что Future::poll получает Pin<&mut Self> и сдвинуть будущее после первого опроса уже нельзя. В gen-блоке исправляется for x in v забирает вектор по значнию и ничего не заимствует, а данные снаружи блока можно одалживать через gen move.

Вариант Panicked в раскладке тоже не для красоты. Если блок упал, вы поймали панику через catch_unwind и снова позвали next, прилетит вторая с текстом «gen fn should just keep returning None after panicking». Сообщение обещает None, а вызов падает. Константа с этим текстом лежит в core/src/panicking.rs, можно сходить полюбоваться.

Раз автомат устроен так явно, оптимизатору придётся с ним повозиться. Он справляется, хоть и не до конца.

Автомат исчез, векторизация тоже

Дальше начинается странное, если сравнить две суммы элементов, кратных трём:

#![feature(gen_blocks)]

#[unsafe(no_mangle)]
pub fn sum_gen(v: &[u32]) -> u32 {
    let it = gen {
        for &x in v {
            if x % 3 == 0 {
                yield x;
            }
        }
    };
    it.sum()
}

#[unsafe(no_mangle)]
pub fn sum_iter(v: &[u32]) -> u32 {
    v.iter().copied().filter(|x| x % 3 == 0).sum()
}

Собираем с --crate-type=lib -C opt-level=3 -C llvm-args=-x86-asm-syntax=intel --emit asm и смотрим на gen-версию:

sum_gen:
    test   rsi, rsi
    je     .LBB0_1
    lea    rcx, [rdi + 4*rsi]
    xor    edx, edx
    mov    rsi, rcx
    xor    eax, eax
.LBB0_4:
    mov    r8d, dword ptr [rdi]
    add    rdi, 4
    imul   r9d, r8d, -1431655765
    cmp    r9d, 1431655766
    cmovae r8d, edx
    cmovb  rsi, rcx
    add    eax, r8d
    cmp    rdi, rsi
    jne    .LBB0_4
    ret

От автомата не осталось ничего. Ни дискриминанта, ни вызовов, цикл без единого ветвления: imul на магическую константу проверяет делимость на 3, cmovae обнуляет неподходящий элемент. Выглядит идеально, пока не откроешь sum_iter. Там код втрое длиннее и почти весь на регистрах xmm. С -O картина та же, и оптимизатор сам объяснит, в чём дело, если попросить отчёт:

rustc +nightly --edition 2024 --crate-type=lib -O \
    -C remark=loop-vectorize -C debuginfo=1 --emit obj -o /dev/null sum.rs

Для gen-версии в отчёте «loop not vectorized: could not determine number of loop iterations» и «Cannot vectorize uncountable loop». Для итераторов «vectorized loop (vectorization width: 4, interleaved count: 2)», т.е по четыре числа за раз и ещё разворот цикла вдвое. gen-блок идёт по одному.

Подозреваю строчку cmovb rsi, rcx. Она условно записывает в указатель конца цикла то же значение, которое там уже лежит. Процессору всё равно, а LLVM видит, что граница меняется внутри тела, и считать итерации отказывается. По-моему, это след того, как автомат выходил из цикла на каждом yield и заходил обратно, хотя по IR я эту версию до конца не проследил.

Но хоронить gen-блоки еще рано. Без фильтра, на gen { for &x in v { yield x.wrapping_mul(3); } }.sum(), векторизация на месте, и ассемблер почти совпадает с v.iter().map(...). Вариант с while по индексу и тем же фильтром тоже векторизуется. Ломается конкретная связка из цикла по итератору среза и условного yield, так что флаг -C remark=loop-vectorize для горячих циклов на gen-блоках лучше держать под рукой.

LLVM здесь не хватило знания о цикле. Следующая фича про обратное: как подсунуть компилятору знание о значениях, до которого он сам не дойдёт.

Число, из которого вырезали кусок

В исходниках stable лежит модуль core::num::niche_types. Если поставить исходники через rustup component add rust-src и заглянуть в вызовы макроса define_valid_range_type!, попадутся вот такие строчки:

pub struct Nanoseconds(u32 is 0..=999_999_999);
pub struct NonZeroU32Inner(u32 is 1..);
pub struct NonZeroI32Inner(i32 is ..0 | 1..);
pub struct UsizeNoHighBit(usize is 0..=HALF_USIZE);
pub struct I32NotAllOnes(i32 is ..-1 | 0..);
pub struct NonZeroCharInner(char is '\u{1}' ..= '\u{10ffff}');

Макрос превращает каждую в struct $name(pattern_type!($int is $pat)), то есть в число, у которого часть значений запрещена прямо в типе. Nanoseconds сидит внутри Duration, UsizeNoHighBit служит ёмкостью RawVec, через I32NotAllOnes описан дескриптор в OwnedFd, а NonNull хранит поле pattern_type!(*const T is !null). Весь модуль закрыт фичей temporary_niche_types, и в пояснении к ней честно написано, что это для внутренностей core, alloc и std, пока pattern types не дозреют.

Раньше ту же задачу решали атрибуты rustc_layout_scalar_valid_range_start и _end на обычной структуре. Из библиотеки их вычистили до последнего, а свежий nightly на попытку их повесить отвечает «cannot find attribute». Компилятор про них уже забыл.

У себя фичу можно попробовать, хотя компилятор сразу даёт понять, что лезть сюда так то не стоило:

#![feature(pattern_types, pattern_type_macro)]
use std::pat::pattern_type;

type Percent = pattern_type!(u8 is 0..=100);

fn main() {
    let ok: Percent = 42;
    let bad: Percent = 150;
}

warning: the feature `pattern_types` is internal to the compiler or standard library
  = note: using it is strongly discouraged

error[E0308]: mismatched types
  |     let bad: Percent = 150;
  |              -------   ^^^ expected `pattern_type!(u8 is 0..=100)`, found integer

Литерал проверяется при компиляции, 42 проходит, 150 нет. С рантайм-значениями повеселее. Приведения через as нет, компилятор отвечает E0605, неявного превращения Percent обратно в u8 тоже нет. Входить в тип и выходить из него приходится через transmute, и std делает ровно то же. Метод new у типов из niche_types сначала проверяет число через if let $pat = val и потом зовёт transmute, а as_inner достаёт значение тоже через transmute с комментарием, что обращение к .0 давало регрессии производительности. Для своего типа это выглядит так:

fn percent(v: u8) -> Option<Percent> {
    if let 0..=100 = v {
        // SAFETY: диапазон только что проверен
        Some(unsafe { std::mem::transmute::<u8, Percent>(v) })
    } else {
        None
    }
}

fn value(p: Percent) -> u8 {
    unsafe { std::mem::transmute::<Percent, u8>(p) }
}

percent(42).map(value) возвращает Some(42), percent(150) возвращает None. Суеты много, так что посмотрим, что компилятор даёт за неё взамен.

Куда уходят запрещённые значения

Первым делом он прячет в дырку диапазона дискриминант Option. Значения в комментариях сняты с запуска:

use std::mem::{size_of, transmute};
use std::os::fd::OwnedFd;

println!("{}", size_of::<Option<Percent>>());                  // 1
let none: u8 = unsafe { transmute(None::<Percent>) };          // 0xff
let inner: u8 = unsafe { transmute(Some(None::<Percent>)) };   // 0xff
let outer: u8 = unsafe { transmute(None::<Option<Percent>>) }; // 0xfe
println!("{}", size_of::<Option<OwnedFd>>());                  // 4
let fd: i32 = unsafe { transmute(None::<OwnedFd>) };           // -1

Option<Percent> занимает один байт, None кодируется как 0xff. Вложенный Option<Option<Percent>> тоже влезает в байт: внутренний None занял 0xff, внешнему досталось 0xfe. Каждый уровень съедает одно свободное значение, а у Percent их 155. Option<OwnedFd> весит 4 байта, и его None в битах равен -1, та самая договорённость, которой C обозначает «дескриптора нет». Option<Duration> занимает те же 16 байт, что и сам Duration, дискриминант уехал в наносекунды.

Второе интереснее, потому что знание о диапазоне доезжает до ассемблера. Две функции читают таблицу на 101 элемент:

#[unsafe(no_mangle)]
pub fn lookup_raw(table: &[u8; 101], i: u8) -> u8 {
    table[i as usize]
}

#[unsafe(no_mangle)]
pub fn lookup_pat(table: &[u8; 101], p: Percent) -> u8 {
    let i: u8 = unsafe { std::mem::transmute(p) };
    table[i as usize]
}

В LLVM IR параметр второй функции выглядит как i8 noundef range(i8 0, 101) %p. С -O это превращается в такой ассемблер:

lookup_raw:
    mov    rax, rdi
    movzx  edi, sil
    cmp    dil, 100
    ja     .LBB1_2              ; дальше вызов panic_bounds_check
    movzx  eax, byte ptr [rax + rdi]
    ret

lookup_pat:
    movzx  eax, sil
    movzx  eax, byte ptr [rdi + rax]
    ret

У lookup_raw на каждое обращение сравнение и ветка на панику, у lookup_pat два movzx и возврат. Проверка никуда не делась, она тупо переехала туда, где число впервые становится Percent, и выполняется там один раз. Если значение гуляет через десяток функций и в каждой индексирует таблицу, экономия набегает в каждой.

Мой любимый момент тут связан с NonZeroI32Inner(i32 is ..0 | 1..). Это or-паттерн, два диапазона с дыркой на нуле, а раскладка типа умеет хранить только один допустимый диапазон. Как компилятор выкручивается, видно через отладочный атрибут:

#![feature(pattern_types, pattern_type_macro, rustc_attrs,
           const_trait_impl, pattern_type_range_trait)]
#![allow(internal_features)]
use std::pat::pattern_type;

#[rustc_dump_layout(debug)]
type NonZeroI32ish = pattern_type!(i32 is ..0 | 1..);

fn main() {}

error: layout_of(pattern_type!(i32 is (i32::MIN..=-1 | 1..))) = Layout {
           size: Size(4 bytes),
           ...
           largest_niche: Some(
               ...
                   valid_range: 1..=4294967295,

Сначала ..0 переписан в i32::MIN..=-1, потом оба куска склеены. Всё решают биты: отрицательные числа занимают верхнюю половину, от 0x80000000 до 0xFFFFFFFF, положительные лежат снизу, от 1 до 0x7FFFFFFF, и вместе это один отрезок 1..=4294967295. У беззнаковых такого фокуса нет, и компилятор пока пускает or-паттерны только для знаковых типов, о чём прямо пишет в ошибке. Лишние флаги const_trait_impl и pattern_type_range_trait понадобились из-за невключённой границы: ..0 компилятор пересчитывает константным вызовом sub_one, а без флагов такой вызов в константе запрещён. С 0..=100 их можно не ставить.

По-моему, из всех пяти фич эта самая недооценённая, ведь снаружи её не видно совсем, а пользуется ей любая программа, где есть Vec или Duration.

Специализация, которой нет

Полную специализацию компилятор встречает без энтузиазма:

warning: the feature `specialization` is incomplete and may not be safe to use and/or cause compiler crashes
  = help: consider using `min_specialization` instead, which is more stable and complete

А в lib.rs у core, alloc и std спокойно стоит #![feature(min_specialization)]. Сколько на ней держится, считается одной командой прямо в исходниках:

cd "$(rustc +stable --print sysroot)/lib/rustlib/src/rust/library"
grep -rEn '^\s*[^/]*\bdefault fn\b' core/src alloc/src std/src --include=*.rs | wc -l

Выходит 126. Вместе с default unsafe fn и default const fn набегает 136: 92 в core, 34 в alloc и 10 в std. Слово default помечает реализацию, которую разрешено перекрыть более узкой, и компилятор при выборе берёт самую узкую из подходящих.

Заметнее всего это в collect. Когда цепочка начинается с Vec::into_iter и заканчивается сбором обратно в Vec, специализация складывает результат прямо в старый буфер:

fn main() {
    let v: Vec<u64> = (0..1_000_000).collect();
    let p = v.as_ptr();
    let small: Vec<u64> = v.into_iter().filter(|x| x % 100_000 == 0).collect();
    println!(
        "len={} cap={} тот же буфер: {}",
        small.len(), small.capacity(), small.as_ptr() == p
    );
}

Печатается len=10 cap=1000000 тот же буфер: true. Десять элементов, буфер на миллион, и восемь мегабайт теперь стерегут восемьдесят байт данных. Пока вектор жив, память никуда не вернётся, поэтому если такой результат уезжает в долгоживущую структуру, без shrink_to_fit не обойтись.

Стоит добавить по дороге .map(|x| x as u32), и буфер уже новый, ёмкость 16. Условие зашито в функцию in_place_collectible из alloc/src/vec/in_place_collect.rs: выравнивание исходного и целевого типа обязано совпадать, потому что перевыделение со сменой выравнивания многие системные аллокаторы делают плохо. Поэтому даже (u32, u32) на месте не собирается, хотя размер у кортежа те же 8 байт: выравнивание у него 4, у u64 8. Кстати, и vec![0; n] работает через специализацию, трейт IsZero позволяет попросить у аллокатора сразу обнулённую память.

С collect специализация просто экономит аллокацию. С io::copy она решает, пойдут ли данные через ядро напрямую.

Как обёртка из двух строк ломает io::copy

В std/src/sys/io/kernel_copy/linux.rs лежит такая пара реализаций:

impl<R: Read + ?Sized, W: Write + ?Sized> SpecCopy for Copier<'_, '_, R, W> {
    default fn copy(self) -> Result<CopyState> {
        Ok(CopyState::Fallback(0))
    }
}

impl<R: CopyRead, W: CopyWrite> SpecCopy for Copier<'_, '_, R, W> {
    fn copy(self) -> Result<CopyState> {
        // copy_file_range, sendfile, splice
    }
}

CopyRead и CopyWrite реализованы для File, TcpStream, UnixStream, пайпов и потоков дочернего процесса. Всем остальным достаётся default fn, который отвечает Fallback, и io::copy уходит в обычный цикл read и write с буфером на 8 КиБ. Копирую файл на 64 МиБ двумя способами: напрямую через io::copy(&mut File, &mut File) и через обёртку, которая только пробрасывает чтение:

struct Wrapped(File);

impl Read for Wrapped {
    fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
        self.0.read(buf)
    }
}

$ strace -f -c -e trace=read,write,copy_file_range ./copy file
100.00    0.148380       74190         2           copy_file_range

$ strace -f -c -e trace=read,write,copy_file_range ./copy wrapped
 65.55    0.037381           4      8195           write
 34.45    0.019649           2      8198           read

В первом случае данные не поднимаются в пространство пользователя, ядро переносит их двумя вызовами copy_file_range. Во втором выходит 8192 пары read и write по 8 КиБ, а оставшиеся несколько вызовов достались загрузчику и выводу в консоль. Wrapped ничего не меняет в логике, но приватный CopyRead для него не реализован, и реализовать его снаружи нельзя. Если своя обёртка над файлом всё-таки нужна, в io::copy лучше отдавать внутренний &mut wrapped.0.

Такая полезная вещь сидит под замком неспроста, и причина в десятке строк.

Десять строк до use-after-free

Нужна обобщённая реализация трейта для всех типов и более узкая для &'static str:

#![feature(specialization)]
use std::sync::Mutex;

static KEPT: Mutex<Vec<&'static str>> = Mutex::new(Vec::new());

trait Remember { fn remember(self); }
impl<T> Remember for T { default fn remember(self) {} }
impl Remember for &'static str {
    fn remember(self) { KEPT.lock().unwrap().push(self); }
}

fn pass_along<T>(value: T) { value.remember(); }

fn main() {
    {
        let temp = String::from("временная строка, которой скоро не станет");
        pass_along(temp.as_str());
    }
    let _noise = String::from("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX");
    let kept = KEPT.lock().unwrap();
    println!("len = {}, bytes = {:?}", kept[0].len(), &kept[0].as_bytes()[..16]);
}

len = 76, bytes = [67, 8, 205, 86, 5, 0, 0, 0, 250, 142, 141, 163, 93, 137, 1, 2]

Строка на 76 байт превратилась в мусор, при каждом запуске разный. Если печатать не байты, а саму строку через {:?}, форматтер падает с «start byte index 8 is not a char boundary», гарантия UTF-8 у str тоже улетела. cargo +nightly miri run выносит однозначный вердикт:

error: Undefined Behavior: constructing invalid value of type &str: encountered a dangling reference (use-after-free)

Виноваты времена жизни, которые существуют только до проверки заимствований. Внутри pass_along про T ничего не известно, так что проверять там нечего. А когда компилятор потом мономорфизирует pass_along::<&str> и выбирает реализацию, 'static и короткая ссылка для него один и тот же тип &str. Он честно берёт самую узкую реализацию, ту, что складывает ссылку в статический вектор, и ссылка на умершую строку переживает её.

min_specialization закрывает дыру грубовато, но вроде как надёжно. Тот же код с ней не собирается:

error: cannot specialize on `'static` lifetime
  --> minspec.rs:15:1
   |
15 | impl Remember for &'static str {

Заодно запрещена специализация по произвольному трейту: impl<T: Copy> Describe for T поверх общей реализации получает «cannot specialize on trait Copy». Разрешены конкретные типы и трейты с внутренними атрибутами #[rustc_specialization_trait] или #[rustc_unsafe_specialization_marker]. В std так размечены TrustedLen, InPlaceIterable, CopyRead, IsZero и другие служебные трейты, а снаружи такой атрибут не повесить, так что своему коду от min_specialization толку немного.

Специализация выбирает код ещё до запуска программы. Две последние фичи будут про то, как код прыгает, пока программа работает, и первая отменяет самое привычное, что умеет функция: возвращаться.

become: вызов без обратного билета

Хвостовая рекурсия в двух вариантах:

#![feature(explicit_tail_calls)]
#![allow(incomplete_features)]

fn sum_plain(n: u64, acc: u64) -> u64 {
    if n == 0 {
        return acc;
    }
    sum_plain(n - 1, acc + n)
}

fn sum_become(n: u64, acc: u64) -> u64 {
    if n == 0 {
        return acc;
    }
    become sum_become(n - 1, acc + n)
}

С -C opt-level=0 на десяти миллионах sum_plain падает с «thread 'main' has overflowed its stack», а sum_become спокойно выдаёт 50000005000000. В LLVM IR вызов помечен musttail, и для LLVM это обязательство: если хвостовой вызов не выйдет, сборка упадёт. Конец функции в ассемблере даже без оптимизаций выглядит так:

    mov    rsi, qword ptr [rsp + 8]
    mov    rdi, qword ptr [rsp + 16]
    add    rsp, 40
    jmp    _RNvCsaKIyyY54WBn_4tail10sum_become

Функция освобождает свой кадр через add rsp, 40 и только потом прыгает в себя. Стек не растёт, сколько бы раз это ни повторилось.

Пример, правда, слегка жульничает: с -O обычная sum_plain тоже досчитывает до конца, LLVM и без подсказок превращает такую рекурсию в цикл. Интересно становится, когда в функции живёт переменная с деструктором:

struct Loud(u64);

impl Drop for Loud {
    fn drop(&mut self) {
        if self.0 < 3 { println!("drop {}", self.0); }
    }
}

fn plain(n: u64) -> u64 {
    let _guard = Loud(n);
    if n == 0 { return 0; }
    if n < 3 { println!("call {}", n - 1); }
    plain(n - 1)
}

fn tail(n: u64) -> u64 {
    let _guard = Loud(n);
    if n == 0 { return 0; }
    if n < 3 { println!("call {}", n - 1); }
    become tail(n - 1)
}

Теперь даже с -O на десяти миллионах plain снова упирается в конец стека, а tail доходит до финиша. Обычный вызов обязан вернуться, чтобы деструктор _guard отработал после него, поэтому кадр живёт до самого конца, и оптимизатору выкидывать нечего. become меняет порядок, и на n = 2 это видно глазами. plain печатает call 1, call 0, а потом пачкой drop 0, drop 1, drop 2. У tail выходит call 1, drop 2, call 0, drop 1, drop 0: деструкторы срабатывают до прыжка.

Из этого порядка вытекают оба ограничения. Сигнатуры вызывающей и вызываемой функций обязаны совпадать:

error: mismatched signatures
  = note: `become` requires caller and callee to have matching signatures
  = note: caller signature: `fn(u64) -> u64`
  = note: callee signature: `fn(u64, u64) -> u64`

И ссылку на локальную переменную передать нельзя, к моменту прыжка её уже нет. become len_of(&owned) ловится обычной E0597 с пояснением, что owned уничтожена, пока её ещё заимствуют.

Одинаковые сигнатуры звучат как какая-то неудобная фигня, но интерпретатору это только на руку, у него все обработчики опкодов и так принимают одно и то же.

Интерпретатор, где каждый опкод прыгает сам

Начнём с привычного: цикл, match по опкоду, три регистра.

const HALT: u8 = 0; const DEC: u8 = 1; const ADD: u8 = 2;
const MIX: u8 = 3;  const INC: u8 = 4; const JNZ: u8 = 5;

#[derive(Clone, Copy)]
struct Reg { a: u64, b: u64, c: u64 }

fn run_match(code: &[u8], mut r: Reg) -> Reg {
    let mut pc = 0;
    loop {
        match code[pc] {
            DEC => { r.a -= 1; pc += 1; }
            ADD => { r.b = r.b.wrapping_add(r.a); pc += 1; }
            MIX => { r.b ^= r.b << 7; r.b ^= r.b >> 9; pc += 1; }
            INC => { r.c += 1; pc += 1; }
            JNZ => { pc = if r.a != 0 { 0 } else { pc + 1 }; }
            _ => return r,
        }
    }
}

На become та же машина превращается в таблицу функций, где каждый обработчик сам достаёт следующий опкод и прыгает дальше. Такую схему называют шитым кодом:

type Op = fn(&[u8], usize, Reg) -> Reg;
static OPS: [Op; 6] = [op_halt, op_dec, op_add, op_mix, op_inc, op_jnz];

#[inline(always)]
fn next(code: &[u8], pc: usize, r: Reg) -> Reg {
    become OPS[code[pc] as usize](code, pc, r)
}

fn op_add(code: &[u8], pc: usize, mut r: Reg) -> Reg {
    r.b = r.b.wrapping_add(r.a);
    become next(code, pc + 1, r)
}

fn op_jnz(code: &[u8], pc: usize, r: Reg) -> Reg {
    let to = if r.a != 0 { 0 } else { pc + 1 };
    become next(code, to, r)
}
// op_halt, op_dec, op_mix и op_inc устроены так же

Программа [DEC, ADD, INC, MIX, ADD, JNZ, HALT] с a = 50_000_000 делает 300 миллионов переходов между обработчиками, регистры в конце сверяются через assert_eq!. С -O у меня цикл с match отработал за 500–540 мс, шитый код за 280–285.

Ассемблер показывает, чем они различаются по форме. В run_match LLVM строит таблицу переходов, и все пять опкодов уходят через одну косвенную ветку jmp r14, куда управление возвращается после каждого обработчика. У шитого кода косвенная ветка своя в конце каждого обработчика:

op_add:
    push   rax
    mov    rax, qword ptr [r8]
    add    qword ptr [r8 + 8], rax
    inc    rcx
    cmp    rcx, rdx
    jae    .LBB7_3              ; выход за code
    movzx  eax, byte ptr [rsi + rcx]
    cmp    rax, 6
    jae    .LBB7_2              ; выход за OPS
    lea    r9, [rip + OPS]
    pop    r10
    jmp    qword ptr [r9 + 8*rax]

У match предсказателю переходов приходится угадывать следующий опкод по истории единственной точки. У шитого кода после DEC на своей ветке почти всегда стоит ADD, и угадывать проще. Разницу во времени я списываю в основном на это, но промахи предсказателя отдельно не мерил, так что это моя трактовка ассемблера. Заодно видно, где лежит ещё запас: в каждом обработчике по две проверки границ, для code[pc] и для индекса в OPS.

В отладочной сборке всё переворачивается. С -C opt-level=0 на пяти миллионах итераций match укладывается в 76 мс, а become-версия тратит 383, почти впятеро дольше.

Шитый код хорош, когда следующий шаг зависит от данных: опкод лежит в code[pc], и заранее его не знает никто. У многих автоматов переходы устроены скромнее, и там хочется другого инструмента.

#[loop_match]: сразу в нужную ветку

Лексер, увидев цифру, точно знает, что дальше состояние «число», и гонять ради этого знания match по кругу обидно. #[loop_match] позволяет это знание передать. Состояние присваивается из блока с меткой, внутри которого стоит match, а #[const_continue] над break с константой велит прыгнуть сразу в нужную ветку:

#![feature(loop_match)]
#![allow(incomplete_features)]

#[derive(Clone, Copy)]
enum S { A, B, C }

#[unsafe(no_mangle)]
pub fn with_lm(mut n: u32) -> u32 {
    let mut acc = 0;
    let mut s = S::A;
    #[loop_match]
    loop {
        s = 'blk: {
            match s {
                S::A => {
                    acc += 1;
                    #[const_continue]
                    break 'blk S::B;
                }
                S::B => {
                    acc *= 3;
                    if n == 0 {
                        #[const_continue]
                        break 'blk S::C;
                    }
                    n -= 1;
                    #[const_continue]
                    break 'blk S::A;
                }
                S::C => return acc,
            }
        }
    }
}

Разницу проще всего увидеть в MIR через --crate-type=lib -C opt-level=0 --emit mir. С атрибутами проверка состояния остаётся только на входе, а переход из S::A в S::B превращается в прямой goto на блок ветки:

bb0: {
    _2 = const 0_u32;
    _3 = S::A;
    _4 = discriminant(_3);
    switchInt(move _4) -> [0: bb4, 1: bb3, 2: bb2, otherwise: bb1];
}

bb5: {
    _2 = move (_5.0: u32);
    _3 = S::B;
    goto -> bb3;
}

В копии без атрибутов каждая ветка бежит в общий блок, а оттуда на новую проверку дискриминанта:

bb11: {
    _3 = move _4;
    goto -> bb1;
}

bb1: {
    _5 = discriminant(_3);
    switchInt(move _5) -> [0: bb5, 1: bb4, 2: bb3, otherwise: bb2];
}

С -O на этом игрушечном автомате вышло так, что он версию с атрибутами LLVM распознал как обычный счётный цикл и склеил по восемь шагов в один:

.LBB0_2:
    imul   eax, eax, 6561
    add    eax, 9840
    add    edx, -8
    jne    .LBB0_2

6561 — это 3 в восьмой степени, а 9840 равно 3 + 9 + … + 6561, то есть восемь применений acc = (acc + 1) * 3 одной формулой. Хвост из остатка по модулю 8 доделывается по шагу. Без атрибутов LLVM выдал цикл на шаг за итерацию, где выход завязан на cmovb и значение n с прошлого прохода. Похожую картину мы видели у gen-блока: оптимизатор не вывел число итераций и дальше не пошёл.

Значение в #[const_continue] обязано быть константой. Если выбрать следующее состояние через if и написать break 'blk next, компилятор скажет «could not determine the target branch for this #[const_continue]» и подскажет, что нужен литерал или мономорфная константа. Поэтому интерпретатору байткода эта штука не поможет, опкод там лежит в данных. Байткод остаётся за become, а loop_match пригодится лексерам, парсерам и декодерам, где переходы известны при компиляции.

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

Размещайте облачную инфраструктуру и масштабируйте сервисы с надежным облачным провайдером Beget.
Эксклюзивно для читателей Хабра мы даем бонус 10% при первом пополнении.