Hi,
A while ago there was a post on a similar topic, but I wanted to start a more thoughtful discussion this time. Currently, I am using to use Rust to write CodeCup, and I’m curious about your experiences and opinions.
Here are some questions:
How Rust compares to C++ in competitive programming verbosity vs safety vs speed.
Situations where Rust shines or struggles compared to other languages.
Is Rust's standard library big enough for competetive programming?
In competetive programming would you rather .unwrap() everything or do more complex error handling?
I’d love to hear everyone’s thoughts, experiences, and any general advice about using Rust in competitive programming.
If you're not literally trying to get functionality as fast as possible (live programming?) but also long term reliability and architecture aren't a big issue I'm not sure it matters too much what you choose, it's more about familiarity than anything.
Given that caveat; I'd say in particular Rust is about the same to a little better than C++ on verbosity (no headers, derives and more powerful macros for example), and it mostly has a better standard library (though coverage is spotty if you're not using any libraries: C++ has built in async executors and regex for example. Rust prefers to let external crates figure out what's needed if there's not a single obvious implementation, while C++ prefers to add the obvious interface and let implementations figure it out)
Safety is hopefully a fairly obvious Rust win: with the caveat that the ability to avoid hitting issues with the borrow checker and related things is a fairly hard won skill. Arguably, that skill is exactly the ability to not be writing crashing bugs in the first place, but you might find Rust getting in your way too much if you're trying to get something like this done quick.
Error handling with unwrap/expect vs Result isn't actually that big a deal in terms of effort saved. Even without crates like anyhow you can just type Result<T> = std::result::Result<T, Box<dyn Debug>>; and you're 90% there. The bigger issue is the Result doesn't tell you where it failed unless you put that message in yourself, so if you don't need to keep going on some error unwrap/expect is probably nicer.
In CodeCup you have several months to write code so it's basically a regular programming project. I've won it using Rust so it's possible.
It's similar in verbosity and speed, much better in terms of safety of course.
The main thing I was missing was that rand wasn't available so I re-implemented ChaCha20 as my PRNG. Other times I've used my own little versions of things like EnumMap, Either, ArrayVec. You can probably copy-paste some code from external crates (with appropriate attribution and whatever the license requires).
Use unwrap or expect for things that are guaranteed not to fail thanks to the logic of the code inside whatever module you're implementing, otherwise handle or propagate errors as appropriate.
In live competitions I think it's a more interesting question; I think really you'd have to try and see if it works for you. My guess, though, is most people wouldn't like it as you're getting pushed into "doing it right" so you're spending a lot more time up front before you see anything working - in exchange for not spending a lot of time at the end trying to squash bugs, presumably.
The really notable exception, though, is threaded code, which is hilariously easier in Rust than nearly anything else to get right. If you want to do a whole bunch of CPU and get the code right fast, I think Rust is a great choice!
I have the unpopular opinion, that you still solve real-world problems using your brain, and, that it's unimportant in which Turing-complete language you formulate the solution.
NB: Of course, in companies and teams there may be limitations due to other constraints, such as infrastructure, compliance and overall team knowledge and collaboration.
Also, Rust can help you during development with its strong type system and helpful compiler errors.
LCG is not random enough for many algorithm, especially with arbitrary parameters. Use xorshift family or pcg family or wyhash when you want a <10 line RNG.
A digression: Rust is not Turing complete for the same reason C isn't Turing complete -- both have to limit the size of potentially allocated memory at the beginning of the program (to usize::MAX), making simulating an unbounded tape impossible. Other languages that don't expose such limitations (like ML or Python) are Turing-complete.
In C every object have to have an address, but is it true for Rust? Wouldn't it be enough to create two threads with two recursive functions to hold two stacks? That's enough for Turing-completeness.
An allocation is a subset of program memory which is addressable from Rust, and within which pointer arithmetic is possible. Examples of allocations include heap allocations, stack-allocated variables, statics, and consts.
An allocation has a base address, a size, and a set of memory addresses.
But is there a limit on the number of files you could create? Or how much could fit in a pipe that you loop back to yourself on a diffrent file descriptor?
Of course any real computer is limited in memory. Any real physical system even. Probably even in theory: bounded by the size of the observable universe (though I am no physicist).
You can still do a lot of useful computation without being Turing complete. And that is why Turing completeness does not matter in real world. The more useful class to consider is bounded storage machines, since that pretty closely reflects real computers.
Obviously. I was really just nitpicking on the terminology, it wasn't meant as a criticism of Rust. Turing-completeness is overrated. A better computational model for C and Rust is the Word RAM model. Most work in algorithms assumes the Word RAM model, not Turing machines.
If you are nitpicking on the terminology then you need to first define what does it mean for the language to be Turing Complete.
It's obvious that none of exsisting implementations of Rust can execute a program that requires 2¹⁰⁰⁰ tape cells. But you can always execute your program on a larger system.
Neither C nor Rust limit the size of uintptr_t/usize, it can be 32, 64, 1024 or even larger.
Does the fact that “ computational system” that would employ Python program may increase uintptr_t/usize when the need would arise and C or Rust program-based one would need to throw calculations aways and start from scratch make one of them “Turing-complete” and the other one not “Turing-complete”?
I don't see how. Turing equivalence is not concerned with programs that never stop it only talks about functions that may be computed — and for every such function and for every input you may pick Rust runtime that would be able to compute it…
Hmm.. If I bolt a Turing style tape storage system onto to my computer that tape could be infinitely long in either direction. Winding it backwards a forwards 2¹⁰⁰⁰ positions would be perfectly possible using Rust or most other languages. Such a tape system has no notion of an "address", only move left or right, read or write. It would be up to the Rust program to keep track of position if it wants to and 1000 bit number for such is no problem.
