Почему Rust должен стать функциональным языком программирования | | ДОСТУПНЫЙ ОТДЫХ
Интересное

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

Привет, Хабр!

Начав изучение 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).

    Читать  Gifex — все посты | Пикабу

    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.

    Спасибо за внимание.
    Источник

    I heart FeedBurner