Warum Rost eine funktionale Programmiersprache werden sollte

Hallo habr

Als ich anfing, Scala zu studieren, stieß ich sofort auf die Tatsache, dass die funktionale Implementierung des einfachsten schnellen Sortieralgorithmus wesentlich langsamer arbeitet und erheblich mehr Speicher verbraucht als eine ähnliche zwingende Implementierung. Gleichzeitig bestreitet niemand, dass der Funktionscode präziser, aussagekräftiger und fehlerresistenter ist. Beim Umschreiben beider Beispiele in Rust habe ich einige wichtige Dinge entdeckt, die ich mitteilen möchte. Details unter dem Schnitt, und hier werde ich nur kurze Schlussfolgerungen geben:

1. Für die zwingende Umsetzung - der Gewinn von Rust betrug nur 20%. Dies bedeutet, dass die JVM der nativen Leistung nahe gekommen ist und nichts mehr zu verbessern ist.
2. Für eine funktionale Implementierung erwies sich Rust als 4,5-mal schneller, der Speicherverbrauch verringerte sich um das 5,5-fache, und das Fehlen eines Garbage Collectors machte das Programm stabiler (weniger Leistungsschwankungen). Dies ist interessant für diejenigen, die schnelle Funktionsprogramme schreiben möchten.
3. Das Konzept des alleinigen Eigentümers der Daten (und der einzigen veränderlichen Referenz), das in Rust übernommen wurde, ist dem Konzept der Unveränderlichkeit sehr ähnlich, wodurch Funktionsalgorithmen, die auf Unveränderlichkeit, Rekursion und Kopieren basieren, praktisch ohne Umschreiben auf Rust fallen, während zwingende Algorithmen eine Neugestaltung des Codes erfordern. Berücksichtigen Sie die Verknüpfungsveränderlichkeit, die Lebensdauer usw.

Fazit - Rust scheint speziell für die FP geschaffen worden zu sein, obwohl die Möglichkeiten seiner Syntax Scala noch nicht erreichen.

Beginnen wir also mit Scala und implementieren eine schnelle Sortierung in zwei Stilen:

Unbedingt verwenden wir dasselbe Array und ordnen die darin enthaltenen Elemente mithilfe einer rekursiven Prozedur neu an. Wir sehen ausführlichen Code, der möglicherweise anfällig für Tippfehler ist, aber den Speicher optimal nutzt und so schnell wie möglich ist.

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.

.