Сериализация
По сути, мы получили косвенную базу данных в памяти. Далее нам нужно сериализовать её, чтобы проверить, как interning влияет на её постоянное хранение. Кроме того, сериализация — это важный шаг для проверки реальности заявленной экономии места. И, наконец, это ещё одна возможность для дальнейшего сжатия данных.
В Rust для сериализации стандартно используется крейт serde, который мы уже использовали для импортирования входных данных в JSON. Serde изначально имеет поддержку множества форматов благодаря крейтам расширений, поэтому я решил попробовать несколько из них.
Пишем собственные (де)сериализаторы с помощью Serde (0,29%)
Обычно достаточно лишь аннотировать каждый тип в схеме #[derive(Serialize, Deserialize)], и Serde предоставит готовые функции (де)сериализации, благодаря чему этот фреймворк и настолько привлекателен. Однако это будет не очень эффективно для таблицы Interner<T>, содержащей одинаковые объекты дважды (в векторе и хэш-таблице). Кроме того, в документации Serde говорится, что несмотря на то, что Rc (де)сериализируем, если выбрать фичу rc, он копирует внутреннее содержимое при каждой ссылке на него, что неоптимально и семантически неэквивалентно.
struct Interner<T> {
vec: Vec<Rc<T>>,
map: HashMap<Rc<T>, u32>,
}В этом случае мы не хотим сериализировать и вектор объектов, и таблицу поиска индексов: всё состояние интернера можно восстановить из одного вектора. И в самом деле, если мы десериализируем объекты в том же порядке, то получим те же индексы. А Serde как будто упрощает сериализацию последовательности.
Документация Serialize и Serializer быстро приводит нас к решению, а именно к методам serialize_seq() или collect_seq() (первый хорошо работает с итераторами в функциональном стиле).
use serde::{Serialize, Serializer};
impl<T: Serialize> Serialize for Interner<T> {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
// Приказываем Serde сериализовать последовательность элементов.
serializer.collect_seq(self.vec.iter().map(|rc| rc.deref()))
}
}С десериализацией всё сложнее, и это неудивительно, ведь нужно обрабатывать потенциальные ошибки в сериализованном потоке. В конечном итоге, придётся изучить руководство непосредственно на веб-сайте Serde, так как в обычной документации API подробности не объясняются.
Необходимо не только манипулировать трейтами Deserialize и Deserializer, но и написать Visitor, а также (в этом случае) манипулировать SeqAccess. Бойлерплейта намного больше, но в итоге всё работает.
use serde::de::{SeqAccess, Visitor};
use serde::{Deserialize, Deserializer};
impl<'de, T> Deserialize<'de> for Interner<T>
where
T: Eq + Hash + Deserialize<'de>,
{
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: Deserializer<'de>,
{
// Приказываем Serde десериализовать последовательность элементов при помощи указанного visitor.
deserializer.deserialize_seq(InternerVisitor::new())
}
}
// Visitor для создания Interner<T>.
struct InternerVisitor<T> {
// Этот visitor не хранит состояние, но Rust требует использовать обобщённый параметр T.
_phantom: PhantomData<fn() -> Interner<T>>,
}
impl<T> InternerVisitor<T> {
fn new() -> Self {
Self {
_phantom: PhantomData,
}
}
}
impl<'de, T> Visitor<'de> for InternerVisitor<T>
where
T: Eq + Hash + Deserialize<'de>,
{
// Сообщаем Serde, что на выходе будет Interner.
type Value = Interner<T>;
// Сообщение об ошибке, отображаемое, если входной поток не содержит последовательности из Ts.
fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
formatter.write_str("a sequence of values")
}
// Обратный вызов, совершаемый Serde с последовательностью элементов.
fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
where
A: SeqAccess<'de>,
{
// Serde может дать нам подсказку о количестве элементов в последовательности.
let mut interner = match seq.size_hint() {
None => Interner::default(),
Some(size_hint) => Interner {
vec: Vec::with_capacity(size_hint),
map: HashMap::with_capacity(size_hint),
references: 0,
},
};
// Cобираем элементы в цикле и возвращаем Interner.
while let Some(t) = seq.next_element()? {
interner.push(t);
}
Ok(interner)
}
}
// Для полноты создаём новую функцию push(), немного более эффективную, чем intern().
impl<T: Eq + Hash> Interner<T> {
/// Безусловно записываем значение без валидации того, что оно уже интернировано.
fn push(&mut self, value: T) -> u32 {
let id = self.vec.len();
assert!(id <= u32::MAX as usize);
let id = id as u32;
let rc: Rc<T> = Rc::new(value);
self.vec.push(Rc::clone(&rc));
self.map.insert(rc, id);
id
}
}Вот сравнение форматов сериализации на этом этапе, отсортированное по размеру закодированных данных. Явным победителем оказался Postcard с 3,2 МБ, что намного меньше, чем JSON с 65 МБ в красивом виде или 26 МБ в минифицированном виде (коммит b5013e6).
Формат | Байты | Относительный размер | Время кодирования | Время декодирования |
|---|---|---|---|---|
Postcard | 3275869 | 0.29% | 17 ms | 16 ms |
Bincode | 5437330 | 0.48% | 16 ms | 24 ms |
CBOR | 17484567 | 1.54% | 56 ms | 128 ms |
JSON | 26485131 | 2.33% | 74 ms | 118 ms |
JSON (pretty) | 65026281 | 5.72% | 152 ms | 135 ms |
Интересно также сравнить время кодирования и декодирования, так как более компактные форматы обычно и быстрее обрабатываются. Впрочем, результаты стоит воспринимать с долей скепсиса, потому что это не бенчмарк, а единственный пример данных на моей машине и без использования оптимизированных библиотек наподобие simd_json.
Сжатие и борьба с Linux pipes (0,05%)
После сериализации базы данных в байты можно применить к ним стандартные операции сжатия. Даже после interning стоит ожидать какой-то доли избыточности: например, сообщения о нарушениях движения составляются по шаблонам, в которых варьируются только некоторые детали.
Мне не особо хотелось изучать различные библиотеки сжатия Rust, потому что я думал, что в этом эксперименте будет проще породить команду. И в самом деле, тип Command в стандартной библиотеке Rust позволяет запускать другие программы, безопасным образом передавая им аргументы и входные данные, а также получать вывод. В принципе, следует конфигурировать Stdio::piped() для взаимодействия с stdin/stdout/stderr дочернего процесса, и на этом всё... По крайней мере, так я думал.
// Наивная реализация, которая не заработала (межпроцессная взаимная блокировка).
fn gzip_compress(input: &[u8]) -> Result<Vec<u8>, Box<dyn std::error::Error>> {
let compress = Command::new("gzip")
.arg("-c") // Сжатие в stdout.
.arg("-6") // Уровень сжатия.
.stdin(Stdio::piped())
.stdout(Stdio::piped())
.stderr(Stdio::null())
.spawn()?;
compress.stdin.as_mut().expect("Failed to open stdin").write_all(input)?;
let output = compress.wait_with_output()?;
if !output.status.success() {
/* Возвращает ошибку */
}
Ok(output.stdout)
}Эта наивная реализация работала с простыми примерами с короткими входными данными, но, похоже, приводила к взаимной блокировке при попытке сжатия более объёмных данных!
Разгадка кроется в руководстве Linux по конвейерам. Когда родительский и дочерний процессы общаются через stdin/stdout/stderr, это происходит через так называемый pipe (конвейер). При этом ядро предоставляет буфер, в который один процесс может выполнять запись, а другой процесс может читать.
Однако чтобы не исчерпывать ресурсы системы, буфер имеет ограниченный размер. В частности, /proc/sys/fs/pipe-max-size задаёт максимальный размер (в байтах) одного конвейера, который в моей системе равен 1 МиБ. Кроме того, в /proc/sys/fs/pipe-user-pages-hard и /proc/sys/fs/pipe-user-pages-soft задаётся максимальное количество страниц, которое может создавать один пользователь конвейера (среди всех процессов). На моей машине это значение равно 64 МиБ.
$ cat /proc/sys/fs/pipe-max-size
1048576
$ cat /proc/sys/fs/pipe-user-pages-hard
0
$ cat /proc/sys/fs/pipe-user-pages-soft
16384Вернёмся к вызову gzip: проблема в том, что если входные данные слишком велики, то вызов write_all(input) будет заблокирован, пока дочерний процесс (gzip) считывает данные из конвейера. Процесс gzip действительно начинает чтение из него, но также стремится максимально скоро записывать в свой стандартный вывод сжатый вывод (чтобы ограничить используемую память). Однако при наивной реализации мой родительский процесс не читает этот вывод, пока не завершится вся запись входных данных. Поэтому сжатый вывод будет тоже заполнять этот конвейер.
В какой-то момент мы оказываемся в ситуации, когда мой родительский процесс оказывается заблокирован на записи новых входных данных в конвейер stdin (ожидая, пока их считает gzip), а дочерний процесс gzip заблокирован на записи нового сжатого вывода в конвейер stdout (ожидая, пока его считает родительский процесс). Иными словами, возникает межпроцессная взаимная блокировка (deadlock)!
С этим ограничением нужно быть очень аккуратным: даже если вы думаете, что вам не понадобится записывать больше 1 МиБ (или того значения, которое указано в /proc/sys/fs/pipe-max-size вашей системы), общий лимит на одного пользователя может ограничить конвейеры только одной страницей (после достижения /proc/sys/fs/pipe-user-pages-soft), которая обычно равна 4 КиБ, то есть намного меньше, чем стандартный 1 МиБ.
Чтобы решить эту проблему, надо сделать так, чтобы несжатые входные данные и сжатый вывод записывались одновременно, то есть использовать потоки. Мы всё равно сможем пользоваться удобными функциями write_all() и read_to_end(), если они будут находиться в параллельных потоках.
В конечном итоге я создал вспомогательную функцию для автоматизации этого паттерна записи всего среза входных данных и чтения всего вывода. Обратите внимание на использование std::thread::scope(), позволяющего перехватывать входные срезы с нестатическими сроками жизни.
#![feature(exit_status_error)]
fn io_command(mut child: Child, input: &[u8]) -> Result<Vec<u8>, Box<dyn std::error::Error>> {
std::thread::scope(|s| -> Result<Vec<u8>, Box<dyn std::error::Error>> {
let mut stdin = child.stdin.take().expect("Failed to open stdin");
let mut stdout = child.stdout.take().expect("Failed to open stdout");
let input_thread = s.spawn(move || -> std::io::Result<()> {
eprintln!("Writing {} bytes...", input.len());
stdin.write_all(input)?;
drop(stdin);
Ok(())
});
let output_thread = s.spawn(move || -> std::io::Result<Vec<u8>> {
eprintln!("Reading bytes...");
let mut output = Vec::new();
stdout.read_to_end(&mut output)?;
Ok(output)
});
eprintln!("Waiting for child...");
child.wait()?.exit_ok()?;
input_thread.join().expect("Failed to join input thread")?;
let output = output_thread
.join()
.expect("Failed to join output thread")?;
Ok(output)
})
}Вернёмся к нашей теме: я выполнил бенчмарки нескольких популярных алгоритмов сжатия. Они показали. что разница размеров между форматами обычно становится меньше после сжатия. На текущий момент мы достигли порога 2000-кратного уменьшения размера для самых компактных форатов: с 1,1 ГБ до 530 КБ для данных за май 2024 года (коммит b7281f5).
Формат | Сериализация | gzip -6 | brotli -6 | xz -6 | ||||
|---|---|---|---|---|---|---|---|---|
Postcard | 3275869 | 0.29% | 861917 | 0.08% | 721120 | 0.06% | 539200 | 0.05% |
Bincode | 5437330 | 0.48% | 893271 | 0.08% | 700194 | 0.06% | 529996 | 0.05% |
CBOR | 17484567 | 1.54% | 1187575 | 0.10% | 826739 | 0.07% | 615124 | 0.05% |
JSON | 26485131 | 2.33% | 1253219 | 0.11% | 916683 | 0.08% | 736036 | 0.06% |
JSON (красивый) | 65026281 | 5.72% | 1563418 | 0.14% | 1006035 | 0.09% | 958624 | 0.08% |
Однако схожие размеры после сжатия не означают что можно просто использовать JSON и забыть об этом: скорости (де)сериализации и (де)компрессии выше при более оптимизированных форматах наподобие Postcard!
Формат | Сериализация | gzip -6 | brotli -6 | xz -6 | ||||
|---|---|---|---|---|---|---|---|---|
encode | decode | encode | decode | encode | decode | encode | decode | |
Postcard | 22 ms | 27 ms | 88 ms | 21 ms | 144 ms | 18 ms | 583 ms | 37 ms |
Bincode | 9 ms | 24 ms | 166 ms | 28 ms | 191 ms | 19 ms | 1111 ms | 39 ms |
CBOR | 72 ms | 131 ms | 189 ms | 63 ms | 230 ms | 36 ms | 3255 ms | 51 ms |
JSON | 72 ms | 100 ms | 233 ms | 96 ms | 449 ms | 44 ms | 3314 ms | 60 ms |
JSON (красивый) | 137 ms | 129 ms | 376 ms | 180 ms | 441 ms | 74 ms | 2934 ms | 81 ms |
Ещё один аспект, не охваченный моим экспериментом — это влияние на размер кода: я ожидаю, что более простые форматы скомпилируются в более компактный код. Учитывайте это, особенно если вы развёртываете код для встроенных систем или в WebAssembly для веб-сайта.
Кодирование в кортежи
При более внимательном изучении сериализованного вывода я заметил в выводе JSON и CBOR множество строк _phantom.
{"id": 11, "_phantom": null}Что-то наподобие Interned<T>, который по моим ожиданиям должен быть сериализоваться как простой integer, занимал слишком много места.
struct Interned<T> {
id: u32,
_phantom: PhantomData<fn() -> T>,
}По умолчанию Serde сериализует каждую struct как map, что вызывает две проблемы:
имена полей сериализуются как ключи в map,
типы нулевого размера наподобие
PhantomDataсериализуются, хотя они и не содержат никакой информации и их можно тривиально воссоздать.
Это поведение по умолчанию может быть полезно, если ваши типы эволюционируют со временем (поля добавляются, удаляются или переименовываются) и вы хотите сохранять некий уровень «стандартной» совместимости, но это уже проектное решение1. Однако в моём случае абстракция Interned<T> использовалась настолько часто, что обеспечивала большую избыточность.
1. На мой взгляд, такой подход, ставший популярным благодаря форматам наподобие Protocol Buffers, может, к сожалению, создать иллюзию версионности «из коробки». Если вы меняете семантику системы, то вам почти всегда приходится писать дополнительный код, чтобы обеспечить совместимость между версиями. Версионность «из коробки» может предотвратить явные сбои в кратковременной перспективе, но в то же время способствует тому, что вы можете забыть написать нужный код совместимости, а также тому, что появятся более тонкие различия, вызванные игнорированием неизвестных, но важных полей. В долговременной перспективе может вызывать ошибки, повреждение данных, нестабильности или даже прочие сбои.
Изучив вопрос, я нашёл пару issue, а также обсуждение, начатое мейнтейнером Serde, которое в итоге свелось к тому, что лучше сериализовать struct как кортеж, а не как map. Учитывая то, что у кортежей нет имён полей, это должно решить проблему. Этот запрос фичи так и не был реализован в самом крейте serde, однако в отдельном крейте serde_tuple есть макросы derive Serialize_tuple и Deserialize_tuple.
use serde_tuple::{Deserialize_tuple, Serialize_tuple};
#[derive(Serialize_tuple, Deserialize_tuple)]
struct Interned<T> {
id: u32,
_phantom: PhantomData<fn() -> T>,
}Это решает первую проблему (коммиты a9924e9 и cec5359). Однако PhantomData всё равно продолжали встречаться в сериализованном выводе как значения null.
[11, null]Учитывая частоту использования типа Interned, я в конечном итоге снова написал особый сериализатор.
impl<T> Serialize for Interned<T> {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
serializer.serialize_u32(self.id)
}
}Для соответствующих форматов (CBOR и JSON) эти оптимизации уменьшили закодированный размер на 72-75%). После сжатия снижение размера оказывалось более скромным, в пределах 11-33% (коммит 356bc0a).
Формат | Сериализация | gzip -6 | brotli -6 | xz -6 |
|---|---|---|---|---|
Postcard | 3275869 | 861917 | 721120 | 539200 |
Bincode | 5437330 | 893271 | 700194 | 529996 |
CBOR | 4475821 (-74%) | 955541 (-20%) | 731878 (-11%) | 535068 (-13%) |
JSON | 6560658 (-75%) | 1005689 (-20%) | 777507 (-15%) | 545832 (-26%) |
JSON (pretty) | 18168838 (-72%) | 1162250 (-26%) | 890102 (-12%) | 639072 (-33%) |
Стоит отметить, что такие форматы, как Postcard и Bincode, и так по умолчанию выполняют эту оптимизацию, используя то, что они не самоописываемые. Благодаря использованию крейта serde_tuple можно отказаться от гарантий самоописания и других форматов наподобие JSON, так как для обмена данными без их повреждения отправитель и получатель должны согласовать схему (то есть конкретный порядок полей в каждой struct).
Возвращаемся к оптимизации множеств
В предыдущей части поста я говорил, что множества объектов можно лучше унифицировать, отсортировав их. Наивное решение (используемое по умолчанию) заключается в их сериализации как списка интернированных ID. Однако на практике эти ID часто идут последовательно, потому что объекты были созданы примерно в одно и то же время. Например, все нарушения, происходившие в один день, будут встречаться в таблице Interned<Disruption> рядом друг с другом.
[0, 70, 72, 73, 74, 75, 77, 78, 79, 80, 81]Поэтому мы можем не сериализовать ID напрямую, а использовать дельта-кодирование: сериализовать каждый ID как разность с предыдущим ID.
[0, 70, 2, 1, 1, 1, 2, 1, 1, 1, 1]Это выгодно по двум причинам:
в популярных форматах сериализации используется кодирование переменной длины, то есть малые числа кодируются в меньшее количество байтов, чем большие,
если разности по большей части оказываются малыми числами, то должно возникнуть больше избыточности, которым должны воспользоваться алгоритмы сжатия.
Дельта-кодирование можно достаточно просто реализовать в каждом множестве при помощи модифицированного сериализатора Serde.
struct InternedSet<T> {
set: Box<[Interned<T>]>,
}
impl<T> Serialize for InternedSet<T> {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
let mut prev = 0;
serializer.collect_seq(self.set.iter().map(|x| {
let id = x.id();
let diff = id - prev;
prev = id;
diff
}))
}
}Хотя дифференциальное кодирование не влияет на формат Bincode (который кодирует целые числа с фиксированным размером), для остальных форматов сериализованный размер уменьшился на 9-19%). После сжатия размер в случае gzip и brotli уменьшился на 8-16%, а для xz — на 4-8% (коммит 4ea388f).
Формат | Сериализация | gzip -6 | brotli -6 | xz -6 |
|---|---|---|---|---|
Postcard | 2966573 (-9%) | 746478 (-13%) | 624801 (-13%) | 499524 (-7%) |
Bincode | 5437330 (=) | 821573 (-8%) | 631655 (-10%) | 506956 (-4%) |
CBOR | 3688285 (-18%) | 814306 (-15%) | 634705 (-13%) | 493064 (-8%) |
JSON | 5317810 (-19%) | 841046 (-16%) | 708651 (-9%) | 504196 (-7%) |
JSON (pretty) | 15018136 (-17%) | 988869 (-15%) | 820774 (-8%) | 590380 (-7%) |
На практике, мы можем совершить ещё один шаг: дельты не просто были малыми, но и часто имели значение 1 при длинных последовательностях идущих по порядку элементов. Поэтому я решил добавить ещё кодирование длин серий. Стоит отметить, что поскольку ID отсортированы, дельты гарантированно будут неотрицательными, благодаря чему становится возможным сдвоенное дельта-кодирование/RLE: интерпретируем отрицательное число n как серию из −n последовательных элементов, а неотрицательное число — как дельту от предыдущего элемента.
оригинал: [0, 70, 72, 73, 74, 75, 77, 78, 79, 80, 81]
оптимизированный: [0, 70, 2, -3, 2, -4]impl<T> Serialize for InternedSet<T> {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
// Скомбинировали дельта-кодирование + RLE.
let mut rle_encoded = Vec::with_capacity(self.set.len());
let mut prev: Option<u32> = None;
let mut streak: i32 = 0;
for x in &self.set {
let id = x.id();
let diff = id - prev.unwrap_or(0);
if prev.is_some() && diff == 1 {
streak += 1;
} else {
if streak != 0 {
rle_encoded.push(-streak);
streak = 0;
}
rle_encoded.push(diff as i32);
}
prev = Some(id);
}
if streak != 0 {
rle_encoded.push(-streak);
}
serializer.collect_seq(rle_encoded)
}
}Результаты последней оптимизации были неоднозначными: хотя закодированный размер снизился на 4-11%, сжатый размер остался почти неизменным – в пределах ±2% (коммит d098356).
Формат | Сериализация | gzip -6 | brotli -6 | xz -6 |
|---|---|---|---|---|
Postcard | 2832574 (-5%) | 751517 (+1%) | 632425 (+1%) | 504388 (+1%) |
Bincode | 4855254 (-11%) | 825177 (+0%) | 643860 (+2%) | 516736 (+2%) |
CBOR | 3539237 (-4%) | 813895 (-0%) | 637836 (+0%) | 495860 (+1%) |
JSON | 5103171 (-4%) | 846290 (+1%) | 714886 (+1%) | 510584 (+1%) |
JSON (pretty) | 13361128 (-11%) | 983777 (-1%) | 823720 (+0%) | 587044 (-1%) |
Окончательный результат: легковесная база данных только для добавления
Чтобы воссоздать эти результаты, можно найти мой код на GitHub. Я использовал данные RATP Status из коммита ef028cc (файлы в папке datas/json/).
git init
git remote add origin https://github.com/wincelau/ratpstatus
git fetch --depth 1 origin ef028cce567b6ce9183a185e699206e0f483b99d
git checkout FETCH_HEADКонцептуально, interning — это простая методика, однако мы уже увидели, что она может привести ко множеству вариантов и оптимизаций. Обычно она применяется к строкам, но на практике мы выиграли от interning всевозможных структур данных.
К концу этой статьи мы опосредованно создали одну из самых простых архитектур реляционных баз данных (без части, относящейся к запросам/SQL). Она обладает некоторыми ограничениями, приемлемыми при работе с временными последовательностями:
только добавление данных: мы не можем ни изменять, ни удалять имеющиеся объекты,
в памяти: сериализованный вид не поддерживает произвольного доступа к значению по индексу, поэтому нам нужно десериализовать всю базу данных в памяти,
один писатель: для выполнения инкремента при интернировании нового объекта без синхронизации.
Также относительно легко должно оказаться добавление инкрементных обновлений: учитывая, что таблицы interning предназначены только для добавления данных с инкрементными индексами, можно с лёгкостью создать снэпшот базы данных, а позже создать diff, содержащий только новые объекты, добавленные после снэпшота. Тогда поверх можно реализовать множественные узлы-читатели, и таким образом мы получим базу данных с дублированием: писатель время от времени будет вещать читателям инкрементные обновления.
А следует ли на практике использовать один из бесчисленного количества крейтов для interning, или их следует писать самостоятельно? Ответ зависит от того, что вы хотите сделать!
Вам важна очень оптимизированная структура в памяти для строк? Возможно, вам идеально подойдёт показанное мной наивное представление Rc<String>. Вас устроит единственный глобальный интернер или вы хотите манипулировать локальными аренами интернеров, как показано в этом посте? Вам нужно сериализовать данные, и если да, то должна ли сериализация быть компактной?
Вы можете сами придумать паттерн для interning, даже не зная его названия и того, что его реализует множество библиотек: это тоже абсолютно приемлемо! Надеюсь, этот пост поможет вам оценить существующие библиотеки и принять осознанное решение о том, нужно ли заново изобретать велосипед.
Приложение: оптимизируем функцию interning
Пользователи Reddit предложили мне два способа улучшения реализации interning.
watsonborn порекомендовал использовать
HashMap::entry()API, чтобы не искать значение дважды при его вставке в интернер.angelicosphosphoros порекомендовал использовать для манипуляций со строками
Rc<str>вместоRc<String>.
Должен сказать, что эта статья не посвящена созданию готовой к продакшену библиотеки interning, в первую очередь я делаю упор на экономию размера, но мне любопытно, как можно реализовать эти рекомендации.
Непосредственное применение HashMap::entry() не будет оптимальным, потому что он требует передачи полного ключа, то есть всегда понадобится создавать Rc<T> , даже если мы просто выполняем поиск (при котором будет достаточно передачи &T).
impl<T: Eq + Hash> Interner<T> {
fn intern(&mut self, value: T) -> u32 {
// Функция entry() требует создания Rc<T>.
let rc: Rc<T> = Rc::new(value);
*self.map.entry(Rc::clone(&rc)).or_insert_with(|| {
let id = self.vec.len();
assert!(id <= u32::MAX as usize);
self.vec.push(rc);
id as u32
})
}
}Однако существует более эффективный HashMap::raw_entry_mut() API, доступный в nightly-фиче hash_raw_entry (или в крейте hashbrown стабильного Rust). Этот API позволяет начала поискать элемент с тем, что заимствует ключ (в нашем случае ссылка &T), и позже развернуть полный ключ Rc<T> только в случае, если элемент пуст. Это максимальная оптимизация, доступная для map API в Rust.
#![feature(hash_raw_entry)]
impl<T: Eq + Hash> Interner<T> {
fn intern(&mut self, value: T) -> u32 {
let (_, id) = self
.map
.raw_entry_mut()
// Здесь мы передаём &T для поиска.
.from_key(&value)
.or_insert_with(|| {
let id = self.vec.len();
assert!(id <= u32::MAX as usize);
let rc: Rc<T> = Rc::new(value);
self.vec.push(Rc::clone(&rc));
// Здесь мы передаём Rc<T> для вставки.
(rc, id as u32)
});
*id
}
}Что касается второй рекомендации, то с ней не всё так просто: хотя Rc<str> занимает меньше места в памяти и избегает уровня разыменования указателя, преобразование из String в Rc<str> требует клонирования всего содержимого строки. Однако затраты на это клонирование возникают только при вставке новых строк, поэтому можно надеяться, что они будут амортизированы с запасом в случае многократного повторения одинаковых строк (в чём и заключается смысл interning).
Или же можно использовать что-то типа крейта CompactStr (выполняющего оптимизацию малых строк) для экономии места в памяти.
Но что потребуется для поддержки Interner<str>? Сначала нам нужно добавить повсюду явное ограничение T: ?Sized, так как срез строки str — это динамический тип. Во-вторых, мы не можем вызывать функцию с обычным параметром T = str, потому что он динамический. Вместо этого, например, можно использовать трейты преобразования Borrow и Into, чтобы создать более гибкий обобщённый API.
Если объединить две рекомендации, то функция interning принимает показанный ниже вид. Вместо получения T она принимает любой параметр, который (1) можно заимствовать как &T (чтобы искать его в map) и (2) можно преобразовать в Rc<T> (чтобы вставлять его в map).
impl<T: ?Sized + Eq + Hash> Interner<T> {
fn intern(&mut self, value: impl Borrow<T> + Into<Rc<T>>) -> u32 {
let (_, id) = self
.map
.raw_entry_mut()
// Поиск принимает любой тип, который можно заимствовать как &T.
.from_key(value.borrow())
.or_insert_with(|| {
let id = self.vec.len();
assert!(id <= u32::MAX as usize);
let id = id as u32;
// Вставка принимает любой тип, который можно преобразовать в Rc<T>.
let rc: Rc<T> = value.into();
self.vec.push(Rc::clone(&rc));
(rc, id)
});
*id
}
}Это позволяет передавать Interner<str> широкий спектр типов: заимствованный срез строки &str, принадлежащую строку String, boxed-срез строки Box<str>, срез строки с копированием при записи Cow<'_, str>, и Rc<str> и так далее. Однако стоит учитывать, что преобразование большинства этих типов в Rc<str> (для пути вставки) вызовет клонирование содержимого строки.
Это изменение также потребовало изменений в логике оценки размера и десериализации, подробности приведены в коммите 279e2cb.
And no, RATP status isn’t implemented in Rust. A PHP website can be blazingly fast too! ↩
In my opinion, this approach, made popular by formats like Protocol Buffers, may unfortunately give a false sense of “out-of-the-box” versioning. If you’re changing the semantics of your system, you almost always need to write additional code to ensure compatibility between the various versions. Out-of-the-box versioning can prevent outright outages in the short term, but also makes it easier to forget writing the needed compatibility code and to introduce more subtle differences due to ignoring unknown but important fields. This can cause errors, data corruption, instabilities or even other outages in the longer term. ↩
