Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Comparing Pythagorean triples in C++, D, and Rust

atilanevesoncode.wordpress.com

Post reply on HN
Print view View original

11–20 of 118 posts

Re: Comparing Pythagorean triples in C++, D, and Rust

#11

Post by ekidd »

orf wrote: post #3

I would be really interested to know where the overhead in the simple rust version comes from. At first I thought it might be the println() being less efficient for whatever reason, but even without that line this[1] takes 300ms, compared to 184ms for this[2] (with the printf!). 1. https://raw.githubusercontent.com/atilaneves/pythagoras/mast... 2. https://raw.githubusercontent.com/atilaneves/pythagoras/mast...

I think you've seen this comment about integer overflow optimizations? https://www.reddit.com/r/rust/comments/ab7hsi/comparing_pyth...

But I also note that the original version of your benchmark was calling `println!`, which means that you were essentially benchmarking high-level, thread-safe I/O. EDIT: Not in this case, see the thread below.

Some Rust benchmarking tips:

1. Always run `cargo build --release`. Debug builds are slow.

2. Be sure to use `stdin.lock()` or `stdout.lock()` when reading or writing standard I/O. If you don't, Rust has to lock standard I/O for you on each call. This means using `writeln!` instead of `println!`.

Re: Comparing Pythagorean triples in C++, D, and Rust

#12

Post by steveklabnik »

blattimwind wrote: post #6

If there are big differences in where you don't expect them (e.g. printf in a for loop being very slow), then it usually is a difference in implementation and possibly contract. E.g. I wouldn't be surprised if println! in Rust is synchronous, which tends to be slow on both terminals and redirections (i.e. file I/O). For these simple examples an strace may be enlightening in this regard. Edit: Indeed this seems to be…

println will lock stdout for the duration of its work, yes. You can lock once before and use write! instead.

Re: Comparing Pythagorean triples in C++, D, and Rust

#13

Post by orf »

the_duke wrote: post #9
orf wrote: post #3

I would be really interested to know where the overhead in the simple rust version comes from. At first I thought it might be the println() being less efficient for whatever reason, but even without that line this[1] takes 300ms, compared to 184ms for this[2] (with the printf!). 1. https://raw.githubusercontent.com/atilaneves/pythagoras/mast... 2. https://raw.githubusercontent.com/atilaneves/pythagoras/mast...

Someone found a single character change providing a 2x speedup: https://www.reddit.com/r/rust/comments/ab7hsi/comparing_pyth...

Ahh yeah, using `..(z + 1)` makes it run faster than the C++ version.

Re: Comparing Pythagorean triples in C++, D, and Rust

#14

Post by stabbles »

steveklabnik wrote: post #2

The reddit thread already has one good relevant comment https://www.reddit.com/r/rust/comments/ab7hsi/comparing_pyth...

Well, that seems more like an issue with the compiler then, cause avoiding overflows would not result in a 2x slow-down in C or C++.

Re: Comparing Pythagorean triples in C++, D, and Rust

#15

Post by steveklabnik »

ah- wrote: post #7
blattimwind wrote: post #6

If there are big differences in where you don't expect them (e.g. printf in a for loop being very slow), then it usually is a difference in implementation and possibly contract. E.g. I wouldn't be surprised if println! in Rust is synchronous, which tends to be slow on both terminals and redirections (i.e. file I/O). For these simple examples an strace may be enlightening in this regard. Edit: Indeed this seems to be…

Yes, this benchmark would be much more interesting if it didn't do any println on the hot path and just accumulated the results and wrote them out once in the end. Edit: I've tried (println! vs a single io::stdout::lock() and writeln!), and it doesn't seem to make any difference, at least for the range.rs example. Hmm.

Sometimes, the trick there is that compilers can be really good at compile time stuff, and the whole computation may just be computed at compile time. In this case? Probably not. But it's not always the right way to do a benchmark, or at least, without some tweaks.

Re: Comparing Pythagorean triples in C++, D, and Rust

#16

Post by jordigh »

stabbles wrote: post #10
jordigh wrote: post #5

By the way, is it a secret to programmers that Pythagorean triples can be parametrised? I understand that the point of the code is to enumerate them without knowing that they can be parametrised, but the parametrisation in this case is not so scary, so it's a fun bit of trivia for programmers (for mathematicians, it's more fundamental, as the Pythagorean parametrisation is an important prototype for counting rational…

This was useful to me when doing Project Euler exercises, but I wouldn't know how to prove this generates all triples.

The basic idea I like is, take x^2 + y^2 = z^2, but divide by z^2 to get (x/z)^2 + (y/z)^2 = 1. Now you're looking for the rational points on the unit circle. An important observation is that any two rational points define a line with rational slope. You know of one such rational point on the unit circle, say, (-1, 0). Now you can invert this process and pick a line with rational slope that goes through (-1,0). All lines with rational slope going through (-1,0) will hit another rational point on the circle, so you've found all rational points on the circle by this method, which include all primitive Pythagorean triples.

When you work out this math, you recover the classical parametrisation, where the slope m/n of the line corresponds to the parameters, and this line-intersection method is a good inspiration for how to do the same with some higher-order curves such as elliptic curves, where it leads to the group law on them.

Re: Comparing Pythagorean triples in C++, D, and Rust

#17

Post by steveklabnik »

stabbles wrote: post #14
steveklabnik wrote: post #2

The reddit thread already has one good relevant comment https://www.reddit.com/r/rust/comments/ab7hsi/comparing_pyth...

Well, that seems more like an issue with the compiler then, cause avoiding overflows would not result in a 2x slow-down in C or C++.

Possibly! Remember that the Rust language and C/C++ have different semantics with regards to overflow. It may be the programmer's "fault" for not writing the code with the equivalent semantics (you can make them have the same semantics, but it's not the default).

Re: Comparing Pythagorean triples in C++, D, and Rust

#19

Post by burntsushi »

ekidd wrote: post #11
orf wrote: post #3

I would be really interested to know where the overhead in the simple rust version comes from. At first I thought it might be the println() being less efficient for whatever reason, but even without that line this[1] takes 300ms, compared to 184ms for this[2] (with the printf!). 1. https://raw.githubusercontent.com/atilaneves/pythagoras/mast... 2. https://raw.githubusercontent.com/atilaneves/pythagoras/mast...

I think you've seen this comment about integer overflow optimizations? https://www.reddit.com/r/rust/comments/ab7hsi/comparing_pyth... But I also note that the original version of your benchmark was calling `println!`, which means that you were essentially benchmarking high-level, thread-safe I/O. EDIT: Not in this case, see the thread below. Some Rust benchmarking tips: 1. Always run `cargo build --release`. Debug b…

> But I also note that the original version of your benchmark was calling `println!`, which means that you were essentially benchmarking high-level, thread-safe I/O.

I don't think so. The program is only doing a thousand prints, which is far less than the total number of loop iterations. Try changing to locked stdout and writeln!---I doubt you'll notice a difference.

Re: Comparing Pythagorean triples in C++, D, and Rust

#20

Post by burntsushi »

ah- wrote: post #7
blattimwind wrote: post #6

If there are big differences in where you don't expect them (e.g. printf in a for loop being very slow), then it usually is a difference in implementation and possibly contract. E.g. I wouldn't be surprised if println! in Rust is synchronous, which tends to be slow on both terminals and redirections (i.e. file I/O). For these simple examples an strace may be enlightening in this regard. Edit: Indeed this seems to be…

Yes, this benchmark would be much more interesting if it didn't do any println on the hot path and just accumulated the results and wrote them out once in the end. Edit: I've tried (println! vs a single io::stdout::lock() and writeln!), and it doesn't seem to make any difference, at least for the range.rs example. Hmm.

It's because println! isn't in the hot path. So it's fine to use it here.
Post reply on HN