First week with Rust: I looked at Rust, I compared it, and I like it!
Recently I started to think about learning some completely new programming language I already put my hands on Python and C++ but I wanted to learn something new, something that is still forming and growing, so I chose Rust. I was considering Rust and Go, but I chose Rust mainly because of his memory management and speed. I work as a web developer so I have experience in javaScript and C#. In this article I will try to go through some of the Rust fundamentals and then, in the second part of this article, I will show some benchmarking of the most classic algorithms on different programming languages, including Rust of course, and compare them “in the field” by two parameters, runtime and memory usage, and try to prove the next quote from Rust official website:
“Rust is blazingly fast and memory-efficient: with no runtime or garbage collector, it can power performance-critical services, run on embedded devices, and easily integrate with other languages.”
Disclaimer: This article is written from my perspective (not professional Rust dev.), If you find some inaccuracies or other problems please let me know about it in the comment section.
About Rust
Before we begin, for those who don’t know anything about Rust, here is a quote from Wikipedia:
Rust is a multi-paradigm system programming language focused on safety, especially safe concurrency. Rust is syntactically similar to C++, but is designed to provide better memory safety while maintaining high performance.
Rust is the most loved programming language since 2016 till these days, according to stackoverflow`s developer survey ( last survey for 2018).
But why? Let’s take a closer look at some of the Rust`s main features and try to guess it.
Rust features
1. User friendly error messages, almost every time... First thing that I noticed, is that Rust have pretty useful and understandable error messages. It makes easier to debug your code and saves a lot of time. Sometimes I faced a little weird errors like “thread main panicked, index out of bounds”, but you easily can find info about this and other errors on stackoverflow or on the official website.
2. Possibility of adding abstractions without performance losses or Zero-cost abstractions. It provides us more readable, understandable and clean code.
3. Type inference. Rust automatically detects data type of an expression. We don’t have to declare type of our variable because when we provide value, Rust will automatically evaluate type of this variable for us. But if we want to, we can declare type of our variable manually. In pure JS for example, we can’t declare type of our variable.
4. Ownership method of memory management. It is safe method alike C memory management and Java garbage collecting. Rust programs allocate memory for variables, These variables own allocated memory which can be temporarily borrowed by the other variables. This allows Rust to provide memory safety at compile time without relying on garbage collection.
5. Ownership opens new feature, threads without races, due to ownership nature it is not possible for more than one thread to own the same variable with write access, because ownership passes only owners of object.
6. Patterns and matching. Patterns are a special syntax used for matching not only in Rust but overall. In Rust Using patterns in conjunction with match expressions and other constructs gives more control over a program’s control flow.
7. Rust provides feature of ‘Efficient C bindings’ which means that Rust language can be able to interoperate with the C language.
Now we can understand why developers love Rust, because of its memory management, safety, and speed. Now let’s write some Rust code.
But wait, first things first, we must get Rust itself. I will write down installation process for Windows, Mac and Linux is not much different. If you already have Rust installed you can skip the next part.
Installation
Let’s begin, just go here and download installer, run it and follow the instructions. The easiest way is just to select “default installation”.
After you installed Rustup let’s check if everything is installed correctly. Open command line and type:
rustc — version
You should see something like this:
If you see some errors, check if you have Rust in PATH.
After this make sure you installed visual studio C++ build tools, because it’s used in Rust. If you are still facing some problems, double check all installation process steps.
Now we can write programs in Rust, cool. Next question you can have is: “What IDE use?”. I prefer Visual Studio Code, with Rust extension. But you can use something else (Visual Studio, Intellij Rust, etc).
And the last thing before we begin, let’s check if we have installed Cargo. Cargo is a package manager that helps us in managing dependencies of our projects. By default you have it out of the box along with rustup.
Just enter in your command line:
cargo — version
If everything is fine, you will have next result:
Comparing Rust
Comparing different programming languages is ungrateful job, every language has its own advantages and disadvantages, but still, I dare. In this part I`ll try to show Rust`s main features on live and ease examples. At the same time, this examples will be recreated on the other programming languages, just for comparison purposes. I will show code and time of running of the chosen algorithm (time of executing of helping code not included). For this purpose I chose two classic algorithms, “Bubble” sorting and “Quick” sorting. I chose these two algorithms intentionally, because they consider as slowest and fastest sorting algorithms and known for every developer.
Theory part
Bubble sorting — easiest sorting algorithm which is maximally effective on a small arrays. The idea of the algorithm, program iterating over array A and if element Ai < Ai+1 w here i is a current iteration, than Ai and Ai+1 swaps places in array A. Thi s process continues until the array A is not completely sorted.
Algorithm complexity : O =(n^2)
Quick sorting — universal sorting algorithm, considered as the fastest (what a surprise) algorithms. It is a “Divide and conquer” type of algorithm. The idea of the algorithm:
- Choosing random element from array, pivot element.
- All array elements are compared with pivot element and transferred, forming the following sequences: values less than the pivot, values equal to the pivot and greater than the pivot.
- Repeat step 2 for all sequences, until array sorted.
Algorithm complexity (in average) : O =(n log n)
In all these examples I’ve tried not to use external libraries (used only for supporting functionalities, generating random values, noting time, etc) and optimization techniques because they different on each language and produce different results.
Code snippets
Bubble sorting
C++
#include <iostream>
#include <math.h>
#include <chrono>
#include <algorithm>
#include <stdlib.h>
using namespace std;
using namespace std::chrono;
void swap(int* xp, int* yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
}
}
}
}
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int testArr[1000];
for (int i = 0; i < 1000; ++i) {
testArr[i] = rand() % 1000 + 1;
}
auto start = high_resolution_clock::now();
int n = sizeof(testArr) / sizeof(testArr[0]);
bubbleSort(testArr, n);
auto stop = high_resolution_clock::now();
printArray(testArr, n);
auto duration = duration_cast<microseconds>(stop - start);
cout << "Time taken by algorithm: "
<< duration.count() << " microseconds" << endl;
return 0;
}Python
import random
import time
def bubbleSort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
arr = random.sample(range(1, 10000), 1000)
start_time = time.time()
bubbleSort(arr)
print("--- %s seconds ---" % (time.time() - start_time))
print ("Sorted array is:")
for i in range(len(arr)):
print ("%d" %arr[i]),Java
import java.util.Collections;
import java.util.Random;
public class BubbleSort {
public static void main(String args[]) {
Random random = new Random();
int[] arr = new int[1000];
for (int i = 0; i < 1000; i++) {
arr[i] = random.nextInt(100);
}
System.out.println(System.currentTimeMillis());
bubbleSort(arr);
System.out.println(System.currentTimeMillis());
}
static void bubbleSort(int arr[]) {
int len = arr.length, tmp;
boolean flag;
for (int i = 0; i < len; i++) {
flag = false;
for (int j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = true;
}
}
if (!flag)
break;
}
}
}Rust
extern crate time; (1)
use rand;
use time::PreciseTime; (2)
pub fn bubble_sort(vec: &mut Vec<u64>) { (3)
let mut swapped = true; (4)
while swapped {
swapped = false;
for i in 1..vec.len() { (5)
if vec[i - 1] > vec[i] {
vec.swap(i - 1, i); (6)
swapped = true
}
}
}
}
fn main() { (7)
let mut vec: Vec<u64> = Vec::with_capacity(1000); (8)
for _ in 0..vec.capacity() {
vec.push(rand::random());
}
let start = PreciseTime::now();
bubble_sort(&mut vec);
let end = PreciseTime::now();
println!("{} seconds for whatever you did.", start.to(end));
println!("{:?}", vec); (9)
}Let’s break down some of the lines of previous code snippet.
- Importing all items from “Time” crate.
- Specifying that we going to use “PreciseTime” function from “Time” crate
- Initializing function with argument of Vector type Nothing special for C++ guys except that mut keyword (see next)
- Initializing mutable variable. Here we see Type inference example. Rust is statically typed language, but in this particular case I didn’t specified type of variable and it evaluate at the compiling time. Add link
- Just usual for loop that will look familiar for Python or Js guys.
- Using standard vector method for swapping items in vector.
- Main function which is an entry point for program.
- Initializing vector with 1000 elements.
- Using “println!” Macro for outputting data (vector values).
Let’s look at item (8) closer. It is showing us the main concept of Rust memory safety, ownership. Here vec is owner of 1000 random generated numbers.
Let’s create easier snippet of code to demonstrate ownership on example:
let vec = vec![1, 2, 3];
let test = vec;
println!("{:?}", vec);If we try to run this snippet, we will receive this error:
It means, that we are trying to use “borrowed” values and trying to gain access to moved value. By doing this, we are breaking the rule of One owner, which states: Two variables cannot point to the same memory location. Here, we have two owners of one value, variables vec and test. Look at this diagram.
As you see from diagram, test and vec pointing to the same value in memory heap, Rust is very effective in memory management and don’t copy values in cases like this one, instead he borrows it.
Vec variable borrowed values from test, and now we can use this values only with vec variable.
We can fix this error just by adding & to test variable.
let vec = vec![1, 2, 3];
let test = &vec;
println!("{:?}", vec);Now we referencing to the value of vec. By referencing to the value, we borrowing it and did not breaking the rule of: “One owner”. We can mutate this value if needed, it’s called mutable referencing, remember in this case original vec will be mutated.
Quick sorting
C++
#include <iostream>
#include <math.h>
#include <chrono>
#include <algorithm>
#include <stdlib.h>
using namespace std;
using namespace std::chrono;
using namespace std;
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++)
{
if (arr[j] < pivot)
{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high)
{
if (low < high) {
int p = partition(arr, low, high);
quickSort(arr, low, p - 1);
quickSort(arr, p + 1, high);
}
}
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int testArr[1000];
for (int i = 0; i < 1000; ++i) {
testArr[i] = rand() % 1000 + 1;
}
int n = sizeof(testArr) / sizeof(testArr[0]);
auto start = high_resolution_clock::now();
quickSort(testArr, 0, n - 1);
auto stop = high_resolution_clock::now();
printArray(testArr, n);
auto duration = duration_cast<microseconds>(stop - start);
cout << "Time taken by algorithm: "
<< duration.count() << " microseconds" << endl;
return 0;
}Python
import random
import time
def partition(arr,low,high):
i = (low - 1)
pivot = arr[high]
for j in range(low , high):
if arr[j] < pivot:
i = i + 1
arr[i],arr[j] = arr[j],arr[i]
arr[i + 1],arr[high] = arr[high],arr[i + 1]
return (i + 1)
def quickSort(arr,low,high):
if low < high:
pi = partition(arr,low,high)
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
arr = random.sample(range(1, 10000), 1000)
n = len(arr)
start_time = time.time()
quickSort(arr,0,n - 1)
print("--- %s seconds ---" % (time.time() - start_time))
print("Sorted array is:")
for i in range(n):
print("%d" % arr[i]),Java
import java.util.Random;
public class QuickSort {
public static void main(String args[]) {
Random random = new Random();
int[] arr = new int[1000];
for (int i = 0; i < 1000; i++) {
arr[i] = random.nextInt(100);
}
System.out.println(System.currentTimeMillis());
quickSort(arr, 0 , 999);
System.out.println(System.currentTimeMillis());
}
static void quickSort(int arr[], int lower, int upper) {
if (lower >= upper)
return;
int p = partition(arr, lower, upper);
quickSort(arr, lower, p - 1);
quickSort(arr, p + 1, upper);
}
private static int partition(int arr[], int lower, int upper) {
int pivot = arr[upper];
int j = lower;
int tmp;
for (int i = lower; i <= upper; i++) {
if (arr[i] < pivot) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
j++;
}
}
tmp = arr[upper];
arr[upper] = arr[j];
arr[j] = tmp;
return j;
}
}Rust
extern crate time;
use rand;
use time::PreciseTime;fn quick_sort(array: &mut Vec<u64>, first: usize, last: usize) {
if first < last {
let mut midpoint = partition(array, first, last);
quick_sort(array, first, midpoint - 1);
quick_sort(array, midpoint + 1, last);
}
}
fn swap(array: &mut Vec<u64>, a: usize, b: usize) {
let temp = array[a];
array[a] = array[b];
array[b] = temp;
}
fn partition(array: &mut Vec<u64>, first: usize, last: usize) -> usize {
let pivot = array[last];
let mut i = first;
let mut j = first;
while j < last - 1 {
if array[j] < pivot {
array.swap(i, j);
i += 1;
}
j += 1;
}
if array[last] < array[i] {
array.swap(i, last);
}
i
}
fn main() {
let mut vec: Vec<u64> = Vec::with_capacity(1000);
for _ in 0..vec.capacity() {
vec.push(rand::random());
}
let start = PreciseTime::now();
quick_sort(&mut vec, 0, 999);
let end = PreciseTime::now();
println!("{} seconds.", start.to(end));
println!("{:?}", vec);
}
Results
Let’s look at the results.
C++
Bubble (average):
runtime: 0.00944595
memory used : 3248 kilobytes
Quick (average):
runtime: 0.000368699
memory used 3196 kilobytes
Rust
Bubble (average):
runtime: 0.09225978500000001
memory used: 2192 kilobytes
Quick (average):
runtime: 0.0005941200000000001
memory used: 2272 kilobytes
Java
Bubble (average):
runtime: 0.01008815949
memory used: 30144 kilobytes
Quick (average):
runtime:0.00108797455
memory used: 30980 kilobytes
Python
Bubble (average):
runtime: 0.1853432178497314
memory used: 11328 kilobytes
Quick (average):
runtime: 0.009276270866394043
memory used: 11392 kilobytes
Summary
Let’s sum up results.
Best runtime,
Bubble sorting: C++, Java, Rust, Python,
Quick sorting: C++, Rust, Java, Python,
As it was expected, best time result have C++, because of its low level origin. The second place is for Java and Rust for Bubble and Quick sortings relatively. As you can see Java results not very different from each other, only 9 milliseconds, when Rust results differ from each other in 91.665665 milliseconds! I rewrote this algorithm and tried to use algorithm from bubble_sort crate but results was almost the same. I think this speed bump is connected to two things, first its for in loop, loops in Rust pretty slow by itself and besides for in we have infinite while loop. And the second problem is swapping items right in vector.
Best memory usage:
Bubble: RUST, C++, Python, Java
Quick: RUST, C++, Python, Java
Rust`s selling feature memory management come into play here, and make a difference. Rust showing us the best results in both examples. Difference between the first two places, Rust and C++ is 336 kilobytes and 1056 kilobytes in Bubble and Quick sorting respectively. Maybe not that much for nowadays, but still. But Difference between Rust and Java (last place) is very serious, 27 952 kilobytes and 28 708 kilobytes in Bubble and Quick sorting respectively.
Let’s remember quote from the very beginning of this article about speed of Rust, I think that it’s fully proved with this results. Are you agree?
At last, I want to say that, each language has its strong and weak sides, it’s up to you to pick the right one. So pick wisely, and If my article helped you in this a bit, hit that clap button.