前言

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

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

  1. http://www.minesweeper.info/wiki/3BV  ↩︎

  2. https://users.rust-lang.org/t/why-my-rust-code-is-2-times-slower-than-my-js-code/31189  ↩︎

  3. https://users.rust-lang.org/t/formatting-and-writing-to-a-file-without-malloc-or-locks/52295/2  ↩︎