3 ms·

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 Inductio

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)

lifthrasiir 3y 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.
- asQuirreL 3y 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 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/4be5c05975c250d0ea88b62c03f1719e https://gist.github.com/amnn/4be5c05975c250d0ea88b62c03f1719... So that's fun.
  - ColinWright 3y 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.
    - asQuirreL 3y 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.
      - ColinWright 3y 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.
        asQuirreL 3y ago
        Well yes, that definitely changes the game!!

lifthrasiir 3y 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.

asQuirreL 3y 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 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/4be5c05975c250d0ea88b62c03f1719e https://gist.github.com/amnn/4be5c05975c250d0ea88b62c03f1719... So that's fun.
- ColinWright 3y 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.
  - asQuirreL 3y 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.
    - ColinWright 3y 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.
      - asQuirreL 3y ago
        Well yes, that definitely changes the game!!