#prog #rust #моё

У Алексея Кладова есть пост про реализацию интернирования строк (советую прочитать перед моим постом). Как он замечает, простейший способ интернировать строки — через такой тип:

struct Interner {
    map: HashMap<String, u32>,
    vec: Vec<String>,
}

Новые строки добавляются через вставку в map, а идентификатор строк создаётся от длины vec на момент добавления. map позволяет быстро проверить, была ли строка записана, а vec позволяет быстро получить строку по её идентификатору.

Недостаток такого решения очевиден: каждая строка выделяется в куче дважды. Особенно это печально в связи с тем, что строки часто интернируют именно для того, чтобы сэкономить память, выделяя её только единожды на каждое значение. Алексей решает это тем, что выделяет память по возможности одним куском в одной String и хранит в мапе &str на эту память с принудительно приведённым к 'static временем жизни. Инвалидацию ссылок он обходит остроумным приёмом: при нехватке ёмкости он выделяет новый буфер, вдвое больше предыдущего, и записывает новые строки туда, а старый буфер переносит в отдельный вектор. Он эксплуатирует тот факт, что адреса выделенной в куче памяти стабильны и не меняются при перемещении String. С таким дизайном определение структуры данных выглядит так:

struct Interner {
    map: HashMap<&'static str, u32>,
    vec: Vec<&'static str>,
    // новые строки записывают сюда
    buf: String,
    // буферы с недостаточной памятью переносят сюда
    full: Vec<String>,
}

К сожалению, у этого дизайна есть несколько недостатков.
* Выдаваемые Interner идентификаторы не самодостаточны: всё ещё нужно обращаться к пулу, если нам потребуется содержимое строки. Пул при этом можно перепутать
* Из-за индексации каждый лукап — потенциальная паника.
* Идентификаторы никак не привязаны к пулу временами жизни: если мы создадим пул, выделим строку, дропнем пул, создадим заново и снова выделим строку, то возвращённые значения будут считаться равными — что технически верно, но не вполне корректно.
* Можно сравнивать идентификаторы, полученные от двух разных пулов, и получить как и ложно-положительные, так и ложно-отрицательные результаты, и компилятор вообще никак от этого не защищает.
* Очень нишевый недостаток: u32 не имеет ниши и потому не получает null pointer optimization при оборачивании в Option. Это, в принципе, решаемо оборачиванием в NonNull<u32>, но не очень удобно из-за инкремента при генерации и декремента при индексации.
* Количество потребляемой таки пулом памяти может только расти, явное переиспользование памяти невозможно. Это может быть важно, если нам требуется многократно использовать пул в ограниченной области действия.

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

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

* Выдаваемые идентификаторы могут быть переведены в строки без обращения к пулу — его не надо держать под рукой и получение строки не может паниковать.
* К создаваемой строке можно (на самом деле нужно, для корректности) привязать время жизни. Это позволяет избежать ошибок со случайным переиспользованием строк и до какой-то степени защищает от сравнения строк из разных пулов.
* Указатель имеет естественную нишу в виде null и потому получает оптимизацию раскладки Option.

Второе решение заключается в том, чтобы использовать bump-аллокатор — в данном случае bumpalo. Он даёт гарантии стабильности адресов, а внутри использует тот же трюк с удваиваемыми буферами, который нам не надо повторять самостоятельно. Дополнительно он позволяет скопом освобождать память, сохраняя при этом аллокацию последнего буфера, что позволяет уменьшить потребление памяти и обращение к аллокатору и закрыть таким образом последний недостаток решения Кладова.

Что ж, приступим к реализации!

Запишем сначала определение интернированной строки:

#[derive(Clone, Copy, PartialEq, Eq)]
pub struct InternedStr<'a> {
    ptr: NonNull<u8>,
    _lt: PhantomData<&'a ()>,
}

impl<'a> InternedStr<'a> {
    // Конструктор unsafe, потому что корректность
    // времён жизни нужно обеспечивать пользователю
    unsafe fn from_ptr(ptr: NonNull<u8>) -> Self {
        Self {
            ptr,
            _lt: PhantomData,
        }
    }
}

Самая полезная операция для это строки — перевод в &str. Для этого нам нужно считать размер строки из начала аллокации, сдвинуть указатель на размер usize и сделать толстый указатель из полученного тонкого и длины:

const USIZE_SIZE: usize = std::mem::size_of::<usize>();

impl<'a> InternedStr<'a> {
    pub fn as_str(self) -> &'a str {
        let len = unsafe { self.ptr.cast::<usize>().read() };
        let ptr = unsafe { self.ptr.add(USIZE_SIZE) };
        unsafe {
            str::from_utf8_unchecked(
                std::slice::from_raw_parts(
                    ptr.as_ptr(),
                    len
                )
            )
        }
    }
}

Теперь немного подумаем о том, как будет выглядеть пул строк. Очевидно, нам нужен Bump для выделения памяти. Также нам всё ещё нужно иметь возможность быстро определять, записали мы строку или нет, поэтому в пул нужно включить HashSet<InternedStr<'_>>.

Со вторым полем есть пара вопросов.

Во-первых, какое именно время жизни нужно вписать для хранимых InternedStr? Технически мы заимствуем память из соседнего поля типа Bump, то есть определение является самоссылающимся типом. Воспользуемся типичным для такой ситуации подходом: будем хранить в множестве InternedStr<'static>, а безопасность это, вообще говоря, некорректного времени жизни будем обеспечивать API, который будет выдавать строки со временем жизни, привязанным к пулу строк.

Во-вторых, что делать с мутабельностью? Выделение новых строк в памяти, очевидно, требует модификации множества, но если мы запишем метод вида

fn alloc(&mut self, s: &str) -> InternedStr<'_> { ... }

, то из-за исключительного заимствования пулом будет невозможно пользоваться, пока возвращённая строка не будет дропнута. Очевидно, здесь требуется внутренняя изменяемость, и так как Bump и так !Sync, достаточно немногопоточного RefCell.

Итого определение выглядит так:

const USIZE_ALIGN: usize = std::mem::align_of::<usize>();

#[derive(Default)]
pub struct Interner<S = std::collections::hash_map::RandomState> {
    strs: RefCell<HashSet<InternedStr<'static>, S>>,
    mem: Bump<{ USIZE_ALIGN }>,
}

Bump параметризован минимальным выравниванием для аллокаций. Выравнивание для usize позволяет нам использовать выровненный доступ к длине в InternedStr::as_str, то есть read вместо read_unaligned.

Запишем реализацию метода для выделения строки:

    pub fn alloc(&self, s: &str) -> InternedStr<'_> {
        ...

Для начала нужно проверить, записана ли вообще уже строка. Если да, то сразу возвращаем её — в этом и состоит смысл интернирования:

        ...
        let mut strs = self.strs.borrow_mut();
        if let Some(&interned) = strs.get(s) {
            return interned;
        }
        ...

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

(тут на самом деле можно попенять авторов, потому что этот метод почему-то возвращает NonNull<u8> вместо гораздо более эргономичного &mut [MaybeUninit<u8>])

Продолжим:

        ...
        let len = s.len();
        let ptr = {
            let alloc_len = len
                .checked_add(USIZE_SIZE)
                .expect("length overflow");
            let layout = std::alloc::Layout::array::<u8>(alloc_len)
                .unwrap()
                .align_to(USIZE_ALIGN)
                .expect("invalid layout");
            self.mem.alloc_layout(layout)
        };
        let s = unsafe {
            ptr.cast::<usize>().write(len);
            ptr.byte_add(USIZE_SIZE)
                .as_ptr()
                .copy_from_nonoverlapping(s.as_ptr(), len);
            InternedStr::from_ptr(ptr)
        };
        ...

Bump возвращает указатель на только что выделенную память и потому память под ним никак не может пересекаться с переданной аргументом строкой, поэтому мы можем безопасно воспользоваться copy_from_nonoverlapping

Теперь осталось лишь сохранить вновь созданную строку и вернуть её:

        ...
        strs.insert(unsafe { s.reborrow_unchecked() });
        s
    }

reborrow_unchecked тут — это метод для принудительной смены времени жизни InternedStr:

impl InternedStr<'_> {
    unsafe fn reborrow_unchecked<'b>(self) -> InternedStr<'b> {
        InternedStr {
            ptr: self.ptr,
            _lt: PhantomData,
        }
    }
}

Как и обещано, безопасность обеспечена API: метод для выделения строки заимствует Interner, поэтому использовать возвращённые строки после дропа Interner нельзя.

Как же решается переиспользование памяти? Через делегацию Bump, главным образом:

impl Interner {
    pub fn clear(&mut self) {
        self.strs.get_mut().clear();
        self.mem.reset();
    }
}

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

И ещё пара моментов. Использование strs.get(s), где s имеет тип &str, а в множестве хранятся значения другого типа InternedStr, возможно только при условии, что InternedStr "похож" на str — или, иными словами, реализовывает Borrow<str>. Реализация делается элементарно через делегацию методу as_str. Также InternedStr, очевидно, нужно уметь хэшировать, и хэш должен считаться так же, как и для соответствующей строки. По этой причине #[derive(Hash)] не подойдёт и нужно писать его реализацию руками:

impl Hash for InternedStr<'_> {
    fn hash<H: hash::Hasher>(&self, state: &mut H) {
        self.as_str().hash(state)
    }
}

Теперь поговорим о недостатках этого решения:

* Решение Кладова может себе позволить хранить интернированные строки, как u32. Моё же решение вынуждено использовать указатель размером минимум с usize, что на большинстве используемых систем — 64-битных — более rustочительно расточительно.
* Достоинство в виде привязки времени жизни к пулу строк одновременно является и недостатком: хранить пул строк и выделенные им строки в одном типе невозможно.
* Из-за выравнивания выделенной памяти под выравнивание usize на каждую строку есть переменный оверхед по памяти от нуля до семи (на 64-битных системах) байтов. С другой стороны, оверхед по памяти также есть и потому, что строки почти наверняка не будут укладываться в чанки тютелька в тютельку в обоих решениях, а также потому, что мапы и так имеют оверхед по памяти для вставки значений in-place, поэтому это навряд ли имеет большое значение. С третьей стороны, моё решение позволяет переиспользовать память, поэтому на практике при многократном использовании пула строк с относительно одинаковым суммарным размером строк в какой-то момент мой подход остановится на одном внутреннем чанке внутри Bump.
* Не совсем понятно, насколько корректной является реализация PartialEq для InternedStr. С одной стороны, интернированные строки используют в том числе для того, чтобы сравнение строк выполнялось за константное время. С другой стороны, сравнение InternedStr, полученных из разных пулов, может дать ложно-отрицательный результат. Это можно пофиксить, добавив ручную реализацию PartialEq, которая будет сравнивать сначала ptr, а в случае их неравенства сравнивать результаты возврата .as_str(), но тогда теряется гарантия константного сравнения. Ловушка тихо неверных результатов или ловушка тихо непроизводительных результатов — что хуже? Если подходить с точки зрения, что API нужно дизайнить для pit of success (как это часто и бывает в std) и корректность превыше всего, то нужно делать сравнение с фоллбеком. Если же подходить с точки зрения производительности как требования к API, то нужно оставлять выведенную реализацию PartialEq. У меня нет ответа на этот вопрос, но сделать сравнение строк из разных пулов можно усложнить, сделав InternedStr инвариантным по лайфтайму.

Вот и всё, как всегда, весь код в гисте.

BTW ну вот какой ещё язык позволяет сделать интёрнер с переиспользованием памяти и гарантиями на корректность ссылок строк? Решения, полагающиеся на сборку мусора, не дают детерминированности

Неожиданно хороший юмор на реддите.

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

...а к другому

#meme про плохой пример

#prog #amazingopensource

TweetNaCl:
a crypto library in 100 tweets

TweetNaCl is the world's first auditable high-security cryptographic library. TweetNaCl fits into just 100 tweets while supporting all 25 of the C NaCl functions used by applications. TweetNaCl is a self-contained public-domain C library, so it can easily be integrated into applications.

#prog #rust #article

Exponential growth continued — cargo-semver-checks 2025 Year in Review

#meme про текст песни

#prog #article

snuffle / salsa / chacha

Небольшой текст про анатомию ChaCha20, крутое свойство этого шифра (которым обладают далеко не все поточные шифры) и про то, как это шифр был рождён из-за, внезапно, #politota соображений.

#meme про нефть

#meme

Environmental storytelling

#prog #article

GSoC 2025: Usability Improvements for the Undefined Behavior Sanitizer

clang поддерживает несколько санитайзеров, в том числе UBSan для отловки неопределённого поведения (с оговорками). Запускать их при этом можно в двух разных режимах. Первый — с добавлением рантайма, который при детектировании UB перед завершением работы программы печатает, что конкретно пошло не так. Второй вариант — без рантайма, в котором при детектировании UB просто исполняется trap-инструкция процессора.

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

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

Не обошлось без костылей из-за ограниченности DWARF:

To accomplish this, we needed to find a place to “stuff” the string in the DWARF DIE tree. Using a
DW_TAG_subprogram was deemed the most straightforward and space-efficient location. This means we create a synthetic DISubprogram which is not a real function in the compiled program; it exists only in the debug info as a container.
<...>
When a trap is hit in the debugger, the debugger retrieves this string from the debug info and shows it as the reason for trapping.

Почти все до сих пор не решены :/ Ну, хотя бы по cross crate analysis и type checking подвижки есть