{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/10301","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/10301/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/10301/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/10301/events","html_url":"https://github.com/JuliaLang/julia/issues/10301","id":58631139,"number":10301,"title":"Performance problem with memory loads/stores","user":{"login":"epn","id":3374184,"avatar_url":"https://avatars.githubusercontent.com/u/3374184?v=3","gravatar_id":"","url":"https://api.github.com/users/epn","html_url":"https://github.com/epn","followers_url":"https://api.github.com/users/epn/followers","following_url":"https://api.github.com/users/epn/following{/other_user}","gists_url":"https://api.github.com/users/epn/gists{/gist_id}","starred_url":"https://api.github.com/users/epn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/epn/subscriptions","organizations_url":"https://api.github.com/users/epn/orgs","repos_url":"https://api.github.com/users/epn/repos","events_url":"https://api.github.com/users/epn/events{/privacy}","received_events_url":"https://api.github.com/users/epn/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/JuliaLang/julia/labels/performance","name":"performance","color":"d7e102"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":15,"created_at":"2015-02-23T18:57:15Z","updated_at":"2015-02-25T05:31:27Z","closed_at":null,"body":"Julia has the following performance problem with array accesses.\r\nConsider the following code snippets. \r\n\r\n```jl\r\n# c and x are arrays of size n\r\nfunction optimized(c, x)\r\n  n = size(x, 1)\r\n  x_ = x [n] \r\n  for i = n - 1 : -1 : 1\r\n    x_  = x [i] = (x [i] - c [i + 1] * x_)\r\n  end\r\nend\r\n\r\nfunction unoptimized(c, x)\r\n  n = size(x, 1)\r\n  for i = n - 1 : -1 : 1\r\n    x [i] = (x [i] - c [i + 1] * x [i + 1])\r\n  end\r\nend\r\n```\r\n\r\nBoth functions do the same computation.\r\nThere is a loop-carry dependency in this code, that is, x [i] depends on the value of x [i+1].\r\n\r\nWhile \"optimized\" forces reading x [i+1] from the local variable x_, \"unoptimized\" simply accesses x [i+1] .\r\n\r\nFor n = 100 million, and for 100 runs of each function on my macbook air, i have the following runtimes.\r\n\r\noptimized : min 0.307929443 max 0.448113027 mean 0.31504216288000003 variance 0.00036038772082227653\r\nunoptimized : min 0.508484855 max 0.674296101 mean 0.54576100111 variance 0.001543397115546402\r\n\r\nSimilar runtimes were obtained from using julia -O.\r\n\r\nI haven't looked at the assembly code, but it seems that the unoptimized version loads x[i+1] from memory though x [i+1] was just computed in the previous iteration."},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/75908087","html_url":"https://github.com/JuliaLang/julia/issues/10301#issuecomment-75908087","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/10301","id":75908087,"user":{"login":"JeffBezanson","id":744556,"avatar_url":"https://avatars.githubusercontent.com/u/744556?v=3","gravatar_id":"","url":"https://api.github.com/users/JeffBezanson","html_url":"https://github.com/JeffBezanson","followers_url":"https://api.github.com/users/JeffBezanson/followers","following_url":"https://api.github.com/users/JeffBezanson/following{/other_user}","gists_url":"https://api.github.com/users/JeffBezanson/gists{/gist_id}","starred_url":"https://api.github.com/users/JeffBezanson/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JeffBezanson/subscriptions","organizations_url":"https://api.github.com/users/JeffBezanson/orgs","repos_url":"https://api.github.com/users/JeffBezanson/repos","events_url":"https://api.github.com/users/JeffBezanson/events{/privacy}","received_events_url":"https://api.github.com/users/JeffBezanson/received_events","type":"User","site_admin":false},"created_at":"2015-02-25T05:31:27Z","updated_at":"2015-02-25T05:31:27Z","body":"With the StepRange constructor changed to make it inlineable, plus `@inbounds`, the example at the top gets optimized."}}