Hi,
This is my first answer here, I'm not an expert on Julia.. Seems tuple is
slow. It's more general,
On my machine this beats Python:
function sort_Pair()
gc(); @time temp = rand(500_000)
gc(); @time temp2 = [Pair(temp[i],i) for i=1:length(temp)]
gc(); @time sort!(temp2); println(typeof(temp2))
end
julia> @time sort_pair()
elapsed time: 0.006823427 seconds (4000088 bytes allocated)
elapsed time: 0.035921609 seconds (31991872 bytes allocated)
elapsed time: 1.975542283 seconds (4000048 bytes allocated)
Array{Pair,1}
elapsed time: 2.20708157 seconds (40892612 bytes allocated, 7.46% gc time)
compared to (or 2.7 sec total in Python):
julia> @time sort_any()
elapsed time: 0.006287604 seconds (4000088 bytes allocated)
elapsed time: 0.047933539 seconds (35991872 bytes allocated)
elapsed time: 5.989875809 seconds (191154832 bytes allocated)
Array{Any,1}
elapsed time: 6.247331383 seconds (231803748 bytes allocated, 2.76% gc time)
I used:
type Pair
x
y
end
import Base.isless
function isless(a, b)
if a.x < b.x
true
elseif a.x == b.x && a.y < b.y
true
else
false
end
end
You can maybe think of a tuple as a type, but I'm not sure where to look
for code for it nor looked into the profiler (use @profile, not @time). A
tuple can of course be a 2-tupel (pair), 3-tuple, etc. And I could change
the function for each case, just not sure how I would make my own type that
would handle n-tuples.. Julia does that and maybe just has to be optimized.
Maybe in 0.4 it is..
Types in Julia are supposed to be abstraction-free, but included tuples
seem to have a 231803748/40892612 = 5.6 times overhead compared to my Pair
judging by the memory allocations.
--
Palli.
On Friday, January 9, 2015 at 10:06:30 AM UTC, Andras Niedermayer wrote:
>
>
>
> The performance of the sort algorithm varies largely with the element type
> of an Array, in an unexpected (at least for me) way. Sorting time is
> ordered like this: Vector{(Any,Any)} < Vector{Any} <
> Vector{(Float64,Int64}). Is this a bug or is this behavior intended? Here's
> the code:
>
> ---
>
> julia> function sort_floatint_tuple()
> temp = rand(500_000)
> temp2 = (Float64,Int64)[(temp[i],i) for i=1:length(temp)]
> sort!(temp2)
> end
> sort_floatint_tuple (generic function with 1 method)
>
> julia> gc(); @time sort_floatint_tuple();
> elapsed time: 5.371570706 seconds (2187115768 bytes allocated, 44.77% gc
> time)
>
> julia> gc(); @time sort_floatint_tuple();
> elapsed time: 7.522759215 seconds (2184593304 bytes allocated, 57.48% gc
> time)
>
> julia> function sort_any_tuple()
> temp = rand(500_000)
> temp2 = (Any,Any)[(temp[i],i) for i=1:length(temp)]
> sort!(temp2)
> end
> sort_any_tuple (generic function with 1 method)
>
> julia> gc(); @time sort_any_tuple();
> elapsed time: 2.705974449 seconds (526135400 bytes allocated, 23.32% gc
> time)
>
> julia> gc(); @time sort_any_tuple();
> elapsed time: 3.215082563 seconds (523241560 bytes allocated, 37.72% gc
> time)
>
> julia> function sort_any()
> temp = rand(500_000)
> temp2 = Any[(temp[i],i) for i=1:length(temp)]
> sort!(temp2)
> end
> sort_any (generic function with 1 method)
>
> julia> gc(); @time sort_any();
> elapsed time: 3.591829528 seconds (231327824 bytes allocated, 6.01% gc
> time)
>
> julia> gc(); @time sort_any();
> elapsed time: 3.932805966 seconds (231203560 bytes allocated, 12.54% gc
> time)
>
> ---
>
>
> Python is much faster here:
> ---
> %timeit temp=np.random.rand(500000); temp2=zip(temp,range(len(temp)));
> temp2.sort()
> 1 loops, best of 3: 1.33 s per loop
>
> ---
>
> PS: Type inference gives Vector{(Float64,Int64)} if I write the for
> comprehension in a function and Vector{(Any,Any)} if I run it outside of a
> function.
>
> PPS: After looking at this in detail, I found out that "sortperm" would
> have been a better option for this. But it is still surprising to me that
> losing type information ((Any,Any) instead of (Float64,Int64)) speeds up
> the code.
>
