- PVSM.RU - https://www.pvsm.ru -
Не так давно я стал присматриваться к языку программирования Rust
. Прочитав Rustbook
[1], изучив код некоторых популярных проектов, я решил своими руками попробовать этот язык программирования и своими глазами оценить его преимущества и недостатки, его производительность и эко-систему.
Язык Rust
позиционирует себя, как язык системного программирования, поэтому основным его vis-à-vis следует называть C/C++
. Сравнивать же молодой и мультипарадигмальный Rust
, который поддерживает множество современных конструкций программирования (таких, как итераторы [2], RAII
[3] и др.) с «голым» C
я считаю не правильно. Поэтому в данной статье речь пойдет об сравнении с C++
.
Чтобы сравнить код и производительность Rust
и C++, я взял ряд алгоритмических задач, которые нашел в онлайн курсах по программированию и алгоритмам.
Статья построена следующим образом: в первой части я опишу основные плюсы и минусы, на которые я обратил внимание, работая с Rust
. Во второй части я приведу краткое описание алгоритмических задач, которые были решены в Rust
и C++, прокомментирую основные моменты реализации программ. В третьей части будет приведена таблица замера производительности программ на Rust
и C++.
Данная статья достаточно субъективная. Даже сравнение производительности программ, которые делают одинаковые вещи, но написаны на разных языках, подвержены авторскому подходу. Поэтому я не претендую на объективные замеры, и, чтобы не навязывать свои результаты, предлагаю всем ознакомится с кодом программ и с подходом к замеру производительности. Код выложен на github [4]. Буду рад любой критике и замечаниям. Начнем.
+ Разработчики Rust
поставляют свой компилятор уже с «батарейками внутри» тут есть: компилятор, менеджер пакетов (он же сборщик проектов, он же отвечает за запуск тестов), генератор документации и отладчик gdb
. Исходный код на Rust
может включать в себя сразу тесты и документацию, и чтобы собрать все это не требуется дополнительных программ или библиотек.
+Компилятор строг к тексту программы, который подается ему на вход: в его выводе можно увидеть какой код не используется, какие переменные можно изменить на константный тип, и даже предупреждения, связанные со стилем программирования. Часто для ошибок компиляции приведены варианты ее устранения, а ошибки при инстанциировании обобщенного кода (шаблонов) лаконичны и понятны (привет ошибкам с шаблонами STL
в C++
).
+ При присваивании или передачи аргументов по умолчанию работает семантика перемещения [5] (аналог std::move
, но не совсем). Если функция принимает ссылку на объект необходимо явно взять адрес (символ &
, как в C++
).
+ Все строки — это юникод в кодировке UTF-8
[6]. Да, для подсчета количества символов нужно О(N)
операций, но зато никакого зоопарка с кодировками.
+ Есть поддержка итераторов и замыканий (лямбда функций) [7]. Благодаря этому можно писать однострочные конструкции, которые выполняют множество операций с сложной логикой (то, чем славится Python
).
+-В Rust
отсутствуют исключения, обработку ошибок необходимо делать после вызова каждой функции. Причем Rust
не позволит получить возвращаемое значение, если вы не обработаете случай неуспешного завершения функции. Есть макросы и встроенные конструкции языка, которые позволяют упростить эту обработку и не сильно раздувать код проверками.
- Нужно писать программы так, чтобы компилятор (точнее borrow checker) поверил, что вы не делаете ничего плохого с памятью (или с ресурсами в целом). Часто это работает как надо, но иногда приходится писать код в несколько хитрой форме только для того, что бы удовлетворить условиям borrow checker'а.
- В Rust
нет классов, но есть типажи, на основе которых можно построить объектно ориентированную программу. Но скопировать реализацию с полиморфными классами в C++
в язык Rust
напрямую не получиться.
- Rust
достаточно молод. Мало полезного материала в сети, на StackOverflow. Мало хороших библиотек. Например, нет библиотек для построения GUI, нет портов wxWidgets
, Qt
.
Нужно для для каждого значения из вектора B найти его позицию в векторе A. По сути нужно применить n раз бинарный поиск, предварительно отсортировав A, где n — кол-во элементов в B. Поэтому тут я приведу функцию бинарного поиска.
// return position of the element if found (indexing from 1),
// return -1 otherwise
fn binary_search(vec: &Vec<u32>, value: u32) -> i32 {
let mut l: i32 = 0;
let mut r: i32 = vec.len() as i32 - 1;
while l <= r {
let i = ((l + r) / 2) as usize;
if vec[i] == value {
return i as i32 + 1;
} else if vec[i] > value {
r = i as i32 - 1;
} else if vec[i] < value {
l = i as i32 + 1;
}
}
-1
}
Кто первый раз видит Rust
, обратите внимание на пару особенностей:
mut
Rust
не переводит типы неявно, даже числовые. Поэтому нужно писать явный перевод типа l = i as i32 + 1
Формально задача звучит так: для заданного массива подсчитать кол-во перестановок, необходимых для сортировки массива. По факту нам требуется реализовать сортировку слиянием, подсчитывая по ходу длину перестановок элементов.
Давайте рассмотрим код чтения массива с stdin
fn read_line() -> String {
let mut line = String::new();
io::stdin().read_line(&mut line).unwrap();
line.trim().to_string()
}
fn main() {
// 1. Read the array
let n: usize = read_line().parse().unwrap();
let mut a_vec: Vec<u32> = vec![0; n as usize];
for (i, token) in read_line().split_whitespace().enumerate() {
a_vec[i] = token.parse().unwrap();
}
...
String::new()
выше.Option
, который содержит None
или результат корректного завершения функции. Метод unwrap
позволяет получить результат или вызывает panic!
, если вернулся None
.String::parse
парсит строку в тип возвращаемого значения, т.е. происходит вывод типа по возвращаемому значению.Rust
поддерживает итераторы (как генераторы в Python). Связка split_whitespace().enumerate()
генерирует итератор, который лениво читает следующий токен и инкрементирует счетчик.
Приведу сначала неправильную сигнатуру вызова функции _merge
, которая сливает in place два отсортированных подмассива.
fn _merge(left_slice: &mut [u32], right_slice: &mut [u32]) -> u64
Данная конструкция не взлетит в Rust
без unsafe
кода, т.к. тут мы передаем два изменяемых подмассива, которые располагаются в исходном массиве. Система типов в Rust
не позволяет иметь две изменяемых переменных на один объект (мы знаем, что подмассивы не пересекаются по памяти, но компилятор — нет). Вместо этого надо использовать такую сигнатуру:
fn _merge(vec: &mut [u32], left: usize, mid: usize, right: usize) -> u64
Для заданной строки нужно построить беспрефиксный код и вывести закодированное сообщение. Для данной задачи нужно построить дерево на основе частотных характеристик символов в исходном сообщении. Построение деревьев, списков, графов на Rust
— задачи не из простых, т.к., например, в случае двусвязного списка нам необходимо иметь два mut
указателей на один нод, а это запрещено системой типов. Поэтому эффективно написать двусвязный список без unsafe
кода не получится. В данной задаче мы имеем однонаправленное дерево, поэтому эта особенность нас не коснется, но есть свои сложности реализации.
Заведем класс Node:
// Type of the reference to the node
type Link = Option<Box<Node>>;
// Huffman tree node struct
#[derive(Debug,Eq)]
struct Node {
freq: u32,
letter: char,
left: Link,
right: Link,
}
impl Ord for Node {
// reverse order to make Min-Heap
fn cmp(&self, b: &Self) -> Ordering {
b.freq.cmp(&self.freq)
}
}
#[derive(Debug,Eq)]
. Debug
— поддерживаем форматированную печать объекта по-умолчанию. Eq
— определяем операцию сравнения на равенство.Ord
. Типажи позволяют расширять возможности объектов. В частности, здесь мы сможем использовать Node
для хранения Min-куче.Метод для посещения нод дерева сверху вниз и для составления таблицы кодирования.
impl Node {
...
// traverse tree building letter->code `map`
fn build_map(&self, map: &mut HashMap<char, String>, prefix: String) {
match &self.right {
&Some(ref leaf) => leaf.build_map(map, prefix.clone() + "1"),
_ => { },
}
match &self.left {
&Some(ref leaf) => { leaf.build_map(map, prefix.clone() + "0"); },
_ => { map.insert(self.letter, prefix); },
}
}
}
&Some(ref leaf)
.match
похожа на switch
в C
. match
должен обработать все варианты, поэтому тут присутсвует _ => { }
.prefix.clone()
, чтобы в каждую ветвь дерева передалась своя строка.
Обратная задача: для известной таблицы кодирования и закодированной строки получить исходное сообщение. Для декодирования удобно пользоваться бинарным деревом кодирования, поэтому в программе нам нужно из таблицы кодирования получить дерево декодирования. На словах задача простая: нужно перемещаться вниз по дереву (0 — влево, 1 — вправо), создавая промежуточные узлы при необходимости, и в листья дерева помещать символ исходного сообщения. Но для Rust
задача оказалась сложная, ведь нам нужно перемещаться по изменяемым ссылкам, создавать объекты, и при этом избегать ситуации, когда объектом владеет более одной переменной. Код функции заполнения бинарного дерева:
fn add_letter(root: &mut Link, letter: char, code: &str) {
let mut p: &mut Node = root.as_mut().unwrap();
for c in code.chars() {
p = match {p} {
&mut Node {left: Some(ref mut node), ..} if c == '0' => {
node
},
&mut Node {left: ref mut opt @ None, ..} if c == '0' => {
*opt = Node::root();
opt.as_mut().unwrap()
},
&mut Node {right: Some(ref mut node), ..} if c == '1' => {
node
},
&mut Node {right: ref mut opt @ None, ..} if c == '1' => {
*opt = Node::root();
opt.as_mut().unwrap()
},
_ => { panic!("error"); }
}
}
p.letter = letter;
}
match
используется для сравнения структуры переменной p
. &mut Node {left: Some(ref mut node), ..} if c == '0'
означает «если p
это изменяемая ссылка на объект Node
у, которого поле left
указывает на существующий node
и при этом символ c
равен '0'».Rust
нет исключений, поэтому panic!("...")
раскрутит стек и остановит программу (или поток).Нужно для двух строк посчитать расстояние Левенштейна — кол-во действий редактирования строк, чтобы из одной получить другую. Код функции:
fn get_levenshtein_distance(str1: &str, str2: &str) -> u32 {
let n = str1.len() + 1;
let m = str2.len() + 1;
// compute 2D indexes into flat 1D index
let ind = |i, j| i * m + j;
let mut vec_d: Vec<u32> = vec![0; n * m];
for i in 0..n {
vec_d[ind(i, 0)] = i as u32;
}
for j in 0..m {
vec_d[ind(0, j)] = j as u32;
}
for (i, c1) in str1.chars().enumerate() {
for (j, c2) in str2.chars().enumerate() {
let c = if c1 == c2 {0} else {1};
vec_d[ind(i + 1, j + 1)] = min( min( vec_d[ind(i, j + 1)] + 1
, vec_d[ind(i + 1, j)] + 1
)
, vec_d[ind(i, j)] + c
);
}
}
return vec_d[ind(n - 1, m - 1)];
}
str1: &str
— это срез строки. Легковесный объект, который указывает на строку в памяти, аналог std::string_view
C++17.let ind = |i, j| i * m + j;
— такой конструкцией определяется лямбда функция.В конце, как обещал, прикладываю таблицу сравнения времени работы программ, описанных выше. Запуск производился на современной рабочей станции Intel Core i7-4770, 16GB DDR3, SSD, Linux Mint 18.1 64-bit. Использовались компиляторы:
[>] rustc --version
rustc 1.20.0 (f3d6973f4 2017-08-27)
[>] g++ -v
...
gcc version 7.2.0
Пару замечаний по результатам:
/dev/null
C++
проигрывает из-за библиотеки потокового чтения/записи iostream
. Но эту гипотезу еще предстоит проверить.И да, в коде есть std::sync_with_stdio(false)
Rust
сильно проигрывает в тесте Huffman encoding
по причине медленных хешей в HashMap
[8]Rust
показал, что по производительности он не уступает C++
Повторюсь, что статья субъективна, и признана в первую очередь оценить в грубом масштабе, где находится Rust
по отношению к C++
. Если у вас есть пожелания, идеи или замечания, которые позволят добавить статье объективности, пишите в комментарии.
Вы можете ознакомиться со всеми кодами, необходимыми для повторения замеров на github [4].
Спасибо, что дочитали до конца!
Автор: dmitryikh
Источник [9]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/proizvoditel-nost/270277
Ссылки в тексте:
[1] Rustbook
: https://github.com/ruRust/rust_book_ru
[2] итераторы: https://rustbyexample.com/trait/iter.html
[3] RAII
: https://rustbyexample.com/scope/raii.html
[4] github: https://github.com/dmitryikh/rust-vs-cpp-bench
[5] семантика перемещения: https://rustbyexample.com/scope/move.html
[6] юникод в кодировке UTF-8
: https://rustbyexample.com/std/str.htm://rustbyexample.com/std/str.html""
[7] замыканий (лямбда функций): https://rustbyexample.com/fn/closures.html
[8] медленных хешей в HashMap
: https://www.rust-lang.org/en-US/faq.html#why-are-rusts-hashmaps-slow
[9] Источник: https://habrahabr.ru/post/344282/?utm_source=habrahabr&utm_medium=rss&utm_campaign=sandbox
Нажмите здесь для печати.