Привет!
Начав изучение Scala, я сразу столкнулся с тем, что функциональная реализация простейшего алгоритма быстрой сортировки работает радикально медленней и потребляет существенно больше памяти, чем аналогичная императивная реализация. При этом никто не спорит, что функциональный код более краток, выразителен, и устойчив к ошибкам. Переписав оба примера на Rust, я обнаружил несколько важных вещей, которыми и хочу поделиться. Подробности под катом, а здесь приведу лишь краткие выводы:
- Для императивной реализации — выигрыш от Rust получился всего 20 %. Это означает, что JVM вплотную приблизилась к нативной производительности, и тут уже нечего улучшать.
- Для функциональной реализации — Rust оказался быстрее в 4.5 раза, потребление памяти снизилось в 5.5 раза, а отсутствие сборщика мусора сделало программу более стабильной (меньше разброс показателей). Это интересно для тех, кто хочет писать быстрые функциональные программы.
- Концепция единственного владельца данных (и единственной мутабельной ссылки), принятая в 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 sort_fun(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.
Спасибо за внимание.
Автор: balajahe
