Rust vs. C++: Fine-grained Performance
Github: http://github.com/ncm/nytm-spelling-bee
Reddit: https://redd.it/42qc78
If Rust is to take on work previously reserved to C++, we need to know how well it does what C++ does best. What’s fast, what’s slow? What’s harder to do, what’s easier? I wouldn’t know how to look up answers for those questions, but I can write programs.
I had a C++ program that was just the right length to experiment with – one printed page – and that did nothing tricky to express in an unfamilar language. (It generates all possible versions of a puzzle by Frank Longo called “Spelling Bee”, found in the New York Times Magazine.) I began by transcribing the program straight across to equivalent Rust code. The Rust program turned out close to the same length, but only half as fast. As I made the Rust code more idiomatic, it got faster. At the same time, I worked to speed up the C++ program, still hewing to the original one-page limit. After each change, I checked performance. Few programs get this much attention to optimization.
The C++ version now runs more than three times as fast as when I started; about as fast, I think, as it can be made without making it longer,1 or parallel,2 or using third-party libraries. In 90 ms on modern hardware, it performs some 190 million basic operations (at an astonishing 1 cycle per iteration), filtering to 5 million more-complex operations (at an astonishing 28 cycles per bit). Meanwhile, the Rust program does about the same operations in about the same time: just a few percent faster or slower on various hardware. Many variations that seemed like they ought to run the same speed or faster turned out slower, often much slower. By contrast, in C++ it was hard to discover a way to express the same operations differently and get a different run time.
Below, I present each program in fragments. The code may be denser than you are used to, just to keep it to one printed page. When I write “much slower”, below, it might mean 1.3x to 2x, not the order of magnitude it might mean outside systems programming. Huge swaths of both languages are ignored: C++ templates, destructors, futures, lambdas; Rust channels, threads, traits, cells, lifetimes, borrowing, modules, macros. Those are essential to really using the language, but this project is deliberately about the nitty-gritty of coding.
So, the programs. First, dependencies: headers, modules.
C++:
#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
#include <string>
#include <algorithm>
#include <bitset>
And Rust:
use std::io::prelude::*;
use std::{fs, io, env, process};
Rust wins, here. Rust provides much of its standard library by default, or with just the first line above, and supports ganging module use
s on one line. Rust’s module system is exemplary; any future language that ignores its lessons courts failure.
Next, argument and input-file processing.
C++:
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;
And Rust:
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)
}))
};
Point, C++. This stuff just takes more code to do in Rust. Most people coding Rust would let a toy program like this report usage errors by “panicking”, although that produces very ugly output. Rust does make it hard to accidentally ignore an I/O error result, which is good so long as people don’t get used to deliberately ignoring them; but in Rust, ignoring errors takes more work.
Both programs take an optional file name on the command line, and can read from stdin
, which is convenient for testing. On standard Linux systems the words
file is a list of practical English words, including proper names, contractions, and short words that must be filtered out. Notable, here, is the use of Box
for type-erasure so io::stdin
can be substituted for the fs::File
handle. The odd construct &*
extracts the character sequence hidden inside the (Option
-wrapped) String
produced by nth()
, so that match
will have something it can compare directly to the built-in literal string "-"
.
I don’t mind locking io::stdin
to get faster input, but requiring that the call to lock()
be in a separate statement is weird.
Data structure and input setup follows, along with the input loop header.
C++:
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) {
Rust:
let mut sevens = Vec::with_capacity(1 << 14);
let mut words = Vec::with_capacity(1 << 15);
let (mut word, mut len, mut ones) = (0u32, 0, 0);
for c in io::BufReader::new(file).bytes().filter_map(Result::ok) {
One point here for Rust. Rust integer types support count_ones()
. The C++ version needs std::bitset
for its member count()
(which would be size()
if bitset
were a proper C++ set) because it is the only way in C++ to get at the POPCNT
instruction without using a non-standard compiler intrinsic like Gcc’s __builtin_popcountl
. Using bitset<32>
instead of <26>
suppresses some redundant masking operations. Since the smallest bitset<>
on Gcc/amd64 is 64 bits, the values are stored more efficiently as unsigned
. Rust has no equivalent to bitset (yet), so we’re lucky all the bits we needed fit in an available integer type; but similarly so for C++.
The actual types of the Rust sevens
and words
vectors are deduced from the way they are used way further down in the program. The filter_map
call strips off a Result
wrapping, discarding any file-reading errors.
Next, we have the the input state machine.
C++:
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; }
And Rust:
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 }
These are exactly even. The state machine is straightforward: gather up and store eligible words, and skip past ineligible words. On earlier versions of the Rust compiler, I had to use an iterator pipeline, using .scan()
, match
, .filter()
, and .collect()
, at twice the line count, to get tolerable performance. Now the loop is faster. A match
would work here, but the code would be longer. Rust could have just one push
call, as in the C++ version, but it would be ugly, and slower besides. Using a value of ones
to flag ineligible words saves one unpredictable branch per character.
Incidentally, I don’t know why I can write
let (mut word, mut len, mut ones) = (0u32, 0, 0);
but not
(word, len, ones) = (0, 0, 0);
Obviously the present syntax doesn’t allow it, but syntax is not physics. Surprising syntactic restrictions make the language more complex for users.
Next, we need to sort the collection of seven-different-letter words, and count duplicates.
C++:
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;
}
And Rust:
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
}
These are close to even. In Rust, when working with two elements of the same vector, we need to index both elements to avoid an ownership conflict with an iterator, but that comes with bounds checking, at least for count
. (The optimizer ought to know that i
is in bounds.) Rust wants indices unsigned, but we have to start count
at 0 (not !0
, i.e. all 1s) so the optimizer has a chance to notice that count
cannot exceed i
, and so elide bounds checking on it, too. Then we need the extra if
check to start out right.3
The program to this point is all setup, accounting for a small fraction of run time. Using <map>
or BTreeMap
, respectively, to store sevens
and counts
would make this last fragment unnecessary, in exchange for at least 3% more total run time.
Rust’s convenience operations for booleans, by the way, are curiously neglected, vs. Result
and Option
. For example, some code would read better if I could write something like:
return is(c).then_some(||f(c))
instead of
return if is(c) { Some(f(c)) } else { None }
The body of then_some()
is just a one-liner, but to be useful it needs to be standard.4
The main loop is presented below, in two phases. The first phase is where the program spends practically all its time.
C++:
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;
And Rust:
let mut stdout = io::stdout();
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
});
This is close to even.
The first inner loop explodes the positions of bits in seven
out to the bits
array, one per element, so that subsequent loops can be unrolled and executed out-of-order. (Optimizers actually seem able to do this all by themselves, but the code is shorter this way, and maybe easier to understand.) Rust’s trailing_zeros()
maps to the machine instruction CTZ
. C++ offers no direct equivalent, but given a bit of arithmetic bitset<>::count()
serves.
The “.filter
” line is executed 190M times; the programs spend ~60% of their time in just four instructions, and almost all the rest in the loop inside. In one sense, this whole exercise only examines how well the languages execute these two lines; but that is only because both race through the rest of the code. Only some 720K iterations reach the “.fold()
”, but the innermost loop runs 5M times, and scores[place]
is actually incremented 3M times. The “fold()
”, with its scores
state passed along from one iteration to the next, is much faster than the equivalent loop with outer-scope state variables. The words
iterator is “lazy”, but the “fold()
” call drives it to completion.
I found that iterating over an array with (e.g.) “array.iter()
” was much faster than with “&array
”, although it should be the same. (I suppose that will be fixed soon.) Curiously, using 16-bit elements for bits
and scores
slowed down earlier versions of the C++ program by quite a large amount – 8% in some tests. The Rust program was also affected, but less so. Current versions run the same, short
or int
.
The second phase of the main loop does output based on the scores accumulated above.
C++:
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);
}
}
And Rust:
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
{ stdout.write(&out).unwrap(); }
}
}
This is even, too.
The loop walks the out
array, pairing each byte with its corresponding score and a bit position from bits
. The output is built of u8
bytes instead of proper Rust characters because operations on character and string types would be slowed by runtime error checks and conversions. (The algorithm used here only works with ASCII anyhow.) Unlike in the C++ code, the out
elements are initialized twice (although it’s possible the optimizer elides that). People complain online about the few choices available for initializing arrays, which often requires the arrays to be made unnecessarily mutable.
Curiously, most variations of the C++ version run only half as fast as they should on Intel Haswell chips, when built with Gcc or Clang, 5 a consequence of an instruction-sequence choice that makes the main inner loop take two cycles instead of one. (Wrapping “!(word & ~seven)
” in __builtin_expect(..., false)
helps.) It’s possible that Gcc will learn someday to generate better code for Haswell and newer Skylake chips; that the Rust code was not affected really traces to luck.
Rust has some rough edges, but coding in it was kind of fun.6 As with C++, if a Rust program compiles at all, it generally works, more or less (but perhaps more). Rust’s support for generics is improving, but is still well short of what a Rusty STL would need. The compiler was slow, but they’re working hard on that, and I believe its speed will be unremarkable by this time next year. (I could forgive its slowness if it kept its opinions on redundant parentheses to itself.) Rust’s iterator primitives string together nicely.
It is a signal achievement to match C++ in low-level performance and brevity while surpassing it in safety, with reasonable prospects to match its expressive power in the foreseeable future. C++ is a rapidly moving target, held back only by legacy compatibility requirements and committee politics, so Rust will need to keep moving fast just to keep up. While Rust could “jump the shark” any time, thus far there’s every reason to expect to see, ten years on, recruiters advertising for warm bodies with ten years’ production experience coding Rust.
[Thanks to Steve Klabnik, eddyb
, leonardo
, huon
, comex
, marcianix
, alexeiz
, killercup
, and skade
for major improvements to the code and to the article. The mistakes remain mine, all mine. Material alterations:
a. Examples for `then_some` improved
b. In C++, s/short/int/; Rust s/0u16/0/; resulting in speedup
c. Simplify output loop -- rustc has improved, allowing simpler code
d. Simplify argument processing, slightly
e. Improve counting logic
f. Enable unrolled/out-of-order loops by precomputing bit positions
g. Replace innermost-loop conditional branch with a bitwise operation
h. Improve state machine test for valid word characters
i. s/int/short/ arrays, both C++ and Rust; no slowdown.
j. Correct attribution of slow Haswell code.
k. Correct cycle counts. Again.
]
Allowed to grow without bound, this article would never have been published↩
Few would say that threading is what C++ does best, in either sense↩
The bounds checks are not actually elided, yet, and in any case the time to run them is not detectable here.↩
I do not dare to propose “
ergo_some()
”.↩The low points were haggling with the compiler over where
&
was allowed or required.↩