Привет!
Заверните обычный 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% при первом пополнении.
