Por que a ferrugem deve se tornar uma linguagem de programação funcional

Olá Habr!

Depois de começar a estudar o Scala, deparei-me imediatamente com o fato de que a implementação funcional do algoritmo de classificação rápida mais simples funciona radicalmente mais devagar e consome significativamente mais memória do que uma implementação imperativa semelhante. Ao mesmo tempo, ninguém contesta que o código funcional seja mais conciso, expressivo e resistente a erros. Reescrevendo os dois exemplos no Rust, descobri várias coisas importantes que quero compartilhar. Detalhes sob o corte, e aqui vou dar apenas breves conclusões:

1. Para implementação imperativa - o ganho da Rust foi de apenas 20%. Isso significa que a JVM chegou perto do desempenho nativo e não há mais nada a melhorar.
2. Para uma implementação funcional, o Rust se mostrou 4,5 vezes mais rápido, o consumo de memória diminuiu 5,5 vezes e a ausência de um coletor de lixo tornou o programa mais estável (menos variação no desempenho). Isso é interessante para quem deseja escrever programas funcionais rápidos.
3. O conceito de proprietário único dos dados (e a única referência mutável) adotada no Rust é muito semelhante ao conceito de imutabilidade, como resultado dos quais algoritmos funcionais baseados em imutabilidade, recursão e cópia caem facilmente no Rust praticamente sem reescrever, enquanto algoritmos imperativos forçam o código a ser redesenhado. considere a mutabilidade do link, as vidas úteis, etc.

Conclusão - A ferrugem parece ter sido criada especialmente para o FP, embora as possibilidades de sua sintaxe ainda não cheguem ao Scala.

Então, vamos começar com o Scala e implementar a classificação rápida em 2 estilos:

Imperativamente - usamos a mesma matriz, reorganizando os elementos nela usando um procedimento recursivo. Vemos código detalhado, potencialmente vulnerável a erros de digitação, mas usando a memória de maneira ideal e o mais rápido possível.

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.

.