Привет, Хабр!
При этом никто не спорит, что функциональный код более краток, выразителен, и устойчив к ошибкам. Начав изучение Scala, я сразу столкнулся с тем, что функциональная реализация простейшего алгоритма быстрой сортировки работает радикально медленней и потребляет существенно больше памяти, чем аналогичная императивная реализация. Подробности под катом, а здесь приведу лишь краткие выводы: Переписав оба примера на Rust, я обнаружил несколько важных вещей, которыми и хочу поделиться.
- Для императивной реализации — выигрыш от Rust получился всего 20 %. Это означает, что JVM вплотную приблизилась к нативной производительности, и тут уже нечего улучшать.
- Для функциональной реализации — Rust оказался быстрее в 4.5 раза, потребление памяти снизилось в 5.5 раза, а отсутствие сборщика мусора сделало программу более стабильной (меньше разброс показателей). Это интересно для тех, кто хочет писать быстрые функциональные программы.
- Концепция единственного владельца данных (и единственной мутабельной ссылки), принятая в Rust, очень близка концепции иммутабельности, в результате чего функциональные алгоритмы, основанные на неизменяемости, рекурсии и копировании, легко ложатся на Rust практически без переписывания, тогда как императивные алгоритмы заставляют редизайнить код, учитывать мутабельность ссылок, времена жизни, и т.д.
Вывод — Rust как будто специально создан для ФП, хотя возможности его синтаксиса пока не дотягивают до Scala.
Итак, начнем со Scala и реализуем быструю сортировку в 2-х стилях:
Мы видим многословный код, потенциально уязвимый для опечаток, но оптимально использующий память, и максимально быстрый. Императивно — используем один и тот же массив, переставляя в нем элементы с помощью рекурсивной процедуры.
def sort_imp(arr: Array[Double]) 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 Гб.
UPD
Скомпилировал в нативный код через LLVM с опцией nativeMode := «release» и сборщиком мусора «immix gc», результат получился еще хуже:
- императивно — 2.3 секунды
- функционально — 63 секунды
Перепишем то же самое на 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 в нем тоже нет). Если писать императивно, с использованием общего изменяемого состояния — прикладному программисту нет смысла переходить с управляемых языков на компилируемые, так как выигрыш в производительности не компенсирует сложности программирования и многословности исходных текстов.
И если Rust будет двигаться в этом направлении — возможно ФП-подход найдет больше сторонников. В мире есть много быстрых и выразительных ООП-языков, а по настоящему быстрых zero-cost функциональных языков — не очень. Тем более, что по итогам 2019 года и Scala и Rust показали существенный рост популярности на фоне спада мейнстримных языков.
Полный текст на Scala.
Полный текст на Rust.
Спасибо за внимание.
