Converting a Python library to Rust

cover

/writings/programming/rust.png

tags

Programming, Rust, Python

summary

I rewrote a Python project in Rust. The rewrite took a fair bit longer than expected, but the results were good (about 9 times faster and ½ the memory usage). In the process, I learned a fair bit about Rust.

Introduction

The Rust programming language isn’t exactly new by any means, but it’s finally been around long enough that I figured I should stop being lazy and actually try to do something concrete with it. These days, I do a lot of work with Python, but Python programs are not particularly fast, and it’s often very difficult to identify problems in them via static analysis, which means unless you have a very through testing suite, your users find your silly typos for you.

Perhaps the most exciting feature about Rust is the distinct lack of a general null values (or nil or None depending on your language). There are a lot of excuses for using use null in other languages—It’s the way it’s always been done, having a value wrapped in an option type looks “ugly”, “It’s only a problem if you’re a bad programmer”, etc. A lot of languages have an option type now, but they aren’t heavily used by the standard libraries, so you’re still prone to surprise nulls coming from code you didn’t write.

Additionally, I wanted a language without a garbage collector. Garbage collectors make it a lot more complicated (and inefficient) to share code between language platforms, since you have to start up two large run times, each with their own GC that will run and halt your program every now-and-then. To this end, Rust’s borrow checker was promising. I’ve written a bit of C++ code, and you end up using std::shared_ptr (though at the time we used boost) a lot, but this doesn’t work if you’re using another library, and all they send you is a Foo*. In a complicated code base, you’ll end up sooner or later with a circular reference: A references B, and B references A. Once you find the problem, you can solve it with std::weak_ptr (A references B, and B weakly references A). However, most of the time this is done, there is an implicit that B should not outlive A. If you mess that up, you get null, and a segfault. References in Rust give you a way to explicitly design this so that the compiler ensures that B will not outlive A.

I’m going to claim that Rust is a similar language to Python. It’s very much not, but they do feel somewhat spiritually connected, perhaps something like Timon and Pumbaa from The Lion King. It’s not terribly far-fetched to imagine that much of PEP 20 was written about Rust. Rust is very explicit. It’s terse, but not so much so that readability suffers. It strongly supports the idea of errors never being silent, and avoids ambiguity. It has a fairly similar mechanism for importing modules and aliasing names. As it turns out, I’m not the first person to notice this either [AR2017].

A while ago, I wrote a Python library called August [AP2018] to convert HTML into text, and recently I ported it to Rust [AR2018]. It was essentially an HTML renderer, though much closer in feature parity to Lynx than Firefox. It was useful for converting HTML emails into plain text. It also made a good candidate for code to rewrite in Rust for several reasons:

  • It had few dependencies (just beautiful soup and standard library things)

  • It had a simple public interface (just one function that took a string and a number and returned a string)

  • It had a reasonable set of integration tests, so you could say with some degree of confidence that once the tests pass, the rewrite was complete.

  • It was a pretty good example of non-trivial Python code in the wild. It had a small class hierarchy and lot of python-isms like dictionaries of class & function objects, generators, and other iterators.

Additionally, I didn’t go to any particular effort to optimize the code. I hadn’t tried that hard to optimize the original code, and I wanted to get a clear sense of what a rewrite of this form might look like in the real world.

Results

The outcome of the project had two easily measurable results: the amount of time it took and the performance of the resulting programs. There were also a number of results that are more difficult to measure, like correctness, reliability, readability, and overall code complexity.

In terms of cost, the rewrite took about 30–40 hours of work. I had expected it to take about 10 hours, so this was quite a surprise. The original project had only taken something like 20 hours.

Run times of Python and Rust program

Program

Source File

Task Clock (msec)

IPCs 2

Memory usage (MB)

Python

Empty file

92.3 ± 0.16%

1.3

26

Rust

Empty file

0.964 ± 1.90%

1.0

4

Python

Rust homepage

102 ± 0.13%

1.4

27

Rust

Rust homepage

2.23 ± 0.62%

1.5

5

Python

War & Peace

1580 ± 0.18%

2.4

87

Rust

War & Peace

167 ± 0.32%

2.3

34

In order to test the performance I got 3 files:

  1. An empty file (0 bytes): For the most part, an empty file should just test the amount of time it takes to load the program and runtime into memory and open file descriptors. Not much actual processing would happen on an empty file.

  2. Rust homepage [RH2018] (17 KB): This is intended to be a reasonably fair example of what you’d normally process with this library.

  3. Tolstoy’s War and Peace from Project Gutenberg [LT2009] (3.8 MB): This is the closest thing I easily find for a stress test. The file is laid out with large tables, which are a fair bit of a pain to lay out properly; and, well, it’s War and Peace, clearly Tolstoy intended it for benchmarking and not for actual reading.

I used perf stat -r 10 to compile the average CPU times and time -v to calculate the memory usage (or more specifically, the maximum resident set size). I ran into trouble trying to use file redirectors with perf stat 1, so I had to copy my command into a little shell script and run that. I also redirected all the output to /dev/null so I wasn’t just profiling the amount of time it takes for the terminal to render text. The results are in Table 1.

The Rust version was faster. About 9 times faster, and about 100 times faster if you count the time it takes to load the Python runtime for a small file. Faster performance in Rust is no big surprise due to being native code, and the general slowness of Python’s object model. However, I wasn’t certain this would be the case, because the Rust code I wrote wasn’t terribly efficient and the Rust version also has better support for unicode graphemes (which is expensive, at least when rendering tables).

Discussion

Time Taken

The biggest surprise I encountered during the rewrite was the amount of time it took, about 3 or 4 times what I had expected. I’d figured that because I already had a working project that I’d written myself, and because it had a decent set of integration tests, that a rewrite would be really strait-forward.

I think this was due to several causes. First, the original code was actually a fair bit more complex than I’d remembered. A bit part of this is that the Python code used class hierarchies, and Rust doesn’t have subclassing. I had code that handled different elements in the DOM and subclassing worked nicely because they had a lot of implementation details in common, but had small variations between them. It took me several attempts to figure out a decent way of handling this in Rust, and the resulting code looked a lot different.

A second, and closely related reason was that the difference between writing Rust and Python was greater than I’d expected, and it took me longer to become comfortable with Rust than I expected. I probably shouldn’t have been surprised by this. In a lot of ways, designing Rust code probably has more in common with designing C code than it does with Python. That said, once I started to pick it up, the difficulties diminished pretty rapidly.

A third, and not terribly important reason was that html5ever is a more correct and complete parser, and as a result it made me correct a few issues.

Some Lessons Learned

There’s a lot of little gotchas that you might run into if you’re not thinking about things in a very rust-y way.

  • Often a struct might be defined in one place, but the methods for implementing specific traits with that struct are defined elsewhere. For example, if you want to read from stdin, you have to add use std::io::Read; at the top, even though you’re not actually using the Read name anywhere.

  • In most cases, Rust will disambiguate types for you. Sometimes this happens in ways that you weren’t expecting.

  • If you’re not used to it, paying attention to whether your variables are on the stack or on the heap can be a little confusing at first.

  • Lifetime specifiers seem like they should be easy in theory, but they’re a big learning curve in practice. In the end, I didn’t actually use them.

  • The following code let a = if b { "x" } else { "y"; } won’t compile due to a type mismatch, the first block returns "x" and the second block returns nothing. If you’re not used to Rust syntax, this error message is a little confusing.

  • There’s a pretty big difference between fn method(&self) and fn method(self) and they are both valid (but you probably want the first one).

  • Error messages are actually pretty good, but they can still be confusing if you’re not thinking clearly about lifetimes or traits, or if you haven’t gotten comfortable with the syntax. Also, VS Code isn’t great at highlighting all the relevant parts in an error message.

  • Pattern matching is great, but if you use the “_” catch-all, it’s easy to accidentally miss a case.

  • Strings in Rust look like byte collections (in Python they look like collections of Unicode code points). For example, the length of "«" is 2 in Rust, and 1 in Python. This is probably fine most of the time, because if you’re segmenting text, you should be doing it based on Unicode graphemes instead of code points. For example, the length of "🇨🇦" is 8 in Rust, and 2 in Python, but you really want it to be 1. The crate unicode_segmentation is pretty helpful with that.

  • All the type and lifetime checking is great, but it didn’t prevent me from being completely retarded every now and then.

Conclusion

Replacing small Python modules with Rust code can provide some significant improvements in performance benefits. In fact, the PyO3 project has already made some nice tools for creating Python packages from rust code. The languages are fairly different, however, so don’t be surprised if a rewrite takes a lot of work. Your mileage may vary, of course, because every bit of code is different and comes with its own unique challenges.

There’s also still a lot of room to optimize the Rust version of August. I didn’t want the port to take forever, and I also wanted to get a sense of how writing Rust is as a newbie. Fortunately, because of all the compile-time checking in Rust, it’s probably one of the easiest programming languages to refactor.

Since you’re still reading this, you might be interested in my next post about making Python bindings for the Rust port.

Footnotes

1

perf stat -r 10 command < input appears to only read the copy of input to the command on the first iteration. The following iterations might get the same file handler, but he cursor is presumably already at the end, so it doesn’t bother reading anything.

2

Instructions per cycle: this statistic roughly indicates how memory or instruction bound a program is, which higher values meaning instruction bound, and lower values meaning memory bound.

References

AP2018
Alan Trick. August (Python Version).
AR2018
Alan Trick. August (Rust Version).
AR2017
Armin Ronacher. 2017-6-9. A Python and Rust Love Story.
LT2009
Leo Tolstoy. 2009-1-10. War and Peace. (retrieved 2018-12-21).
RH2018
2018. Rust programming language. (retrieved 2018-12-21).