Segmentation fault when using sortperm with lt=!isless

[ronisbr]

Hi guys!

I tried to get the indexes to sort an array in descending order using:

idx = sortperm(k; lt=!isless)

However, when I use the following array:

k = [38, 18, 38, 38, 3, 37, 26, 26, 6, 29, 38, 36, 38, 1, 38, 36, 38, 38, 38, 36, 36, 36, 28, 34, 35, 38, 25, 20, 38, 1, 1, 5, 38, 38, 3, 34, 16, 38, 4, 10, 35, 37, 38, 38, 2, 38, 25, 35, 38, 1, 35, 36, 20, 33, 36, 18, 38, 1, 24, 4, 38, 18, 12, 38, 34, 35, 36, 38, 26, 31, 36, 38, 38, 30, 36, 35, 35, 7, 22, 35, 38, 35, 30, 21, 37]

I get sometimes a segmentation fault because it is trying to access the position -5:

julia> k = [38, 18, 38, 38, 3, 37, 26, 26, 6, 29, 38, 36, 38, 1, 38, 36, 38, 38, 38, 36, 36, 36, 28, 34, 35, 38, 25, 20, 38, 1, 1, 5, 38, 38, 3, 34, 16, 38, 4, 10, 35, 37, 38, 38, 2, 38, 25, 35, 38, 1, 35, 36, 20, 33, 36, 18, 38, 1, 24, 4, 38, 18, 12, 38, 34, 35, 36, 38, 26, 31, 36, 38, 38, 30, 36, 35, 35, 7, 22, 35, 38, 35, 30, 21, 37];

julia> idx = sortperm(k; lt=!isless)
ERROR: BoundsError: attempt to access 85-element Array{Int64,1} at index [-5]
Stacktrace:
 [1] getindex at ./array.jl:729 [inlined]
 [2] partition!(::Array{Int64,1}, ::Int64, ::Int64, ::Base.Order.Perm{Base.Order.Lt{getfield(Base, Symbol("##58#59")){typeof(isless)}},Array{Int64,1}}) at ./sort.jl:512
 [3] sort!(::Array{Int64,1}, ::Int64, ::Int64, ::Base.Sort.QuickSortAlg, ::Base.Order.Perm{Base.Order.Lt{getfield(Base, Symbol("##58#59")){typeof(isless)}},Array{Int64,1}}) at ./sort.jl:523
 [4] sort!(::Array{Int64,1}, ::Base.Sort.QuickSortAlg, ::Base.Order.Perm{Base.Order.Lt{getfield(Base, Symbol("##58#59")){typeof(isless)}},Array{Int64,1}}) at ./sort.jl:634
 [5] #sortperm#11(::Base.Sort.QuickSortAlg, ::Function, ::Function, ::Nothing, ::Base.Order.ForwardOrdering, ::Function, ::Array{Int64,1}) at ./sort.jl:856
 [6] (::getfield(Base, Symbol("#kw##sortperm")))(::NamedTuple{(:lt,),Tuple{getfield(Base, Symbol("##58#59")){typeof(isless)}}}, ::typeof(sortperm), ::Array{Int64,1}) at ./none:0
 [7] top-level scope at none:0

[ronisbr]

Notice that I think I know why this is happening. Maybe it is because the !isless returns true if the values are equal, which does not happen with isless. However, I think that a segmentation fault should not happen. Am I right?

[sostock]

Note that you can use the rev keyword to sort in descending order:

sortperm(k; rev=true)

One could add to the documentation that the function supplied via the lt keyword must implement a strict total order (which !isless doesn’t), otherwise unexpected behavior may occur.

Of course, if this leads to a segfault, it should probably be fixed regardless.

[sostock]

I can confirm that this occasionally segfaults on 1.0.4, 1.1.1, and master:

julia> k = [38, 18, 38, 38, 3, 37, 26, 26, 6, 29, 38, 36, 38, 1, 38, 36, 38, 38, 38, 36, 36, 36, 28, 34, 35, 38, 25, 20, 38, 1, 1, 5, 38, 38, 3, 34, 16, 38, 4, 10, 35, 37, 38, 38, 2, 38, 25, 35, 38, 1, 35, 36, 20, 33, 36, 18, 38, 1, 24, 4, 38, 18, 12, 38, 34, 35, 36, 38, 26, 31, 36, 38, 38, 30, 36, 35, 35, 7, 22, 35, 38, 35, 30, 21, 37];

julia> idx = sortperm(k; lt=!isless)
ERROR: BoundsError: attempt to access 85-element Array{Int64,1} at index [-5]
[…]

julia> idx = sortperm(k; lt=!isless)

signal (11): Segmentation fault
in expression starting at REPL[2]:1
getindex at ./array.jl:742 [inlined]
partition! at ./sort.jl:521
sort! at ./sort.jl:536
sort! at ./sort.jl:643
#sortperm#11 at ./sort.jl:865
#sortperm at ./none:0
jl_apply at /home/sebastian/Development/julia/src/julia.h:1630 [inlined]
do_call at /home/sebastian/Development/julia/src/interpreter.c:328
eval_value at /home/sebastian/Development/julia/src/interpreter.c:417
eval_stmt_value at /home/sebastian/Development/julia/src/interpreter.c:368 [inlined]
eval_body at /home/sebastian/Development/julia/src/interpreter.c:760
jl_interpret_toplevel_thunk_callback at /home/sebastian/Development/julia/src/interpreter.c:888
unknown function (ip: 0xfffffffffffffffe)
unknown function (ip: 0x7f8e03e3008f)
unknown function (ip: 0x5)
jl_interpret_toplevel_thunk at /home/sebastian/Development/julia/src/interpreter.c:897
jl_toplevel_eval_flex at /home/sebastian/Development/julia/src/toplevel.c:814
jl_toplevel_eval_flex at /home/sebastian/Development/julia/src/toplevel.c:764
jl_toplevel_eval_in at /home/sebastian/Development/julia/src/toplevel.c:843
eval at ./boot.jl:330
eval_user_input at /home/sebastian/Development/julia/usr/share/julia/stdlib/v1.3/REPL/src/REPL.jl:86
macro expansion at /home/sebastian/Development/julia/usr/share/julia/stdlib/v1.3/REPL/src/REPL.jl:118 [inlined]
#26 at ./task.jl:292
jl_apply at /home/sebastian/Development/julia/src/julia.h:1630 [inlined]
start_task at /home/sebastian/Development/julia/src/task.c:604
unknown function (ip: 0xffffffffffffffff)
Allocations: 2687719 (Pool: 2687036; Big: 683); GC: 3
zsh: segmentation fault (core dumped)  ./julia

[ronisbr]

I think that one possible way to fix that is to call the function lt like lt(v[1],v[1]). Thus, if this return true, then we throw an error. Is it too hacky ?