Sortperm with keyword lt = !isless throws BoundsError

Does this happen to any of you too?
Do you have any idea why?

sortperm(rand(1:10,10))  # ok
sortperm(rand(1:10,10^2))  # ok
sortperm(rand(1:10,10^7))  # ok

sortperm(rand(1:10,10), lt= >=) #ok
sortperm(rand(1:10,10^2), lt= >=) #ok or sometime crashes language server
sortperm(rand(1:10,10^3), lt= >=) # crashes language server

what i get sometimes using Julia directly not in vscode

   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.8.3 (2022-11-14)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> sortperm(rand(1:10,10^3), lt= >=)
ERROR: BoundsError: attempt to access 1000-element Vector{Int64} at index [-5]
Stacktrace:
 [1] getindex
   @ .\array.jl:924 [inlined]
 [2] partition!(v::Vector{Int64}, lo::Int64, hi::Int64, o::Base.Order.Perm{Base.Order.Lt{Base.Order.var"#1#3"{typeof(>=), typeof(identity)}}, Vector{Int64}})
   @ Base.Sort .\sort.jl:561
 [3] sort!(v::Vector{Int64}, lo::Int64, hi::Int64, a::Base.Sort.QuickSortAlg, o::Base.Order.Perm{Base.Order.Lt{Base.Order.var"#1#3"{typeof(>=), typeof(identity)}}, Vector{Int64}})
   @ Base.Sort .\sort.jl:572
 [4] sort!(v::Vector{Int64}, lo::Int64, hi::Int64, a::Base.Sort.QuickSortAlg, o::Base.Order.Perm{Base.Order.Lt{Base.Order.var"#1#3"{typeof(>=), typeof(identity)}}, Vector{Int64}}) (repeats 2 times)
   @ Base.Sort .\sort.jl:577
 [5] sort!(v::Vector{Int64}, alg::Base.Sort.QuickSortAlg, order::Base.Order.Perm{Base.Order.Lt{Base.Order.var"#1#3"{typeof(>=), typeof(identity)}}, Vector{Int64}})
   @ Base.Sort .\sort.jl:661
 [6] sortperm(v::Vector{Int64}; alg::Base.Sort.QuickSortAlg, lt::Function, by::Function, rev::Nothing, order::Base.Order.ForwardOrdering)
   @ Base.Sort .\sort.jl:927
 [7] top-level scope
   @ REPL[1]:1

julia>
3 Likes

I can reproduce.

Interestingly, this seems to crash every Julia version all the way back to Julia 0.4. However, in Julia 0.3 it throws a BoundsError exception.

I filed an issue: sortperm segfaults with lt=(>=) ¡ Issue #48172 ¡ JuliaLang/julia ¡ GitHub

1 Like

No issues with:

sortperm(rand(1:10,10^3), lt= >=)

on Win 11 Julia Version 1.9.0-beta2

try this, also for values grater than 22

julia> bget22=repeat([1],22);

julia> 

julia> sort(bget22, lt=(>=))
ERROR: BoundsError: attempt to access 22-element Vector{Int64} at index [0]
Julia 1.8.0 - crashes
julia> versioninfo()
Julia Version 1.8.0
Commit 5544a0fab7 (2022-08-17 13:38 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 20 × 12th Gen Intel(R) Core(TM) i9-12900HK
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-13.0.1 (ORCJIT, goldmont)
  Threads: 1 on 20 virtual cores

julia> sortperm(rand(1:10,10^3), lt= >=)

Please submit a bug report with steps to reproduce this fault, and any error messages that follow (in their entirety). Thanks.
Exception: EXCEPTION_ACCESS_VIOLATION at 0x614cdf98 -- getindex at .\array.jl:924 [inlined]
lt at .\ordering.jl:123 [inlined]
partition! at .\sort.jl:555
in expression starting at REPL[13]:1
getindex at .\array.jl:924 [inlined]
lt at .\ordering.jl:123 [inlined]
partition! at .\sort.jl:555
sort! at .\sort.jl:571
sort! at .\sort.jl:579
sort! at .\sort.jl:660
unknown function (ip: 00000000614ce334)
#sortperm#12 at .\sort.jl:926
sortperm##kw at .\sort.jl:903
jl_apply at /cygdrive/c/buildbot/worker/package_win64/build/src\julia.h:1838 [inlined]
do_call at /cygdrive/c/buildbot/worker/package_win64/build/src\interpreter.c:126
eval_value at /cygdrive/c/buildbot/worker/package_win64/build/src\interpreter.c:215
eval_stmt_value at /cygdrive/c/buildbot/worker/package_win64/build/src\interpreter.c:166 [inlined]
eval_body at /cygdrive/c/buildbot/worker/package_win64/build/src\interpreter.c:594
jl_interpret_toplevel_thunk at /cygdrive/c/buildbot/worker/package_win64/build/src\interpreter.c:750
jl_toplevel_eval_flex at /cygdrive/c/buildbot/worker/package_win64/build/src\toplevel.c:906
jl_toplevel_eval_flex at /cygdrive/c/buildbot/worker/package_win64/build/src\toplevel.c:850
ijl_toplevel_eval at /cygdrive/c/buildbot/worker/package_win64/build/src\toplevel.c:915 [inlined]
ijl_toplevel_eval_in at /cygdrive/c/buildbot/worker/package_win64/build/src\toplevel.c:965
eval at .\boot.jl:368 [inlined]
eval_user_input at C:\buildbot\worker\package_win64\build\usr\share\julia\stdlib\v1.8\REPL\src\REPL.jl:151
repl_backend_loop at C:\buildbot\worker\package_win64\build\usr\share\julia\stdlib\v1.8\REPL\src\REPL.jl:247
start_repl_backend at C:\buildbot\worker\package_win64\build\usr\share\julia\stdlib\v1.8\REPL\src\REPL.jl:232
#run_repl#47 at C:\buildbot\worker\package_win64\build\usr\share\julia\stdlib\v1.8\REPL\src\REPL.jl:369
run_repl at C:\buildbot\worker\package_win64\build\usr\share\julia\stdlib\v1.8\REPL\src\REPL.jl:355
jfptr_run_repl_69828.clone_1 at C:\Users\unime\AppData\Local\Programs\Julia-1.8.0\lib\julia\sys.dll (unknown line)
#966 at .\client.jl:419
jfptr_YY.966_58133.clone_1 at C:\Users\unime\AppData\Local\Programs\Julia-1.8.0\lib\julia\sys.dll (unknown line)
jl_apply at /cygdrive/c/buildbot/worker/package_win64/build/src\julia.h:1838 [inlined]
jl_f__call_latest at /cygdrive/c/buildbot/worker/package_win64/build/src\builtins.c:774
#invokelatest#2 at .\essentials.jl:729 [inlined]
invokelatest at .\essentials.jl:726 [inlined]
run_main_repl at .\client.jl:404
exec_options at .\client.jl:318
_start at .\client.jl:522
jfptr__start_57488.clone_1 at C:\Users\unime\AppData\Local\Programs\Julia-1.8.0\lib\julia\sys.dll (unknown line)
jl_apply at /cygdrive/c/buildbot/worker/package_win64/build/src\julia.h:1838 [inlined]
true_main at /cygdrive/c/buildbot/worker/package_win64/build/src\jlapi.c:575
jl_repl_entrypoint at /cygdrive/c/buildbot/worker/package_win64/build/src\jlapi.c:719
mainCRTStartup at /cygdrive/c/buildbot/worker/package_win64/build/cli\loader_exe.c:59
BaseThreadInitThunk at C:\WINDOWS\System32\KERNEL32.DLL (unknown line)
RtlUserThreadStart at C:\WINDOWS\SYSTEM32\ntdll.dll (unknown line)
Allocations: 3406323 (Pool: 3404487; Big: 1836); GC: 4

process killed

Julia 1.8.3 - crashes
julia> sortperm(rand(1:10,10^3), lt= >=)
ERROR: BoundsError: attempt to access 1000-element Vector{Int64} at index [-5]
Stacktrace:
 [1] getindex
   @ .\array.jl:924 [inlined]
 [2] partition!(v::Vector{Int64}, lo::Int64, hi::Int64, o::Base.Order.Perm{Base.Order.Lt{Base.Order.var"#1#3"{typeof(>=), typeof(identity)}}, Vector{Int64}})
   @ Base.Sort .\sort.jl:561
 [3] sort!(v::Vector{Int64}, lo::Int64, hi::Int64, a::Base.Sort.QuickSortAlg, o::Base.Order.Perm{Base.Order.Lt{Base.Order.var"#1#3"{typeof(>=), typeof(identity)}}, Vector{Int64}})
   @ Base.Sort .\sort.jl:572
 [4] sort!(v::Vector{Int64}, alg::Base.Sort.QuickSortAlg, order::Base.Order.Perm{Base.Order.Lt{Base.Order.var"#1#3"{typeof(>=), typeof(identity)}}, Vector{Int64}})
   @ Base.Sort .\sort.jl:661
 [5] sortperm(v::Vector{Int64}; alg::Base.Sort.QuickSortAlg, lt::Function, by::Function, rev::Nothing, order::Base.Order.ForwardOrdering)
   @ Base.Sort .\sort.jl:927
 [6] top-level scope
   @ REPL[1]:1

julia> versioninfo()
Julia Version 1.8.3
Commit 0434deb161 (2022-11-14 20:14 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 20 × 12th Gen Intel(R) Core(TM) i9-12900HK
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-13.0.1 (ORCJIT, goldmont)
  Threads: 1 on 20 virtual cores

julia> sortperm(rand(1:10,10^3), lt= >=)

Please submit a bug report with steps to reproduce this fault, and any error messages that follow (in their entirety). Thanks.
Exception: EXCEPTION_ACCESS_VIOLATION at 0x1bba6de0ce8 -- getindex at .\array.jl:924 [inlined]
lt at .\ordering.jl:123 [inlined]
partition! at .\sort.jl:556
in expression starting at REPL[2]:1
getindex at .\array.jl:924 [inlined]
lt at .\ordering.jl:123 [inlined]
partition! at .\sort.jl:556
sort! at .\sort.jl:572
sort! at .\sort.jl:580
sort! at .\sort.jl:661
unknown function (ip: 000001bba6de1089)
#sortperm#12 at .\sort.jl:927
sortperm##kw at .\sort.jl:904
jl_apply at C:/workdir/src\julia.h:1839 [inlined]
do_call at C:/workdir/src\interpreter.c:126
eval_value at C:/workdir/src\interpreter.c:215
eval_stmt_value at C:/workdir/src\interpreter.c:166 [inlined]
eval_body at C:/workdir/src\interpreter.c:612
jl_interpret_toplevel_thunk at C:/workdir/src\interpreter.c:750
jl_toplevel_eval_flex at C:/workdir/src\toplevel.c:906
jl_toplevel_eval_flex at C:/workdir/src\toplevel.c:850
ijl_toplevel_eval at C:/workdir/src\toplevel.c:915 [inlined]
ijl_toplevel_eval_in at C:/workdir/src\toplevel.c:965
eval at .\boot.jl:368 [inlined]
eval_user_input at C:\workdir\usr\share\julia\stdlib\v1.8\REPL\src\REPL.jl:151
repl_backend_loop at C:\workdir\usr\share\julia\stdlib\v1.8\REPL\src\REPL.jl:247
start_repl_backend at C:\workdir\usr\share\julia\stdlib\v1.8\REPL\src\REPL.jl:232
#run_repl#47 at C:\workdir\usr\share\julia\stdlib\v1.8\REPL\src\REPL.jl:369
run_repl at C:\workdir\usr\share\julia\stdlib\v1.8\REPL\src\REPL.jl:355
jfptr_run_repl_67122.clone_1 at C:\Users\unime\AppData\Local\Programs\Julia-1.8.3\lib\julia\sys.dll (unknown line)
#967 at .\client.jl:419
jfptr_YY.967_56773.clone_1 at C:\Users\unime\AppData\Local\Programs\Julia-1.8.3\lib\julia\sys.dll (unknown line)
jl_apply at C:/workdir/src\julia.h:1839 [inlined]
jl_f__call_latest at C:/workdir/src\builtins.c:774
#invokelatest#2 at .\essentials.jl:729 [inlined]
invokelatest at .\essentials.jl:726 [inlined]
run_main_repl at .\client.jl:404
exec_options at .\client.jl:318
_start at .\client.jl:522
jfptr__start_36493.clone_1 at C:\Users\unime\AppData\Local\Programs\Julia-1.8.3\lib\julia\sys.dll (unknown line)
jl_apply at C:/workdir/src\julia.h:1839 [inlined]
true_main at C:/workdir/src\jlapi.c:575
jl_repl_entrypoint at C:/workdir/src\jlapi.c:719
mainCRTStartup at C:/workdir/cli\loader_exe.c:59
BaseThreadInitThunk at C:\WINDOWS\System32\KERNEL32.DLL (unknown line)
RtlUserThreadStart at C:\WINDOWS\SYSTEM32\ntdll.dll (unknown line)
Allocations: 2574545 (Pool: 2573238; Big: 1307); GC: 3

throws error first time, killed second

Interestingly, with the MWE in issue #48172, I consistently must run it twice to get a crash; the first time throws an error instead.

Julia 1.9.0-alpha1 - runs fine
julia> versioninfo()
Julia Version 1.9.0-alpha1
Commit 0540f9d739 (2022-11-15 14:37 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 20 × 12th Gen Intel(R) Core(TM) i9-12900HK
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, alderlake)
  Threads: 20 on 20 virtual cores

julia> sortperm(rand(1:10,10^3), lt= >=)
1000-element Vector{Int64}:
 995
 983
 982
 981
 980
 965
 963
 960
 955
 953
 951
 932
 924
   ⋮
 102
  95
  92
  90
  80
  78
  76
  67
  49
  34
  27
   9

julia> a = [10, 9, 8, 9, 7, 1, 3, 10, 4, 5, 5, 4, 6, 10, 10, 2, 2, 2, 8, 9, 1, 2, 8, 6, 7, 10, 1, 3, 5, 10];

julia> sortperm(a, lt=(>=))
30-element Vector{Int64}:
 30
 26
 15
 14
  8
  1
 20
  4
  2
 23
 19
  3
 25
  ⋮
 10
 12
  9
 28
  7
 22
 18
 17
 16
 27
 21
  6

julia> a[sortperm(a, lt=(>=))]
30-element Vector{Int64}:
 10
 10
 10
 10
 10
 10
  9
  9
  9
  8
  8
  8
  7
  ⋮
  5
  4
  4
  3
  3
  2
  2
  2
  2
  1
  1
  1

On Julia 1.9.0-alpha1:

julia> bget22=repeat([1],22);

julia> sort(bget22, lt=(>=))
22-element Vector{Int64}:
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1

julia> bget22=repeat([23],22);

julia> sort(bget22, lt=(>=))
22-element Vector{Int64}:
 23
 23
 23
 23
 23
 23
 23
 23
 23
 23
 23
 23
 23
 23
 23
 23
 23
 23
 23
 23
 23
 23

The problem (or part of it) seems to be in calculating the left end of the pivot for the sort! function.
Is it possible to trace the steps of the calculation via debug in vscode?
how?

Silent crash is a bug, but sort(lt= >=) isn’t expected to work anyway. Docs say:

the lt keyword allows providing a custom “less than” function (note that
for every x and y, only one of lt(x,y) and lt(y,x) can return true

4 Likes

not only crashing silently, but you may end up in a loop that seems to never end

sort!(rand(1:10, 10^7),lt= >=)

In any case, it would be preferable to block unmanaged inputs from code.
And, if possible, give reasons for introducing this limitation, which seems artificial in the context of a sorting function.

I also submit this case to tell where this problem came from.

here I wanted to use the sortperm function to sort the values in descending order as requested by the OP.
Instead of rev=true it occurred to me to use the kwarg lt, which has by default isless. I tried isgreater but it wasn’t defined so I thought !isless or (>=)

1 Like

Perhaps, introduce unsafe_sort which can take a non-pre-vetted order, and the regular sort will work with functions bearing ‘Ordering’ trait?

But writing unsafe_sort would be a pain. Checking order is non-reflexive (lt(x,x) is false) once before sort, might cost little and do away with many such problem cases.