{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/10588","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/10588/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/10588/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/10588/events","html_url":"https://github.com/JuliaLang/julia/pull/10588","id":63276590,"number":10588,"title":"Simplify real givensAlgorithm.","user":{"login":"andreasnoack","id":505001,"avatar_url":"https://avatars.githubusercontent.com/u/505001?v=3","gravatar_id":"","url":"https://api.github.com/users/andreasnoack","html_url":"https://github.com/andreasnoack","followers_url":"https://api.github.com/users/andreasnoack/followers","following_url":"https://api.github.com/users/andreasnoack/following{/other_user}","gists_url":"https://api.github.com/users/andreasnoack/gists{/gist_id}","starred_url":"https://api.github.com/users/andreasnoack/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/andreasnoack/subscriptions","organizations_url":"https://api.github.com/users/andreasnoack/orgs","repos_url":"https://api.github.com/users/andreasnoack/repos","events_url":"https://api.github.com/users/andreasnoack/events{/privacy}","received_events_url":"https://api.github.com/users/andreasnoack/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":9,"created_at":"2015-03-20T18:12:24Z","updated_at":"2015-03-24T02:19:12Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/JuliaLang/julia/pulls/10588","html_url":"https://github.com/JuliaLang/julia/pull/10588","diff_url":"https://github.com/JuliaLang/julia/pull/10588.diff","patch_url":"https://github.com/JuliaLang/julia/pull/10588.patch"},"body":"So far, we have been using a translation of the real givens rotations subroutine DLARTG from LAPACK. However, it is basically reimplementing `hypot` so I think we can make the implementation much simpler by just using our `hypot` function and it is also approxmately 20 pct. faster.\r\n```julia\r\njulia> let\r\n       f, g = randn(2)\r\n       @time for i = 1:10^8; tmp1 = LinAlg.givensAlgorithm(f, g); end # New Givens\r\n       @time for i = 1:10^8; Hypot.givensAlgorithm(f, g); end  # LAPACK Givens\r\n       end\r\nelapsed time: 0.901623412 seconds (0 bytes allocated)\r\nelapsed time: 1.182648847 seconds (0 bytes allocated)\r\n```\r\nFurthermore, the simplification makes the cosine and sine continuous in the angle which the LAPACK version is not. \r\n\r\n![lapackgivens](https://cloud.githubusercontent.com/assets/505001/6757861/ab279ff0-cf0a-11e4-8206-53f57cfc77f0.png)\r\n![newgivens](https://cloud.githubusercontent.com/assets/505001/6757862/aea801c4-cf0a-11e4-953d-d7891e3e160c.png)\r\nThis note\r\n\r\nhttp://www.netlib.org/lapack/lawnspdf/lawn150.pdf\r\n\r\nargues that continuity is useful, but for some reason, the LAPACK authors haven't followed the advice.\r\n\r\ncc: @alanedelman, @stevengj "},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/85298889","html_url":"https://github.com/JuliaLang/julia/pull/10588#issuecomment-85298889","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/10588","id":85298889,"user":{"login":"simonster","id":470884,"avatar_url":"https://avatars.githubusercontent.com/u/470884?v=3","gravatar_id":"","url":"https://api.github.com/users/simonster","html_url":"https://github.com/simonster","followers_url":"https://api.github.com/users/simonster/followers","following_url":"https://api.github.com/users/simonster/following{/other_user}","gists_url":"https://api.github.com/users/simonster/gists{/gist_id}","starred_url":"https://api.github.com/users/simonster/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/simonster/subscriptions","organizations_url":"https://api.github.com/users/simonster/orgs","repos_url":"https://api.github.com/users/simonster/repos","events_url":"https://api.github.com/users/simonster/events{/privacy}","received_events_url":"https://api.github.com/users/simonster/received_events","type":"User","site_admin":false},"created_at":"2015-03-24T02:19:12Z","updated_at":"2015-03-24T02:19:12Z","body":"@andreasnoack That's a good question. I suspect the answer has something to do with having an inlined function that returns a tuple from two possible points, but the allocation seems to disappear if I put everything in a function rather than using a `let` block, so I wouldn't worry too much.\r\n\r\nBut this is hard to benchmark, and the times above are not accurate. The reason there is no difference between `givens1` and `givens2` is that they are actually the same loop :smile:. Since you aren't doing anything with the output, LLVM is just removing the multiplication and division. Even if you do something with the output, LLVM is still smart enough to remove the branch in `givens3` since it knows at compile time that `g != 0`, so you won't be able to benchmark its cost.\r\n\r\n@jakebolewski I think the lowering after type inference isn't doing the right thing with that because it doesn't know about loop trip counts and thinks `t3` could be returned undefined. You could fix that by initializing it as `t3 = (1.0, 1.0, 1.0)` or similar instead of `local t3`, and that gets rid of the allocation, but the same caveats above still apply. The code that runs will only perform the multiplication/division on the last iteration of the loop."}}