Por qué el óxido debería convertirse en un lenguaje de programación funcional

Hola Habr!

Después de comenzar a estudiar Scala, inmediatamente me encontré con el hecho de que la implementación funcional del algoritmo de clasificación rápida más simple funciona radicalmente más lento y consume significativamente más memoria que una implementación imperativa similar. Al mismo tiempo, nadie discute que el código funcional es más conciso, expresivo y resistente a errores. Reescribiendo ambos ejemplos en Rust, descubrí varias cosas importantes que quiero compartir. Detalles debajo del corte, y aquí solo daré breves conclusiones:

1. Para una implementación imperativa, la ganancia de Rust fue solo del 20%. Esto significa que la JVM se ha acercado al rendimiento nativo, y no queda nada por mejorar.
2. Para una implementación funcional, Rust resultó ser 4,5 veces más rápido, el consumo de memoria disminuyó en 5,5 veces y la ausencia de un recolector de basura hizo que el programa fuera más estable (hay menos variación en los indicadores). Esto es interesante para aquellos que desean escribir programas funcionales rápidos.
3. El concepto del único propietario de los datos (y la única referencia mutable) adoptado en Rust es muy similar al concepto de inmutabilidad, como resultado de lo cual los algoritmos funcionales basados ​​en la inmutabilidad, la recursión y la copia caen fácilmente en Rust prácticamente sin reescritura, mientras que los algoritmos imperativos obligan a que el código se rediseñe. considerar la mutabilidad del enlace, la vida útil, etc.

Conclusión : Rust parece haber sido creado especialmente para el FP, aunque las posibilidades de su sintaxis aún no han llegado a Scala.

Entonces, comencemos con Scala e implementemos una ordenación rápida en 2 estilos:

Imperativamente : utilizamos la misma matriz, reorganizando los elementos que contiene utilizando un procedimiento recursivo. Vemos código detallado, potencialmente vulnerable a errores tipográficos, pero que utiliza la memoria de manera óptima y lo más rápido posible.

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.

.