Почему Rust должен стать функциональным языком программирования

Начав изучение Scala, я сразу столкнулся с тем, что функциональная реализация простейшего алгоритма быстрой сортировки работает радикально медленней и потребляет существенно больше памяти, чем аналогичная императивная реализация. При этом никто не спорит, что функциональный код более краток, выразителен, и устойчив к ошибкам. Переписав оба примера на Rust, я обнаружил несколько важных вещей, которыми и хочу поделиться. Подробности под катом, а здесь приведу лишь краткие выводы:

1. Для императивной реализации — выигрыш от Rust получился всего 20 %. Это означает, что JVM вплотную приблизилась к нативной производительности, и тут уже нечего улучшать.
2. Для функциональной реализации — Rust оказался быстрее в 4.5 раза, потребление памяти снизилось в 5.5 раза, а отсутствие сборщика мусора сделало программу более стабильной (меньше разброс показателей). Это интересно для тех, кто хочет писать быстрые функциональные программы.
3. Концепция единственного владельца данных (и единственной мутабельной ссылки), принятая в Rust, очень близка концепции иммутабельности, в результате чего функциональные алгоритмы, основанные на неизменяемости, рекурсии и копировании, легко ложатся на Rust практически без переписывания, тогда как императивные алгоритмы заставляют редизайнить код, учитывать мутабельность ссылок, времена жизни, и т.д.

Вывод — Rust как будто специально создан для ФП, хотя возможности его синтаксиса пока не дотягивают до Scala.

Итак, начнем со Scala и реализуем быструю сортировку в 2-х стилях:

Императивно — используем один и тот же массив, переставляя в нем элементы с помощью рекурсивной процедуры. Мы видим многословный код, потенциально уязвимый для опечаток, но оптимально использующий память, и максимально быстрый.

def sort_imp(arr: Array[Double]) {   def swap(i: Int, j: Int) {     val t = arr(i)     arr(i) = arr(j)     arr(j) = t   }    def sort1(l: Int, r: Int) {     val pivot = arr((l + r) / 2)     var i = l     var j = r     while (i <= j) {       while (arr(i) < pivot) i += 1       while (arr(j) > pivot) j -= 1       if (i <= j) {         swap(i, j)         i += 1         j -= 1       }     }     if (l < j) sort1(l, j)     if (j < r) sort1(i, r)   }    sort1(0, arr.length - 1) }

Функционально — используем рекурсивную функцию, которая создает три новых массива, и затем возвращает их объединение. Очень компактный и красивый код, практически негде ошибиться, но очень медленный и прожорливый (бедный, бедный GC).

def sort_fun(arr: Array[Double]): Array[Double] = {   if (arr.length <= 1)      arr   else {     val pivot = arr(arr.length / 2)     Array.concat(       sort_fun(arr filter (pivot > _)),       arr filter (pivot == _),       sort_fun(arr filter (pivot < _))     )   } }

Бенчмаркинг ($ sbt run) на массиве 10 млн. случайных чисел и моем дохлом ноутбуке:

• императивно — 2.5 секунды
• функционально — 40 секунд

Как правильно считать память приложения я не знаю, но сам процесс java занял 3.6 Гб.

Перепишем то же самое на Rust:

Императивно — алгоритм не изменился, единственная проблема в том, что внутрь функций пришлось явно передавать мутабельную ссылку на исходный массив, так как замыкания для внутренних функций не работают, а использование специального синтаксиса замыканий, создает проблемы при рекурсии. Если наш алгоритм будет сложнее, мы можем столкнуться с ограничениями borrow-checker.

fn sort_imp(arr: &mut Vec<f64>) {   fn swap(arr: &mut Vec<f64>, i: usize, j: usize) {     let t = arr[i];     arr[i] = arr[j];     arr[j] = t;   };    fn sort1(arr: &mut Vec<f64>, l: usize, r: usize) {     let pivot = arr[(l + r) / 2];     let mut i = l;     let mut j = r;     while i <= j {       while arr[i] < pivot { i += 1; }       while arr[j] > pivot { j -= 1; }       if i <= j {         swap(arr, i, j);         i += 1;         j -= 1;       }     }     if l < j { sort1(arr, l, j); }     if j < r { sort1(arr, i, r); }   };    sort1(arr, 0, arr.len() - 1); }

Функционально — мы видим, что алгоритм идентичен, однако синтаксис Rust хуже приспособлен для функциональщины, пришлось объявлять промежуточный вектор.

Последовательное применение iter() и filter() к элементам массива приводит к тому, что параметр замыкания x получает тип &&f64, и двойную ссылку приходится разыменовывать **. Нужно явно клонировать отфильтрованные значения. Сигнатура функции append() требует именно мутабельную ссылку, а не сам вектор, что также увеличивает количество букв.

fn sort_fun(arr: Vec<f64>) -> Vec<f64> {   if arr.len() <= 1 {     arr   } else {     let pivot = arr[arr.len() / 2];     let mut a = Vec::<f64>::with_capacity(arr.len());     a.append(&mut sort_fun(arr.iter().filter(|x| pivot > **x).cloned().collect()));     a.append(&mut arr.iter().filter(|x| pivot == **x).cloned().collect());     a.append(&mut sort_fun(arr.iter().filter(|x| pivot < **x).cloned().collect()));     a   } }

Можно было бы попытаться сделать код красивее, применив вместо объединения массивов — объединение итераторов iter().filter(…).chain(…). Это был бы полный zero-cost, но в итераторе мы не можем определить количество элементов, значит не можем поделить его пополам, а значит — реализовать алгоритм. Но в других случаях ленивые итераторы это красиво, экономно и быстро.

Обратите внимание — в императивный алгоритм я передаю мутабельную ссылку на массив, а в функциональный — сам массив, который автоматически уничтожается при выходе из функции (также уничтожаются все временные массивы на каждом шаге рекурсии).

Бенчмаркинг ($ cargo build —release):

• императивно — 2 секунды
• функционально — 9 секунд

Максимальное потребление памяти — 650 Мб.

В сухом остатке:

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

В мире есть много быстрых и выразительных ООП-языков, а по настоящему быстрых zero-cost функциональных языков — не очень. И если Rust будет двигаться в этом направлении — возможно ФП-подход найдет больше сторонников. Тем более, что по итогам 2019 года и Scala и Rust показали существенный рост популярности на фоне спада мейнстримных языков.

Полный текст на Scala.
Полный текст на Rust.

Спасибо за внимание.