Man könnte denken, bei der Rückgabe einer großen struct
müsse diese zwischen den Stack Frames kopiert werden. Tatsächlich
erzeugt der Compiler eine große struct im Stack Frame
des Aufrufers und einen Zeiger auf die struct als
Referenzparameter. Das gleiche gilt für eine große enum.
Würde man die struct mit Box einhüllen,
würde das Programm sogar weniger effizient sein, weil ständig
Heap-Allokationen und -Freigaben vorgenommen würden.
Beispiel:
struct Chunck {
data: [u64; 10]
}
impl Chunck {
fn new() -> Box<Chunck> {
Box::new(Chunck {data: [0; 10]})
}
}
fn main() {
let a = Chunck::new();
println!("{:?}", a.data);
}
Es sollte besser auf Box verzichtet werden:
impl Chunck {
fn new() -> Chunck {
Chunck {data: [0; 10]}
}
}
Betrachten wir nochmals den Typ Ru32 aus dem
Abschnitt ›Monaden‹ im Kapitel
›Sichere Programmierung‹. Mit einem gewissen Unbehagen stellt man
bei diesem fest, dass std::mem::size_of::<Ru32>()
auf einer 32 Bit-Architektur den Wert 8 liefert.
Da ist nun wie in einem Hefezopf viel Luft im Typ enthalten.
Benutzt man für die Fehlerinformation stattdessen Werte aus dem
ursprünglichen Definitionsbereich, erlaubt dies die Kompression auf den
ursprünglichen Speicherplatz von 32 Bit. Den Fehlerwert kodieren
wir einfach als u32::MAX. Unter geringfügigen semantischen
Änderungen nimmt das Programm dann die folgende Form an:
mod ru32 {
#[derive(Clone, Copy)]
pub struct Ru32 (u32);
impl Ru32 {
pub fn err() -> Self {Ru32(u32::MAX)}
fn bind(self, f: impl Fn(u32)->Self) -> Self {
match self.0 {
u32::MAX => Self::err(),
x => f(x)
}
}
}
impl std::fmt::Display for Ru32 {
fn fmt(&self, f: &mut std::fmt::Formatter)
-> std::fmt::Result
{
match self.0 {
u32::MAX => write!(f, "Ru32(Err)"),
x => write!(f, "Ru32({})", x)
}
}
}
impl From<u32> for Ru32 {
fn from(x: u32) -> Self {Self(x)}
}
impl From<char> for Ru32 {
fn from(c: char) -> Self {Self(u32::from(c))}
}
impl From<Option<u32>> for Ru32 {
fn from(x: Option<u32>) -> Self {Self(x.unwrap_or(u32::MAX))}
}
impl std::ops::Add<Self> for Ru32 {
type Output = Self;
fn add(self, y: Self) -> Self {
self.bind(|x| y.bind(|y| Self::from(x.checked_add(y))))
}
}
impl std::ops::Mul<Ru32> for u32 {
type Output = Ru32;
fn mul(self, y: Ru32) -> Ru32 {
y.bind(|y| Ru32::from(self.checked_mul(y)))
}
}
}
use ru32::Ru32;
fn str_to_u32(s: &str) -> Ru32 {
let mut acc = Ru32::from(0);
for digit in s.chars() {
if !digit.is_digit(10) {return Ru32::err();}
acc = 10*acc + Ru32::from(u32::from(digit) - u32::from('0'));
}
acc
}
fn main() {
println!("size of Ru32: {}", std::mem::size_of::<Ru32>());
println!("{}", str_to_u32("1440"));
println!("{}", str_to_u32("10000000000"));
}
Rust erlaubt die abstrakte Verkettung von Operatoren, womit
allokationsfreie Operationen ermöglicht werden. Man definiert dazu
einen Trait Flush, dessen Methode das Endergebnis
der Berechnung in einen zur Verfügung stehenden Puffer schreibt.
Im Wesentlichen erhält man so etwas hübschere Schreibweisen für Routinen als wie die in BLAS (Basic Linear Algebra Subprograms). Man muss das nicht sinnvoll finden, ich will es nur einmal gezeigt haben.
Es folgt eine Demonstration anhand von Linearkombinationen.
use std::ops::{Add, Mul};
struct Vector {
data: Vec<f64>
}
impl Vector {
pub fn new(v: Vec<f64>) -> Self {Vector {data: v}}
}
impl std::fmt::Display for Vector {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "{:?}", self.data)
}
}
trait Flush {
fn flush(self, buffer: &mut Vector) -> &mut Vector;
}
struct Multiplication<'a> {
r: f64,
v: &'a Vector
}
struct Addition<'a> {
v: &'a Vector,
w: &'a Vector
}
struct AddMul<'a> {
m: Multiplication<'a>,
v: &'a Vector
}
struct AddMulMul<'a> {
ma: Multiplication<'a>,
mb: Multiplication<'a>
}
impl Mul<f64> for Vector {
type Output = Vector;
fn mul(mut self, r: f64) -> Vector {
for x in &mut self.data {*x *= r;}
self
}
}
impl Mul<Vector> for f64 {
type Output = Vector;
fn mul(self, mut rhs: Vector) -> Vector {
for x in &mut rhs.data {*x *= self;}
rhs
}
}
impl<'a> Mul<&'a Vector> for f64 {
type Output = Multiplication<'a>;
fn mul(self, b: &'a Vector) -> Multiplication<'a> {
Multiplication {r: self, v: b}
}
}
impl<'a> Mul<&'a mut Vector> for f64 {
type Output = Multiplication<'a>;
fn mul(self, b: &'a mut Vector) -> Multiplication<'a> {
Multiplication {r: self, v: b}
}
}
impl Add<&Vector> for Vector {
type Output = Vector;
fn add(mut self, b: &Vector) -> Vector {
for (i, x) in self.data.iter_mut().enumerate() {
*x += b.data[i];
}
self
}
}
impl Add<Vector> for Vector {
type Output = Vector;
fn add(self, b: Vector) -> Vector {self+&b}
}
impl<'a> Add<&'a Vector> for &'a Vector {
type Output = Addition<'a>;
fn add(self, b: &'a Vector) -> Addition<'a> {
Addition {v: self, w: b}
}
}
impl<'a> Add<&'a Vector> for Multiplication<'a> {
type Output = AddMul<'a>;
fn add(self, b: &'a Vector) -> AddMul<'a> {
AddMul {m: self, v: b}
}
}
impl<'a> Add<Multiplication<'a>> for Multiplication<'a> {
type Output = AddMulMul<'a>;
fn add(self, b: Multiplication<'a>) -> AddMulMul<'a> {
AddMulMul {ma: self, mb: b}
}
}
impl<'a> Flush for Multiplication<'a> {
fn flush(self, buffer: &mut Vector) -> &mut Vector {
let data = &mut buffer.data;
for (i,x) in data.iter_mut().enumerate() {
*x = self.r*self.v.data[i];
}
buffer
}
}
impl<'a> Flush for Addition<'a> {
fn flush(self, buffer: &mut Vector) -> &mut Vector {
let data = &mut buffer.data;
for (i, x) in data.iter_mut().enumerate() {
*x = self.v.data[i] + self.w.data[i];
}
buffer
}
}
impl<'a> Flush for AddMul<'a> {
fn flush(self, buffer: &mut Vector) -> &mut Vector {
let data = &mut buffer.data;
let m = &self.m;
let v = &self.v;
for (i, x) in data.iter_mut().enumerate() {
*x = m.r*m.v.data[i] + v.data[i];
}
buffer
}
}
impl<'a> Flush for AddMulMul<'a> {
fn flush(self, buffer: &mut Vector) -> &mut Vector {
let data = &mut buffer.data;
let ma = &self.ma;
let mb = &self.mb;
for (i, x) in data.iter_mut().enumerate() {
*x = ma.r*ma.v.data[i] + mb.r*mb.v.data[i];
}
buffer
}
}
#[allow(unused_macros)]
macro_rules! calc {
( $x:tt = $value:expr ) => {
let $x = $value.flush($x);
}
}
fn main() {
let e1 = &Vector::new(vec![1.0, 0.0]);
let e2 = &Vector::new(vec![0.0, 1.0]);
let a = &mut Vector::new(vec![0.0, 0.0]);
let b = &mut Vector::new(vec![0.0, 0.0]);
calc!{a = 2.0*e1 + 4.0*e2};
calc!{b = 2.0*(a as &Vector) + 2.0*e2};
println!("{}", a);
println!("{}", b);
}
Beim vorangegangenen Ansatz ist die Form der Ausdrücke
eingeschränkt. Diese Einschränkung kann man durch generische
Implementationen auflösen, die rekursiv über die zugrunde
liegende Struktur formuliert sind. Diese Struktur muss man
dann nur noch ausrechnen lassen. Die Idee zur Vermeidung von
Komplikationen ist dabei eine abstrakte Indizierungsoperation
get, die Strukturen indizieren kann. Idealerweise
sind die Strukturen zero cost, werden also vollständig
wegoptimiert.
pub mod vector {
use std::ops::{Add, Sub, Mul};
pub struct Vector(pub Vec<f64>);
pub struct Addition<A: Get, B: Get>(A, B);
pub struct ScalarMul<A: Get>(f64, A);
impl Vector {
pub fn flush<A: Get>(&mut self, a: A) {
for (i, v) in self.0.iter_mut().enumerate() {
*v = a.get(i);
}
}
}
impl std::fmt::Display for Vector {
fn fmt(&self, f: &mut std::fmt::Formatter)
-> std::fmt::Result
{
write!(f, "{:?}", self.0)
}
}
pub trait Get {
fn len(&self) -> usize;
fn get(&self, i: usize) -> f64;
}
impl Get for &Vector {
fn len(&self) -> usize {self.0.len()}
fn get(&self, i: usize) -> f64 {self.0[i]}
}
impl<A: Get, B: Get> Get for Addition<A, B> {
fn len(&self) -> usize {self.0.len()}
fn get(&self, i: usize) -> f64 {
self.0.get(i) + self.1.get(i)
}
}
impl<A: Get> Get for ScalarMul<A> {
fn len(&self) -> usize {self.1.len()}
fn get(&self, i: usize) -> f64 {
self.0*self.1.get(i)
}
}
impl<'a, B: Get> Add<B> for &'a Vector {
type Output = Addition<&'a Vector, B>;
fn add(self, b: B) -> Self::Output {
Addition(self, b)
}
}
impl<'a, B: Get> Sub<B> for &'a Vector {
type Output = Addition<&'a Vector, ScalarMul<B>>;
fn sub(self, b: B) -> Self::Output {
Addition(self, ScalarMul(-1.0, b))
}
}
impl<A0: Get, A1: Get, B: Get> Add<B> for Addition<A0, A1> {
type Output = Addition<Self, B>;
fn add(self, b: B) -> Self::Output {
Addition(self, b)
}
}
impl<A0: Get, A1: Get, B: Get> Sub<B> for Addition<A0, A1> {
type Output = Addition<Self, ScalarMul<B>>;
fn sub(self, b: B) -> Self::Output {
Addition(self, ScalarMul(-1.0, b))
}
}
impl<A: Get, B: Get> Add<B> for ScalarMul<A> {
type Output = Addition<Self, B>;
fn add(self, b: B) -> Self::Output {
Addition(self, b)
}
}
impl<A: Get, B: Get> Sub<B> for ScalarMul<A> {
type Output = Addition<Self, ScalarMul<B>>;
fn sub(self, b: B) -> Self::Output {
Addition(self, ScalarMul(-1.0, b))
}
}
impl<'a> Mul<&'a Vector> for f64 {
type Output = ScalarMul<&'a Vector>;
fn mul(self, a: &'a Vector) -> Self::Output {
ScalarMul(self, a)
}
}
impl<A: Get, B: Get> Mul<Addition<A, B>> for f64 {
type Output = ScalarMul<Addition<A, B>>;
fn mul(self, a: Addition<A, B>) -> Self::Output {
ScalarMul(self, a)
}
}
impl<B: Get> Mul<B> for &Vector {
type Output = f64;
fn mul(self, b: B) -> f64 {
let a = &self.0;
let mut acc = 0.0;
for i in 0..a.len() {
acc += a[i]*b.get(i);
}
acc
}
}
impl<A0: Get, A1: Get, B: Get> Mul<B> for Addition<A0, A1> {
type Output = f64;
fn mul(self, b: B) -> f64 {
let mut acc = 0.0;
for i in 0..self.len() {
acc += self.get(i)*b.get(i);
}
acc
}
}
pub fn norm<A: Get>(v: A) -> f64 {
let mut s = 0.0;
for i in 0..v.len() {
let a = v.get(i);
s += a*a;
}
s.sqrt()
}
}
use vector::Vector;
fn main() {
let v = &Vector(vec![1.0, 2.0]);
let w = &Vector(vec![3.0, 4.0]);
let mut buf = Vector(vec![0.0, 0.0]);
buf.flush(2.0*v + 4.0*w + 5.0*(v - 2.0*w));
println!("{}", buf);
println!("{}", (v + w)*(v - w));
println!("{}", v*v - w*w);
}
Funktionsaufrufe kosten einen gewissen Verwaltungsaufwand, weil ein Teil des Maschinenzustands gespeichert werden muss, damit der Programmablauf beim Verlassen der Funktion wieder zurückfindet. Aus diesem Grund setzt der Compiler bei kurzen Funktionen die Berechnungen der Funktion anstelle des Aufrufs direkt ein, womit der Verwaltungsaufwand entfällt. Man spricht von einer Inline-Ersetzung. Dieses Verfahren ist einer Makro-Expansion recht ähnlich, – und als diese Art von Optimierung in der Frühzeit der Computer-Programmierung noch nicht zur Verfügung stand, hat man dafür tatsächlich Makros herangezogen.
Im Normalfall entscheidet der Compiler darüber, ob eine Inline-Ersetzung günstig ist. Zur manuellen Kontrolle kann man Funktionen aber auch mit einem Attribut versehen.
| Attribut | Wirkung |
|---|---|
#[inline] | Inline-Ersetzung über die Crate-Grenze hinaus gewünscht |
#[inline(always)] | Inline-Ersetzung nachdrücklich gewünscht |
#[inline(never)] | Inline-Ersetzung nachdrücklich ungewünscht |
Nun kann es sein, dass man Inline-Ersetzung derselben Funktion lediglich an bestimmten Stellen geschehen lassen möchte. In Programmen sind nur bestimmte Ausführungspfade heiß. Viele kalte Pfade liegen dagegen außerhalb von berechnungsintensiven Schleifen. Durch übermäßige Inline-Ersetzung, die auch an kalten Pfaden vorgenommen wird, kann sich ein Programm mehr oder weniger aufblähen, sodass mit der erhöhten Programmgröße auch der Cache-Speicher höher belegt wird, was der Performanz im Extremfall paradoxerweise zuwiderlaufen kann.
Um die feinere Kontrolle über die Inline-Ersetzung einer
Funktion f zu erhalten, schreibt man zunächst die
Variante f_inline der Funktion, bei welcher die
Inline-Ersetzung stattfinden soll. Zum Verhindern der Ersetzung
schreibt man eine zweite Variante f, welche den
Aufruf schlicht an f_inline weitergibt, woraufhin die
Berechnung aus f_inline in den Körper
von f inline-ersetzt wird. Weil f
eine separate Funktion ist, darf f nun ein anderes
Attribut als f_inline erhalten.
Kurzes Beispiel:
#[inline(always)]
fn f_inline(x: i32) -> i32 {x + 1}
#[inline(never)]
fn f(x: i32) -> i32 {f_inline(x)}
Um in Erfahrung zu bringen ob die Inline-Ersetzung an einer bestimmten kritischen Stelle zielführend ist, sollte man sicherlich Messungen durchführen und das erzeugte Maschinenprogramm untersuchen.
Nebenbei bemerkt taucht im Release-Modus bedingt durch die
Inline-Ersetzung nicht jeder Funktionsaufruf im Stack-Trace
auf. Man benögtigt inline(never), um das Erscheinen
zu erzwingen.