gpt4 book ai didi

java - 诊断性能问题

转载 作者:塔克拉玛干 更新时间:2023-11-02 19:14:50 24 4
gpt4 key购买 nike

我对 Rust 不是很有经验,我正在尝试诊断性能问题。下面是一个非常快的 Java 代码(在 7 秒内运行),我认为应该是等效的 Rust 代码。但是,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);

}

最佳答案

为了诊断一般的性能问题,我:

  1. 获取基准时间或速率。最好创建一个只需要几秒钟的测试用例,因为分析器往往会稍微减慢系统速度。您还需要经常迭代。
  2. 使用调试符号在 Release模式下编译。
  3. 在分析器中运行代码。我使用的是 OS X,所以我的主要选择是 Instruments,但我也使用 valgrind。
  4. 找到 HitTest 门的代码路径,思考为什么它很慢,尝试一些东西,测量。

最后一步是困难的部分。


在您的情况下,您有一个单独的实现可以用作基准。比较这两种实现,我们可以看到您的数据结构不同。在 Java 中,您正在构建嵌套数组,但在 Rust 中,您使用的是 ndarray crate。我知道 crate 有一个很好的维护者,但我个人对它的内部结构一无所知,或者它最适合的用例。

所以我使用标准库 Vec 重写了它。

我知道的另一件事是直接数组访问不如使用迭代器快。这是因为数组访问需要执行边界检查,而迭代器将边界检查烘焙到自身中。很多时候这意味着在 Iterator 上使用方法。

另一个变化是尽可能执行批量数据传输。不是逐个元素地复制,而是移动整个切片,使用像 copy_from_slice 这样的方法。

通过这些更改,代码看起来像这样(对于糟糕的变量名称表示歉意,我相信您可以为它们想出语义名称):

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 - Rust 1.9.0
  • 2.225s - Java 1.7.0_45-b18

在配备 2.3 GHz Intel Core i7 的 OS X 10.11.5 上。

我没有足够的 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"

关于java - 诊断性能问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37522187/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com