Rust vs. C++:性能大比拼

netwan 6年前
   <p>如果 Rust 要做 C++ 做的工作,我们需要知道 Rust 会把 C++ 最擅长的工作做成什么样子。什么是快,什么是慢? 什么更难做,什么更容易? 我不知道该如何回答这些问题,但我可以编写程序来寻求答案。</p>    <p>我有一个 C ++ 程序,其长度用来实验正好合适——一个打印的页面长度,并且使用不熟悉的语言重写也不会有什么棘手的问题。(它生成由 Frank Longo 设计的名字为“拼写蜜蜂”的拼图游戏的所有可能的方案,我是在“纽约时报”杂志发现的。)我在 Rust 上使用等效的代码直接重写了该程序。Rust 程序的长度与之前 C++ 的接近,但运行效率只有原来的一半。因为我使用了更加规范的 Rust 代码管理,它运行得更快。同时,我努力加快 C++ 程序执行速度,仍然保持原来的代码长度一页限制。每次更改后,我都会检查下性能。很少有程序得到这么多的优化关注。</p>    <p>C ++ 版本现在运行的速度是我开始时的三倍;我认为在不改变增加其长度、不考虑并行或者不使用第三方库的情况下,这基本达到在性能最佳的情况。在现代硬件上 90ms 内,它执行大约 1.9 亿次基本操作(每次迭代的 1 个时钟周期),过滤高达 500 万次更复杂的操作(每位占用 28 个时钟周期)。同时,Rust 程序大致在相同的时间执行相同的操作:在不同硬件上只有几个百分比的更快或更慢差距。许多变量显示似乎他们应该运行速度相同或更快但结果却是速度更慢,通常是慢得多。相比之下,在C++ 中很难发现表达相同操作的不同方式,并获得不同的运行时间。</p>    <p>下面,我展示下每个程序的片段。代码可能比你之前常用的更密集,只是为了保持它长度在一个打印页内。当我在下文中使用“慢得多”,它可能意味着 1.3x 到 2x 之间,而不是在系统编程外的意义上的数量级。忽略这两种语言的巨大差距:C++ 的模板、析构函数、futures、lambdas;Rust 的通道、线程、traits、单元格、生命周期、借用、模块、宏。这些都是使用语言的关键,但这个项目是更关注编码的本身。</p>    <p>来看程序。首先是依赖项:头文件,模块。</p>    <p>C++:</p>    <pre>  <code class="language-cpp">#include <iostream>  #include <fstream>  #include <vector>  #include <iterator>  #include <string>  #include <algorithm>  #include <bitset></code></pre>    <p>和 Rust:</p>    <pre>  <code class="language-cpp">use std::io::prelude::*;  use std::{fs, io, env, process};</code></pre>    <p>这里 Rust 赢了。Rust 提供大量默认的标准库。上面的代码中,就第一行,就 use 了一堆模块。Rust 的模块系统非常典型;任何未来的语言都不能忽视这种模块系统。</p>    <p>然后是参数和处理输入文件。</p>    <p>C++:</p>    <pre>  <code class="language-cpp">int main(int argc, char** argv) {      std::string name = (argc > 1) ? argv[1] : "/usr/share/dict/words";      std::ifstream fs;      std::istream& file = (name == "-") ? std::cin : (fs.open(name), fs);      if (!file)          return std::cerr << "file open failed: \"" << name << "\"\n", 1;</code></pre>    <p>和 Rust:</p>    <pre>  <code class="language-cpp">fn main() {      let fname = &*env::args().nth(1).unwrap_or("/usr/share/dict/words".into());      let stdin = io::stdin();      let file: Box<Read> = match fname {          "-" => Box::new(stdin.lock()),          _ => Box::new(fs::File::open(fname).unwrap_or_else(|err| {                   writeln!(io::stderr(), "{}: \"{}\"", err, fname).unwrap();                   process::exit(1)               }))      };</code></pre>    <p>在这一点上 C++ 获胜。用 Rust 来做这些事情需要更多代码。多数使用 Rust 的人都会让这种简单的程序,因为“恐慌”而报告用法错误,虽然这样产生的输出非常难看。使用 Rust 很难放过一个 I/O 错误,只要这不会让人们习惯忽视之些错误,就不算坏事;在 Rust 中忽略错误需要很多工作。</p>    <p>两个程序都从命令行获得一个可选的文件名参数,并从 stdin 读取数据,用于测试转换。在标准的 Linux 系统中,words 文件保存着真实的英文单词列表,包含合适的名称、缩写和需要过滤掉的短小单词。注意这里使用 Box 擦除类型,因此可以使用 io::stdin 来代替 fs:File 句柄。奇特的 &* 用于提取隐藏在(Option -已包装)由 nth() 产生的 String 中的字符序列,因此 match 有一些能直接与文本字符串 "-" 比较的东西。</p>    <p>我不介意锁定 io::stdin 来获得更快的输入,但得在另一个语句中要求调用 lock() 是件奇怪的事情。</p>    <p>数据结构和输入设置如下,同时包括输入循环的开始部分:</p>    <p>C++:</p>    <pre>  <code class="language-cpp">std::vector<unsigned> sevens; sevens.reserve(1<<14);  std::vector<unsigned> words; words.reserve(1<<15);  std::bitset<32> word; int len = 0; int ones = 0;  for (std::istreambuf_iterator<char> in(file), eof; in != eof; ++in) {</code></pre>    <p>Rust:</p>    <pre>  <code class="language-cpp">if (*in == '\n') {              if (len >= 5 && ones <= 7)                  (ones == 7 ? sevens : words).push_back(word.to_ulong());              word = len = ones = 0;          } else if (ones != 8 && *in >= 'a' && *in <= 'z') {              ++len, ones = word.set(25 - (*in - 'a')).count();          } else { ones = 8; }</code></pre>    <p>这里有一点关于 Rust 的说明。Rust 整数类型支持 count_ones()。C ++ 版本需要使用 std::bitset 的成员函数 count()(如果 bitset 算是一个 C++ 集合的话,这将是 size() 接口),因为这是在 C++中不使用非标准的编译器指令,诸如 GCC 的 __builtin_popcountl 来获得在 POPCNT 指令的唯一方法。使用 bitset <32> 而不是 <26> 可以避免一些不必要的掩码操作。 由于在 gcc/amd64 上的最小的 bitset <> 是 64 位的,因此这些值更有效地存储方式是 unsigned。Rust 到目前为止还没有 bitset 的替换对象,但很幸运的是我们可以使用一个整数类型来表示所有位; 不过非常类似于 C++。</p>    <p>Rust sevens 和words 向量是从实际在程序中使用的方式推导出来。filter_map 调用剥离了一个 Result 包装,并丢弃任何其他文件读取错误。</p>    <p>下面是输入状态机的代码:</p>    <p>C++:</p>    <pre>  <code class="language-cpp">if (*in == '\n') {            if (len >= 5 && ones <= 7)                  (ones == 7 ? sevens : words).push_back(word.to_ulong());              word = len = ones = 0;          } else if (ones != 8 && *in >= 'a' && *in <= 'z') {              ++len, ones = word.set(25 - (*in - 'a')).count();          } else { ones = 8; }</code></pre>    <p>Rust:</p>    <pre>  <code class="language-cpp">if c == b'\n' {            if len >= 5 && ones <= 7                  { if ones == 7 { sevens.push(word) } else { words.push(word) } }              word = 0; len = 0; ones = 0          } else if ones != 8 && c >= b'a' && c <= b'z' {              word |= 1 << (25 - (c - b'a')); len += 1; ones = word.count_ones()          } else { ones = 8 }</code></pre>    <p>这些都是对称的。状态机是直接的:收集和存储合适的词,并跳过不合适的词。在早期版本的 Rust 编译器上,我不得不使用迭代器管道,使用 .scan(),match,.filter() 和 .collect(),在行数的两倍位置,以获得不错的性能。现在循环更快了。这里可以添加一个匹配工作,但代码会更长。就像在 C++ 中一样,Rust 可能仅需一次 push 调用,但它会是丑陋,而且速度更慢。 使用值 ofonesto 标志不合格的字为每个字符保存一个不可预测的分支。</p>    <p>顺便说一下,我不知道为什么我可以写下面代码:</p>    <pre>  <code class="language-cpp">let (mut word, mut len, mut ones) = (0u32, 0, 0);</code></pre>    <p>而不是</p>    <pre>  <code class="language-cpp">(word, len, ones) = (0, 0, 0);</code></pre>    <p>很显然现在的语法不支持这种写法,但是语法不是物理规律。令人惊讶的语法限制使语言对用户来说更复杂。</p>    <p>下一步,我们需要对保存着 7 个不同字母的 words 列表排序,并统计哪些存在重复。</p>    <p>C++:</p>    <pre>  <code class="language-cpp">std::sort(sevens.begin(), sevens.end());  std::vector<short> counts(sevens.size());  int count = -1; unsigned prev = 0;  for (auto seven : sevens) {      if (prev != seven)          sevens[++count] = prev = seven;      counts[count] += 3;  }</code></pre>    <p>Rust:</p>    <pre>  <code class="language-cpp">sevens.sort();  let (mut count, mut prev, mut counts) = (0, 0, vec![0u16; sevens.len()]);  if !sevens.is_empty() { prev = sevens[0]; counts[0] = 3 }  for i in 1..sevens.len() {      if prev != sevens[i]          { count += 1; prev = sevens[i]; sevens[count] = prev }      counts[count] += 3  }</code></pre>    <p>它们性能相近。Rust 中如果要同时使用一个 vector 中的两个元素,需要通过索引来访问以避免产生迭代器中元素所有权的冲突,这来自于边界检查,至少因为 count。(优化器应该知道 i 在范围内。)Rust 需要无符号的索引,但是我们必须从 0(不是 !0,比如所有都是1)开始对 count 计数,因此优化器可能会注意到 count 不会超出 i,于是省略了对它进行边界检查。然后,我们需要额外的 if 检查开始的条件。</p>    <p>到这一点的程序都是设置的,占运行时间的一小部分。 分别使用 <map> 或者 BreeMap 来存储 sevens 和 counts,使得这最后一个片段是不必要的,交换至少 3% 的总运行时间。</p>    <p>Rust 操作布尔值很方便,顺便说一句容易被忽略的,Result 和 Option。 例如,一些代码更容易阅读,如果我这么写:</p>    <pre>  <code class="language-cpp">return is(c).then_some(||f(c))</code></pre>    <p>代替</p>    <pre>  <code class="language-cpp">return is(c) { Some(f(c)) } else { None }</code></pre>    <p>then_some() 主体仅一行,这是一种有用的标准写法。</p>    <p>主循环就在下面,分为两段。程序会把几乎所有时间都花在前面这段上。</p>    <p>C++:</p>    <pre>  <code class="language-cpp">for (; count >= 0; --count) {      unsigned const seven = sevens[count];      short bits[7], scores[7];      for (unsigned rest = seven, place = 7; place-- != 0; rest &= rest - 1) {          bits[place] = std::bitset<32>((rest & ~(rest - 1)) - 1).count();          scores[place] = counts[count];      }      for (unsigned word : words)          if (!(word & ~seven))              for (int place = 0; place < 7; ++place)                  scores[place] += (word >> bits[place]) & 1;</code></pre>    <p>和 Rust:</p>    <pre>  <code class="language-cpp">let stdout = io::stdout();  let mut sink = io::BufWriter::new(stdout.lock());  for count in (0..(count + 1)).rev() {      let seven = sevens[count];      let (mut rest, mut bits) = (seven, [0u16;7]);      for place in (0..7).rev()          { bits[place] = rest.trailing_zeros() as u16; rest &= rest - 1 }      let scores = words.iter()          .filter(|&word| word & !seven == 0)          .fold([counts[count];7], |mut scores, &word| {              for place in 0..7                   { scores[place] += ((word >> bits[place]) & 1) as u16 }              scores          });</code></pre>    <p>它们非常相近,不过 Rust 的前两行看起来有点多余的代码可以带来更快的输出。</p>    <p>第一内循环将 seven 中的 bit 的位置保存到 bit 数组中,每个元素保存一位,以保证后续循环可以被展开并且随机执行。 (优化器实际上能够自己完成这一切,但是这样做代码会更短,也许更容易理解。)Rust 的 trailing_zeros() 被映射到机器指令 CTZ 上。 C++ 没有提供直接等价方式,但 bitset<>::count() 提供了类似的位算法。</p>    <p>“.filter”行被执行 190 M 次;程序花费大约 60% 的时间在四条指令上,其他时间几乎都用在了循环内部。从某种意义上说,这整个练习只测试了语言执行这两行的能力。但是这仅仅是因为其余代码之间的竞态条件。只有大约 720K 次迭代到达“.fold()”,但是最内层循环执行 5 M 次,scores[place] 实际上自增 3 M 次。 “fold()”将其 scores 状态从一个迭代传递到下一个迭代,比带有外部范围状态变量的等效循环快得多。words 的迭代器是“懒惰的”,但是“fold()”调用驱动它完成。</p>    <p>我发现,使用(例如)“array.iter()”迭代数组比使用“&array”快得多,尽管它理论上应该是一样的。(我想这将很快就会确定下来的。)奇怪的是,在 bits 和 scores 中使用 16 位元素在较早版本的 C ++ 程序大量降低了其性能——在一些测试中高达 8%。Rust 程序也受到类似影响,但相对轻微些。当前版本中使用 short 或者 int 运行效率是相同的。</p>    <p>主循环的第二段在上面积累积分的基础上进行输出。</p>    <p>C++:</p>    <pre>  <code class="language-cpp">        bool any = false; char out[8];          for (int place = 0; place != 7; ++place) {              int points = scores[place];              char a = (points >= 26 && points <= 32) ? any = true, 'A' : 'a';              out[place] = a + (25 - bits[place]);          }          if (any)              out[7] = '\n', std::cout.rdbuf()->sputn(out, 8);      }  }</code></pre>    <p>和 Rust:</p>    <pre>  <code class="language-cpp">        let (mut any, mut out) = (false, *b".......\n");          for place in 0..7 {              let a = match scores[place]                 { 26 ... 32 => { any = true; b'A' }, _ => b'a' };              out[place] = a + (25 - bits[place]) as u8          }          if any              { sink.write(&out).unwrap(); }      }  }</code></pre>    <p>这也很相近。</p>    <p>这个循环遍历 out 数组,将每一个字节和它对应的分数,以及 bits 中相同位置的位进行配对。Rust 代码中这个结果保存在 u8 中,没按一正常情况使用字符是因为在字符和字符串之间运算会很慢,因为运行时会检查错误并进行转换。(这里的算法只能用于 ASCII。)而 C++ 代码不同,out 的元素被初始化两次(不过可以通过优化省略)。有人在网上报怨可供选择的几种初始化数组的方法,都需要数组进行不必要的改变。</p>    <p>奇怪的是,大多数 C++ 版本变化的运行速度只有 Intel Haswell 芯片的一半,当使用 Gcc 或者 Clang 构建时,一个指令序列的选择,需要内部主循环的两个周期,而不是一个而已。(在 in __builtin_expect(..., false) 封装了 in __builtin_expect(..., false) 的帮助)。有可能 Gcc 以后会学着为 Haswell 和新的 SKylake 芯片生成更好的代码。真幸运,Rust 代码没有受到影响。</p>    <p>Rust 的包装有点粗糙,但是用它编程充满乐趣。假如是 Rust 独立编程,它会或多或少会产生很好的效果。Rust 的通用支持不断改善,但是它仍然需要 Rusty 的 STL。虽然其编译器运行缓慢,但是它们正不断努力改善,我相信明年的此时它的速度会有很大提升。(如果它可以对多余括号保持现有处理方式就好了)。另外,Rust 的字符串组合迭代体验也很棒。</p>    <p>Rust 现在的趋势是:与 C++ 低端性能和简洁相媲美,安全方面的话正在超越,在可预见的未来有着匹配表达能力的合理前景。C++ 是逐步发展的目标,仅保留传统的兼容性要求与委员会政策,所以 Rust 将会需要不断快速发展。Rust 如果可以随时“跨越障碍”,十年之后,招募者都会以有着十年 Rust 开发经验而骄傲的。</p>    <p> </p>    <p>来自:https://www.oschina.net/translate/rust-vs-cpp</p>    <p> </p>