Призывая Божий гнев проклятый Rust

Перевод | Автор оригинала: troubles.md

В этой статье рассказывается об оптимизации размера и производительности std::заимствовать::Cow в Rust. Это требует некоторых базовых знаний программирования на Rust, но не требует каких-либо знаний о низкоуровневых деталях модели компиляции Rust. Позже мы затронем некоторые довольно второстепенные темы, но я объясню их по ходу дела. Оптимизация начнется довольно разумно, но будет продолжать становиться все более отвратительной и проклятой, пока весь ад не вырвется наружу, а сами небеса не станут кроваво-красными от ярости древних.

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

В частности, поговорим об указателях на массивы. В C указатели на массивы такие же, как «обычные» указатели, и не имеют размера или других прикрепленных метаданных. Если вы хотите узнать размер массива в C, вы должны реализовать это самостоятельно. Для строк это обычно реализуется путем завершения строки «контрольным значением», поэтому при итерации по строке вы можете постоянно проверять это значение и выходить. Для других массивов это обычно реализуется путем предоставления некоторых метаданных в качестве дополнительного параметра функции или поля в структуре. Однако для безопасного языка, такого как Rust, это просто не работает. Rust имеет тип &[T], который представляет заимствованный массив, и Box<[T]>, который является собственным массивом. Оба они используют тот же синтаксис, что и «обычные» указатели на один элемент, но дополнительно сохраняют свою длину, используя некоторую магию в самом компиляторе. Вы можете представить себе указатели в Rust, разделенные на два разных типа: указатель на тип размера (указатель на тип, размер которого известен во время компиляции, например & u64, &[u8; 10], &() и т.д.) и указатель на тип без размера (указатель на тип, размер которого известен только во время выполнения, например &[u8], &str или & dyn Trait).

struct Ptr<T>
where
    T: Sized
{
    address: usize,
}

struct Ptr<T>
where
    T: !Sized
{
    address: usize,
    // Rust currently only ever uses a pointer or pointer-sized integer for the fat pointer
    // extra data, but in theory we could have anything here, and it could be more than just
    // the size of a `usize`.
    extra_data: usize,
}

Это означает, что &[T] и Box<[T]> на самом деле являются двумя целыми числами размером с указатель (т.е. 64-битными в 64-битных архитектурах и 32-битными в 32-битных архитектурах), одно для указателя на первый элемент. и еще один для длины массива. Я собираюсь объяснить здесь некоторые основы, чтобы убедиться, что, когда мы начнем использовать темные обряды, чтобы извлекать и изгибать их, вы не потерялись полностью.

Итак, если вы действительно использовали Rust в реальном коде, вы могли заметить, что здесь не упоминается Vec. Box<[T]> не является распространенным типом в Rust, поскольку Vec гораздо более гибок - он позволяет добавлять больше элементов в массив во время выполнения без создания нового массива, тогда как Box<[T]> делает нет. Причина этой разницы в том, что Box<[T]> хранит только количество элементов, и все эти элементы должны быть определены. Vec работает иначе. Он имеет целое число, представляющее объем имеющегося у него места, которое может быть больше, чем количество элементов в Vec. Это означает, что он может выделить дополнительное пространство, которое не содержит определенных элементов, а затем, нажав на него, Vec просто записывает в это пространство, без необходимости выделять целый новый массив. Пока все в порядке, хотя это означает, что Vec, к сожалению, требует три целых числа размером с указатель. Вот краткая справка:

// This is invalid syntax in Rust of course, but it's just an illustration
// Size: 2 * size_of::<usize>()
struct &'a [T] {
    ptr: *const T,
    length: usize,
}

// Size: 2 * size_of::<usize>()
#[no_mangle]
pub fn dyn_as_ref<'a>(cow: &'a CursedCow<'_, dyn Foo>) -> &'a dyn Foo {
    &**cow
}

#[no_mangle]
pub fn dyn_to_cow<'a>(cow: CursedCow<'a, dyn Foo>) -> std::borrow::Cow<'a, dyn Foo> {
    cow.into()
}

#[no_mangle]
pub fn dyn_new_cow(cow: Box<dyn Foo>) -> Option<CursedCow<'static, dyn Foo>> {
    CursedCow::try_owned(cow)
}

#[repr(transparent)]
pub struct Test(u64);

impl ToOwned for Test {
    type Owned = Box<Test>;
    
    fn to_owned(&self) -> Self::Owned {
        Box::new(Test(self.0))
    }
}

#[no_mangle]
pub fn static_new_cow(cow: Box<Test>) -> Option<CursedCow<'static, Test>> {
    CursedCow::try_owned(cow)
}
struct Box<T> {
    ptr: *mut T,
    length: usize
}

// Size: 3 * size_of::<usize>()
struct Vec<T> {
    ptr: *mut T,
    length: usize,
    capacity: usize,
}

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

Итак, есть еще один тип массива, о котором я хочу поговорить, и именно ему будет посвящена остальная часть этой статьи. Этот тип - std::заимствовать::Корова. Мы начнем с обсуждения Cow <[T]> и Cow , хотя Cow является общим и работает с другими типами, о которых мы поговорим позже. Когда дело доходит до реализации, мы в основном будем говорить о Cow <[T]>, поскольку Cow во время выполнения то же самое, что Cow <[u8]> - просто требуется, чтобы некоторые дополнительные инварианты были истинными для байтов, которые он содержит, поэтому он должен быть отдельным типом. Cow <[T]> / Cow может быть &'a [T] / &' a str или Vec / String. Они полезны во многих случаях, но одна большая проблема - в синтаксическом анализе. Один из примеров того, где это может быть полезно, - это если у вас есть синтаксический анализатор для языка программирования, в котором есть строки, которые могут иметь escape-символы. У вас может быть много строк, просто являющихся ссылкой на исходный текст программы:

let a = "Hello, world";
         ^----------^ Take a reference to these characters in the original program text
                      and use it as the string value.

Однако если у вас есть escape-последовательность, вам необходимо выделить новую String, которая является принадлежащим типу строки, размещенной в куче, например Box<[T]> является типом принадлежащего массива. Это запрашивает блок памяти, который не должен следовать тем же правилам времени жизни, что и заимствования - заимствования должны создаваться во внешней области и передаваться внутрь, но собственные указатели могут быть созданы во внутренней области и переданы обратно наружу, и в целом являются гораздо более гибкими за счет подавления некоторых оптимизаций и необходимости выполнения вычислений для их создания и уничтожения. После того, как мы выделили нашу строку, мы записываем версию строки из текста программы в этот буфер, при этом все escape-последовательности превращаются в символы, которые они представляют. Вы можете представить это с помощью Cow - либо Cow::Borrowed (some_string_reference), если строка может быть взята из текста программы без изменений, либо Cow::Owned (some_computed_string), если строку нужно было отредактировать. Итак, сколько байтов занимает Cow <[T]>? Ну, это либо Vec, либо &[T], так что нам нужно достаточно места для Vec, но мы можем повторно использовать часть этого пространства, если это &[T], поскольку он может только быть тем или другим. Vec принимает 3 целых числа размером с указатель, и мы можем повторно использовать 2 из них для &[T], так что нам нужно только 3 целых числа с размером указателя. За исключением того, что нам также нужно хранить «тег», независимо от того, является ли это Vec или &[T]. Это означает, что это 3 целых числа размером с указатель плюс один бит, который может быть либо 0 для Vec, либо 1 для &[T]. Итак, для 64-разрядной версии это будет 3 * 64 + 1 или 193, верно?

К сожалению нет. Вы не можете получить доступ к типу с битовым смещением, только с байтовым смещением. Это означает, что наш размер должен быть кратен 8. Легко, мы округляем его в большую сторону и получаем 7 неиспользуемых бит, верно? Ну все равно нет. Целые числа должны иметь смещение, кратное его размеру. Вы можете сохранить u64 со смещением 8, 16, 24, 32, 40 и т.д., Но не со смещением 9, 10, 11, 12 и т.д. Что ж, легко, мы просто видим, какой самый большой размер целого числа, которое у нас есть в качестве поля нашего типа (в данном случае размер указателя), и округляем наш размер до этого. Итак, теперь размер нашего типа Cow имеет размер 4 указателя, что в два раза больше размера &[T]. Звучит неплохо, но это складывается, и у этого увеличения размера есть и другие недостатки, о которых я расскажу позже. Мы можем подтвердить размер так:

fn main() {
    // Prints 32 on 64-bit systems, which is 4 * 8, where 8 is the number of bytes in a 64-bit
    // integer
    println!("{}", std::mem::size_of::<std::borrow::Cow<[u8]>>());
}

Акт 1. Некоторые разумные оптимизации

Итак, чем мы можем помочь? Ну, есть несколько вещей. Для начала мы можем заметить, что если вектор имеет нулевую емкость, мы можем рассматривать его как пустой массив для большинства операций. Например, векторы с нулевой пропускной способностью не нуждаются в запуске их «кода отбрасывания». Итак, давайте создадим версию Vec, в которой он всегда должен иметь ненулевую емкость.

use std::num::NonZeroUsize;

struct NonZeroCapVec<T> {
    ptr: *mut T,
    len: usize,
    cap: NonZeroUsize,
}

Вы заметите, что у нас все еще может быть вектор без элементов, если в нем есть место для хранения элементов. Итак, теперь мы можем снова выполнить вычисления размера Cow <[T]>, заменив Vec на NonZeroCapVec. Снова мы замечаем, что у нас NonZeroCapVec 3 размера указателя, и мы можем повторно использовать 2 размера указателя из них для хранения среза, за исключением того, что теперь компилятор Rust знает, что он может использовать cap как для тега, так и для емкости, где если cap равен нулю, то он срез, и если он не равен нулю, то это Vec. Это полезный трюк. Мы можем подтвердить, что этот тип теперь имеет 3 размера указателя, например:

enum CowArr<'a, T> {
    Borrowed(&'a [T]),
    Owned(NonZeroCapVec<T>),
}

fn main() {
    println!("{}", std::mem::size_of::<CowArr<u8>>());
}

Но, к сожалению, мы не можем это подтвердить. На момент написания Rust еще не оптимизировал это правильно и по-прежнему сообщает, что размер равен 32. Это прискорбно, но до тех пор мы можем реализовать эту оптимизацию вручную:

struct CowArr<'a, T> {
    // We can use `*mut` to store immutable pointers like `&T`, as long as we never derive an
    // `&mut T` from an `&T`
    ptr: *mut T,
    len: usize,
    cap: usize,
}

Затем, когда нам нужно знать, принадлежит ли стоимость или заимствована, мы можем просто проверить, равен ли кэп нулю.

В Rust есть варианты NonZero для всех целых чисел, а также тип указателя NonNull, который действует так же, как * mut T, за исключением того, что Rust знает, что он не может быть нулевым, он может использовать нулевой указатель в качестве тега перечисления. Хотя Rust не оптимизирует размер перечисления, определенного выше, он будет правильно использовать эти типы NonZero / NonNull в Option, что означает, что Option<Box<[T] >> имеет тот же размер, что и Box<[T]> - он может использовать нулевой указатель для обозначения None. Таким образом, мы можем заставить наш тип CowArr работать так же, как Box<[T]> для Option, и позволить ему использовать нулевой указатель для представления None, например:

use std::ptr::NonNull;

struct CowArr<'a, T> {
    ptr: NonNull<T>,
    len: usize,
    cap: usize,
}

Опять же, мы можем вручную выполнить оптимизацию, где мы проверяем cap на ноль, но теперь Rust будет автоматически использовать нулевой указатель для ptr, чтобы обозначать None, если у нас есть Option<CowArr>.

fn main() {
    // Both of these print 24 on 64-bit systems, and 12 on 32-bit systems
    println!("{}", std::mem::size_of::<CowArr<u8>>());
    println!("{}", std::mem::size_of::<Option<CowArr<u8>>>());
}

Хм, за исключением того, что у нас здесь есть нечто большее, чем просто уменьшение размера. Чтобы объяснить, что я имею в виду, нам нужно поговорить о сборке. Для std::заимствовать::Cow, чтобы сделать as_ref, мы сначала должны проверить, есть ли у нас Cow::Borrowed или Cow::Owned, затем, если у нас есть первое, мы возвращаем заем, который у нас уже есть, и если у нас есть в последнем случае мы выполняем <Vec>::as_ref, что довольно просто - взять ptr и len из вектора и создать срез с этими ptr и len. Остальная часть преобразования выполняется только в системе типов, во время выполнения все, что делает <Vec>::as_ref, - это копирование указателя и длины из одного места в другое. Что ж, с CowArr наш код проще. Заимствованные ptr и len точно такие же, как и собственные ptr и len, с той лишь разницей, что если у нас есть собственное значение, то cap не равно нулю. Это означает, что нам вообще не нужно проверять ограничение, нам нужно только убедиться, что части системы типов преобразования верны - по сути, нам нужно только убедиться, что мы правильно аннотируем время жизни. Затем, когда сборка создана, информация о типе удаляется, и остается реализация as_ref, которая, по сути, не работает. Что ж, в Rust Playground есть функция «Показать сборку», так что давайте воспользуемся ею:

use std::{
    borrow::Cow,
    ptr::NonNull
    marker::PhantomData,
};

pub struct CowArr<'a, T> {
    ptr: NonNull<T>,
    len: usize,
    cap: usize,
    // I omitted this before since it's just to silence the error that `'a` is unused.
    // There is more to `PhantomData` than just silencing errors, but it's out of scope
    // for this article.
    _marker: PhantomData<&'a T>,
}

impl<'a, T> CowArr<'a, T> {
    pub fn as_ref(&self) -> &[T] {
        unsafe { std::slice::from_raw_parts(self.ptr.as_ptr(), self.len) }
    }
}

#[no_mangle]
pub fn cow_as_ref<'a>(a: &'a Cow<'_, [u8]>) -> &'a [u8] {
    a.as_ref()
}

#[no_mangle]
pub fn cowarr_as_ref<'a>(a: &'a CowArr<'_, u8>) -> &'a [u8] {
    a.as_ref()
}

Щелчок по «Показать сборку» (конечно, в режиме выпуска) показывает нам, во что это компилируется. Не волнуйтесь, я знаю, что сборка может быть пугающей, поэтому написал комментарии:

;; For the standard library `Cow`...
cow_as_ref:
    ;; We only need to load the `ptr` once (good!)
    mov   rax, [rdi + 8]
    ;; Unfortunately, we check the tag to load the length
    cmp   [rdi], 1

    ;; This is a pointer to the length if we have a borrowed slice
    lea   rcx, [rdi + 16]

    ;; This is a pointer to the length if we have an owned vector
    lea   rdx, [rdi + 24]
    ;; We use `cmov`, which will overwrite the pointer to the borrowed
    ;; slice's length with the pointer to the owned vector's length if
    ;; our `Cow`'s tag shows that it is owned.
    cmove rcx, rdx

    ;; Then finally, we dereference this pointer-to-length to get the
    ;; actual length
    mov   rdx, [rcx]
    ret

;; For our `CowArr`
cowarr_as_ref:
    ;; We return the `ptr`
    mov rax, [rdi]
    ;; We return the `len`
    mov rdx, [rdi + 8]
    ;; That's it! We're done
    ret

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

Если вы знаете что-нибудь о соглашениях о вызовах, вы можете заметить что-то странное в этом ассемблерном коде. Мы доберемся до этого в свое время, хотя и не раньше, чем перейдем в Запретные миры.

Акт 2: Шаг в запретные миры

Пока все просто. Но мы можем добиться большего, если захотим добавить некоторые ограничения. Мы не можем уменьшить размер ptr, поскольку на самом деле невозможно безопасно делать много предположений о диапазоне значений, которые может принимать указатель, но этого нельзя сказать о len и cap. Если мы находимся в 64-битной системе, использование 64-битной длины и емкости позволяет нам хранить до 18 446 744 073 709 551 615 элементов, и я думаю, мы можем согласиться с тем, что маловероятно, чтобы один массив содержал такое количество элементов в большинстве программы. Фактически, невозможно даже создать такой большой массив для чего-либо, кроме u8 и других однобайтовых (или даже меньших) типов, поскольку у вас закончится адресное пространство задолго до этого, даже не говоря о том, что вы не хватит памяти на вашем компьютере задолго до того, как закончится адресное пространство. Итак, допустим, что len и cap являются 32-битными в 64-битных системах. На данный момент мы проигнорируем 32-битные системы, в 32-битных системах мы могли бы сделать либо len, и cap 16-битными, либо вернуться к реализации, описанной в предыдущем разделе. Этот выбор пока не так важен, поэтому я остановлюсь на 64-битной версии. С 32-битными len и cap мы можем хранить массивы до 4294967295 элементов, что означает, например, что одна строка может иметь длину до 4 Гб. Это ограничение, конечно, нет ничего невероятного, что ваша программа захочет обрабатывать строки большего размера, но стандартная библиотека Cow всегда будет поддерживать это, если вам это нужно. Если вам не нужно такое количество элементов, это дает вам уменьшение размера.

use std::ptr::NonNull;

struct CowArr<'a, T> {
    ptr: NonNull<T>,
    len: u32,
    cap: u32,
}

fn main() {
    // Both of these print 16 on 64-bit systems, and still print 12 on 32-bit systems
    println!("{}", std::mem::size_of::<CowArr<u8>>());
    println!("{}", std::mem::size_of::<Option<CowArr<u8>>>());
}

Если вы похожи на меня, таких 8 байтов достаточно, чтобы заставить вас плакать от радости, но, может быть, мы сможем лучше. Теперь вернемся к тому «кое-чему немного странному», о котором я упоминал выше. Видите ли, когда Rust передает структуру в функцию или возвращает структуру из функции, у него есть несколько способов обработки совместного использования структуры между вызывающим и вызываемым объектами. Если структура «малая» (имеется в виду два поля или меньше, каждое поле помещается в один регистр), тогда структура будет передана как аргумент в регистрах и возвращена в регистрах. В противном случае структура будет записана в стек, а указатель на структуру будет передан вызываемому. Это «что-то немного странное», о котором я упоминал ранее - многие люди предполагают, что Rust всегда передает структуры с более чем одним элементом по указателю, и на самом деле до относительно недавнего времени так и было. Теперь, если вы такой же юрист по правилам, как и я, вы могли бы заметить трюк, который мы можем здесь сделать: хотя структура выше не считается «маленькой» в Rust, мы можем сделать ее версию, которая будет считаться небольшой. . Давайте сделаем это:

use std::ptr::NonNull;

struct CowArr<'a, T> {
    ptr: NonNull<T>,
    len_cap: u64,
}

const LEN_MASK: u64 = std::u32::MAX as u64;
const CAP_MASK: u64 = !LEN_MASK;
// We want the low 32 bits of `len_cap` to be `len`, and the high 32 bits to be `cap`,
// so we need to shift `cap` when reading and writing it.
const CAP_SHIFT: u64 = 32;

impl<'a, T> CowArr<'a, T> {
    pub fn as_ref(&self) -> &[T] {
        unsafe { std::slice::from_raw_parts(self.ptr.as_ptr(), self.len & LEN_MASK) }
    }
}

Итак, конечно, теперь у нас есть структура того же размера, но ее можно передавать в регистрах, что ускоряет вызовы функций, которые ее используют. Круто, но разве это и маскировка длины добавят дополнительных затрат? К счастью для нас, в x86 есть способ бесплатно замаскировать младшие биты числа! Поскольку сборка не типизирована, мы можем просто притвориться, что наше 64-битное число является 32-битным числом, когда мы его используем, и это будет так же, как если бы мы замаскировали младшие 32 бита. Кроме того, нам нужно только выделить пространство стека и передать указатель вызываемому объекту, когда нам действительно нужно передать ссылку на Cow. Если мы передадим собственное значение, оно останется в регистрах. Давайте посмотрим здесь на сборку, чтобы понять, что я имею в виду:

struct CowArr3Fields<'a, T> {
    ptr: NonNull<T>,
    len: u32,
    cap: u32,
}

struct CowArr2Fields<'a, T> {
    ptr: NonNull<T>,
    len_cap: u64,
}

#[no_mangle]
pub fn cow_as_ref<'a>(a: &'a Cow<'_, [u8]>) -> &'a [u8] {
    a.as_ref()
}

#[no_mangle]
pub fn cowarr2fields_as_ref<'a>(a: &'a CowArr2Fields<'_, u8>) -> &'a [u8] {
    a.as_ref()
}
#[no_mangle]
pub fn cowarr3fields_as_ref<'a>(a: &'a CowArr3Fields<'_, u8>) -> &'a [u8] {
    a.as_ref()
}

#[no_mangle]
pub fn cow_noop(a: Cow<'_, [u8]>) -> Cow<'_, [u8]> {
    a
}

#[no_mangle]
pub fn cowarr2fields_noop(a: CowArr2Fields<'_, u8>) -> CowArr2Fields<'_, u8> {
    a
}

#[no_mangle]
pub fn cowarr3fields_noop(a: CowArr3Fields<'_, u8>) -> CowArr3Fields<'_, u8> {
    a
}

cow_as_ref:
    mov   rax, [rdi + 8]
    cmp   [rdi], 1
    lea   rcx, [rdi + 16]
    lea   rdx, [rdi + 24]
    cmove rcx, rdx
    mov   rdx, [rcx]
    ret

cowarr2fields_as_ref:
    mov rax, [rdi]
    mov edx, [rdi + 8]
    ret

cowarr3fields_as_ref:
    mov rax, [rdi]
    mov edx, [rdi + 8]
    ret
    
cow_noop:
    mov    rax, rdi
    movups xmm0, [rsi]
    movups xmm1, [rsi + 16]
    movups [rdi + 16], xmm1
    movups [rdi], xmm0
    ret

cowarr2fields_noop:
    mov rdx, rsi
    mov rax, rdi
    ret

cowarr3fields_noop:
    mov    rax, rdi
    movups xmm0, [rsi]
    movups [rdi], xmm0
    ret

Если вы умеете читать сборку, вы можете видеть, что просто возврат немодифицированной Cow требует некоторой возни с загрузкой и хранением данных для всех структур, кроме CowArr2Fields. Если вы не можете читать сборку, то все, что вам нужно знать, - это [...] квадратные скобки для доступа к памяти, а cowarr2fields_noop - единственная функция, которая в них не нуждается.

Итак, мы максимально оптимизировали массивы Cow. Сейчас мы начинаем использовать Темную Магию и рискуем навлечь на себя гнев Древних (вы знаете, основная команда Rust). Давайте создадим «общую» оптимизированную Cow, которая работает не только с массивами.

Акт 3: прости меня

Так что это все хорошо, но этого недостаточно. По сути, он переопределяет Cow <[T]> с настраиваемым типом, который не работает для Cow - вам нужно написать свою собственную оболочку, возможно, назовите ее CowStr. Затем повторите это для каждого типа. Нет, мы можем лучше. Мы можем сделать CursedCow, который будет одинаково работать с вами, независимо от того, CursedCow <[T]>, CursedCow или даже CursedCow . Именно в этом последнем код действительно начинает наносить ущерб душе. Если вы однажды окажетесь в аду, знайте, что это может быть потому, что вы прочитали эту статью. Думаю, мы оба можем согласиться, что это справедливое и справедливое наказание. В любом случае, прежде чем мы сможем по-настоящему проклясть себя, нам нужно заложить основу и заставить работать гораздо более простую CursedCow <[T]> / CursedCow . Чтобы это сработало, нам понадобится трэйта.

pub unsafe trait Cursed<T: ?Sized>: Borrow<T> {
    fn borrowed(borowed: &T) -> Option<NonNull<T>>;
    fn owned(self) -> Option<NonNull<T>>;
    fn is_owned(ptr: NonNull<T>) -> bool;
    unsafe fn as_ref<'a>(ptr: NonNull<T>) -> &'a T;
    unsafe fn reconstruct(ptr: NonNull<T>) -> Self;
}

Эта трэйта фактически реализована для собственного варианта, в отличие от ToOwned, который реализован для заимствованного варианта. Это связано с тем, что многие типы могут реализовывать ToOwned, указывающий на один и тот же тип (вы можете представить себе обертку среза, в которой ToOwned по-прежнему генерирует Vec), но мы по-прежнему хотим явно выделить Box и другие интеллектуальные указатели. Реализация для собственного варианта означает, что нам не нужно писать какие-либо общие реализации с impl Cursed for T where ..., что позволяет нам обойти проблему перекрывающихся реализаций. Эта трэйта небезопасна, так как требует, чтобы некоторые инварианты были истинными в отношении Borrow, и требует, чтобы заимствованные, принадлежащие и принадлежащие им были согласованы в отношении того, как выглядят заимствованные и принадлежащие указатели. Кроме того, as_ref и reconstruct должны быть небезопасными функциями, потому что в них должны передаваться только действительные указатели.

Итак, давайте сейчас напишем реальную структуру CursedCow. Итак, хотя в предыдущих разделах мы в основном переопределяли систему «толстых указателей» в Rust, мы больше не можем этого делать, если хотим поддерживать больше, чем просто массивы. Мы хотим иметь CursedCow шириной 2 указателя, если T не имеет размера (например, [T], str или dyn Trait), и CursedCow шириной 1 указатель - просто обычный указатель - если T равно размер. Мы делаем это, просто используя NonNull, который является жирным указателем для типов без размера, и позволяя реализации Cursed handle где-то скрывать тег.

// `repr(transparent)` ensures that this struct is always treated exactly the same as `NonNull<T>`
// at runtime.
#[repr(transparent)]
pub struct CursedCow<'a, T>
where
    T: ?Sized + ToOwned,
    T::Owned: Cursed<T>,
{
    ptr: NonNull<T>,
    _marker: PhantomData<&'a T>,
}

Помимо того факта, что вы не можете явно сопоставить его варианты (или получить изменяемую ссылку на внутренние компоненты, но есть способы обойти это), это идентично std::заимствовать::Cow - вы не делаете CowArr < T>, вы просто выполняете CursedCow <[T]>, и этот новый CursedCow имеет ширину 2 указателя. Это то же самое, что и раньше для 64-битной версии, но меньше в 32-битной за счет того, что допускается только до 65 535 элементов.

Реализовать необходимые методы для нашего нового CursedCow - методов для его создания из собственных или заимствованных данных, реализации Deref, реализации Drop и т.д. - довольно просто, поэтому я пропущу это, но вы можете увидеть это в полная суть (ссылка в конце статьи).

Настоящая работа выполняется в реализациях Cursed для Vec, String, Box и так далее. Я пока пропущу реализацию String, так как она в основном такая же, как Vec, но давайте начнем с объяснения того, как мы храним всю информацию, необходимую для CursedCow <[T]> в одном NonNull <[ T]>. Вы увидите ссылки на эти константы CAP_SHIFT, CAP_MASK и LEN_MASK в следующих функциях, поэтому я начну с их определения здесь:

use std::mem;

const CAP_SHIFT: usize = (mem::size_of::<usize>() * 8) / 2;
const LEN_MASK: usize = usize::MAX >> CAP_SHIFT;
const CAP_MASK: usize = !LEN_MASK;

CAP_SHIFT - это величина, на которую вам нужно сдвинуть поле len указателя жира NonNull <[T]>, чтобы получить емкость, которую мы скрыли в этом поле, то есть верхние 32/16 бит (в 64- и 32-битных версиях). , соответственно). LEN_MASK и CAP_MASK являются «масками» для этих битов, поэтому мы можем использовать побитовое & только для получения битов, которые представляют длину или емкость, соответственно.

unsafe impl<T> Cursed<[T]> for Vec<T> {
    fn borrowed(ptr: &[T]) -> Option<NonNull<[T]>> {
        if ptr.len() & CAP_MASK != 0 {
            None
        } else {
            Some(NonNull::from(ptr))
        }
    }

    fn owned(self) -> Option<NonNull<[T]>> {
        // Fail if the capacity is too high
        if self.len() & CAP_MASK != 0 || self.capacity() & CAP_MASK != 0 {
            None
        } else {
            let mut this = mem::ManuallyDrop::new(self);
            unsafe {
                Some(NonNull::from(slice::from_raw_parts_mut(
                    this.as_mut_ptr(),
                    // This combines the length and capacity into a single `usize`
                    this.len() | (this.capacity() << CAP_SHIFT),
                )))
            }
        }
    }

    // ...snip...
}

Итак, здесь вы можете видеть, как мы проверяем, что длина заимствованных / принадлежащих ценностей не превышает сумму, которую мы можем представить в уменьшенном объеме пространства, которое у нас есть. Если у нас слишком много элементов или слишком много емкости, мы возвращаем None, поскольку у нас нет возможности сохранить это. Хотя мы можем обрезать len, мы не можем безопасно обрезать емкость, не нарушив работу некоторых распределителей, а усечение len было бы ненужным. В остальном это выглядит примерно так же, как было раньше.

Остальная часть трейта реализована так, как вы ожидаете, и выглядит почти так же, как CowArr, которая была у нас раньше. Реализация этой трэйты в целом выглядит точно так же для String.

unsafe impl<T> Cursed<[T]> for Vec<T> {
    // ...snip...

    fn is_owned(ptr: NonNull<[T]>) -> bool {
        unsafe { ptr.as_ref() }.len() & CAP_MASK != 0
    }

    unsafe fn as_ref<'a>(ptr: NonNull<[T]>) -> &'a [T] {
        // Like before, this mask is essentially free because we can just treat `self.len`
        // like a smaller value, which acts the same as if we did the mask, instead of
        // actually masking.
        slice::from_raw_parts(ptr.as_ptr() as *const T, ptr.as_ref().len() & LEN_MASK)
    }

    unsafe fn reconstruct(ptr: NonNull<[T]>) -> Self {
        Vec::from_raw_parts(
            ptr.as_ptr() as *mut T,
            ptr.as_ref().len() & LEN_MASK,
            ptr.as_ref().len() >> CAP_SHIFT,
        )
    }
}

Ну вот и все. Теперь наш новый CursedCow <[T]> автоматически действует как CowArr. Проклятье скрывать тег и емкость внутри поля len фрагмента, но мы только начинаем

Теперь мы переходим к самой дрянной части - CursedCow для других значений T и, в частности, CursedCow . Теперь мы не можем быть универсальными для любого CursedCow , поскольку нет способа указать «некоторый объект-трэйт» в системе типов, но допустим, что если вы используете CursedCow по одной причине или в другом случае может быть реализация ToOwned с Owned = Box, поскольку это единственный способ иметь принадлежащий объект-трэйт. Это может выглядеть примерно так:

trait MyCoolTrait {
    fn clone_boxed(&self) -> Box<Self>;

    // ... the rest of my cool functions... 
}

impl ToOwned for dyn MyCoolTrait {
    type Owned = Box<dyn MyCoolTrait>;

    fn to_owned(&self) -> Self::ToOwned {
        self.clone_boxed()
    }
}

Итак, как нам сохранить тег, представляющий принадлежащий или заимствованный тег в Box, поскольку Box также внутренне использует, возможно, толстый указатель NonNull? Что ж, есть пара методов, оба полагаются на тот факт, что используются не все биты указателей. Для начала, большинство типов имеют выравнивание больше 1. Мы упоминали о выравнивании ниже - u64 могут находиться только в местах, кратных mem::size_of::(), u32 могут находиться только в местах, которые являются кратное mem::size_of::() и т.д. Итак, из-за этого мы знаем, что если целочисленное значение указателя нечетное, то оно должно быть недействительным. Мы можем использовать это для хранения тега - если указатель нечетный, значит, он принадлежит (и мы должны вычесть 1, чтобы получить истинный указатель), если четный, то это просто обычный заимствованный указатель. Конечно, это была бы довольно проклятая реализация Cow, но мы не можем реализовать ее в общем, и мы не можем реализовать ее для dyn Trait, так как это привело бы к странным ошибкам, где Cow подходила для большинства типов. , но не работает, если реализация вашего трейта имеет размер 1, и вы не узнаете об этом, пока он не взорвется во время выполнения.

Другая возможность состоит в том, что Rust изо всех сил старается убедиться, что указатели не могут переполнить isize, поскольку это означает, что добавление двух указателей никогда не приведет к переполнению. Насколько я знаю, это не жесткая гарантия, но, безусловно, на 64-битном x86 невозможно даже на любом оборудовании, которое существует в реальном мире, иметь указатель больше 63 бит, так что 64-й бит всегда будет 0 . Мы можем воспользоваться этим, и если мы получим указатель, у которого установлен верхний бит, мы можем просто вернуть None, как если бы мы получили слишком большой &[T] / Vec хранить. Теперь ручное управление полем указателя толстого указателя запрещено в Rust - мы можем выполнять арифметические операции с обычным, «тонким» указателем, но нет способа изменить поле указателя толстого указателя. Однако мы можем обойти это, выполнив приведение указателя к указателю, что является неопределенным поведением в C, но не в Rust. Это в высшей степени небезопасно, и нам нужно быть предельно осторожными, чтобы заставить его вообще работать, не говоря уже о том, чтобы он работал так, чтобы не сразу вызывать неопределенное поведение. В основе всего этого лежит проклятая функция, которая позволяет нам обрабатывать указатель данных жирного указателя, как если бы он использовался, и, таким образом, позволяет нам напрямую манипулировать его битами.

fn update_as_usize<O, F: FnOnce(&mut usize) -> O, T: ?Sized>(ptr: &mut *mut T, func: F) -> O {
    unsafe {
        // Here's where we invoke the darkest of dark magic, explanation below.
        let ptr_as_bytes = mem::transmute::<&mut *mut T, &mut usize>(ptr);
        // Since this is dark magic, we make sure that we explode if our
        // assumptions are wrong.
        assert_eq!(*ptr_as_bytes, *ptr as *mut u8 as usize);
        func(ptr_as_bytes)
    }
}

Это работает при условии, что в макете жирного указателя сначала указан указатель данных. По сути, жирный указатель для NonNull выглядит так, и на самом деле вы можете найти эту точную структуру в std::raw::TraitObject:

struct TraitObject {
    data: *mut(),
    vtable: *mut(),
}

Однако даже с ночным Rust мы не можем использовать std::raw::TraitObject, поскольку он не работает ни с одним жирным указателем, а только с dyn Trait, и, как упоминалось ранее, мы не можем быть универсальными по «любому объекту трейта». . Таким образом, мы должны сделать дополнительное предположение, что не только объекты-трэйты сначала имеют указатель данных, но и все жирные указатели сначала имеют указатель данных. Именно это и делает assert_eq в update_as_usize: он использует встроенную способность Rust преобразовывать указатель в thin * mut u8, чтобы убедиться, что наш изменяемый указатель на использование указывает на правильные данные. Это в высшей степени небезопасно, и хотя в обозримом будущем это, вероятно, будет работать для всех жирных указателей, поддерживаемых Rust, нет никакой гарантии, что это будет так, и если это когда-либо станет некорректным таким образом, что assert_eq не поймает тогда вы получите неопределенное поведение. Так что пока мы продолжим использовать это, потому что это работает, но я хочу подчеркнуть, что вы НЕ должны ИСПОЛЬЗОВАТЬ ЭТО В НАСТОЯЩЕМ ПРОГРАММНОМ ОБЕСПЕЧЕНИИ, если вы не хотите, чтобы вас уволили и вы этого не заслужили.

В любом случае, пока это работает отлично, давай исследуем эти проклятые миры еще немного, не так ли?

// The mask for the actual pointer
const PTR_MASK: usize = usize::MAX >> 1;
// The mask for just the "is owned" tag
const TAG_MASK: usize = !PTR_MASK;

unsafe impl<T: ?Sized> Cursed<T> for Box<T> {
    fn borrowed(ptr: &T) -> Option<NonNull<T>> {
        // We use `Self::is_owned` here to avoid duplicating information. You can think of this
        // in this context as expressing "if we _would think_ that `ptr` was owned"
        if Self::is_owned(NonNull::from(ptr)) {
            None
        } else {
            Some(NonNull::from(ptr))
        }
    }

    fn owned(self) -> Option<NonNull<T>> {
        let mut this = mem::ManuallyDrop::new(self);
        let original_ptr = &mut **this as *mut T;
        let mut ptr = original_ptr;

        update_as_usize(&mut ptr, |p| *p |= TAG_MASK);

        unsafe {
            if Self::is_owned(NonNull::new_unchecked(original_ptr)) {
                this.into_inner();
                None
            } else {
                Some(NonNull::new_unchecked(ptr))
            }
        }
    }

    fn is_owned(ptr: NonNull<T>) -> bool {
        ptr.as_ptr() as *mut u8 as usize &TAG_MASK != 0
    }

    unsafe fn as_ref<'a>(ptr: NonNull<T>) -> &'a T {
        let mut ptr = ptr.as_ptr();
        update_as_usize(&mut ptr, |p| *p &= PTR_MASK);
        &*ptr
    }

    unsafe fn reconstruct(ptr: NonNull<T>) -> Self {
        let mut ptr = ptr.as_ptr();
        update_as_usize(&mut ptr, |p| *p &= PTR_MASK);
        Box::from_raw(ptr)
    }
}

Итак, мы идем, помимо реализаций черт, которые вы ожидаете от реализации Cow, которая должна быть довольно понятной, и реализации Drop, которая также довольно проста, это более или менее полностью - рабочая замена для std::заимствовать::корова. Наконец, давайте посмотрим, как выглядит кодогенератор для этой реализации Cursed for Box. Вы можете просто поверить мне на слово, что CursedCow <[T]> генерирует точно такой же код, что и CowArr. Давайте напишем код для пары разных сценариев, для которых мы хотим протестировать кодогенератор - сначала для жирных указателей, а затем для тонких указателей (если по какой-то причине у вас была реализация ToOwned для типа нединамического размера, который все еще использовался Коробка когда есть в собственности).

#[no_mangle]
pub fn dyn_as_ref<'a>(cow: &'a CursedCow<'_, dyn Foo>) -> &'a dyn Foo {
    &**cow
}

#[no_mangle]
pub fn dyn_to_cow<'a>(cow: CursedCow<'a, dyn Foo>) -> std::borrow::Cow<'a, dyn Foo> {
    cow.into()
}

#[no_mangle]
pub fn dyn_new_cow(cow: Box<dyn Foo>) -> Option<CursedCow<'static, dyn Foo>> {
    CursedCow::try_owned(cow)
}

#[repr(transparent)]
pub struct Test(u64);

impl ToOwned for Test {
    type Owned = Box<Test>;
    
    fn to_owned(&self) -> Self::Owned {
        Box::new(Test(self.0))
    }
}

#[no_mangle]
pub fn static_new_cow(cow: Box<Test>) -> Option<CursedCow<'static, Test>> {
    CursedCow::try_owned(cow)
}

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

dyn_as_ref:
    mov    rdx, [rdi + 8]
    movabs rax, 9223372036854775807
    and    rax, [rdi]
    ret

dyn_to_cow:
    mov    rax, rdi
    movabs rcx, 9223372036854775807
    and    rcx, rsi
    test   rsi, rsi
    jns    .is_ref
    mov    esi, 1
    mov    [rax + 8], rcx
    mov    [rax + 16], rdx
    mov    [rax], rsi
    ret
.is_ref:
    xor    esi, esi
    mov    [rax + 8], rcx
    mov    [rax + 16], rdx
    mov    [rax], rsi
    ret

dyn_new_cow:
    mov    rdx, rsi
    movabs rcx, -9223372036854775808
    or     rcx, rdi
    xor    eax, eax
    test   rdi, rdi
    cmovns rax, rcx
    ret

static_new_cow:
    movabs rcx, -9223372036854775808
    or     rcx, rdi
    xor    eax, eax
    test   rdi, rdi
    cmovns rax, rcx
    ret

В любом случае, если вы хотите попробовать это, я рекомендую крэйт для говядины, который в большинстве случаев служит заменой для std::заимствовать::Cow. Ее написал мой коллега и друг, и эта статья появилась из-за дискуссий о том, как оптимизировать этот крэйт для использования при синтаксическом анализе JSON. Слава богу, здесь нет нашей невероятно схематичной реализации Dyn Trait. Также есть более простой крэйт cowvec, который является моей более ранней реализацией, примерно эквивалентный коду, который мы имели в конце акта 2. Я бы рекомендовал только говядину вместо cowvec, потому что cowvec не действует как замена, поскольку он имеет другая подпись для std::заимствовать::Cow. Ну, и тот факт, что говядина - явно лучшее название.

крэйт для синтаксического анализа JSON simdjson-rs недавно фактически интегрировал beef, и вы можете увидеть улучшения в пропускной способности, которые они увидели, просто отключив свою реализацию Cow в интеграционном PR.

А теперь, если вы не возражаете, я пойду за советом к священнику.

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