{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/15244","repository_url":"https://api.github.com/repos/JuliaLang/julia","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/15244/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/15244/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/15244/events","html_url":"https://github.com/JuliaLang/julia/pull/15244","id":136506294,"number":15244,"title":"Proof of concept for inverted marking of vector tuple type (WIP)","user":{"login":"ArchRobison","id":2983330,"avatar_url":"https://avatars.githubusercontent.com/u/2983330?v=3","gravatar_id":"","url":"https://api.github.com/users/ArchRobison","html_url":"https://github.com/ArchRobison","followers_url":"https://api.github.com/users/ArchRobison/followers","following_url":"https://api.github.com/users/ArchRobison/following{/other_user}","gists_url":"https://api.github.com/users/ArchRobison/gists{/gist_id}","starred_url":"https://api.github.com/users/ArchRobison/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ArchRobison/subscriptions","organizations_url":"https://api.github.com/users/ArchRobison/orgs","repos_url":"https://api.github.com/users/ArchRobison/repos","events_url":"https://api.github.com/users/ArchRobison/events{/privacy}","received_events_url":"https://api.github.com/users/ArchRobison/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":22,"created_at":"2016-02-25T20:45:18Z","updated_at":"2016-02-29T18:15:44Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/JuliaLang/julia/pulls/15244","html_url":"https://github.com/JuliaLang/julia/pull/15244","diff_url":"https://github.com/JuliaLang/julia/pull/15244.diff","patch_url":"https://github.com/JuliaLang/julia/pull/15244.patch"},"body":"This is PR is intended to generate a discussion about a solution to a problem that @eschnett and I were discussing.  See [here](https://github.com/eschnett/SIMD.jl/issues/1#issuecomment-182132687) for start of discussion chain. The problem is how to get access to LLVM vector types from Julia.  The intent of the PR is to get feedback on whether the inverted approach (5 below) is something we should take forward.\r\n\r\nSome approaches to the general problem are:\r\n\r\n1.  Map homogeneous tuples to LLVM vector types automatically.  This introduces layout problems, which though I've been able to surmount though type punning, but can cause performance problems since sometimes the vector type causes  *worse* performance, as when operations on a tuple do not map to vector operations and require excessive extract/insert code.\r\n\r\n2.  Modify LLVM SLP to work on arrays as if they were vectors.  This approach works up to a point, but requires type punning on loads/stores that starts to break down for vectors that are members of structs, such as in the [GradientNumber](https://github.com/eschnett/SIMD.jl/issues/1#issuecomment-182093320) example.  If we could talk the LLVM community into adding cast operations or intrinsics to case between arrays and vectors, this approach would be my preference since it keeps use of SIMD instructions hidden.  Though some users want explicit SIMD.\r\n\r\n3.  Introduce a special Julia type that maps to an LLVM vector.  This requires teaching the Julia type system and users about the type (yuck!)\r\n\r\n4.  Use an immutable Julia type with a single tuple field.  Mark the type in some way to indicate that the tuple should map to an LLVM vector.  [Experience](https://github.com/eschnett/SIMD.jl/issues/1#issuecomment-186357742) so far indicates that this is awkward.  In retrospect, the approach is troublesome because the interpretation of a tuple type depends on surrounding context.\r\n\r\n5.  Use a homogeneous Julia tuple where the *elements* have a marked type.  Marking the element types eliminates the context-sensitivity problems of approach 4.\r\n\r\nApproach 5, which sounds upside-down, seems to be the simplest solution.  This PR implements it.  [Updated 2016-2-29 to reflect update in PR] The ~~name `Banana`~~type `Base.Banana` is used as the mark.   Example:\r\n```\r\n#from Base\r\n#immutable Banana{T}  # Marked type\r\n#    value :: T\r\n#end\r\n#export Banana\r\n\r\ntypealias V NTuple{4,Banana{Float32}}\r\n```\r\nThe PR causes two special mappings for the example:\r\n* A `Banana{T}` maps to the LLVM type for a T, not an LLVM struct containing the LLVM representation of T.  In other words,  bananas are pre-peeled in LLVM.  \r\n* A homogeneous tuple of `Banana{T}` maps to an LLVM vector of T.  I.e., an LLVM vector is used instead of an array.  \r\n\r\nThe pre-peeling rule ensures that a `Banana{T}` is mapped consistently regardless of surrounding context.\r\n\r\nBelow is an example that uses the definitions above:\r\n```\r\nadd(u,v) = (Banana(u[1].value+v[1].value),\r\n            Banana(u[2].value+v[2].value),\r\n            Banana(u[3].value+v[3].value),\r\n            Banana(u[4].value+v[4].value))\r\n\r\ncode_llvm(add,(V,V))\r\n```\r\nAt -O3, the code is:\r\n```\r\ndefine void @julia_add_22173(<4 x float>* sret, <4 x float>, <4 x float>) #0 {\r\ntop:\r\n  %3 = fadd <4 x float> %1, %2\r\n  store <4 x float> %3, <4 x float>* %0, align 16\r\n  ret void\r\n}\r\n```\r\nA library such as SIMD.jl could presumably obtain similar effect without -O via `llvmcall`."},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/190317232","html_url":"https://github.com/JuliaLang/julia/pull/15244#issuecomment-190317232","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/15244","id":190317232,"user":{"login":"KristofferC","id":1282691,"avatar_url":"https://avatars.githubusercontent.com/u/1282691?v=3","gravatar_id":"","url":"https://api.github.com/users/KristofferC","html_url":"https://github.com/KristofferC","followers_url":"https://api.github.com/users/KristofferC/followers","following_url":"https://api.github.com/users/KristofferC/following{/other_user}","gists_url":"https://api.github.com/users/KristofferC/gists{/gist_id}","starred_url":"https://api.github.com/users/KristofferC/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/KristofferC/subscriptions","organizations_url":"https://api.github.com/users/KristofferC/orgs","repos_url":"https://api.github.com/users/KristofferC/repos","events_url":"https://api.github.com/users/KristofferC/events{/privacy}","received_events_url":"https://api.github.com/users/KristofferC/received_events","type":"User","site_admin":false},"created_at":"2016-02-29T18:15:44Z","updated_at":"2016-02-29T18:15:44Z","body":"Actually creating a `Vec{8, Float32}` so it doesn't really matter what code is being generated :P :\r\n\r\n```jl\r\n@generated function Base.rand{N, T}(::Type{Vec{N,T}})\r\n    Expr(:tuple, [:(Banana(rand(T))) for i in 1:N]...)\r\nend\r\n\r\na = rand(Vec{8,Float32})\r\n\r\n\r\nsignal (11): Segmentation fault\r\nwhile loading no file, in expression starting on line 0\r\nindexed_next at ./tuple.jl:33\r\nunknown function (ip: 0x7eff2c7b4188)\r\n[inline] at /home/kristoffer/julia/src/julia_internal.h:69\r\njl_call_method_internal at /home/kristoffer/julia/src/gf.c:1906\r\nsend_to_backend at ./REPL.jl:613\r\nunknown function (ip: 0x7f013f4a8655)\r\njl_apply_generic at /home/kristoffer/julia/src/gf.c:1909\r\n[inline] at ./REPL.jl:610\r\n#18 at ./REPL.jl:624\r\nunknown function (ip: 0x7eff3c41d60d)\r\njl_apply_generic at /home/kristoffer/julia/src/gf.c:1909\r\nrun_interface at ./LineEdit.jl:1604\r\nunknown function (ip: 0x7f013f496920)\r\njl_apply_generic at /home/kristoffer/julia/src/gf.c:1909\r\nrun_frontend at ./REPL.jl:859\r\nrun_repl at ./REPL.jl:168\r\nunknown function (ip: 0x7eff3c47e16a)\r\n[inline] at /home/kristoffer/julia/src/julia_internal.h:69\r\njl_call_method_internal at /home/kristoffer/julia/src/gf.c:1906\r\n_start at ./client.jl:360\r\nunknown function (ip: 0x7f013f4c91e5)\r\njl_apply_generic at /home/kristoffer/julia/src/gf.c:1909\r\nunknown function (ip: 0x401e93)\r\nunknown function (ip: 0x40186b)\r\n__libc_start_main at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)\r\nunknown function (ip: 0x4018b1)\r\nAllocations: 4703615 (Pool: 4700646; Big: 2969); GC: 10\r\nSegmentation fault (core dumped)\r\n```"}}