Как стать автором
Обновить
2765.91
RUVDS.com
VDS/VPS-хостинг. Скидка 15% по коду HABR15

Собственный строковый тип на Rust

Уровень сложностиСредний
Время на прочтение14 мин
Количество просмотров7.1K
Автор оригинала: mcyoung

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

pub enum Expr<'src> {
  Int(u32)
  Ident(&'src str),
  // ...
}

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

К сожалению, это не так просто для строк в кавычках. Большинство строк, например, "all my jelly babies" посимвольно находятся в оригинальном исходнике, как идентификатор. Но строки с escape-последовательностями отличаются: \n кодируется в исходном коде байтами [0x5c, 0x6e], но настоящее «декодированное значение» строкового литерала заменяет каждую escape-последовательность одним 0x0a.

Обычно эту проблему решают при помощи Cow<str>. В более распространённой версии без escape-последовательности можно использовать Cow::Borrowed, который позволяет избежать лишнего распределения и копирования, а в версии с escape-последовательностью мы кодируем escape-последовательность в String и оборачиваем её в Cow::Owned.

Например, предположим, что мы пишем парсер для языка, имеющего закавыченные строки с escape-последовательностями. Строку "all my jelly babies" можно представить как байтовую строку, заимствующую входной исходный код, поэтому мы используем вариант Cow::Borrowed. Таково большинство строк в любом языке: escape-последовательности обычно редки.

Например, если у нас есть строка "not UTF-8 \xff", то истинное значение байтовой строки отличается от того, которое есть в исходном коде.

// Байты в исходном коде.
hex:   6e 6f 74 20 55 54 46 2d 38 20 5c 78 66 66
ascii: n  o  t     U  T  F  -  8     \  x  f  f

// Байты, представленные строкой.
hex:   6e 6f 74 20 55 54 46 2d 38 20 ff
ascii: n  o  t     U  T  F  -  8

Escape-последовательности относительно редки, поэтому для большинства обрабатываемых парсером строк не нужно тратить ресурсы на распределение.

Однако нам всё равно нужно тратить ресурсы на это дополнительное слово, потому что Cow<str> — это 24 байта (если не сказано иное, предполагается, все величины в байтах заданы для 64-битной системы), что на восемь больше, чем &str. Хуже того, это даже больше, чем сами строковые данные, которые занимают 11 байтов.

Если бОльшая часть строк мала (что довольно часто бывает в парсере AST), то в конечном счёте придётся потратить существенно больше ресурсов.

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

Yarn — это сильно оптимизированный строковый тип, обеспечивающий (по сравнению с String) множество полезных свойств:

  • Всегда имеет ширину в два указателя, поэтому всегда передаётся в функции и из функций в регистрах.
  • Small string optimization (SSO) до 15 байт в 64-битных архитектурах.
  • Может быть или с собственным (owned), или заимствованным (borrowed) буфером (как Cow<str>).
  • Может быть преобразован в срок жизни 'static, если создан из известной статической строки.

Я бы хотел рассказать о том, как я добился этих свойств при помощи аккуратной оптимизации структуры.

Допущения


Мы начнём с изложения допущений о том, как будут использоваться наши строки:

  1. Большинство строк бОльшую часть времени не изменяется.
  2. Большинство строк мало.
  3. Большинство строк является подстроками.

▍ Большинство строк неизменяемо


String смоделирована по примеру std::string языка C++, являющегося буфером с возможностью расширения, который реализует append за амортизированное линейное время. Это значит, что если мы выполняем append n байтов к буферу, то тратим ресурсы только на n байтов memcpy.

Это полезное, но часто необязательное свойство. Например, строки Go неизменяемы, и при создании большой строки ожидается, что вы будете использовать strings.Builder, который, по сути, реализован как String языка Rust. В Java со строками похожая история, что позволяет создавать очень компактные представления java.lang.String.

В Rust такой вид неизменяемой строки представлен в виде Box<str>, который на восемь байт меньше, чем String. Для преобразования из String в Box<str> достаточно выполнить вызов realloc(), чтобы изменить размер распределения (что часто бывает малозатратно1) из длины capacity байтов в длину len байтов.

[1] Распределители редко передают точно запрошенный размер памяти. У них есть понятие «класса размера», позволяющее использовать более эффективные методики распределения, о которых я писал ранее.

Поэтому если изменение размера в realloc() не изменяет класс размера, то оно становится no-op, особенно если распределитель может воспользоваться информацией о текущем размере, предоставленной ему Rust
.

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

▍ Большинство строк — это подстроки


Снова предположим, что мы парсим какой-то текстовый формат. Многие структурные элементы будут дословными ссылками на текстовый ввод. Не только строковые литералы без escape-последовательностей, но и идентификаторы.

Box<str> не может содержать заимствованные данные, потому что всегда будет приказывать распределителю освободить свой указатель, когда он выходит за пределы области видимости. Как мы видели раньше, Cow<str> позволяет одинаково работать с данными (в том числе и с владением), но имеет минимальные лишние затраты в 24 байта. Это значение нельзя уменьшить, потому что Cow<str> может содержать 24-байтное значение String.

Но нам не нужно хранить ёмкость строки (capacity). Можно ли избежать траты лишнего слова в Cow<str>?

▍ Большинство строк мало


Рассмотрим строку, которая не является подстрокой, но имеет малый размер. Например, при парсинге строкового литерала наподобие "Hello, world!\n" завершающие \n (байты 0x5c 0x6e) должны быть заменены байтом новой строки (0x0a). Это значит, что нам нужно обрабатывать крошечное распределение кучи длиной 14 байтов, которое меньше, чем ссылающаяся на него &str.

Это хуже для строк из одного символа2. Лишняя трата ресурсов для Box<str> велика.

[2] Здесь и далее под символом подразумевается «32-битное скалярное значение Unicode».

  • Сама структура Box<str> имеет поле указателя (восемь байт) и поле длины (тоже восемь байт). Длина имеет вид 0x0000_0000_0000_0001. Целая куча нулей!
  • Сам указатель указывает на распределение кучи, которое может и не быть одним байтом! Распределители не имеют дела с обработкой таких мелких фрагментов памяти. Поэтому распределение, скорее всего, стоит нам ещё восемь дополнительных байтов!

То есть строка "a", данные которых составляют всего один байт, занимает 24 байта памяти.

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

Крадём биты


Допустим, мы хотим придерживаться бюджета в 16 байт для нашего типа Yarn. Осталось ли лишнее место для данных в паре (*mut u8, usize)?

usize имеет размер 64 бита, то есть длина &str может иметь значение в интервале от нуля до 18446744073709551615, или примерно 18 эксабайтов. Для справки: «сотни эксабайтов» — это приблизительная оценка объёма ОЗУ во всём мире на 2023 год (прикинем: 4 миллиарда смартфонов по 4 ГБ каждый). Если подходить более практически, то максимальный объём ОЗУ, который можно установить в blade-сервер, измеряется в терабайтах.

Если мы используем на один бит меньше, то есть 63 бита, то это вдвое уменьшает максимально представляемую память (до девяти эксабайтов). Если мы возьмём ещё один бит, то останется четыре эксабайта. А это гораздо больше памяти, чем вы когда-либо запишете в строку. Википедия утверждает, что Wikimedia Commons содержит примерно 428 терабайт данных (текст статей с историей — это всего 10 ТБ).

Рассмотрим ситуацию, когда вы программируете для 32-битной машины (сегодня это, скорее всего, означает дешёвый телефон, встроенный микроконтроллер или WASM).

На 32-битной машине всё чуть серьёзнее: теперь usize имеет размер 32 бита, то есть максимальный размер строки составляет 4 гигабайта (если вы помните 32-битную эпоху, то это ограничение может показаться вам знакомым). «Гигабайты» — это уже тот объём памяти, который вполне можно представить сохранённым в строке.

Но даже в этом случае 1 ГБ памяти (если мы украдём два бита) на 32-битной машине — это куча данных. В адресном пространстве может быть всего четыре строки такого размера, и все 32-битные распределители в мире откажутся обрабатывать распределение такого размера. Если ваши строки сравнимы по размеру со всем адресным пространством, то вам следует создать собственный строковый тип.

Вывод: в каждой &str есть два бита, которые, скорее всего, не используются. Наша бесплатная собственность.3

[3] Вы можете отметить, что Rust и C не разрешают создавать распределения, размер которых больше, чем тип смещения указателя (соответственно, isize и ptrdiff_t). На практике это означает, что старший бит, согласно собственным правилам языка, всегда равен нулю.

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


▍ Рукописная нишевая оптимизация


В Rust есть концепция ниш, или недопустимых битовых паттернов определённого вида, используемых для автоматической оптимизации структуры enum. Например, ссылки никогда не могут быть null, поэтому битовый паттерн указателей 0x0000_0000_0000_0000 не используется никогда; этот битовый паттерн называется «нишей». Пример:

enum Foo<'a> {
  First(&'a T),
  Second
}

enum такого вида не требует никакого «лишнего» пространства для хранения значения, различающегося между двумя вариантами: если все биты Foo равны нулю, то это Foo::Second; в противном случае это Foo::First и полезная нагрузка формируется из битового паттерна Foo. К тому же это делает Option<&T> валидным представлением указателя, допускающего нулевое значение.

Есть и более обобщённые примеры: bool представлен как один байт, валидными в котором являются два бита; остальные 254 потенциальных битовых паттерна — это ниши. В последних версиях Rust RawFd имеет нишу для универсального битового паттерна, поскольку дескрипторы файлов POSIX всегда являются неотрицательными int.

Отобрав у длины два бита, мы получили четыре ниши; по сути, это означает, что у нас получится рукописная версия чего-то вроде этого enum.

enum Yarn {
  First(*mut u8, u62),
  Second(*mut u8, u62),
  Third(*mut u8, u62),
  Fourth(*mut u8, u62),
}

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

[4] Интересно, что LLVM компилирует (x << 2) >> 2 так:

movabs rax,0x3fffffffffffffff
and    rax,rdi
ret

Если мы хотим поиграть в игру «байт за байт», то это стоит 14 байтов при кодировании кодировкой переменной длины Intel. Можно подумать, что два сдвига приведут к незначительному уменьшению кода, но нет, поскольку ввод поступает в rdi и должен оказаться в rax.

Однако в RISC-V, похоже, LLVM решает, что два сдвига на самом деле менее затратны, и даже выполняет оптимизацию x & 0x3fff_ffff_ffff_ffff обратно в два сдвига.


Вот код, который реализует это для низкоуровневого типа, на основе которого будет создан наш строковый тип.

#[repr(C)]
#[derive(Copy, Clone)]
struct RawYarn {
  ptr: *mut u8,
  len: usize,
}

impl RawYarn {
  /// Создаёт новый RawYarn из сырых компонентов: 2-битного вида,
  /// длины и указателя.
  fn from_raw_parts(kind: u8, len: usize, ptr: *mut u8) {
    assert!(len <= usize::MAX / 4, "no way you have a string that big");

    RawYarn {
      ptr,
      len: (kind as usize & 0b11) << (usize::BITS - 2) | len,
    }
  }

  /// Извлекает вид.
  fn kind(self) -> u8 {
    (self.len >> (usize::BITS - 2)) as u8
  }

  /// Извлекает срез (вне зависимости от вида).
  unsafe fn as_slice(&self) -> &[u8] {
    slice::from_raw_parts(self.ptr, (self.len << 2) >> 2)
  }
}

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

  1. Существует тип Yarn, который сам по себе является Copy, хотя я не рассматриваю его в этой статье.
  2. Это структура из двух слов, поэтому на большинстве структур она подходит для передачи в паре регистров. Передача по значению в низкоуровневом коде помогает оставлять их в регистрах. Как мы увидим ниже при обсуждении SSO, это не всегда возможно.

Давайте решим, что вид 0 означает «это заимствованные данные», а вид 1 — «это распределённые в куче данные». Это можно использовать, чтобы запомнить, нужно ли нам вызывать деструктор.

pub struct Yarn<'a> {
  raw: RawYarn,
  _ph: PhantomData<&'a str>,
}

const BORROWED: u8 = 0;
const HEAP: u8 = 1;

impl<'a> Yarn<'a> {
  /// Создание нового yarn из заимствованных данных.
  pub fn borrowed(data: &'a str) -> Self {
    let len = data.len();
    let ptr = data.as_ptr().cast_mut();
    Self {
      raw: RawYarn::from_raw_parts(BORROWED, len, ptr),
      _ph: PhantomData,
    }
  }

  /// Создание нового yarn из данных с владением.
  pub fn owned(data: Box<str>) -> Self {
    let len = data.len();
    let ptr = data.as_ptr().cast_mut();
    mem::forget(data);

    Self {
      raw: RawYarn::from_raw_parts(HEAP, len, ptr),
      _ph: PhantomData,
    }
  }

  /// Извлечение данных.
  pub fn as_slice(&self) -> &str {
    unsafe {
      // БЕЗОПАСНОСТЬ: инициализация или из данных с уникальным владением,
      // или из заимствованных данных со сроком жизни 'a, которые переживут self.
      str::from_utf8(self.as_slice())
    }
  }
}

impl Drop for Yarn<'_> {
  fn drop(&mut self) {
    if self.raw.kind() == HEAP {
      let dropped = unsafe {
        // БЕЗОПАСНОСТЬ: это просто воспроизведение box, от которого мы отказались
        // in Yarn::owned().
        Box::from_raw(self.as_slice())
      };
    }
  }
}

Это даёт нам тип, сильно напоминающий Cow<str>, но занимающий в два раза меньше байтов. Мы даже можем написать код для продления срока жизни Yarn:

impl Yarn<'_> {
  /// Удаляет назначенный yarn срок жизни, по необходимости
  /// выполняя распределение.
  pub fn immortalize(mut self) -> Yarn<'static> {
    if self.raw.kind() == BORROWED {
      let copy: Box<str> = self.as_slice().into();
      self = Yarn::owned(copy);
    }

    // Нам нужно быть аккуратными при сбросе старого yarn, потому что
    // его деструктор может выполниться и удалить созданное нами выше
    // распределение кучи.
    let raw = self.raw;
    mem::forget(self);
    Yarn::<'static> {
      raw,
      _ph: PhantomData,
    }
  }
}

Оставшиеся две ниши можно использовать для оптимизации малых строк.

Small String Optimization


std::string языка C++ тоже предполагает, что «большинство строк мало». В реализации libc++ стандартной библиотеки std::string размером вплоть до 23 байтов никогда не попадают в кучу!

Реализациям C++ удаётся это благодаря тому, что основная часть полей указателя, длины и ёмкости используется как буфер хранения маленьких строк, это так называемая small string optimization (SSO). В режиме SSO в libc++ длина std::string умещается в один байт, поэтому остальные 23 байта можно использовать для хранения. Ёмкость строки вообще не хранится: строка SSO всегда имеет ёмкость 23.

RawYarn остаётся ещё две ниши, так что давайте отдадим их под «маленькое» представление. В режиме малых строк вид будет иметь значение 2, и только 16-й байт будет длиной.

Именно поэтому, мы использовали под вспомогательное пространство два старших бита len: в каком бы режиме мы ни находились, мы можем с лёгкостью извлечь эти биты5.

[5] Это работает только с little endian. К счастью, все компьютеры работают в little endian.

Однако часть из уже существующих методов RawYarn придётся изменить.

#[repr(C)]
#[derive(Copy, Clone)]
struct RawYarn {
  ptr: MaybeUninit<*mut u8>,
  len: usize,
}

const SMALL: u8 = 2;

impl RawYarn {
  /// Создание нового RawYarn из сырых компонентов: 2-битного вида,
  /// длины и указателя.
  fn from_raw_parts(kind: u8, len: usize, ptr: *mut u8) {
    debug_assert!(kind != SMALL);
    assert!(len <= usize::MAX / 4, "no way you have a string that big");

    RawYarn {
      ptr: MaybeUninit::new(ptr),
      len: (kind as usize & 0b11) << (usize::BITS - 2) | len,
    }
  }

  /// Извлечение среза (вне зависимости от типа).
  unsafe fn as_slice(&self) -> &[u8] {
    let (ptr, adjust) = match self.kind() {
      SMALL => (self as *const Self as *const u8, usize::BITS - 8),
      _ => (self.ptr.assume_init(), 0),
    };

    slice::from_raw_parts(ptr, (self.len << 2) >> (2 + adjust))
  }
}

В случае, когда вид не является SMALL мы, как и раньше, дважды выполняем сдвиг, но в случае SMALL нам необходимо получить старший байт поля len, поэтому нужно выполнить сдвиг вниз на дополнительные usize::BITS - 8. Вне зависимости от того, что записано в младших байтах len, таким образом, мы всегда получим только длину.

Также в зависимости от того, находимся ли мы в режиме SMALL, нужно использовать разные значения указателя. Именно поэтому as_slice должен получать ссылку как аргумент, потому что данные среза могут быть непосредственно в self!

Кроме того, ptr теперь является MaybeUninit, что станет понятно из следующего фрагмента кода.

Нам нужно также обеспечить способ создания малых строк.

const SSO_LEN: usize = size_of::<usize>() * 2 - 1;

impl RawYarn {
  /// Создание нового малого yarn. `data` должны быть валидны для `len` байтов,
  /// а `len` должно быть меньше `SSO_LEN`.
  unsafe fn from_small(data: *const u8, len: usize) -> RawYarn {
    debug_assert!(len <= SSO_LEN);

    // Создание yarn с неинициализированным значением указателя (!!)
    // и длиной, в старший байт которой записаны `small` и
    // `len`.
    let mut yarn = RawYarn {
      ptr: MaybeUninit::uninit(),
      len: (SMALL as usize << 6 | len)
          << (usize::BITS - 8),
    };

    // Делаем Memcpy данных в новый yarn.
    // Мы выполняем запись напрямую в переменную `yarn`. Не будем
    // перезаписывать длину старшего байта, потому что `len`
    // никогда не будет >= 16.
    ptr::copy_nonoverlapping(
      data,
      &mut yarn as *mut RawYarn as *mut u8,
      data,
    );

    yarn
  }
}

Точный максимальный размер строки SSO — чуть более тонкий вопрос, чем изложено выше, но смысл передан верно. RawYarn::from_small иллюстрирует, почему значение указателя скрыто в MaybeUninit: мы собираемся перезаписать его мусором, и в таком случае это вообще не будет указателем.

Можно дополнить наш публичный тип Yarn, чтобы он по возможности использовал новое малое представление строк.

impl<'a> Yarn<'a> {
  /// Создание нового yarn из заимствованных данных.
  pub fn borrowed(data: &'a str) -> Self {
    let len = data.len();
    let ptr = data.as_ptr().cast_mut();

    if len <= SSO_LEN {
      return Self {
        raw: unsafe { RawYarn::from_small(len, ptr) },
        _ph: PhantomData,
      }
    }

    Self {
      raw: RawYarn::from_raw_parts(BORROWED, len, ptr),
      _ph: PhantomData,
    }
  }

  /// Создание нового yarn из данных с владением.
  pub fn owned(data: Box<str>) -> Self {
    if data.len() <= SSO_LEN {
      return Self {
        raw: unsafe { RawYarn::from_small(data.len(), data.as_ptr()) },
        _ph: PhantomData,
      }
    }

    let len = data.len();
    let ptr = data.as_ptr().cast_mut();
    mem::forget(data);

    Self {
      raw: RawYarn::from_raw_parts(HEAP, len, ptr),
      _ph: PhantomData,
    }
  }
}

Теперь также можно создавать Yarn напрямую из символа!

impl<'a> Yarn<'a> {
  /// Создание нового yarn из заимствованных данных.
  pub fn from_char(data: char) -> Self {
    let mut buf = [0u8; 4];
    let data = data.encode_utf8(&mut buf);
    Self {
      raw: unsafe { RawYarn::from_small(len, ptr) },
      _ph: PhantomData,
    }
  }
}

(Стоит также отметить, что нам не нужно изменять Yarn::immortalize().)

Теперь у нас есть строка с возможным владением, не требующая распределения для малых строк. Однако у нас остаётся ещё одна лишняя ниша…

Строковые константы


Строковые константы в Rust интересны, потому что мы можем выявлять их только во время компиляции6.

[6] Строго говоря, &'static str также может указывать на утёкшую память. В нашем случае существенной разницы нет.

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

const STATIC: u8 = 3;

impl<'a> Yarn<'a> {
  /// Создание нового yarn из заимствованных данных.
  pub fn from_static(data: &'static str) -> Self {
    let len = data.len();
    let ptr = data.as_ptr().cast_mut();

    if len <= SSO_LEN {
      return Self {
        raw: unsafe { RawYarn::from_small(len, ptr) },
        _ph: PhantomData,
      }
    }

    Self {
      raw: RawYarn::from_raw_parts(STATIC, len, ptr),
      _ph: PhantomData,
    }
  }
}

Эта функция идентична Yarn::borrowed, только теперь data должно иметь статический срок службы, и мы передаём STATIC в RawYarn::from_raw_parts().

Благодаря тому, как мы написали весь предыдущий код, он не требует никакой особой поддержки в Yarn::immortalize() или в коде низкоуровневого RawYarn.

В библиотеке byteyarn есть макрос yarn!(), имеющий тот же синтаксис, что и format!(). Это основной способ создания yarn. Он был аккуратно написан так, чтобы yarn!("this is a literal") всегда создавал строку STATIC, а не строку с распределением в памяти.

Лишняя ниша в качестве бонуса?


К сожалению, из-за особенностей написания кода Option<Yarn> занимает 24 байта — на целое слово больше, чем Yarn. Однако у нас всё равно есть немного места, куда можно уместить вариант None. Оказалось, из-за выбора параметров len равно нулю тогда и только тогда, когда это пустая строка BORROWED. Но это не единственный ноль: если старший байт равен 0x80, то это пустая строка SMALL. Если мы просто потребуем, чтобы никогда не создавалась никакая другая пустая строка (пометив RawYarn::from_raw_parts() как unsafe и указав, что ему нельзя передавать нулевую длину), то мы сможем гарантировать, что len никогда не равно нулю.

Таким образом, мы можем изменить len так, чтобы оно было NonZeroUsize.

#[repr(C)]
#[derive(Copy, Clone)]
struct RawYarn {
  ptr: MaybeUninit<*mut u8>,
  len: NonZeroUsize,  // (!!)
}

impl RawYarn {
  /// Создание нового RawYarn из сырых компонентов: 2-битного вида,
  /// *ненулевой* длины и указателя.
  unsafe fn from_raw_parts(kind: u8, len: usize, ptr: *mut u8) {
    debug_assert!(kind != SMALL);
    debug_assert!(len != 0);
    assert!(len <= usize::MAX / 4, "no way you have a string that big");

    RawYarn {
      ptr: MaybeUninit::new(ptr),
      len: NonZeroUsize::new_unchecked(
        (kind as usize & 0b11) << (usize::BITS - 2) | len),
    }
  }
}

Компилятор Rust знает, что конкретно этот тип имеет нишевый битовый паттерн из одних нулей, что позволяет Option<Yarn> тоже иметь размер 16 байт. Также он имеет удобное свойство: битовый паттерн из одних нулей для Option<Yarn> является None.

Заключение


В описании byteyarn сказано, что мы создали:

Yarn — это высокооптимизированный строковый тип, имеющий множество полезных преимуществ перед String:

  • Всегда имеет ширину в два указателя, поэтому всегда передаётся в функции и из них в регистрах.
  • Small string optimization (SSO) до 15 байт в 64-битных архитектурах.
  • Может быть или с собственным (owned), или заимствованным (borrowed) буфером (как Cow<str>)
Может быть преобразован в срок жизни 'static, если создан из известной статической строки.

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

Настоящая реализация Yarn чуть сложнее; в основном это связано с тем, что весь низкоуровневый контроль должен находиться в одном месте, а частично тем, чтобы обеспечить эргономичный API, позволяющий Yarn стать заменой Box<str> практически без дополнительной настройки.

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

Telegram-канал с розыгрышами призов, новостями IT и постами о ретроиграх 🕹️
Теги:
Хабы:
Всего голосов 48: ↑47 и ↓1+63
Комментарии6

Публикации

Информация

Сайт
ruvds.com
Дата регистрации
Дата основания
Численность
11–30 человек
Местоположение
Россия
Представитель
ruvds