前言
最近 Lynn 大佬将一个密集计算的场景(迷宫地图 3BV1 的计算,一个衡量迷宫难度的指标)由 JavaScript 迁移至 Rust,然后我几乎围观了全程,其中碰到了一个很有趣的性能问题,JavaScript 居然比 Rust 执行的快。
实现 Vec.join()
因为 Rust 特别灵活的写法特性,在写这段代码的时候,尝试了许多 Vec<u8>
to String
的方法:
最早使用的思路是使用 map
然后 collect
,但是觉得好丑啊,就开始寻找其他的方案:
["a", "b", "c"].iter().map(|x| x.to_string()).collect::<String>();
但是我们知道,map
传入的是一个函数,而我们刚好有 ToString::to_string
,实际上是利用 Rust 的 trait:
vec.iter().map(ToString::to_string).collect::<String>();
然后我就在想,Rust 应该有类似 JavaScript 中的 reduce
:
vec.iter().fold(String::new(), |mut acc, x| {
acc.push_str(&x.to_string());
acc
});
然后通过各种渠道的提示,找到了 itertools
,里面有很多实用的迭代器函数,比如 join
, chunk
等等:
use itertools::itertools;
assert_eq!(["a", "b", "c"].iter().join(""));
运行结果
然后抱着 Rust 要比 JavaScript 快很多的愿景进行测试,看到结果人都傻了啊:
> cargo run --release
Compiling test v0.1.0
Finished release [optimized + debuginfo] target(s) in 1.31s
Running `target/release/test`
Elapsed: 853.73ms
> node src/test.js
elapsed 546
不快就算了(JavaScript 在进行密集计算会用 JIT,可以理解)但是为什么是两倍慢?
抱着好奇,我在 Google 搜了:“Why rust is two times slower than javascript?",没想到还真的得到了许多类似的声音,比如官方社区的 Why my rust code is 2 times slower than my js code2。
我们这里先贴出运行缓慢的代码,折叠查看:
Rust Code
use rand::seq::SliceRandom;
use rand::thread_rng;
use std::time::Instant;
fn main() {
let now = Instant::now();
for _i in 0..100000 {
gen()
}
let elapsed = now.elapsed();
println!("Elapsed: {:.2?}", elapsed);
}
fn vec_to_str(vec: &Vec<i8>) -> String {
vec.iter().map(|x| x.to_string()).collect::<String>()
}
fn gen() {
let height = 10;
let width = 10;
let sweeper_count = 10;
let map_size = height * width;
let mut map: Vec<i8> = vec![0; map_size];
for _i in 0..sweeper_count {
map.push(1);
}
map.shuffle(&mut thread_rng());
vec_to_str(&map);
let get_index = |x: usize, y: usize| -> Option<usize> {
match y + x * width {
x if x < map_size => Some(x),
_ => None,
}
};
for y in 0..width {
for x in 0..height {
if map[get_index(y, x).unwrap()] == 1 {
for i in -1..2i32 {
let next_y = y as i32 + i;
if next_y < 0 {
continue;
}
for j in -1..2i32 {
let next_x = x as i32 + j;
if next_x < 0 {
continue;
}
if let Some(index) = get_index(next_y as usize, next_x as usize) {
if map.get(index) == Some(&0) {
map[index] = 2;
}
}
}
}
}
}
}
}
JavaScript Code
const _ = require('lodash')
function main() {
let now = Date.now();
for (let i = 0; i < 100000; ++i) {
gen()
}
let elapsed = Date.now() - now;
console.log('elapsed', elapsed)
}
function gen() {
let height = 10, width = 10,
sweeper_count = 10,
wi = width - 1, hi = height - 1,
map_size = width * height;
let map = new Array(map_size).fill(0);
for (let i = 0; i < sweeper_count; ++i) {
map[i] = 1;
}
map = _.shuffle(map);
let mapstr = map.join('');
for (let y = 0; y < width; ++y) {
for (let x = 0; x < height; ++x) {
if (map[y + x * width]) continue;
for (let i = -1; i < 2; i++) {
let next_y, next_x;
if ((next_y = y + i) < 0 || next_y > hi) continue;
for (let j = -1; j < 2; j++) {
if ((next_x = x + j) < 0 || next_x > wi) continue;
const index = y + x * width;
if (map[index] == 0) {
map[index] = 2;
}
}
}
}
}
}
main()
性能分析
在优化代码之前,我们首先要对我们的代码进行一个性能分析。
在 The Rust Performance Book
首当其冲的便是,Linux 下的 perf
,利用他我们能够对任何程序进行一个比较快速的性能分析。但他只工作在 Linux 所以如果对 perf 感兴趣可以看看文章 Rust 程序性能分析
对程序进行 On-CPU
和 Off-CPU
与火焰图的绘制。
我这里选择了一个比较简单的方案是使用 Rust 社区提供的 flamegraph 他几乎支持所有系统,通过以下命令就可以很快的绘制火焰图:
sudo cargo flamegraph
另外关于 Node.js 官方也有提供分析器,
node --prof src/test.js
node --prof-process isolated-****.log > processed.log
其提供的信息较为全,其中我们可以在 [summary]
一节查看到底有多少代码被 JIT 了,
[Summary]:
ticks total nonlib name
104 19.7% 22.4% JavaScript
354 67.2% 76.3% C++
39 7.4% 8.4% GC
63 12.0% Shared libraries
6 1.1% Unaccounted
具体的应用可以查阅 Using the inbuilt Node.js profiler 。
下面是我对原来的代码的火焰图:
能够发现,最多的时间主要集中在 collect::FromIterator<alloc::string::String>
,居然是我们的处理字符串的方案有问题(首尾呼应了啊喂)!
我们来建议验证一下,把这段代码去掉,来一次测速:
> cargo run --release
Finished release [optimized + debuginfo] target(s) in 1.11s
Running `target/release/rs-test`
Elapsed: 222.31ms
> node src/test.js
elapsed 351
WoW,现在我的 Rust 比 JavaScript 快了,既然我们定位到了原因,这时候我们就要想办法解决了。
我们再仔细看一下火焰图,不知道为什么在 iter 中有非常多的 malloc
,这就非常有意思了,为什么一个 to_string
需要那么大量的空间操作。
那通过官方社区又了解到了,format!
依赖 String
是堆驱动的,所以会进行大量的空间操作3,所以实际上我们进行了 map_size * iter_cnt
次内存分配与销毁,那怪不得会慢了,官方社区的回答说,可以使用 write!()
,那根据这个思路改造一下代码:
vec.iter().fold(String::new(), |mut s, &n| {
write!(s, "{}", n).ok();
s
})
进行测速:
> cargo run --release
Finished release [optimized + debuginfo] target(s) in 1.11s
Running `target/release/rs-test`
Elapsed: 174.85ms
Ohhh,终于快了!
然后,又联想到,因为我们是一个 u8
,那我是不是可以直接对 offset 进行一个进行一个类似的效果?
let buf = BufWriter::new(vec.iter().map(|m| m + 48).collect());
let bytes = buf.into_inner().unwrap();
String::from_utf8(bytes).unwrap()
实测效果差不多。
拓展
同时研究的过程中我害找到了一篇文章,Performance Showdown: Rust vs JavaScript
,这篇文章也是讲述的 Rust 字符串的性能问题,不过他遇到的是 to_lowercase
的性能差异,这篇文章对 Rust 的一个性能分析有一个比较完整的思路流程,所以我也觉得非常值得看:
- 编译优化级别
- 优化报告
- 分析源码
- 解决
所以为什么 Rust 的 to_lowercase
这么慢?原因是 Rust 为了保证他在人和语言的健壮性与正确性,他维护了一个字符串的大数组,并且使用二分法进行搜索 log2(n)
级别的算法,随着迭代次数的上升,性能差距则会越来越明显,解决方法是使用 eq_ignore_ascii_case
。
总结
看到这真的觉得 Rust 提供的功能非常丰富,他在正确性上下了非常大的功夫。同时走了这一个流程,对性能分析也有了一个大概的认知:
- 在 Linux 下,可以使用 perf 工具进行 On-CPU 与 Off-CPU 的方便的性能测试;
- MacOS 也提供了 Instruments 用来性能测试;
- Rust 社区也提供了 flamegraph 对代码进行一个快速的火焰图工具;
- TiKV 也提供一个 CPU Profiler 工具 pprof-rs ;