EbTech's blog

By EbTech, history, 6 weeks ago, In English,

Having spent a number of Codeforces rounds practicing the ins and outs of Rust, I think it's finally safe to encourage wider participation in the language! This guide is intended primarily for C++ programmers who may have taken interest in Rust, but had doubts regarding its feasibility in timed contests. On Quora, I summarized why I think Rust is suitable for contests in 2019 onward. Granted, the learning curve is substantial enough that it may not seem that way at first. To make the transition easier, for anyone who's interested, here I'll go over some aspects of my Codeforces submissions in more detail, with some tips along the way.

My solution to 1168C: And Reachability

My solution to 1158D: Winding polygonal line

Right away, you'll notice certain characteristics:

  • The only global variable is a compile-time constant. By scoping things appropriately, I don't have to worry about accidentally forgetting to reset data.

  • Very few mutable variables. This makes code easier to reason about, and mistakes less likely.

  • Very strict type-checking. For example, I might use the usize type for array indices, and i64 for geometric coordinates. Conversions between the two must be made explicit. This seems annoying at first, but it caught quite a few of my bugs.

  • A polymorphic Scanner.next() method. It can read space-separated tokens of any type that implements the trait FromStr.

  • Output via BufWriter. This is needed for speed, if you want to write a large number of lines. BufWriter flushes automatically when it goes out of scope, but you'll probably want to flush() manually on interactive problems. Further I/O optimizations are possible (see comments section), but this is the major one and is sufficient for contests.

  • A mix of imperative-style and functional-style constructions, depending on which is clearer.

In Rust, you can read a Vec (i.e., vector in C++, ArrayList in Java) of floats from standard input in imperative style:

let mut v = Vec::with_capacity(n);
for _ in 0..n {
    let elem = scan.next::<f64>();
    v.push(elem)
}

Or you can do it in functional style, rendering the result immutable:

let v: Vec<f64> = (0..n).map(|_| scan.next()).collect();

Both versions are very efficient: the Vec initially allocates space for n elements, similar to v.reserve(n) in C++!

You can "consume" (i.e., move) a Vec if you won't need it anymore:

for elem in v { // equivalent to v.into_iter().for_each(|elem| ...)
    // do something with elem
}

Or borrow its contents mutably, to change some of its elements:

for elem in &mut v { // equivalent to v.iter_mut().for_each(|elem| ...)
    // do something with *elem
}

Or borrow its contents immutably:

for elem in &v { // equivalent to v.iter().for_each(|elem| ...)
    // do something with *elem
}

If the elements implement Copy, the dereference can be copied into the variable elem by pattern matching. This time, let's also keep track of the index:

for (i, &elem) in v.iter().enumerate() {
    // do something with elem
}

Rust Strings are UTF-8. To get random access, you'll have to convert them to .bytes() or .chars(). And if you're reading a String made entirely of 0s and 1s? Convert them to bools as follows:

let s: String = scan.next();
let v: Vec<bool> = s.chars().map(|ch| ch == ‘1’).collect();

My 1168C submission features the following rather magical line:

let (zero_bits, one_bits): (Vec<usize>, Vec<usize>) =
                (0..BITS).partition(|b| (ai & (1usize << b)) == 0);

Where did I get the idea to do this? Well, I wanted to know which positions of the binary number ai contain a 0, and which contain a 1. I knew that the Range object 0..BITS implements the Iterator trait, so I Googled "rust iterator", landed on a doc page, and browsed through the list of methods. (0..BITS).filter().collect() seems close to what I wanted: it selects the bits which satisfy a given condition. However, (0..BITS).partition() does more, giving both the passing and the failing bits! Note that collect() and partition() are polymorphic, so I could just as easily have obtained HashSets instead.

As you can see, the language is very expressive, and the standard library quite flexible. One very interesting finding from my experience with Rust is that "production-quality" code and "quick hacky" code look much more alike than they do in C++. This is because Rust not only makes it harder to do things the wrong way, but also makes it much easier to do things the right way. As a result, I naturally find myself coding in a clearer style, even under time pressure.

Overall, my solutions attain much fewer WA verdicts in Rust than they did in C++. Development time is sometimes more, sometimes less, but it gets better with practice. Best of all, I now find coding to be a less paranoid experience: I can have fun with problems instead of being hyper-alert to programming errors. Try it out and see!

As additional resources, feel free to check out my past submissions on Codeforces, my competitive programming codebook full of algorithms and data structures you can use, and Rust's new dbg!() macro for a more informative way to inspect run-time values. Leave your competitive Rust questions in the comments, and good luck!

 
 
 
 
  • Vote: I like it
  • +102
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

there's my IO template for rust: 53175781. Yeah, it's not pretty, but it is very, very fast, on par with fastest C++ templates (getchar etc).

Also rust compiler version on codeforces is a bit outdated, so you need to put

[package]
edition = "2015"

into your Cargo.toml

  • »
    »
    6 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    The Rust version on Codeforces is 1.31, which is exactly the release of 2018 edition!

    Just for fun, I re-submitted your solution with my Scanner. It seems to work well enough, though indeed yours is faster: https://codeforces.com/contest/1151/submission/55073106

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The Rust version on Codeforces is 1.31, which is exactly the release of 2018 edition!

      codeforces compiler can't deal with "non-lexical lifetimes".

      fn main() {
          let mut scores = vec![1, 2, 3];
          let score = &scores[0];
          scores.push(4);
      }
      

      - compilation error. Hence edition = "2015"

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually you can use getchar from Rust.

    https://codeforces.com/contest/947/submission/41213727

    If I understand correctly, at linking stage the program is linked to the symtem's libc. Hence that extern { fn getchar() -> i32 } works. Tho there's no getchar_unlocked since it's not compiled on POSIX system.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what a dirty hack! I like it. However, my template can read from any BufReader. For example from Vec<u8>, which is good for testing.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Looks like my unsafe Scanner is now even faster than getchar()!

      https://codeforces.com/contest/947/submission/55268770

      Thanks for the discussion everyone. It took a while to get to this point, but I think Rust is seriously competitively viable now!!

  • »
    »
    6 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    What I'd like to know is which part of Scanner<StdinLock> makes it slower, and what can we do to get optimal performance while being generic in T: FromStr?

    Could it be that read_line reads too little at a time? But it seems wrapping the StdinLock in a BufReader doesn't help much...

    Is it the fact that Scanner reads to a String, which must be checked to be valid UTF-8? If so, that's a waste since it seems the source code for parse::<i64>() ends up calling .as_bytes() anyway.

    Is it because I'm allocating new Strings for each word and storing them in a Vec? If so, maybe we can use the SplitWhitespace object directly without the allocations.

    Is the parse() method itself much slower than your custom digit multiplication? It shouldn't be, since the implementation seems similar, just with a few extra checks for the sign and such.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yes, it copies bytes from buffer to string, then validates this string. This leads to serious slowdown.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thanks. Alright, time to bring this to the attention of the Rust community: https://stackoverflow.com/questions/56449027

        Gosh I had never been active on sites like Quora, Reddit, Stackoverflow before...

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I don't know how to profile properly, but my unscientific measurements suggest the Scanner<StdinLock> (maybe even without the lock) is at most twice as slow as FastInput, which is probably good enough!

        More data would be nice though.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 6   Vote: I like it 0 Vote: I do not like it

        Hey check this out! By avoiding the Vec<String> allocations, I made it almost as fast as yours! It's ugly though because it has to read line by line, passing around references to a String and a StdinLock. I commented the nicer version which, unfortunately, doesn't compile. Would you care to play against the lifetime checker to see if it can be made to work?

        Edit: improved, but with an unsafe operation...

        Edit2: and the really unsafe dark arts version! It's as fast as you could ever want, I think, and generic so you can use it with any FromStr type.

»
6 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Regarding

Very few mutable variables.

C++ has const, but it's not the default, and it's inconvenient to use them because of std::cin.

Very strict type-checking.

g++ also have -Wconversion for warning for e.g. conversion from long long to int. I often use it and it's quite useful (although it's annoying that it doesn't recognize that (long long)a*b%MOD can be converted to int safely if MOD is an int.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried using Rust one year ago. Here's my template: https://codeforces.com/contest/1036/submission/42644334. It's written for Rust 1.15 (atCoder still hasn't updated since) that's why it contains some weird workarounds. It supports reading in tuples, which makes the input very nice in my opinion, especially together with automatic type inference:

fn main() {
    init(); // would not be needed anymore today by using something similar to lazy_static
    let n: usize = read(); // explicitly writing the type
    let mut lines = Vec::new();
    for _ in 0..n {
        let (a, b, c, d) = read(); // type is automatically inferred
        lines.push((Point { x: a, y: b }, Point { x: c, y: d }));
    }
    ...
}

I had to do my own I/O implementation anyways, since stdin() and stdout() are impossible to use efficiently (every time you read or write something, a mutex gets locked and I tested that that's already too slow for some tasks).

Note that I have written my own debug!() macro before dbg!() even existed (or was discussed about).

My two main reason against Rust are the lack of a good codebook (there's this one which is pretty good though: https://github.com/hatoo/competitive-rust-snippets -- it even comes with its snippet library: https://github.com/hatoo/cargo-snippet) and that I am turned down by the old compilers available on CF and atCoder. Now that CF has updated, I might give it another try.

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

The current command line to compile Rust solutions is rustc --edition=2018 -O -C link-args=/STACK:268435456 --cfg ONLINE_JUDGE %1