Rust: «Векторы — это значения»

http://smallcultfollowing.com/babysteps/blog/2018/02/01/in-rust-ordinary-vectors-are-values/
  • Перевод

В последнее время я долго думал над персистентными коллекциями и в особенности над тем, как они относятся к Rust. Хочу поделиться с вами своими наблюдениями.


О том, как устроены персистентные векторы, быстрее ли они традиционных коллекций — смотрите под катом.


Что такое персистентная коллекция?


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


vec.push(element);

вы вызываете метод add, который оставляет исходный вектор на своем месте и возвращает новый измененный вектор:


let vec2 = vec.add(element);

Важно заметить, что vec не меняется. Данная особенность хорошо вписывается в функциональные языки, хорошо применяется это и в написании многопоточных програм.


Как работают персистентные коллекции?


Не буду вдаваться в подробности какого-то конкретного решения, но большинство из них реализованы на каком-либо виде деревьев. Например, имея вектор вида [1, 2, 3, 4, 5, 6], вы можете сохранять элементы не в одном большом блоке, а в виде дерева, листами которого являются значения. На следующей диаграмме набор значений поделен на два дочерних узла, на которые указывает родительский узел:


 [*        *] // <-- данный родительский узел является вектором
  |        |
-----    -----
1 2 3    4 5 6

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


 [*        *]   // <--исходный вектор
  |        |    //     до сих пор существует, не изменен
-----    -----
1 2 3    4 5 6
-----
  |      4 5 10 // <-- новая копия правого узла
  |      ------
  |        |
 [*        *]   // <-- новый вектор

В сбалансированном дереве операция добавления в персистентный вектор стремится к O(log n) — мы должны склонировать некоторый лист и изменить его, после этого мы должны скопировать и изменить все родительский узлы на пути до корня. Это гораздо более ресурсозатратно, чем изменение обычного вектора, что требует лишь нескольких процессорных инструкций.


Несколько замечаний:


  • если на вектор имеется только одна ссылка, вы часто можете избежать этих клонирований и просто менять дерево на месте. Позже я расскажу об экспериментальной библиотеке персистентных коллекций DVec, использующей этот трюк. Это сложно реализовать в языке со сборкой мусора, потому что вы никогда не знаете, сколько ссылок имеется на вашу коллекцию. — есть много других вариантов реализации персистентных коллекий, которые имеют своей целью оптимизацию под конкретные случаи использования. Например, здесь приводится решение, подходящее для Prolog-подобных приложений. Данный дизайн использует изменяемость "под капотом", чтобы можно было делать вставку за O(1), но скрывает это от пользователя. Разумеется, за эти быстрые вставки нужно платить: использование старых копий структуры данных стоит дороже.

Персистентные коллекции превращают коллекции в значения


В некоторых случаях персистентные коллекции дают возможность писать более легкий для понимания код. Это потому, что они выступают как "обычные значения" и не являются уникальными. Посмотрите на этот работающий с числами JS-код:


function foo() {
    let x = 0;
    let y = x;
    y += 1;
    return y - x;
}

Если мы меняем y, мы ожидаем, что x не поменяется. Это потому, что x являтся простым значением. Однако если мы будем использовать массив:


function foo() {
    let x = [];
    let y = x;
    y.push(22);
    use(x, y);
}

Теперь, когда я меняю y, переменная x тоже меняется. Возможно, что мне это нужно, а возможно и нет. Вещи становятся более запутанными, когда векторы находятся внутри объектов:


function foo() {
    let object = {
        field: []
    };
    ...
    let object2 = {
        field: object.field
    };
    ...
    // Теперь `object.field` и `object2.field`
    // связаны, что не очевидно на первый взгляд.
    ...
}

Не поймите меня неправильно, часто бывает удобно, когда object.field и object2.field являются одним и тем же вектором, и изменения одного будут отражены на другом. Однако иногда это не то, что вам нужно. Я часто замечал, что использование персистентных коллекций позволяет сделать мой код чище и легче для понимания.


Rust не такой


Если вы видели одно из моих выступлений по Rust, то знаете, что в них был упор на следующую особенность дизайна Rust:


Предоставление общего доступа и изменяемость: хороши сами по себе, отвратительны вкупе.

Проще говоря, когда у вас имеются два указателя на один и тот же участок памяти (как object.field и object2.field в прошлом примере), тогда изменение данных через один из указателей чревато опасностью гонки. Особенно ярко это проявляется в Rust, когда вы хотите обойтись без сборщика мусора, ибо при сборщике мусора неизвестно, сколько указателей ссылается на участок памяти. Это верно даже при наличии GC, ибо дейстия, подобные object.field.push(...) могут затронуть больше объектов, чем вы предполагаете, порождая баги (в частности, но не исключительно — при одновременной работе нескольких потоков).


Что же произойдет в Rust, если вы захотите получить доступ к одному вектору через два отдельных указателя? Давайте вернемся к JavaScript-примерам, но теперь спроецируем их на Rust. Первый пример работает так же, как и на JS:


let x = 0;
let mut y = x;
y += 1;
return y - x;

Однако второй пример с векторами не скомпилируется:


let x = vec![];
let mut y = x;
y.push(...);
use(x, y); // ОШИБКА: использование 'перемещенной' переменной

Проблема в том, что как только мы сделаем y = x, владение значением x будет передано другой переменной, поэтому она (x) не сможет больше использоваться.


Rust — обычные векторы являются значениями


Это ведет нас к следующему выводу: обычные коллекции Rust'а, которые мы используем каждый день, ведут себя как значения. Даже больше — так делает любой тип в Rust, не использующий Cell или RefCell. Если ваш код компилируется, вы знаете, что ваш вектор не доступен для изменения через разные указатели — вы можете заменить его числом, и оно будет вести себя так же.


Из всего вышесказанного следует, что персистентные коллекции в Rust не обязательно должны иметь другой интерфейс, что и обычные.Например, я написал реализацию персистентного вектора — библиотеку dogged. Библиотека предоставляет тип DVec, который основан на персистентных векторах, предоставляемых Clojure. Если вы посмотрите на меторы, которые доступны у DVec, вы увидите, что они самые обычные (push и т. д.).


Вот один из примеров использования DVec:


let mut x = DVec::new();
x.push(something);
x.push(something_else);
for element in &x { ... }

Тем не менее DVec является персистентной структурой данных, которая реализована как префиксное дерево. DVec содержит внутри себя Arc (потокобезопасный счетчик ссылок), который ссылается на внутренние данные. Когда вы вызываете push, то мы обновляем Arc, так что теперь он будет ссылаться на новый вектор, оставляя старый на своем месте.


(Arc::make_mut — очень крутой метод, он проверяет значение счетчика — если оно равно 1, то дает вам исключительный доступ к содержимому с возможностью изменения. Если же значение счетчика не равно 1, тогда метод склонирует Arc (и его содержимое) на месте и даст вам изменяемую ссылку на этот клон. Если вы помните как работают персистентные структуры данных, то данная ситуация очень удобна для обновления дерева при обходе. Это позволяет вам избежать клонирования в тех случаях, когда на структуру данных ссылается только одна ссылка.)


Однако персистентные коллекции отличаются


Главное отличие между Vec и DVec лежит не в поддерживаемых операциях, а в том, насколько затратно выполнение этих операций. Когда вы вызываете push у Vec, это O(1). Когда вы клонируете, это O(n). У DVec эти оценки сложности переставлены: push требует O(log n), а клонирование — O(1).


clone на DVec увеличивает значение счетчика ссылок у внутреннего Arc, в то время как та же операция на обычном векторе клонирует все данные. Разумеется, когда вы вызываете push на DVec, он будет клонировать часть данных, перестраивая затронутые части дерева (в то время как Vec обычно просто пишет в конец массива).


Однако эта big O — нотация, как все знают, говорит только об асимптотическом поведении. Одной из проблем, с которыми я сталкивался при работе с DVec было то, что довольно сложно соревноваться со стандартным Vec в скорости. Часто копирование набора данных бывает быстрее чем обновление деревьев и выделение памяти. Я понял, что вы должны приложить много усилий для того, чтобы обосновать использование DVec — например, вы много раз клонируете вектор, и они содержат в себе большой объём данных.


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


Вывод


Я попытался показать как система владения в Rust предлагает сплав функционального и императивного стилей посредством использования персистентных коллекций. Это значит, что хотя представленные в стандартной библиотеке Rust коллекции реализованы в императивном стиле, они ведут себя как обычные значения: когда вы присваиваете одному вектору другой вектор, если вы хотите сохранить исходный вектор, мы должны ccloneировать его, что делает новый вектор независимым от старого.


Мои наблюдения не новы. В 1990 году Фил Вадлер (Phil Wadler) написал статью "Линейные типы способны изменить мир", в которой он выдвигает те же утверждения, хотя и с несколько другой стороны. Он говорит, что вы можете предоставлять персистентный интерфейс (например, метод vec.add(element), который возвращает новый вектор). Однако если вы используете линейные типы, вы можете реализовать это как императивную структуру данных (предоставляя vec.push(element)), и никто об этом не узнает.


Играясь с DVec, я понял, что очень удобно иметь персистентный вектор, который предлагает такой же интерфейс, как и обычный. Например, было очень легко изменить основанную на векторах библиотеку ena так, чтобы она работала в персистентном режиме (используя DVec) или в императивном режиме (используя Vec). Проще говоря, идея в том, чтобы скрывать используемый тип под единообразным интерфейсом.


(Отвлекаясь от основной темы, скажу, что я хотел бы видеть некоторые экспериментальные исследования: скажем, было бы удобно иметь вектор, который бы преобразовывался в персистентный после достижения определенной длины).


Я думаю, что есть еще одна причина для того, чтобы кто-то целенаправленно занялся персистентными коллециями. В то время как одновременное предоставление доступа и изменяемость могут представлять опасность, иногда это бывает очень нужно, хотя в Rust это сейчас неудобно. Я считаю, что мы должны исправить текущее положение вещей, так же у меня есть некоторые мысли на этот счет (которые я хочу отложить до следующей статьи). Rust уже имеет персистентные коллекции, клонирование которых, однако, неэффективно.

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Что вы думаете насчет включения в стандартную библиотеку персистентных структур данных?
Поделиться публикацией
Ой, у вас баннер убежал!

Ну. И что?
Реклама
Комментарии 10
    +7

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


    Что касается опросника, то у меня много вопросов к его содержимому. В отличие от других языков, Rust не пытается впихнуть в std всё что можно. Существует отличный крейт rpds, который можно использовать, если возникает нужда в персистентных коллекциях.

      +2
      А мне понравилась статья (я, правда, оригинал читал). Очень интересный инсайт, совпадающий с моим опытом активной работы с serde_json::Value.

      Уменьшил мою экзистенциальную тревогу по поводу того, что я хочу персистентный вариант этого Value. Ведь он у меня уже есть, просто clone дорогой. :)
      +2
      Вот этот кусочек перевода имеет строго обратный смысл в оригинале:

      >Из всего вышесказанного следует, что персистентные коллекции в Rust не обязательно должны иметь тот же самый интерфейс, что и обычные.

      Оригинал:

      >This implies to me that persistent collections in Rust don’t necessarily want to have a “different interface” than ordinary ones.

      Как раз смысл статьи в том, что персистентные коллекции в Rust могут иметь тот же интерфейс, что и обычные, благодаря системе владения.
        0
        don't necessarily want — не обязательно хотят? Ваш перевод выражает ту же мысль, только выглядит по-другому.
          +1
          Моего перевода тут нет (я скопировал перевод из статьи).

          Я бы перевёл так:

          Из всего вышесказанного следует, что персистентные коллекции в Rust не обязательно должны иметь тот же самыйдругой интерфейс, что и обычные.
            0
            Исправил, спасибо.
        +1
        Имело бы смысл, если бы персистентная коллекция в случае возможности заменялась на обычный массив, например когда не требуется персистентность.
          0

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

            +1

            Вот ссылка на комменты rpds с асимптотической сложностью для вектора. Копирование за O(1) — тот параметр, который превосходит обычный вектор. Для желающих почитать теорию: Understanding Clojure's Persistent Vectors, pt.1, Understanding Clojure's Persistent Vectors, pt.2
            .


            Крайне советую почитать ридми rpds, толково описано.


            А вообще у этого есть реальный профит, когда тебе надо делать undo/redo и хранить историю изменений или заменять значение по индексу с возможностью отменить сделанные изменения. дерево git — персистентная структура. Смотрите доклад Inheritance Is The Base Class of Evil by Sean Parent. history_t и есть тот самый персистентный вектор.

              –2
              Я понимаю так: например, когда хочется иметь историю состояний вектора, где каждый этап немного отличается от предыдущего/следующего состояния. Персистентные векторы дают как раз это — ибо общая часть у снимков векторов одна и та же, а та, что отличается(присуще только этому снимку) — у каждого снимка своя => получаем экономию памяти. С обычным вектором так не получится, ибо для хранения снимков вектора нужно каждый раз копировать(клонировать) его заново.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое