パフォーマンスの問題を診断する

Question

私はRustをよく経験しておらず、パフォーマンスの問題を診断しようとしています。下にはかなり速いJavaコード（7秒で実行）があり、これと同等のRustコードが必要です。しかし、錆のコードは非常にゆっくり実行されます（はい、私は--releaseでコンパイルしました）、またオーバーフローするようです。 i32からi64に変更すると、あとでオーバーフローがプッシュされますが、それでも問題は発生します。私が書いたものにはいくつかのバグがあると思われますが、長い間問題を見つめた後、私は助けを求めることにしました。

public class Blah { 

    static final int N = 100; 
    static final int K = 50; 

    public static void main(String[] args) { 
     //initialize S 
     int[] S = new int[N]; 
     for (int n = 1; n <= N; n++) S[n-1] = n*n; 

     // compute maxsum and minsum 
     int maxsum = 0; 
     int minsum = 0; 
     for (int n = 0; n < K; n++) { 
      minsum += S[n]; 
      maxsum += S[N-n-1]; 
     } 

     // initialize x and y 
     int[][] x = new int[K+1][maxsum+1]; 
     int[][] y = new int[K+1][maxsum+1]; 
     y[0][0] = 1; 

     // bottom-up DP over n 
     for (int n = 1; n <= N; n++) { 
      x[0][0] = 1; 
      for (int k = 1; k <= K; k++) { 
       int e = S[n-1]; 
       for (int s = 0; s < e; s++) x[k][s] = y[k][s]; 
       for (int s = 0; s <= maxsum-e; s++) { 
        x[k][s+e] = y[k-1][s] + y[k][s+e]; 
       } 
      } 
      int[][] t = x; 
      x = y; 
      y = t; 
     } 

     // sum of unique K-subset sums 
     int sum = 0; 
     for (int s = minsum; s <= maxsum; s++) { 
      if (y[K][s] == 1) sum += s; 
     } 
     System.out.println(sum); 
    } 

} 

extern crate ndarray; 

use ndarray::prelude::*; 
use std::mem; 

fn main() { 
    let numbers: Vec<i32> = (1..101).map(|x| x * x).collect(); 

    let deg: usize = 50; 

    let mut min_sum: usize = 0; 
    for i in 0..deg { 
     min_sum += numbers[i] as usize; 
    } 

    let mut max_sum: usize = 0; 
    for i in deg..numbers.len() { 
     max_sum += numbers[i] as usize; 
    } 

    // Make an array 
    let mut x = OwnedArray::from_elem((deg + 1, max_sum + 1), 0i32); 
    let mut y = OwnedArray::from_elem((deg + 1, max_sum + 1), 0i32); 

    y[(0, 0)] = 1; 

    for n in 1..numbers.len() + 1 { 
     x[(0, 0)] = 1; 
     println!("Completed step {} out of {}", n, numbers.len()); 
     for k in 1..deg + 1 { 
      let e = numbers[n - 1] as usize; 
      for s in 0..e { 
       x[(k, s)] = y[(k, s)]; 
      } 
      for s in 0..max_sum - e + 1 { 
       x[(k, s + e)] = y[(k - 1, s)] + y[(k, s + e)]; 
      } 
     } 
     mem::swap(&mut x, &mut y); 
    } 

    let mut ans = 0; 

    for s in min_sum..max_sum + 1 { 
     if y[(deg, s)] == 1 { 
      ans += s; 
     } 
    } 

    println!("{}", ans); 

} 

Answer 1

一般的にパフォーマンスの問題を診断するには、I：

1. は、ベースライン時またはレートを取得します。プロファイラはシステムを少し遅くする傾向があるので、テストケースを作成するのは数秒しかかかりません。頻繁に繰り返すことも必要です。
2. デバッグシンボルでリリースモードでコンパイルします。
3. プロファイラでコードを実行します。私はOS Xを使用していますので、主な選択肢はInstrumentsですが、valgrindも使用しています。
4. 最もホットなコードパスを見つけて、なぜそれが遅いのか考えてみてください。

最後のステップは難しい部分です。

---

あなたの場合、ベースラインとして使用できる別の実装があります。 2つの実装を比較すると、データ構造がのであることがわかります。 Javaではネストされた配列を構築していますが、Rustではndarrayのcrateを使用しています。クレートには良いメンテナーがいることは知っていますが、私は個人的にはその内部については何も知らないし、ユースケースに最も適しています。

標準ライブラリVecを使用して書き換えました。

私が知っているもう一つのことは、直接配列アクセスはイテレータを使用するほど高速ではないということです。これは、配列アクセスが境界チェックを実行する必要があり、反復子が境界チェックを自分自身にベイク処理するためです。多くの場合、これはIteratorのメソッドを使用することを意味します。

可能なときにバルクデータ転送を実行することもできます。要素ごとにコピーする代わりに、スライス全体をcopy_from_sliceのような方法で移動します。 - 錆1.9​​.0

use std::mem; 

const N: usize = 100; 
const DEGREE: usize = 50; 

fn main() { 
    let numbers: Vec<_> = (1..N+1).map(|v| v*v).collect(); 

    let min_sum = numbers[..DEGREE].iter().fold(0, |a, &v| a + v as usize); 
    let max_sum = numbers[DEGREE..].iter().fold(0, |a, &v| a + v as usize); 

    // different data types for x and y! 
    let mut x = vec![vec![0; max_sum+1]; DEGREE+1]; 
    let mut y = vec![vec![0; max_sum+1]; DEGREE+1]; 
    y[0][0] = 1; 

    for &e in &numbers { 
     let e2 = max_sum - e + 1; 
     let e3 = e + e2; 

     x[0][0] = 1; 

     for k in 0..DEGREE { 
      let current_x = &mut x[k+1]; 
      let prev_y = &y[k]; 
      let current_y = &y[k+1]; 

      // bulk copy 
      current_x[0..e].copy_from_slice(&current_y[0..e]); 

      // more bulk copy 
      current_x[e..e3].copy_from_slice(&prev_y[0..e2]); 

      // avoid array index 
      for (x, y) in current_x[e..e3].iter_mut().zip(&current_y[e..e3]) { 
       *x += *y; 
      } 
     } 

     mem::swap(&mut x, &mut y); 
    } 

    let sum = y[DEGREE][min_sum..max_sum+1].iter().enumerate().filter(|&(_, &v)| v == 1).fold(0, |a, (i, _)| a + i + min_sum); 

    println!("{}", sum); 
    println!("{}", sum == 115039000); 
} 

• 2.060s：コードは次のようになり、これらの変更により
  （貧しい変数名の謝罪、私はあなたがそれらのためのセマンティック名を考え出すことができると確信しています）
• 2.225s - OS X 10.11.5でJava 1.7.0_45-B18

2.3 GHzのインテルCore i7プロセッサーを持ちます。

私は、Javaでどのような最適化を自動的に行うことができるのか十分に知りません。

私が見る最大の可能性は、追加を実行するときにSIMD命令を活用することです。それはSIMDが何のために作られたのかとかなり正確です。 pointed out by Eli Friedmanとして

---

、これを行うのisn't currently the most performant wayをビュンによって、配列のインデックスを回避することができます。

以下の変更で、今度は1.267sになりました。

let xx = &mut current_x[e..e3]; 
xx.copy_from_slice(&prev_y[0..e2]); 

let yy = &current_y[e..e3]; 
for i in 0..(e3-e) { 
    xx[i] += yy[i]; 
} 

これはループだけでなく、SIMD命令を使用して展開するよう表示されるアセンブリを生成します。

+0x9b0 movdqu -48(%rsi), %xmm0 
+0x9b5 movdqu -48(%rcx), %xmm1 
+0x9ba paddd  %xmm0, %xmm1 
+0x9be movdqu %xmm1, -48(%rsi) 
+0x9c3 movdqu -32(%rsi), %xmm0 
+0x9c8 movdqu -32(%rcx), %xmm1 
+0x9cd paddd  %xmm0, %xmm1 
+0x9d1 movdqu %xmm1, -32(%rsi) 
+0x9d6 movdqu -16(%rsi), %xmm0 
+0x9db movdqu -16(%rcx), %xmm1 
+0x9e0 paddd  %xmm0, %xmm1 
+0x9e4 movdqu %xmm1, -16(%rsi) 
+0x9e9 movdqu (%rsi), %xmm0 
+0x9ed movdqu (%rcx), %xmm1 
+0x9f1 paddd  %xmm0, %xmm1 
+0x9f5 movdqu %xmm1, (%rsi) 
+0x9f9 addq  $64, %rcx 
+0x9fd addq  $64, %rsi 
+0xa01 addq  $-16, %rdx 
+0xa05 jne  "slow::main+0x9b0"