Rust vs Go vs C++

code review
1

I was solving a problem on leetcode with c++ and for a very big vector, i get TLE,
so the idea come to me to test with go and then i have tested with rust, still TLE.
Anyways

I thought rust would be faster or rarely same with go but
Results

C++

  • 0.56s to compile
  • 14.61s to execute

Go

  • 0.23s to compile
  • 2.66 to execute

Rust (rustc)

  • 1.47s to compile
  • 109.30s to execute

so i want to know how can i improve this rust code (can it beat go)

    // very big vec (let v = vec![.......])
    let mut ans = 0;
    let n = v.len();
    for i in 0..n {
        for j in i+1..n {
            if v[j]-v[i] > ans {
                ans = v[j]-v[i];
            }
        }
    }
    println!("{}",ans);

go code

    // very big vec (var v []int = []int{...........})
	ans := 0
	n := len(v)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if v[j]-v[i] > ans {
				ans = v[j] - v[i]
			}
		}
	}
	fmt.Println(ans)
2

I think there's an O(n) algorithm for this problem that will be much faster than any of these.

That said, all three of these languages should be in the same ballpark as far as execution time is concerned. Are you enabling optimizations in C++ and Rust?

5 Likes
3

When I paste this code into a file and do rustc -O main.rs, the Rust version is about 8x faster than Go (compiled with go build main.go).

3 Likes
4

The linear algorithm I had in mind is:

    let mut ans = 0;
    let mut start = v[0];
    for i in v {
        start = start.min(i);
        ans = ans.max(i - start);
    }

I think that's equivalent.

2 Likes
5

There is no point in computing the difference on each iteration. You can just search for the minimum and maximum, and take their difference. It should fully vectorize and be blazingly fast. There is also no point in hand-rolling the search, the standard (Iterator::max](Iterator in std::iter - Rust) and (Iterator::min](Iterator in std::iter - Rust) should do the job.

That kind of order of magnitude difference usually means you didn't enable optimizations. For Rust, you should use cargo run --release, for C++ you should compile with -O3.

6 Likes
6

I think this isn't quite what the original code does, though. If v = [2, 1], the original code returns 0, not 1.

7

Yes, sorry. I kinda pattern-matched the original question to the problem "find the greatest difference of elements", but it indeed doesn't correspond to the original algorithm.

8

I don't know if there's anything that can be done, but comparing Rust performance built in debug against other languages comes up kind of a lot?

Maybe it should inject code to check if it's being run under time? :yum:

4 Likes
9

That would require the code to be injected in the generated binary (unless we added it only to cargo run) :slight_smile:

2 Likes
10

actual problem best-time-to-buy-and-sell-stock

i have used time cmd, (e.g. $ time rustc main.rs)

time rustc -O main.rs

45.75s

time ./main

0.43s

This is very good execution time, that's what i wanted

11

Only have to do it in debug builds, and those are bloated anyway :upside_down_face:

1 Like
12

Focussing on the algorithm itself instead of optimising Rust vs other programming languages, it is not hard to create an algorithm equivalent to the original, which runs in linear time:

fn new(v: &[i32]) -> i32
{
    let n = v.len();
    let mut ans = 0;
    let mut greatest = v[n-1];
    for &vi in v[..n-1].iter().rev()
    {
        if vi > greatest
        {
            greatest = vi;
        }
        else if greatest - vi > ans
        {
            ans = greatest - vi;
        }
    }

    ans
}

Comparing timings with a random array of integers in the range -1_000_000..1_000_000, for 100_000 elements:

Original algorithm, answer = 1999870, time = 457 ms
New algorithm, answer = 1999870, time = 0 ms

and for 1_000_000 elements:

Original algorithm, answer = 1999994, time = 48362 ms
New algorithm, answer = 1999994, time = 0 ms

(which BTW, nicely confirms the quadratic scaling of the original code)

6 Likes
13

Cargo already prints

image

and the dotted thing is a hyperlink, in the terimal, pointing to the cargo profiles documentation.

1 Like
14

Yes, but it's been evident for years that a large number of beginners simply don't notice – and/or understand the implications of – the "unoptimized". It's just too technical and gets lost in the noise. Nobody reads messages that are not clearly marked as warnings or errors. And it's difficult to get people to even read and understand those! Also, I don't think it's a hyperlink in any terminal that I use at least.

I feel this could well be a Cargo lint that's warn by default, if it were easy enough to change to disable (eg. if Cargo had a git-like cargo config --global -A beginner-lints or something like that, and the lint told the user exactly what to do to disable it).

2 Likes
15

I don't think that's a surmountable problem in the general case, without making optimized builds the default.

Also, time is a shell built-in, not a parent process. I don't know that there's a sensible way to detect it, even if I thought trying to do so was a good idea.

2 Likes
16

My edit raced with you – what do you think of the lint idea?

17

If zero persons read them then the messages can be moved to --verbose.

1 Like
18

I very much agree. For a non-beginner the Unix philosophy of "print nothing if successful" is quite user-friendly, and even a beginner only needs some indication of success. For cargo run the indication can simply be the fact that your program did, in fact, start. A beginner doesn't know the implications of "non-optimized, debuginfo", and a non-beginner almost never has to be explicitly reminded about that. I really wish that many Cargo subcommands were much quieter by default – cargo test is probably the worst offender as even its "quiet mode" prints several lines per crate tested, including the silliness of "Ran 0 tests, 0 successful, 0 failed, 0 ignored".

5 Likes
19

I was a bit facetious there. I actually appreciate cargo showing me what's happening because some compiles can take a bit of time and it's good to know that it's making progress and to have a reminder what I'm currently executing (e.g. I can't remember which project release profiles I have configured with debuginfo and which not). And sometimes I do have a "oops, I should be running release" moment.
Some things could be made less noisy, e.g. by using raw terminal features and deleting the crate lines once they're done. Make it more like a progress bar.

1 Like
20

The closest to a sensible answer I can figure is something like gits notices, where it prints a big fat message along with instructions on how to stop showing it. But even if that were added, a "hey this will be slower than a release build" still doesn't seem like it would actually be a good idea, just a bad out of the box experience that everyone complains about.

2 Likes