前言

最近 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-CPUOff-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 提供的功能非常丰富,他在正确性上下了非常大的功夫。同时走了这一个流程,对性能分析也有了一个大概的认知:

  1. 在 Linux 下,可以使用 perf 工具进行 On-CPU 与 Off-CPU 的方便的性能测试;
  2. MacOS 也提供了 Instruments 用来性能测试;
  3. Rust 社区也提供了 flamegraph 对代码进行一个快速的火焰图工具;
  4. TiKV 也提供一个 CPU Profiler 工具 pprof-rs