# Type-stable threaded map?

**URL:** <https://discourse.julialang.org/t/type-stable-threaded-map/24498>\
**Category:** General Usage\
**Created:** [May 22, 2019, 11:41pm UTC](https://discourse.julialang.org/t/type-stable-threaded-map/24498 "2019-05-22T23:41:15Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![marius311](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marius311/32/3953_2.png) [@marius311](https://discourse.julialang.org/u/marius311)\
**Post date:** [May 22, 2019, 11:41pm UTC](https://discourse.julialang.org/t/type-stable-threaded-map/24498/1 "2019-05-22T23:41:15Z")

</div>

Can anyone think of a way to write a threaded map function that is type stable? The only way I have come up with so far uses `return_type` which I understand is [not a good idea](https://discourse.julialang.org/t/roadmap-for-a-faster-time-to-first-plot/22956/11).

```julia
function tmap(f, args...)
    cargs = collect(zip(args...))
    n = length(cargs)
    T = Core.Compiler.return_type(f, Tuple{map(typeof,first(cargs))...})
    ans = Vector{T}(undef,n)
    Base.Threads.@threads for i=1:n
        ans[i] = f(cargs[i]...)
    end
    ans
end

```

---

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [May 22, 2019, 11:59pm UTC](https://discourse.julialang.org/t/type-stable-threaded-map/24498/2 "2019-05-22T23:59:01Z")

</div>

Two option for ideas could be [GitHub - madsjulia/RobustPmap.jl: Robust pmap calls for efficient parallelization and high-performance computing](https://github.com/madsjulia/RobustPmap.jl) and [https://github.com/mohamed82008/KissThreading.jl](https://github.com/mohamed82008/KissThreading.jl)

---

<div class="post-metadata">

**Author:** ![marius311](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marius311/32/3953_2.png) [@marius311](https://discourse.julialang.org/u/marius311)\
**Post date:** [May 23, 2019, 12:17am UTC](https://discourse.julialang.org/t/type-stable-threaded-map/24498/3 "2019-05-23T00:17:19Z")

</div>

KissThreading `mapreduce` appears to only be type-stable because it forces you to give the `init` argument, which it then takes the type from.

```julia
julia> @code_warntype KissThreading.tmapreduce(x->x^2, vcat, 1:10, init=Int[])
Body::Array{Int64,1}

julia> @code_warntype KissThreading.tmapreduce(x->x^2, vcat, 1:10, init=Any[])
Body::Array{Any,1}

```

Similarly, RobustPmap also looks like it just lets you give the return type [by hand](https://github.com/madsjulia/RobustPmap.jl/blob/89aea514112a06bdac05871c7aa963d1a9e928ea/src/RobustPmap.jl#L53-L57) if you want.

Here, I’m looking for something that is automatically inferred like how `Base.map` works.

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [May 23, 2019, 1:04am UTC](https://discourse.julialang.org/t/type-stable-threaded-map/24498/4 "2019-05-23T01:04:29Z")

</div>

I think the only way this is really feasible without having the user specify the type is using `return_type` (either explicitly or implicitly) because fundamentally, you want your function to create a container that has an element type that must be determined via inferring the return type of `f` on the elements of your container.

Also, my understanding is that it’s a bad idea to have code that will break if an update makes inference more or less powerful, but it seems that your code will _not_ break if inference becomes more or less precise, it would just mean that the type of vector you allocate could be more or less efficient for your purposes. You’re not relying on the compiler always giving a concrete type. Even `Vector{Any}` would be fine.

* * *

Edit:  
However, there is still a problem with this:

```julia
 T = Core.Compiler.return_type(f, Tuple{map(typeof,first(cargs))...})

```

consider the following contrived example:

```julia
function tmap(f, args...)
    cargs = collect(zip(args...))
    n = length(cargs)
    T = Core.Compiler.return_type(f, Tuple{map(typeof,first(cargs))...})
    ans = Vector{T}(undef,n)
    Base.Threads.@threads for i=1:n
        ans[i] = f(cargs[i]...)
    end
    ans
end

f(x) = rand(Bool) == true ? 1.0 : 1
f(s::String) = "boo!"

julia> tmap(f, [1, 2, "hi"])
Error thrown in threaded loop on thread 2: MethodError(f=typeof(Base.convert)(), args=(Union{Float64, Int64}, "boo!"), world=0x0000000000006408)
 3-element Array{Union{Float64, Int64},1}:
  1.0
  1.0
  0.0

```

---

<div class="post-metadata">

**Author:** ![marius311](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marius311/32/3953_2.png) [@marius311](https://discourse.julialang.org/u/marius311)\
**Post date:** [May 23, 2019, 1:46am UTC](https://discourse.julialang.org/t/type-stable-threaded-map/24498/5 "2019-05-23T01:46:34Z")

</div>

> [@Mason](#):
>
> You’re not relying on the compiler always giving a concrete type. Even `Vector{Any}` would be fine.

I don’t think its quite the same. `Vector{SomeConcreteType}` vs. `Vector{Any}` will dispatch differently when fed into various other functions, so here the functionality of my subsequent code would really change depending on if inference worked fully. As I understand it, `Base.map` uses some method of starting with a vector given the return type of the first element, then widening the type if necessary for subsequent elements, but not relying on inference to determine the eltype (I admit I’ve not read the code though; I guess really that’s what my `tmap` would have to emulate somehow…)

> [@Mason](#):
>
> consider the following contrived example:

Yes good catch, should have mentioned my functions was only meant to work in the case of a homogenously typed array.

---

<div class="post-metadata">

**Author:** ![jeff.bezanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff.bezanson/32/48_2.png) [@jeff.bezanson](https://discourse.julialang.org/u/jeff.bezanson)\
**Post date:** [May 23, 2019, 2:56am UTC](https://discourse.julialang.org/t/type-stable-threaded-map/24498/6 "2019-05-23T02:56:11Z")

</div>

This is a very good question. If you look at the way Base.map works, it actually does a _reduction_ over the types of the values, so a parallel version of the algorithm would need a parallel reduction. A key missing piece for that is the ability to infer the result of a Task. We haven’t really needed that before since Tasks did not tend to be used for performance-critical code, but in the multithreaded future they will be. So we’ll need to work on that. Then you could use a tree reduction approach.

---

<div class="post-metadata">

**Author:** ![jeff.bezanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff.bezanson/32/48_2.png) [@jeff.bezanson](https://discourse.julialang.org/u/jeff.bezanson)\
**Post date:** [May 23, 2019, 2:59am UTC](https://discourse.julialang.org/t/type-stable-threaded-map/24498/7 "2019-05-23T02:59:19Z")

</div>

Ok, in practice the cases you want to be really fast (such that threads are the limiting factor) will probably be homogeneous arrays, so you could also use the type of the first result as the element type and just assume they are all the same.

---

<div class="post-metadata">

**Author:** ![sylvaticus](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sylvaticus/32/203883_2.png) [@sylvaticus](https://discourse.julialang.org/u/sylvaticus)\
**Post date:** [June 18, 2019, 11:11am UTC](https://discourse.julialang.org/t/type-stable-threaded-map/24498/8 "2019-06-18T11:11:59Z")

</div>

Hello, is this related (`map` type-stable but `pmap` not) ?

```julia
julia> using BenchmarkTools
julia> using Distributed
julia> a = rand(1:35,100)
julia> addprocs(3)
julia> @everywhere function fib(n)
         if n == 0 return 0 end
         if n == 1 return 1 end
         return fib(n-1) + fib(n-2)
       end
julia> @code_warntype fib(35) # Body::Int64
julia> @code_warntype map(fib,a)
Body::Array{Int64,1}
1 ─ %1 = %new(Base.Generator{Array{Int64,1},typeof(fib)}, fib, A)::Base.Generator{Array{Int64,1},typeof(fib)}
│ %2 = invoke Base._collect(_3::Array{Int64,1}, %1::Base.Generator{Array{Int64,1},typeof(fib)}, $(QuoteNode(Base.EltypeUnknown()))::Base.EltypeUnknown, $(QuoteNode(Base.HasShape{1}()))::Base.HasShape{1})::Array{Int64,1}
└── return %2
julia> @code_warntype pmap(fib,a)
Body::Any
1 ─ %1 = invoke Distributed.default_worker_pool()::Union{Nothing, WorkerPool}
│ %2 = Distributed.pmap::typeof(pmap)
│ %3 = (isa)(%1, WorkerPool)::Bool
└── goto #3 if not %3
2 ─ %5 = π (%1, WorkerPool)
│ %6 = invoke %2(_2::Function, %5::WorkerPool, _3::Array{Int64,1})::Any
└── goto #6
3 ─ %8 = (isa)(%1, Nothing)::Bool
└── goto #5 if not %8
4 ─ %10 = invoke Distributed.:(#pmap#226)($(QuoteNode(Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}()))::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, Distributed.pmap::Function, fib::Function, nothing::Nothing, _3::Array{Int64,1})::Any
└── goto #6
5 ─ (Core.throw)(ErrorException("fatal error in type inference (type bound)"))
└── $(Expr(:unreachable))
6 ┄ %14 = φ (#2 => %6, #4 => %10)::Any
└── goto #7
7 ─ return %14

```

From [this S.O. question](https://stackoverflow.com/questions/56633458).

---

<div class="post-metadata">

**Author:** ![dstarerstor](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dstarerstor/32/8958_2.png) [@dstarerstor](https://discourse.julialang.org/u/dstarerstor)\
**Post date:** [August 20, 2019, 3:20pm UTC](https://discourse.julialang.org/t/type-stable-threaded-map/24498/9 "2019-08-20T15:20:35Z")

</div>

With Julia 1.3, I’ve been using this:

```julia
function tmap(op, lst)
    refs = [@spawn(op(itm)) for itm in lst]
    return fetch.(refs)
end

function tmapreduce(op, red, lst)
    refs = [@spawn(op(itm)) for itm in lst]
    result = fetch(refs[1])
    for i = 2:length(lst)
        result = red(result, fetch(refs[i]))
    end
    return result
end

```

Its definitely not ideal, but It works very well, and I’m getting ~3-4x speedup from map() and mapreduce().

Maybe someone has an idea on how to improve easily? I tried dividing the work into batches and `@spawn mapreduce()`, but it was actually slower for my simple case.

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [August 20, 2019, 7:44pm UTC](https://discourse.julialang.org/t/type-stable-threaded-map/24498/10 "2019-08-20T19:44:58Z")

</div>

In Transducers.jl `master` you can do

```julia
using Transducers
using BangBang
using StaticArrays

tmap(f, xs) = reduce(append!!, Map(x -> SVector(f(x))), xs; init=Union{}[])

```

to implement threaded map using mutate-or-widen strategy.