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]
> <javascript:>> 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?
>>
>
