{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/10288","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/10288/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/10288/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/10288/events","html_url":"https://github.com/JuliaLang/julia/issues/10288","id":58518351,"number":10288,"title":"Another approach for fast closures","user":{"login":"timholy","id":1525481,"avatar_url":"https://avatars.githubusercontent.com/u/1525481?v=3","gravatar_id":"","url":"https://api.github.com/users/timholy","html_url":"https://github.com/timholy","followers_url":"https://api.github.com/users/timholy/followers","following_url":"https://api.github.com/users/timholy/following{/other_user}","gists_url":"https://api.github.com/users/timholy/gists{/gist_id}","starred_url":"https://api.github.com/users/timholy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/timholy/subscriptions","organizations_url":"https://api.github.com/users/timholy/orgs","repos_url":"https://api.github.com/users/timholy/repos","events_url":"https://api.github.com/users/timholy/events{/privacy}","received_events_url":"https://api.github.com/users/timholy/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":3,"created_at":"2015-02-22T21:01:51Z","updated_at":"2015-02-24T02:53:57Z","closed_at":"2015-02-24T02:53:57Z","body":"Similar goal to #10269, with a very different approach. I've just rewritten FastAnonymous to take advantage of stagedfunctions and call overloading: see the [calloverload branch](https://github.com/timholy/FastAnonymous.jl/tree/teh/calloverload). In brief, the strategy here is:\r\n- encode the function/expression to be executed as a tuple and use it as a type parameter;\r\n- a stagedfunction overloaded `call` generates an inlinable expression.\r\n\r\nA simplified version of the strategy can be illustrated like this:\r\n```julia\r\nmodule Simple\r\n\r\nexport Fun, mymap!\r\n\r\nimmutable Fun{ext,argnames} end  # ext is the expression encoded as a tuple\r\n\r\nFun(ex, argnames::(Symbol...)) = Fun{expr2tuple(ex), argnames}()\r\n\r\nstagedfunction call{ext,argnames}(f::Fun{ext,argnames}, __X__...)\r\n    n = length(__X__)\r\n    ex = tuple2expr(ext)   # convert back to an expression\r\n    # unpack the entries in __X__ into the named variables, and plug them into the expression\r\n    Expr(:block, [:($(argnames[i]) = __X__[$i]) for i = 1:n]..., ex)\r\nend\r\n\r\n# Some utility functions\r\nfunction expr2tuple(ex::Expr)\r\n    args = [expr2tuple(a) for a in ex.args]\r\n    tuple(ex.head, args...)\r\nend\r\nexpr2tuple(s) = s\r\n\r\nfunction tuple2expr(t::Tuple)\r\n    args = [tuple2expr(t[i]) for i = 2:length(t)]\r\n    Expr(t[1], args...)\r\nend\r\ntuple2expr(s) = s\r\n\r\n# And a demo function\r\nfunction mymap!{ext,argnames}(f::Simple.Fun{ext,argnames}, dest, src)\r\n    for i = 1:length(src)\r\n        dest[i] = f(src[i])\r\n    end\r\n    dest\r\nend\r\n\r\nend\r\n```\r\nwith the following results:\r\n```julia\r\njulia> using Simple\r\n\r\njulia> f = Fun(:(x+sin(x)), (:x,))   # equivalent to f = x -> x+sin(x)\r\nSimple.Fun{(:call,:+,:x,(:call,:sin,:x)),(:x,)}()\r\n\r\njulia> a = rand(10);\r\n\r\njulia> b = similar(a);\r\n\r\njulia> mymap!(f, b, a);\r\n\r\njulia> @time 1\r\nelapsed time: 0.004268577 seconds (30 kB allocated)\r\n1\r\n\r\njulia> @time mymap!(f, b, a)\r\nelapsed time: 1.1382e-5 seconds (80 bytes allocated)\r\n10-element Array{Float64,1}:\r\n 1.19225 \r\n 1.29765 \r\n 0.593436\r\n 0.843164\r\n 1.82338 \r\n 1.55407 \r\n 0.605003\r\n 0.268219\r\n 1.51561 \r\n 0.625991\r\n\r\njulia> x = a[1]\r\n0.6151588925104088\r\n\r\njulia> x+sin(x)\r\n1.192247186695486\r\n```\r\nIn particular, note the lack of significant allocation. Using larger inputs, you can easily convince yourself that `mymap!` runs as fast as a hand-written version where you've hard-coded in `x+sin(x)`.\r\n\r\nThe code in FastAnonymous takes this one step further: when necessary, it creates \"stagedtypes\" that encode an environment storing any variables not supplied as arguments. For example:\r\n```julia\r\njulia> using FastAnonymous   # must be on the calloverload branch\r\n\r\njulia> a = 4.2\r\n4.2\r\n\r\njulia> f = @anon (x,y) -> x+a*y\r\n(x,y) -> quote  # none, line 1:\r\n    Main.+(x,Main.*(a,y))\r\nend\r\nwith:\r\n  a: 4.2\r\n\r\njulia> f(1,2)\r\n9.4\r\n\r\njulia> f.a = -7\r\n-7.0\r\n\r\njulia> f(1,2)\r\n-13.0\r\n\r\njulia> f\r\n(x,y) -> quote  # none, line 1:\r\n    Main.+(x,Main.*(a,y))\r\nend\r\nwith:\r\n  a: -7.0\r\n\r\njulia> a = -7\r\n-7\r\n\r\njulia> f = @anon (x,y) -> x+a*y\r\n(x,y) -> quote  # none, line 1:\r\n    Main.+(x,Main.*(a,y))\r\nend\r\nwith:\r\n  a: -7                 # <- note this is an Int, not a Float64\r\n\r\njulia> f(1,2)\r\n-13                     # an Int\r\n```\r\n\r\nCompared to the old approach taken by FastAnonymous, I think this is much closer to what we'd really want from a closure:\r\n- For a given set of environment variable _types_, it only creates one new type (it reuses previously-generated types if you use `@anon` again).\r\n- Consequently much-reduced construction time for `@anon` objects\r\n- There's no negative consequence for garbage collection\r\n- You can update an `anon` object by altering the values stored in its fields\r\n\r\nThere's one showstopper bug, however: currently the return type is not inferred correctly. Obviously this is different from the `Simple` module up above, and the reason comes down to those `Main.+` scoped calls above. I've spelled out the problem in #10287. If the user has defined a function (like the `to_gray` example in the tests for FastAnonymous), then I found I needed to add explicit module scoping---the `call` overloading is not in a macro scope anymore, obviously, so `esc` doesn't solve the problem.\r\n"},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/75689459","html_url":"https://github.com/JuliaLang/julia/issues/10288#issuecomment-75689459","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/10288","id":75689459,"user":{"login":"timholy","id":1525481,"avatar_url":"https://avatars.githubusercontent.com/u/1525481?v=3","gravatar_id":"","url":"https://api.github.com/users/timholy","html_url":"https://github.com/timholy","followers_url":"https://api.github.com/users/timholy/followers","following_url":"https://api.github.com/users/timholy/following{/other_user}","gists_url":"https://api.github.com/users/timholy/gists{/gist_id}","starred_url":"https://api.github.com/users/timholy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/timholy/subscriptions","organizations_url":"https://api.github.com/users/timholy/orgs","repos_url":"https://api.github.com/users/timholy/repos","events_url":"https://api.github.com/users/timholy/events{/privacy}","received_events_url":"https://api.github.com/users/timholy/received_events","type":"User","site_admin":false},"created_at":"2015-02-24T02:53:57Z","updated_at":"2015-02-24T02:53:57Z","body":"If you ever wondered whether we've given ourselves enough rope to hang ourselves with, the answer appears to be \"yes.\" :smile: The final version seems to work really nicely, and has only 141 lines of \"real\" code; however, the implementation is [positively terrifying](https://github.com/timholy/FastAnonymous.jl/commit/b745d3e57e149d37c7fdde8f98a717514cba4ede). So much for the barriers between types and values...\r\n"}}