Pourquoi Rust devrait devenir un langage de programmation fonctionnel

Bonjour, Habr!

Après avoir commencé à étudier Scala, je suis immédiatement tombé sur le fait que l'implémentation fonctionnelle de l'algorithme de tri rapide le plus simple fonctionne radicalement plus lentement et consomme beaucoup plus de mémoire qu'une implémentation impérative similaire. En même temps, personne ne conteste que le code fonctionnel soit plus concis, expressif et résistant aux erreurs. En réécrivant les deux exemples dans Rust, j'ai découvert plusieurs choses importantes que je veux partager. Détails sous la coupe, et ici je ne donnerai que de brèves conclusions:

1. Pour une mise en œuvre impérative - le gain de Rust n'était que de 20%. Cela signifie que la JVM est proche des performances natives et qu'il n'y a plus rien à améliorer.
2. Pour une implémentation fonctionnelle, Rust s'est avéré être 4,5 fois plus rapide, la consommation de mémoire a diminué de 5,5 fois, et l'absence d'un garbage collector a rendu le programme plus stable (moins de variation de performances). C'est intéressant pour ceux qui veulent écrire des programmes fonctionnels rapides.
3. Le concept de propriétaire unique des données (et la seule référence mutable) adopté dans Rust est très similaire au concept d'immuabilité, à la suite duquel les algorithmes fonctionnels basés sur l'immuabilité, la récursivité et la copie tombent facilement sur Rust sans pratiquement réécriture, tandis que les algorithmes impératifs forcent le code à être repensé. considérer la mutabilité des liens, les durées de vie, etc.

Conclusion - Rust semble avoir été spécialement créé pour le FP, bien que les possibilités de sa syntaxe ne soient pas encore accessibles à Scala.

Commençons donc avec Scala et implémentons le tri rapide en 2 styles:

Impérativement - nous utilisons le même tableau, en réorganisant les éléments qu'il contient à l'aide d'une procédure récursive. Nous voyons du code verbeux, potentiellement vulnérable aux fautes de frappe, mais utilisant de manière optimale la mémoire, et aussi rapidement que possible.

def sort_imp(arr: Array[Double]) {
  def swap(i: Int, j: Int) {
    val t = arr(i)
    arr(i) = arr(j)
    arr(j) = t
  }

  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 (i < r) sort1(i, r)
  }

  if (arr.length > 1)
    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 i < r { sort1(arr, i, r); }
  };

  if arr.len() > 1 {
    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
  }
}

UPD
:

fn sort_fun(arr: Vec<f64>) -> Vec<f64> {
    if arr.len() <= 1 {
        arr
    } else {
        let pivot = arr[arr.len() / 2];
        [
            sort_fun(arr.iter().filter(|&&x| pivot > x).cloned().collect()),
            arr.iter().filter(|&&x| pivot == x).cloned().collect(),
            sort_fun(arr.iter().filter(|&&x| pivot < x).cloned().collect()),
        ]
        .concat()
    }
}

, — iter().filter(...).chain(...). zero-cost, , , — . , .

— , — , ( ).

($ cargo build --release):

• — 2
• — 9

— 650 .

:

, — , . , — , Rust -, , Rust , (, null ).

-, zero-cost — . Rust — - . , 2019 Scala Rust .

Scala.
Rust.

.