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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Rust не такой

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

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

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

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

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

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

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

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

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

Тем не менее 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 коллекции реализованы в императивном стиле, они ведут себя как обычные значения: когда вы присваиваете одному вектору другой вектор, если вы хотите сохранить исходный вектор, мы должны c clone ировать его, что делает новый вектор независимым от старого.

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

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

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

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