لماذا يجب أن يصبح الصدأ لغة برمجة وظيفية

مرحبا يا هبر!

بعد أن بدأت دراسة Scala ، واجهت على الفور حقيقة أن التنفيذ الوظيفي لخوارزمية الفرز السريع أبسط يعمل بشكل أبطأ بشكل جذري ويستهلك ذاكرة أكثر بكثير من تنفيذ إلزامي مماثل. في الوقت نفسه ، لا يشكك أحد في أن الكود الوظيفي أكثر دقة وإيجابية ومقاومة للأخطاء. عند إعادة كتابة كلا المثالين في Rust ، اكتشفت العديد من الأشياء المهمة التي أريد مشاركتها. التفاصيل تحت الخفض ، وسأقدم هنا استنتاجات موجزة فقط:

1. للتنفيذ الضروري - كانت المكاسب من Rust 20٪ فقط. هذا يعني أن JVM اقتربت من الأداء الأصلي ، ولم يتبق شيء للتحسين.
2. من أجل تنفيذ وظيفي ، تبين أن Rust كان أسرع بـ 4.5 مرة ، وانخفض استهلاك الذاكرة بمقدار 5.5 مرة ، وجعل عدم وجود أداة تجميع مجمعي البيانات المهملة البرنامج أكثر استقرارًا (تباين أقل في الأداء). هذا مثير للاهتمام لأولئك الذين يرغبون في كتابة برامج وظيفية سريعة.
3. مفهوم المالك الوحيد للبيانات (والمرجع الوحيد القابل للتغيير) المعتمد في Rust مشابه جدًا لمفهوم القابلية للتغير ، ونتيجة لذلك فإن الخوارزميات الوظيفية القائمة على القابلية للتغيير ، العودية والنسخ تقع بسهولة على Rust عملياً دون إعادة كتابتها ، بينما تفرض الخوارزميات الإلزامية إعادة تصميم الكود. ضع في الاعتبار قابلية ارتباط الارتباطات وعمرها وما إلى ذلك

خاتمة - يبدو أن Rust قد تم إنشاؤه خصيصًا لـ FP ، على الرغم من أن إمكانيات بناء الجملة لم تصل بعد إلى Scala.

لذلك ، لنبدأ باستخدام Scala وننفذ عملية فرز سريعة بأسلوبين :

بشكل حتمي - نستخدم نفس الصفيف ، ونعيد ترتيب العناصر الموجودة فيه باستخدام إجراء متكرر. نرى رمزًا مطولًا ، يُحتمل أن يكون عرضةً للأخطاء المطبعية ، ولكن باستخدام الذاكرة على النحو الأمثل ، وبأسرع وقت ممكن.

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.

.