Hacker News new | ask | show | jobs
by asQuirreL 891 days ago
You joke but in Rust all of versions 1 to 4 would probably have compiled to the same machine code because LLVM would use Loop Invariant Code Motion and Induction Variable Analysis to perform the same optimisations that are being done by hand here. (Same would be true of most modern C/C++ compilers)
1 comments
lifthrasiir 891 days ago
While modern compilers do such analyses, the loop in question is too complex to be fully analyzed---it has two independent induction variables in a single loop after all.
link
asQuirreL 891 days ago
You're right -- I got nerd-sniped by this, and ended up rewriting the benchmarks in Rust. The compiler successfully inlines the square root operation, simplifies the exponentiation into multiplication and then does common-subexpression elimination over it, but no induction variable analysis, and therefore also no loop-invariant code motion. Here's it is in Godbolt:

https://godbolt.org/z/Pa6cqd1fb

But the funny thing is, I tried it on my machine, and guess what, the "unoptimised" version is consistently between 4 and 5 times faster than the hand-optimised variants:

https://gist.github.com/amnn/4be5c05975c250d0ea88b62c03f1719...

So that's fun.

link
ColinWright 891 days ago
> ... the "unoptimised" version is consistently between 4 and 5 times faster than the hand-optimised variants:

I'm getting this comment a lot, but so far the reason has been that people are using smallish numbers, and implementing the square root in floats.

In the context where this exploration is taking place, you can't do that. We're working with exact huge integers, and while a square root on floats can get you in the ballpark, you then need to refine the answer to get the exact value, and that takes order of magnitude the same time.

link
asQuirreL 891 days ago
How big are we talking? The benchmarks I tried the two numbers in your example, but yes, if you go above 2^53, then you will run into trouble with the naive solution, but that is for correctness reasons, not performance reasons.
link
ColinWright 890 days ago
This is an experiment on aspects of a factoring algorithm ... we're going to be talking about a few hundred digits base 10.

So up to around 10^200 or so, which is around 2^600.

link
asQuirreL 889 days ago
Well yes, that definitely changes the game!!
link