Svlad_Cjelli's blog

Using Rust for programming contests
By Svlad_Cjelli, history, 3 years ago, In English

I have been trying out Rust in contests and I'm curious about other people's impressions of the language, in comparison with C++. In particular I am interested in the possibility for building higher abstractions, and for better error detection.

C++ definitely has the potential to be error-prone, but I became much more consistent with it once I started using an LSP that shows me warnings/errors as I type. That plus avoiding global variables. Now I feel like almost all of my errors are logic-based rather than due to the unsafety of the language.

Here are some of my first impressions from using Rust to solve some contest problems.

Things I enjoyed:

  • iterators, map, filter, etc. I feel like the syntax is often cleaner than C++, where I would almost always default to mutable variables instead.

  • Type inference is usually good

  • Lightweight tuple and array syntax

  • Ranges

  • "const" is default

  • Automatic error tracing when compiling in debug mode

Dislikes/annoyances:

  • Recursive functions. This is the big one. In C++, recursive lambdas (with a Y combinator) are very convenient and allow for things like DFS without passing in a million parameters (and without global variables).

  • Index has to be usize

  • Casting to and from references

  • The borrow checker doesn't seem to be that useful for contest problems

I'm interested in what else the language can offer! Looking forward for Egor to weigh in.

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

»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

сс qwerty787788

I'll write later

→ Reply
»
3 years ago, # |
  Vote: I like it +55 Vote: I do not like it

I've been using Rust for competitive programming for more than a year now, and I definitely can recommend it!

I switched from Java, and the main reason was being tired of getting a lot of time limits with asymptotically correct solutions. From this point, Rust is perfect as the speed is basically the same as in C++.

If we compare C++ and Rust, I'd say that the Rust compiler saves you from a lot of silly mistakes. Also debugging is much more pleasant. For example, in the case of array index out of bound access, you see a message about it, not undefined behavior. I know you can potentially configure your local C++ environment to catch most of such bugs, but in the testing system, there is still a chance of getting WA instead of RE in C++, which could be confusing.

A little bit of advertising. Really recommend using Egor's rust-competitive-helper, which makes reusing your library code much easier.

For recursive functions, I use a special macro (thanks Egor), which basically does some magic, and can capture local variables the same way as lambdas. See: 157782258. There are still some limitations (you need to use different macros based on the number of arguments you want to pass to a function), but it is still easier than passing a lot of arguments to a real separate function.

At first, I also disliked usize being a separate type and always had to put a lot of casts. But as time goes by, you develop an intuition about when to use which type, and it becomes not that bad. Though sometimes it is still annoying. E.g. if you want to iterate over neighbors of the cell in 2d array (so I just created a special library function for that, and use it with rust-competitive-helper).

One sad thing about using Rust for competitive programming — not all platforms are as good as CodeForces, and they have old compiler versions, so all your library code can't use new language features. Or you can just ignore such platforms (yes, CodeChef, I am looking at you :).

Two other small, but important features. Option< T >. Which just makes your code cleaner and helps to make sure you handled all cases. And powerful enums, which could store data inside. Again, you can live without them, but once you try, you can't stop using them!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thanks for the response!

    I like the RecursiveFunction macros, though they're a bit less convenient to use than y_combinator in C++. It seems like in general, Rust benefits a lot from having an extensive template — I am used to a pretty minimal one in C++ (standard imports, debug macro, y_combinator, and a few shortcuts to save typing).

    I like Rust's debug messages — so far, they have helped me with failed input parsing and array bounds. Are there any other "silly mistakes" that the compiler helps you catch?

    I think Rust enums are great — It's sad that a lot of other languages don't have something similar. Do you have an example of creating custom enums (with stored data) to use in solving a problem?

    About Option — sometimes it's a bit annoying that some library functions return options even when I know it will never be None. So I end up having to write things like v.iter().max().unwrap() and v.last().unwrap() a lot. But I guess it forces you to think about corner cases...

    I do really like some of the syntax that Options allow though — like while let Some(x) = q.pop_front() { ... }

    Oh and I just thought of another small annoyance — you can't do swap(&mut v[i0][j0], &mut v[i1][j1]) like in C++.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      About silly mistakes — I mostly mean random undefined behaviors you can have in C++ (index out of bounds, use after free, use a variable without initializing, dereferencing nulls, ...).

      The most common case for using enums — is in tasks when you need to handle several different types of queries (e.g. change element of the array and calculate the sum of elements).

      About unwrap() — yeah, that could be annoying. That is why I created my own functions like last_exn() and implemented them for vector/slices (via traits).

      Hmm, unfortunatelly forbidding swap(&mut v[i0][j0], &mut v[i1][j1]) kinda makes sense, because compiler wants to protect you from running it on i0 == i1 && j0 == j1 when swap (or some other function) potentially could work badly. Though for 1-dimentional case, you can use v.swap(i0, i1).

      But you can implement your own Array2D and swap function for it :)

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Also I have to add that using vector of vectors when what you really need is rectangular 2d array is suboptimal

        → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Although unwrap() is usually kind of annoying, but sometimes things like unwrap_or() can be helpful, e.g. different behaviour depending on whether array is empty or not.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I agree with all that qwerty787788 said. I guess without using extensive library C++ maybe much easier to use than rust, but then I had not used either without such library.

    About warnings — I can't stress how many times compilator saved me debugging with "this variable is mutable but not changed anywhere"

    One more nice thing about rust is you can implement traits on standard types. But then it is also mostly usable if you do have a library

    One note about my recursive macro — it is theoretically undefined behavior, but at the moment compilator do not seem to do anything unexpected here. This may change in the future

    → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Does Rust has a good collection library like STL in C++?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Yes, Rust has all the common data structures. Here is the equivalence:

    std::vector -> Vec

    std::deque -> VecDeque

    std::set -> BTreeSet

    std::map -> BTreeMap

    std::unordered_set -> HashSet

    std::unordered_map -> HashMap

    std::priority_queue -> BinaryHeap

    I am not sure about performance comparisons. Rust's HashMap and HashSet use better hashing than unordered_set/map, but may be slower as a result — maybe someone with more experience can chime in.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      I tried to push something into Vec once. Got a strange message about borrowing stuff, didn't want to bother learning the language properly and dropped it until maybe next time.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Regarding hashtable performance, I don't have benchmarks, but my intuition suggests the speed should be comparable. Rust uses more complicated hash functions, which slows it down. But on the other hand, it uses open addressing, making it much more cache-friendly than the C++ version.

      Also, you can change what hash function is used and make it ~2x faster (see FxHash).

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The cool thing is, the BTreeMap does 2.5e6 inserts in 500 ms, which is 2x faster than std::map. Rust sort_unstable() sorts 1e7 i32 in 350 ms, 2x faster than std::sort() too.

    → Reply