Rust als sichere Sprache für systemnahe und parallele Software

Stefan Lankes	Jens Breitbart

github.com/stlankes	github.com/jbreitbart
eduOS-rs, HermitCore	jensbreitbart.de
System Software @ RWTH	Here for fun and no profit

Stefan Lankes

Jens Breitbart

stl

jbreitbart

github.com/stlankes

github.com/jbreitbart

eduOS-rs, HermitCore

jensbreitbart.de

System Software @ RWTH

Here for fun and no profit

Hinweise zum Vortrag

Folien: https://stlankes.github.io/rust_parallel2018/
Beispiele: https://github.com/stlankes/rust_parallel2018
Einstieg: https://www.rust-lang.org
Playground: https://play.rust-lang.org
Tutorial: https://rustbyexample.com

curl https://sh.rustup.rs -sSf | sh

Was ist Rust?

Rust ist eine (relativ) neue Programmiersprache für systemnahe Software

fn main() {
    // Die Statements werden ausgeführt sobald
    // das compilierte Binary gestartet wird.

    // Ausgabe auf stdout
    println!("Hello para//el 2018!");
}

Bekannt u.a. für den Einsatz in Firefox

⇒ Rust Code läuft somit auf Millionen von Rechnern

Woher kommt Rust?

Rust ist ein open-source (MIT + Apache) Projekt
Wird aktuell primär von Mozilla Research gesponsort
Die Weiterentwicklung selbst wird allerdings stark durch die Community getrieben

Vorteile von Rust

C/C++ ähnliche Performance
- Link zu Vergleichsmessungen
Compilerbasierte Überprüfungen welche z.B.
- Speichersicherheit (ohne Garbage Collection) garantieren
- Data Races verhindern

⇒ Falscher Code compiliert nicht

Safety vs Speed

URL: http://thoughtram.io/rust-and-nickel/#/11

jhh

Einfache Integration von C

#[repr(C)]
struct RustObject {
    number: c_int
}

#[link(name = "libprinto")]
extern {
    fn c_print_object(object: *mut RustObject) -> c_int;
}

fn main() {
    let mut rust_object = /* TODO */;

    unsafe { c_print_object(&mut *rust_object); }
}

Ownership & Borrowing

std::vector<std::string>* x = nullptr;

{
	std::vector<std::string> z;

	z.push_back("Hello para//el 2018!");
	x = &z;
}

std::cout << (*x)[0] << std::endl;

Ist dieses C++-Beispiel problematisch?

Erlaubt Rust solche Referenzen?

let x;

{
	let z = vec!("Hello para//el 2018!");

	x = &z;
}

println!("{}", x[0]);

Fragen wir den Compiler

error[E0597]: `z` does not live long enough
  --> src/main.rs:9:8
   |
9  |         x = &z;
   |              ^ borrowed value does not live long enough
10 |     }
   |     - `z` dropped here while still borrowed
...
13 | }
   | - borrowed value needs to live until here

Ownership

Variablen werden an einen Besitzer (Owner) gebunden
Wird der Scope des Besitzers verlassen, wird die Variable freigeben
Yehuda Katz: Ownership is the right to destroy

Borrowing

Mit Hilfe von Referenzen kann der Besitzt ausgeliehen werden
Der Besitz geht automatisch wieder zurück, wenn die Referenz nicht mehr existiert

Sind die geschweiften Klammern nötig?

let mut x = vec!("Hello para//el 2018!");

{
	let z = &mut x;
	// Do something with z...
}

println!("{}", x[0]);

Ein einfaches Beispiel: Pi

Pi-Berechnung in C++

Für num_steps Rechtecke die Höhen bestimmen
Höhen Aufsummieren, zum Schluß mit der Breite multiplizieren

const int num_steps = 100000000;

double sum = 0.0;
double step = 1.0 / static_cast<double>(num_steps);

for (int i = 0; i < num_steps; ++i) {
    double x = (i + 0.5) * step;
    sum += 4.0 / (1.0 + x * x);
}

std::cout << "Pi = " <<  sum * step << std::endl;

Pi-Berechnung in Rust

Äquivalenter Code in Rust

const NUM_STEPS: u64 = 100000000;
let step = 1.0 / NUM_STEPS as f64;
let mut sum = 0.0;

for i  in 0..NUM_STEPS {
    let x = (i as f64 + 0.5) * step;
    sum += 4.0 / (1.0 + x * x);
}

println!("Pi: {}", sum * step);

Parallele Berechnung

Verteilung der Rechtecke über die Threads
Hier: Wettlaufsituation um die Variable sum

const double step = 1.0 / NUM_STEPS;
double sum = 0.0;

std::thread t([&](int start, int end){

    for (int i = start; i < end; i++) {
    	double x = (i + 0.5) * step;
    	sum += 4.0 / (1.0 + x * x);
    }

}, (NUM_STEPS / nthreads) *  tid
 , (NUM_STEPS / nthreads) * (tid + 1));

Berechnung mit Rust

Versuch einer Wettlaufsituation in Rust

let step = 1.0 / NUM_STEPS as f64;
let mut sum = 0.0 as f64;

let threads: Vec<_> = (0..nthreads)
    .map(|tid| {
        thread::spawn(|| {
            let start = (NUM_STEPS / nthreads) * tid;
            let end = (NUM_STEPS / nthreads) * (tid+1);

            for i in start..end {
                let x = (i as f64 + 0.5) * step;
                sum += 4.0 / (1.0 + x * x);
            }
        })
    }).collect();

for t in threads {
    t.join().unwrap();
}

Compiler schlägt Alarm

Ausgeliehene Objekte könnten das Original überleben

   |
37 | thread::spawn(|| {
   |               ^^ may outlive borrowed value `**step`
...
42 |    let x = (i as f64 + 0.5) * step;
   |                               ---- `**step` is borrowed
help: to force the closure to take ownership of `**step`
   |
37 |    thread::spawn(move || {
   |                  ^^^^^^^

⇒ Ein std::thread darf nur auf Variablen zugreifen die er besitzt oder welche static lifetime haben

Berechnung mit Rust

Übergabe der Ownership (Compiler Vorschlag)

let step = 1.0 / NUM_STEPS as f64;
let mut sum = 0.0 as f64;

let threads: Vec<_> = (0..nthreads)
    .map(|tid| {
        thread::spawn(move || 	{
            let start = (NUM_STEPS / nthreads) * tid;
            let end = (NUM_STEPS / nthreads) * (tid+1);

            for i  in start..end {
                let x = (i as f64 + 0.5) * step;
                sum += 4.0 / (1.0 + x * x);
            }
        })
    }).collect();

Compiler schlägt Alarm

Objekte werden als unveränderliche übergeben
Wettlaufsituation wird verhindert
Keine Lösung für die Pi-Berechnung

error: cannot assign to immutable captured outer variable
   |
43 |   sum += 4.0 / (1.0 + x * x);
   |   ^^^^^^^^^^^^^^^^^^^^^^^^^^

Schutz statischer Elemente

Statische Element können gelesen werden
unsafe-Blöcke für Änderungen zwingend nötig
- Entwickler wird sich den Gefahren bewußt

static readonly_number: u64 = 42;
static mut counter: u64 = 0;

pub fn init() {
    let i = readonly_number;

    unsafe {
        counter = i;
    }
}

Zugriffsschutz mit Mutexen / RWLock

Rust-Mutexe nehmen zu schützendes Objekt auf
lock-Methode liefert Objekt zum Zugriff zurück
Automatische Freigabe nach Zerstörung des Objekts

static readonly_number: u64 = 42;
static counter: Mutex<u64> = Mutex::new(0);

pub fn init() {
    let guard = counter.lock().unwrap();
    guard = readonly_number;
}

RWLock bietet ein ähnliches Interface.

Gemeinsame Variablen

Heap-Allokation ermöglicht längere Lebenszeit
- Speicherschutz über reference counting
- std::{Rc|Arc}<T> alloziert T auf dem Heap
- std::Arc is thread-sicher
scoped Threads aus dem Crossbeam crate (~OpenMP Thread Model) ermöglicht teilen von Stackvariablen

⇒ Bis jetzt aber nur unveränderliche Variablen

Atomare Variablen

Atomare Variablen (std::sync::atomic::*)
- Schwierig zu benutzen
- Folgt dem C11 Speichermodell mit Acquire/Release Semantik

let reference_count: AtomicUsize = 0;
reference_count.fetch_add(1, Ordering::Relaxed);

Grundsätzlich: Der trait std::marker::Sync muß für gemeinsame veränderliche Variablen implementiert werden

Parallele Berechnung

let sum = Arc::new(Mutex::new(0.0 as f64));

let threads: Vec<_> = (0..nthreads).map(|tid| {
    let sum = sum.clone();

    thread::spawn(move || {
        let start = (NUM_STEPS / nthreads) *  tid;
        let end =   (NUM_STEPS / nthreads) * (tid+1);
        for i in start..end {
            let x = (i as f64 + 0.5) * step;
            *sum.lock().unwrap() += 4.0 / (1.0 + x * x);
        }
    })
}).collect();

Berechnung mit Teilergebnissen

Der Mutex serialisiert die Berechnung
Idee: Teilergebnisse berechnen & zusammenführen

let step = 1.0 / NUM_STEPS as f64;
let sum = 0.0 as f64;

let threads: Vec<_> = (0..nthreads)
	.map(|tid| {
		thread::spawn(move || {
			let mut partial_sum = 0 as f64;
			for i  in start..end {
				let x = (i as f64 + 0.5) * step;
				partial_sum += 4.0 / (1.0 + x * x);
			}
			partial_sum
		})}).collect();

Zusammenführen der Teilergebnisse

Ergebnisse der Threads stehen beim join zur Verfügung

for t in threads {
	sum += t.join().unwrap();
}

Berechnung mit Kanälen

Ergebnisse durch Kanäle zusammenführen
- Analogie zu Communicating Sequential Processes (CSP) und Coroutines

fn term(start: u64, end: u64) -> f64
{
    let step = 1.0 / NUM_STEPS as f64;
    let mut sum = 0.0;

    for i in start..end {
        let x = (i as f64 + 0.5) * step;
        sum += 4.0 / (1.0 + x * x);
    }

    sum
}

Berechnung mit Kanälen

Teilergebnisse berechnen und versenden

let (tx, rx) = mpsc::channel();

for id in 0..nthreads {
    let thread_tx = tx.clone();
    let start = (NUM_STEPS / nthreads as u64) * id;
    let end = (NUM_STEPS / nthreads as u64) * (id+1);

    thread::spawn(move || {
        let partial_sum = term(start, end);
        thread_tx.send(partial_sum).unwrap();
    });
};

Berechnung mit Kanälen

Ergebnisse empfangen und aufaddieren

let mut sum = 0.0;

for _ in 0..nthreads {
    sum = sum + rx.recv().unwrap();
}

Diese Lösung skaliert wie gewünscht
Wie sieht es mit Lastbalanzierung aus?

Rayon: Parallelism in Rust

https://github.com/rayon-rs/rayon
Unterstützt parallele Berechungen auf Basis von Task-Parallelität und Work Stealing
- Ähnlich zu Cilk (daher auch der Name)
Biete aber auch Daten-Parallelität über Iteratoren

Iteratoren in Rust

Serielle Pi-Berechnung mit Hilfe von Iteratoren

let step = 1.0 / NUM_STEPS as f64;

let sum: f64 = (0..NUM_STEPS).into_iter()
    .map(|i| {
        let x = (i as f64 + 0.5) * step;
        4.0 / (1.0 + x * x)
    }).sum();

println!("Pi: {}", sum * (1.0 / NUM_STEPS as f64));

Pi-Berechnung mit Rayon

Parallele Pi-Berechnung mit Rayon
Lohnt sich nur bei größeren Aufgaben

let step = 1.0 / NUM_STEPS as f64;

let sum: f64 = (0..NUM_STEPS).into_par_iter()
    .map(|i| {
        let x = (i as f64 + 0.5) * step;
        4.0 / (1.0 + x * x)
    }).sum();

println!("Pi: {}", sum * (1.0 / NUM_STEPS as f64));

Das Laplace-Problem

Wärme-Verteilung innerhalb einer Platte
Gelöst mit Jacobi Over Relaxation (JOR)

Lösung mit Hilfe von Tasks

Lösung durch eine // For-Schleife

Zusammenfassung

Ownership / Borrowing ist für einen old school Entwickler gewönnungsbedürftig
Fearless concurency
- Der Compiler verhindert race conditions
- std hat Threads, Mutex, RW Lock und Arc
- Rayon und Crossbeam vereinfachen viele Aufgaben