Mengapa Rust Harus Menjadi Bahasa Pemrograman Fungsional

Halo, Habr!

Setelah mulai mempelajari Scala, saya langsung menemukan fakta bahwa implementasi fungsional dari algoritma pengurutan cepat paling sederhana bekerja lebih lambat secara radikal dan mengkonsumsi memori lebih banyak daripada implementasi imperatif serupa. Pada saat yang sama, tidak ada yang membantah bahwa kode fungsional lebih ringkas, ekspresif, dan tahan kesalahan. Menulis ulang kedua contoh di Rust, saya menemukan beberapa hal penting yang ingin saya bagikan. Detail di bawah potongan, dan di sini saya hanya akan memberikan kesimpulan singkat:

1. Untuk implementasi imperatif - keuntungan dari Rust hanya 20%. Ini berarti bahwa JVM telah mendekati kinerja asli, dan tidak ada yang tersisa untuk diperbaiki.
2. Untuk implementasi fungsional, Rust ternyata 4,5 kali lebih cepat, konsumsi memori menurun 5,5 kali, dan tidak adanya pengumpul sampah membuat program lebih stabil (lebih sedikit variasi dalam kinerja). Ini menarik bagi mereka yang ingin menulis program fungsional cepat.
3. Konsep satu-satunya pemilik data (dan satu-satunya referensi yang bisa berubah-ubah) yang diadopsi di Rust sangat mirip dengan konsep immutability, sebagai akibatnya algoritma fungsional berdasarkan pada immutability, rekursi, dan penyalinan dengan mudah jatuh pada Rust dengan hampir tidak ada penulisan ulang, sementara algoritma imperatif memaksa kode untuk didesain ulang. pertimbangkan mutabilitas tautan, masa hidup, dll.

Kesimpulan - Rust tampaknya dibuat secara khusus untuk FP, meskipun kemungkinan sintaksnya belum mencapai Scala.

Jadi, mari kita mulai dengan Scala dan menerapkan pemilahan cepat dalam 2 gaya:

Secara imperatif - kami menggunakan array yang sama, mengatur ulang elemen di dalamnya menggunakan prosedur rekursif. Kami melihat kode verbose, berpotensi rentan terhadap kesalahan ketik, tetapi secara optimal menggunakan memori, dan secepat mungkin.

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.

.