На курсах по программированию связные списки преподаются как одна из фундаментальных структур данных, но на самом деле такие списки чаще встречаются на технических собеседованиях, чем в реальных проектах.
В этом посте будет продемонстрирован практический пример, в котором связный список существенно обгоняет 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
