В последнее время я долго думал над персистентными коллекциями и в особенности над тем, как они относятся к 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 уже имеет персистентные коллекции, клонирование которых, однако, неэффективно.