Comparing Pythagorean triples in C++, D, and Rust
atilanevesoncode.wordpress.com
Comparing Pythagorean triples in C++, D, and Rust
1–10 of 118 posts
Re: Comparing Pythagorean triples in C++, D, and Rust
#2The reddit thread already has one good relevant comment https://www.reddit.com/r/rust/comments/ab7hsi/comparing_pyth...
Re: Comparing Pythagorean triples in C++, D, and Rust
#3I 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...
Re: Comparing Pythagorean triples in C++, D, and Rust
#4I 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...
Perhaps the terminal is linebuffered. (edit: I forgot that `!` was a character in Rust, so I mis-read your comment, oh well).
Re: Comparing Pythagorean triples in C++, D, and Rust
#5By 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 points on elliptic curves, a fundamental problem in number theory).
https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_...
Slightly less easy nor well-known amongst mathemticians (or at least, this is new to me), you can enumerate all primitive Pythagorean triples in a tree!
https://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_...
This tree is really interesting! I wonder where those matrices come from. The proof that it works is a boring mechanical check, but I'm now interested in how they were derived in the first place. This is a 20th century discovery, unlike the parametrisation which comes from antiquity. I think I'll be reading some papers about this.
Re: Comparing Pythagorean triples in C++, D, and Rust
#6If 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 the case from the library source code (println! -> _eprint -> stdout -> LineWriter).
Re: Comparing Pythagorean triples in C++, D, and Rust
#7If 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.
Re: Comparing Pythagorean triples in C++, D, and Rust
#8I 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 looked at the disassembly of both of those in https://godbolt.org/ and it looks like for some reason Rust puts the loop variables x,y and z on the stack and the loads them off the stack. This causes a bunch of L1 hits instead of register hits in the tight loop, causing the 2x slowdown.
I have no idea why LLVM misses optimizing this in Rust's case. Likely it is fed much trickier IR. It also misses the optimization that it does in the C case of lifting the xx and zz multiplications to the appropriate loop level.
Re: Comparing Pythagorean triples in C++, D, and Rust
#9I 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...
Re: Comparing Pythagorean triples in C++, D, and Rust
#10By 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.