Rust for algorithms

This week I was assigned to implement a number of string related algorithms that perform substring search and count, calculate helper functions and build performant structures on them, etc. Algorithms themselves were not too complicated, so I decided to challenge myself and solve the problems using Rust (instead of my main language C++).

Now that I’ve solved the task, I can tell a bit about my experience, things that I found convenient or complicated. I’m a beginner in Rust, but if my idea of the language is interesting to you, read on! 🙂

The assignment I had to solve is part of my Algorithms and Data Structures course at ITMO University. It has been published on the Codeforces competitive programming platform that has recently moved to ITMO. The version of Rust available on Codeforces is 1.26, so I haven’t yet had a chance to check out the new features of Rust 2018 edition.

Searching for an IDE for Rust, I’ve chosen CLion with JetBrains’ official Rust plugin. This IDE is proprietary, but of all IDEs and editors I checked only CLion provided debugging out of the box. I also enjoyed VSCode quite much, but couldn’t get any plugins that provide debug support to work with Rust. I am aware of some efforts to support Rust in KDevelop, as well as of an official Vim plugin, but decided to stick to something I use regularly anyway.

In the end, I solved 12 of 13 tasks using Rust and wrote some extra code for personal tests. I published all of it in a GitHub repository, in case it might be useful for someone.

Generally, the C++ → Rust switch felt pretty natural. With Rust, it takes a lot more time to persuade the compiler that the code is worth building, but it actually helps to fix bugs, and in the end you’re thankful to the borrow checker for its hard work. Then a number of issues gets fixed during a couple of first launches, when the program panics on integer overflows and out-of-bounds array indexes. And finally, a nice static analyzer called clippy suggests some final touches to optimize and prettify the code. Compiler errors feel unexpectedly pleasant and friendly after GCC’s text walls.

Built-in collections were sufficient for the programs I needed to write. Not much to say here really, except for that data structures want to be cloned rather than copied to avoid memory errors.

Sadly, there’s a couple of negative aspects I discovered, both related to performance. First is that rustc does not support tail call optimization (TCO), and likely won’t anytime soon. That was a big disappointment for me because there are so many algorithms out there that are described in a recursive manner, have proper asymptotics limits, but expect a compiler to do the optimization. Of course, they can be rewritten using loops, but usually you want to stick to idiomatic implementations and not reinvent.

Second, the file IO speed. Buffered file input-output in Rust is as fast as fstream in C++ unless the latter is “optimized” with sync_with_stdio(false), tie(nullptr) and no flushes (like std::endl). It’s the sole reason for that 13th program to not be submitted in Rust: it was really hitting the time limit. And even though it may seem to be a rare case, it can play its role in competitive programming.

To sum up, I loved Rust for its strict yet friendly compiler, a nice standard library, and a nice community ready to help (check out #rust on irc.mozilla.org!). There are many cool libraries out there, and I am very eager to try Qt with Rust as soon as I get some free time.

Other than that — have to go now! 🙂 Thanks for bearing with me if you made it to this sentence. Stick around for more random posts about the stuff I enjoy, and have a great day! 😀