In the case of dedup_sorted, the generated code for both types is fine and
the code for f() shows dedup_sorted being called with the correct type in
both cases. Is there any way to check whether the function actually gets
specialised?
On Tuesday, 29 December 2015 14:51:51 UTC, Jamie Brandon wrote:
>
> Adding the type parameter does indeed do the trick. I wasn't aware that
> there were cases where the compiler wouldn't specialise, but it makes sense.
>
> (I used Val{T} instead of Val{T}() because the docs at
> http://docs.julialang.org/en/release-0.4/manual/types/ say "For
> consistency across Julia, the call site should always pass a Val type
> rather than creating an instance.")
>
> Replacing the Val with a tuple works in this case because all the types in
> the example are Int64, but if I try eg
>
> @code_warntype reshape(
> Vector{Tuple{Int64, Float64, Int64}}(0),
> Vector{Tuple{Int64, Float64}}(0),
> (1, 2),
> )
>
> then I can see it boxing again, because without knowing the actual index
> numbers at compile time it can't prove that the types line up. That's fine
> though, I'm happy using Val.
>
> I noticed a similar problem though with sort:
>
> f() = begin
> xs = [(a,b,c) for (a,b,c) in zip(ids(), ids(), ids())]
> @time sort!(xs, alg=QuickSort) 0.215447 seconds (1 allocation: 80
> bytes)
> end
>
> f() = begin
> xs = [(a,b,Float64(c)) for (a,b,c) in zip(ids(), ids(), ids())]
> @time sort!(xs, alg=QuickSort) # 2.563458 seconds (91.95 M
> allocations: 2.055 GB, 13.40% gc time)
> end
>
> If I make my own immutable type instead of using tuples then it works fine
> in both cases. I'm seeing similar behaviour in some of my own code too.
>
> dedup_sorted{X}(xs::Vector{X}) = begin
> ys = Vector{X}(0)
> last = xs[1]
> push!(ys, last)
> for x in xs
> if x != last
> push!(ys, x)
> last = x
> end
> end
> xs
> end
>
> f() = begin
> xs = [(a,b,c) for (a,b,c) in zip(ids(), ids(), ids())]
> sort!(xs, alg=QuickSort)
> @time dedup_sorted(xs) # 0.020497 seconds (20 allocations: 25.500 MB)
> end
>
> f() = begin
> xs = [(a,b,Float64(c)) for (a,b,c) in zip(ids(), ids(), ids())]
> sort!(xs, alg=QuickSort)
> @time dedup_sorted(xs) # 0.137487 seconds (5.47 M allocations: 138.703
> MB, 16.06% gc time)
> end
>
> Again, it works fine if I make my own immutable type types. Is this the
> same kind of heuristic at work? Is it reluctant to specialise on tuples
> with complex types?
>
> On Tuesday, 29 December 2015 10:12:21 UTC, Mike Innes wrote:
>>
>> I think this is down to Julia avoiding specialisation on the `ykey` type
>> in `reshape`, which sometime happens if it's (heuristically) determined
>> that doing so will prevent large amounts of unnecessary code being
>> generated. You can always force specialisation with a type parameter:
>>
>> reshape{T}(xs, ys, ykey::Type{Val{T}}) = begin
>>
>> However, this is unnecessary if you make the types simpler. Changing
>> `::Type{Val{T}}` to `::Val{T}` and `Val{T}` to `Val{(1,3)}()` will do the
>> trick if you want to stick with that approach, but just use a tuple
>> directly:
>>
>> @generated construct(key::Tuple, value) = begin
>> :(begin
>> $(Expr(:meta, :inline))
>> tuple($([:(value[key[$i]]) for i in 1:length(key.parameters)]...))
>> end)
>> end
>>
>> reshape(xs, ys, ykey) = begin
>> for x in xs
>> push!(ys, construct(ykey, x))
>> end
>> return ys
>> end
>>
>> reshape([(10,11,12),(13,14,15)],NTuple{2,Int}[],(1,3))
>>
>> Above: 0.021351 seconds (500.00 k allocations: 30.518 MB, 17.76% gc time)
>> Type{Val{T}} reshape2: 0.021599 seconds (500.00 k allocations: 30.518 MB,
>> 19.60% gc time)
>>
>>
>> On Tue, 29 Dec 2015 at 07:16 Jamie Brandon <[email protected]>
>> wrote:
>>
>>> I have two versions of this reshape function -
>>> https://gist.github.com/jamii/62b3c3695fba95f3f09b
>>>
>>> The produce near-identical ast from code_warntype -
>>> https://www.diffchecker.com/awnv9zvv
>>>
>>> But code_lowered shows that reshape naively boxes tuples whereas
>>> reshape2 does something much more complicated -
>>> https://www.diffchecker.com/jb6aurpl
>>>
>>> The result is that reshape2 is much faster:
>>>
>>> reshape: 0.316513 seconds (2.00 M allocations: 95.036 MB, 5.41% gc time)
>>> reshape2: 0.218963 seconds (41 allocations: 34.001 MB, 0.85% gc time)
>>>
>>> What's going on? How can I make reshape avoid boxing?
>>>
>>
