На курсах по программированию связные списки преподаются как одна из фундаментальных структур данных, но на самом деле такие списки чаще встречаются на технических собеседованиях, чем в реальных проектах.
В этом посте будет продемонстрирован практический пример, в котором связный список существенно обгоняет Vec. Мы напишем простую библиотеку для валидации данных, которая будет показывать, где именно находится ошибка в невалидном вводе. Здесь будет наглядно показано, как можно использовать связные списки при обходе графа.
В этом посте отражены в основном собственные изыскания и ошибки автора, имевшего дело с крейтами jsonschema, поэтому пост не претендует на полное руководство по связным спискам, а скорее призван донести идею о том, как они могут использоваться на практике.
Мы начнём с азбучной реализации, а потом будем постепенно её оптимизировать и рассматривать, как это отразится на производительности.
От читателя поста ожидается, что он на базовом уровне понимает Rust, обычные структуры данных, а также концептуально представляет, как выделяется память (в стеке и куче).
Дополнение (14.05.2024): Я учёл поступившую обратную связь и подчеркнул, какие идеи объективно плохи, прояснил некоторые отступления и удалил идею о imbl.
Чтобы было проще прослеживать этапы реализации и исследовать код, отсылаю вас к репозиторию, сопровождающему этот пост.
Валидационный API
Наша библиотека минималистична, семантически соответствует схеме JSON:
use serde_json::json; fn main() -> Result<(), Box<dyn std::error::Error>> { jsonschema::validate( // Образец JSON для валидации &json!({ "name": "John", "location": { "country": 404 } }), // Схема JSON &json!({ "properties": { "name": { "type": "string" }, "location": { "properties": { "country": { "type": "string" } } } } }), ).expect_err("Should fail"); Ok(()) }
В данном примере 404 — не строка, и этот код должен приводить к примерно такой ошибке:
404 is not of type ‘string’ at /location/country | | | | --------------- | | | Location within the JSON instance | Failing value
Эта библиотека и изложенные в статье идеи оптимизации выведены на базе работы с моим крейтом jsonschema.
Весь процесс валидации сводится к обходу графа. Экземпляр, подаваемый на вход, обходится в соответствии с правилами, заложенными в схеме. На любом из этапов обхода следует знать, где именно мы находимся в экземпляре JSON, чтобы, если возникнет ошибка, информативно её описать.
Мы в первую очередь стремимся реализовать отслеживание местоположения, минимизировав негативное воздействие этой операции на производительность библиотеки.
Не слишком углубляясь в детали реализации Validator и Node, рассмотрим процесс валидации в упрощённом виде, без отслеживания местоположения:
type ValidationResult = Result<(), ValidationError>; fn validate(instance: &Value, schema: &Value) -> ValidationResult { Validator::new(schema) .expect("Invalid schema") .validate(instance) } struct ValidationError { message: String, } impl Validator { /// Проверяем экземпляр JSON при помощи этого валидатора fn validate(&self, instance: &Value) -> ValidationResult { self.node.validate(instance) } } trait Node { fn validate(&self, instance: &Value) -> ValidationResult; } impl Node for Properties { fn validate(&self, instance: &Value) -> ValidationResult { if let Value::Object(object) = instance { // Перебираем свойства и валидируем их, если они имеются. for (key, value) in &self.properties { if let Some(instance) = object.get(key) { // Делегируем проверку дочернему валидатору. value.validate(instance)?; } } } Ok(()) } } impl Node for Type { fn validate(&self, instance: &Value) -> ValidationResult { // ... } }
Функция validate на основе предоставленной схемы создаёт новый экземпляр Validator (это тоже граф), а затем вызывает его метод validate внутри экземпляра JSON. Типаж Node определяет метод validate, который должен быть реализован в каждом правиле валидации.
Притом, что в этой версии просто выдаются сообщения об ошибках, а местоположение ошибок не отслеживается, оно служит верхней планкой для последующих оптимизаций в рамках функции validate.
Расстановка бенчмарков
Чтобы гарантировать, что применяемые оптимизации будут релевантны в рамках типичных сценариев, в которых используется эта библиотека, возьмём экземпляры разного размера, причём как валидные, так и невалидные.
В этой схеме содержится 10 уровней вложенности, и из ключевых слов мы целенаправленно употребляем в ней лишь ключевые слова properties и type — их вполне достаточно, чтобы продемонстрировать издержки поведения path-tracking (отслеживания пути). Зато такой подход помогает упростить бенчмарки и сосредоточиться на исследовании производительности, а не на семантике схемы JSON Schema как таковой. Стоит отметить, что и с другими ключевыми словами поведение path-tracking практически не изменится.
{ "properties":{ "another":{ "type":"string" }, "inner":{ "properties":{ "another":{ "type":"string" }, "inner":{ "properties":{ // И так далее вплоть до 10 уровня } } } } } }
В разных экземплярах 0, 5 или 10 уровней вложенности, в соответствии со структурой схемы. В валидных экземплярах на самом глубоком уровне присутствует строковое значение для свойства "another", а в невалидных экземплярах — целое чис��о.
// Валидный - 5 уровней { "inner":{ "inner":{ "inner":{ "inner":{ "another":"hello" } } } } } // Невалидный - 5 уровней { "inner":{ "inner":{ "inner":{ "inner":{ "another":1 } } } } }
Чтобы сосредоточиться на производительности процесса валидации как такового, мы жёстко закодируем схему в Validator::new, а Validator будем собирать однократно, а затем переиспользовать.
Давайте измерим производительность при помощи criterion, для этого выполним следующую процедуру валидации:
const NUMBER_OF_ITERATIONS: usize = 10000; fn benchmarks(c: &mut Criterion) { // сниппет ... for instance in &benchmark.instances { c.bench_with_input( BenchmarkId::new(instance.kind, &instance.name), &instance.value, |b: &mut Bencher, value| { b.iter(|| { for _ in 0..NUMBER_OF_ITERATIONS { let _ = validator.validate(value); } }); }, ); } }
Числа в этих микробенчмарках не являются абсолютными и могут варьироваться в зависимости от аппаратного обеспечения и окружения. Как правило, все наблюдаемые изменения объяснимы по анализу трассировки стеков, отображаемой на флеймграфах, но лучше всегда проверять бенчмарки самостоятельно.
Плохая идея № 1: клонировать Vec
Начнём со сбора уже обойдённых сегментов пути, которые будем складывать в векторе и добавлять новый сегмент всякий раз, когда валидация пойдёт на уровень ниже:
fn validate(&self, instance: &Value) -> ValidationResult { // Начнём с пустого вектора self.node.validate(instance, vec![]) } trait Node { // Добавим параметр `path`, по которому будем отслеживать, где сейчас находимся в экземпляре JSON fn validate(&self, instance: &Value, path: Vec<&str>) -> ValidationResult; } impl Node for Properties { fn validate(&self, instance: &Value, path: Vec<&str>) -> ValidationResult { if let Value::Object(object) = instance { for (key, value) in &self.properties { if let Some((key, instance)) = object.get_key_value(key) { // КЛОНИРУЕМ! let mut path = path.clone(); path.push(key); value.validate(instance, path)?; } } } Ok(()) } } impl Node for Type { fn validate(&self, instance: &Value, path: Vec<&str>) -> ValidationResult { match (self, instance) { // ... Сравним тип `instance` с ожидаемым типом _ => Err(ValidationError::new( format!("{instance} is not of type '{self}'"), // Преобразуем путь в ит��ратор path.into_iter(), )), } } }
Теперь этот путь хранится в структуре ValidationError:
struct ValidationError { message: String, /// Где именно находится ошибка в экземпляре, полученном на вход. location: Vec<String>, } impl ValidationError { /// Создаём новую ошибку валидации. fn new( message: impl Into<String>, // Принимаем итератор и преобразуем его в `Vec<String>` location: impl Iterator<Item = impl Into<String>>, ) -> Self { Self { message: message.into(), location: location.map(Into::into).collect(), } } }
Если вы уже имеете опыт программирования на Rust, то, вероятно, узнаёте вызов clone() как типичное «решение» проблем с временами жизни и мутабельностью. Притом, что в некоторых ситуациях такое решение приемлемо (в зависимости от того, какие у вас ограничения по производительности и требования к поддержке продукта), зачастую такой вызов сигнализирует, что в коде есть место для оптимизации. Давайте воспользуемся здесь такой возможностью.
Примечание: в таблице та идея, которую мы рассматриваем сейчас, сравнивается с более ранней.
Клонирование — в принципе плохая идея, но на практике такой подход встречается часто, когда от разработчика требуется решить задачу «дёшево и сердито», либо когда о других вариантах он просто не знает. Я и сам неоднократно так делал.
Давайте визуализируем самый медленный «валидный» бенчмарк при помощиcargo flamegraph, чтобы было понятнее, что происходит. Как и ожидалось «перевыделение памяти» отражается на диаграмме:
Такие диаграммы, называемые «флеймграфами», отлично подходят для трассировки стека, подробнее см. здесь.
Нормальная идея №2: переиспользовать выделенную память
Правда, как вы уже могли заметить, совсем не обязательно клонировать данные. Что если менять один и тот же вектор, заталкивая в него сегменты и выталкивая их из него по мере обхода?
trait Node { fn validate<'a>( &self, instance: &'a Value, path: &mut Vec<&'a str>, ) -> ValidationResult; } impl Node for Properties { fn validate<'a>( &self, instance: &'a Value, path: &mut Vec<&'a str>, ) -> ValidationResult { // ... path.push(key); value.validate(instance, path)?; path.pop(); // ... } } impl Node for Type { fn validate<'a>( &self, instance: &'a Value, path: &mut Vec<&'a str>, ) -> ValidationResult { match (self, instance) { // ... Compare `instance` type with expected type _ => Err(ValidationError::new( format!("{instance} is not of type '{self}'"), path.iter().copied(), )), } }
Аннотации времени жизни ('a) требуются здесь потому, что параметр пути — это изменяемая ссылка на Vec, содержащий ссылки на параметр instance. Время жизни 'a гарантирует, что ссылки в path не переживут тот instance, на который указывают.
Действительно, пользуясь &mut Vec , можно значительно повысить производительность по сравнению с упрощённым подходом. В данном случае мы многократно используем один и тот же участок памяти, выделенный из кучи, а не создаём множество клонов. Правда, этот подход немного сложнее с точки зрения учёта данных, а также требует дополнительно аннотировать время жизни.
Именно эту идею возьмём за основу при сравнении. Она подобна той, которую я исходно зафиксировал в моём крейте jsonschema.
Идея №3, получше: связный список
Правда, а есть ли вообще необходимость выделять память кучи под вектор при обходе? Подумайте: для каждого узла во входном значении, который требуется обойти, делается соответствующий вызов функции validate со своим собственным стековым кадром. Поэтому фрагменты пути могут храниться в этих стековых кадрах, и полностью отпадает необходимость выделять память из кучи.
Сделаем шаг назад и рассмотрим эту ситуацию под немного иным углом — так станут нагляднее некоторые идеи, которые не слишком очевидны на низком уровне.
Если мы храним все сегменты в стеке, и в какой-то момент происходит ошибка, все предыдущие сегменты можно отследить. В рамках такой работы требуется сцепить все сегменты, чтобы они образовали путь, и при необходимости собирать их. По описанию напоминает связный список:
/// Узел в связном списке, представляющий собой указатель JSON. struct JsonPointerNode<'a, 'b> { segment: Option<&'a str>, parent: Option<&'b JsonPointerNode<'a, 'b>>, } impl<'a, 'b> JsonPointerNode<'a, 'b> { /// Создать корневой узел указателя JSON const fn new() -> Self { JsonPointerNode { segment: None, parent: None, } } /// Добавить новый сегмент к указателю JSON. fn push(&'a self, segment: &'a str) -> JsonPointerNode<'a, 'b> { JsonPointerNode { segment: Some(segment), parent: Some(self), } } /// Преобразовать узел указателя JSON в вектор, содержащий элементы пути. fn to_vec(&'a self) -> Vec<&'a str> { // Собрать сегменты по направлению от головы к хвосту let mut buffer = Vec::new(); let mut head = self; if let Some(segment) = &head.segment { buffer.push(*segment); } while let Some(next) = head.parent { head = next; if let Some(segment) = &head.segment { buffer.push(*segment); } } // Обратить порядок буфера, чтобы поставить сегменты в правильном порядке buffer.reverse(); buffer } }
Теперь можно заменить &mut Vec:
fn validate(&self, instance: &Value) -> ValidationResult { self.node.validate(instance, JsonPointerNode::new()) } trait Node { fn validate<'a>( &self, instance: &'a Value, path: JsonPointerNode<'a, '_>, ) -> ValidationResult; } impl Node for Properties { fn validate<'a>( &self, instance: &'a Value, path: JsonPointerNode<'a, '_>, ) -> ValidationResult { // ... value.validate(instance, path.push(key.as_str()))?; // ... } impl Node for Type { fn validate<'a>( &self, instance: &'a Value, path: JsonPointerNode<'a, '_>, ) -> ValidationResult { match (self, instance) { // ... Сравнить тип `instance` с ожидаемым типом _ => Err(ValidationError::new( format!("{instance} is not of type '{self}'"), path.to_vec().into_iter(), )), } } }
Во время обхода никакая память из кучи не выделяется! Помогло ли это?
Ух! При работе с валидным вводом так получается значительно лучше! С невалидными образцами всё примерно как и раньше, но мы пока не оптимизировали реализацию связного списка.
Здесь мы исходим из того, что путь понадобится нам только в случае возникновения ошибки. В таком случае можно частично избавиться от издержек, поскольку не приходится поддерживать в течение всего процесса обхода, а память будем выделять из кучи лишь по мере необходимости.
Обратите внимание: связные списки уступают векторам по показателю локальности кэша, и в некоторых сценариях из-за этого может замедляться производительность.
Хорошая идея №4: прицельное выделение памяти
Давайте разберёмся, почему реализация со связными списками отличается не лучшей производительностью, когда получает невалидный ввод, и для этого сначала рассмотрим JsonPointerNode:
Очевидно, проблема заключается в повторном выделении памяти внутри JsonPointerNode::to_vec. Этого можно избежать, выделив ровно столько памяти, сколько нужно. Для этого потребуется лишний раз обойти связный список, чтобы вычислить мощность, но выигрыш в производительности, который приобретается благодаря избавлению от перевыделений, с верхом компенсирует издержки на этот дополнительный обход:
impl<'a, 'b> JsonPointerNode<'a, 'b> { pub(crate) fn to_vec(&'a self) -> Vec<&'a str> { // Обходим связный список для расчёта мощности let mut capacity = 0; let mut head = self; while let Some(next) = head.parent { head = next; capacity += 1; } // Собрать сегменты по направлению от головы к хвосту let mut buffer = Vec::with_capacity(capacity); let mut head = self; if let Some(segment) = &head.segment { buffer.push(*segment); } while let Some(next) = head.parent { head = next; if let Some(segment) = &head.segment { buffer.push(*segment); } } // Обратить порядок буфера, чтобы поставить сегменты в правильном порядке buffer.reverse(); buffer } }
Отлично! При прицельном выделении памяти повышается производительность и при обработке невалидного ввода показатель приближается к обработке валидного. Выделяйте память строго по мере необходимости, чтобы, когда это только возможно, избежать издержек, связанных с её перевыделением.
Хорошая идея №5: избегать временных Vec
На данном этапе временные Vec — наиболее серьёзный фактор, замедляющий работу с невалидным вводом. Если подробнее рассмотреть реализацию ValidationError, заметим в ней вызов collect. Он свидетельствует, что сначала мы собираем Vec<&str> в JsonPointerNode::to_vec, а потом почти сразу же собираем из него Vec<String>, то есть выделяем Vec дважды. Почему бы нам не начать с Vec<String>:
impl ValidationError { fn new(message: impl Into<String>, location: Vec<String>) -> Self { Self { message: message.into(), location, } } } impl Node for Type { fn validate<'a>( &self, instance: &'a Value, path: JsonPointerNode<'a, '_>, ) -> ValidationResult { match (self, instance) { // ... Сравнить тип `instance` с ожидаемым _ => Err(ValidationError::new( format!("{instance} is not of type '{self}'"), path.to_vec(), )), } } } impl<'a, 'b> JsonPointerNode<'a, 'b> { pub(crate) fn to_vec(&self) -> Vec<String> { // ... if let Some(segment) = &head.segment { buffer.push((*segment).to_string()); } while let Some(next) = head.parent { head = next; if let Some(segment) = &head.segment { buffer.push((*segment).to_string()); } } // ... } }
Такая оптимизация позволяет заметно улучшить производительность при обработке невалидных случаев:
Потенциально хорошая идея №6: оптимизировать размер структуры
Иногда стоит попытаться уменьшить размер структур, в особенности, если структура часто передаётся по значению. Если структуры небольшие, то память на них расходуется меньше, а функции вызываются быстрее, причём приходится копировать в стек меньше данных.
Если бы мы попытались отслеживать не только ключи в объектах JSON, но и и��дексы в массивах, то это можно было бы сделать при помощи перечисления, вот так:
enum Segment<'a> { /// Имя свойства внутри объекта JSON. Property(&'a str), /// Индекс внутри массива JSON. Index(usize), } struct JsonPointerNode<'a, 'b> { segment: Option<Segment<'a>>, parent: Option<&'b JsonPointerNode<'a, 'b>>, }
В таком случае структура JsonPointerNode будет занимать 32 байта:
_eq!(std::mem::size_of::<JsonPointerNode>(), 32);
Однако, избегая Option в поле segment, можно сократить размер структуры до 24 байт. Идея в том, чтобы положить в корневой узел какое-нибудь дешёвое значение и никогда его не читать:
struct JsonPointerNode<'a, 'b> { segment: Segment<'a>, parent: Option<&'b JsonPointerNode<'a, 'b>>, } impl<'a, 'b> JsonPointerNode<'a, 'b> { /// Создать корневой узел указателя JSON const fn new() -> Self { JsonPointerNode { // Данное значение несущественно, оно никогда использоваться не будет segment: Segment::Index(0), parent: None, } } fn push(&'a self, segment: Segment<'a>) -> JsonPointerNode<'a, 'b> { JsonPointerNode { segment, parent: Some(self), } } /// Преобразуем указатель JSON в вектор элементов пути. pub(crate) fn to_vec(&self) -> Vec<String> { // ... if head.parent.is_some() { buffer.push(head.segment.to_string()) } while let Some(next) = head.parent { head = next; if head.parent.is_some() { buffer.push(head.segment.to_string()); } } // ... } }
Именно такая техника непосредственно используется в крейте jsonschema для уменьшения структуры JsonPointerNode, но здесь я её не применяю, чтобы не усложнять.
Другие идеи, не доведённые до ума
Думаю, также можно было бы немного нарастить производительность, избавившись от вызова reverse в JsonPointerNode::to_vec, поскольку он тоже перекидывает данные. Есть, например, такой способ: присваивать сегменты, начиная с задней части вектора, заполненного значениями, задаваемыми по умолчанию. Но для такой записи в обратном порядке потребуется вести дополнительный учёт, который может нивелировать наши приобретения. Поэтому важно профилировать любые изменения и расставлять бенчмарки — так гарантируется, что по каждому практическому случаю можно будет достичь измеримой выгоды.
Ещё одна идея — хранить ссылки на сегменты пути внутри ValidationError, а не клонировать строки:
struct ValidationError<'a> { message: String, location: Vec<&'a str>, }
Таким образом, можно обойтись без клонирования сегментов пути, а вместо этого хранить ссылки на них. Так можно было бы повысить производительность, особенно, если приходится иметь дело с длинными путями или большим количеством ошибок. Однако, при таком подходе ValidationError станет менее гибкой, поскольку будет привязана к времени жизни входных данных JSON.
Отличная идея № 7: может быть, связный список вам не нужен?
Такую идею высказал @Kobzol, отметивший, что путь к ошибке можно лениво собрать из стека вызовов, ориентируясь на путь распространения ошибки. Я реализовал эту идею, опираясь на его предложение и на исходный сниппет кода:
impl ValidationError { pub(crate) fn push_segment(&mut self, segment: String) { self.location.push(segment); } pub(crate) fn finish(mut self) -> ValidationError { self.location.reverse(); self } } fn validate(&self, instance: &Value) -> ValidationResult { if let Err(error) = self.node.validate(instance, 0) { // Обратить сегменты пути в методе `finish` Err(error.finish()) } else { Ok(()) } } impl Node for Properties { fn validate(&self, instance: &Value, level: u32) -> ValidationResult { // ... for (key, value) in &self.properties { if let Some(instance) = object.get(key) { if let Err(mut error) = value.validate(instance, level + 1) { error.push_segment(key.to_string()); return Err(error); // ... } } impl Node for Type { fn validate(&self, instance: &'a Value, level: u32) -> ValidationResult { // ... _ => Err(ValidationError::new( format!("{instance} is not of type '{self}'"), Vec::with_capacity(level as usize) // ... } }
Правда, в этом примере мне пока не удалось добиться стабильного улучшения бенчмарков :(
Ещё один плюс может быть связан с тем, что мы больше не используем оператор ?. Ведь при обращении с ним выполняется преобразование From/Into, но у нас предусмотрен всего один тип ошибок, и нам не требуется его преобразовывать. Именно поэтому в serde есть собственный макрос tri!, используемый вместо ?;.
Заключение
В конечном счёте, нам удалось повысить производительность приблизительно в 1,9/1,3 раза (по сравнению с исходной реализацией) – соответственно, в сценариях с валидным и невалидным вводом. В целом эта фича даёт выигрыш в 18% / 95% сверх версии, в которой не используется путь!
Польза от некоторых вариантов оптимизации, рассмотренных в этой статье, очевидна не сразу, особенно, если вы уже ��наете, где возникнут узкие места. Но, исследуя сравнительно простые варианты оптимизации, зачастую можно обнаружить неожиданные варианты улучшения. Даже если в некоторых случаях оптимизация сразу не даёт результата или замедляет ваш код, она может открыть вам путь к дальнейшим возможностям оптимизации.
Выводы
Упрощённый подход может быть вполне хорош
Проблему нужно рассматривать в разных масштабах
Нужно подыскивать такую структуру данных, которая решает стоящую перед вами проблему
Выделяйте ровно столько памяти, сколько нужно, и тогда, когда это необходимо
Если какие‑то значения приходится часто передавать — постарайтесь уменьшить их размер
Если пишете посты — избегайте употреблять в заголовке слово «сверхскоростные»
Спасибо за внимание!
© 2021-2024 Dmitry Dygalo
