Skip to content

Bug in sorting offset vectors #45568

@LilithHafner

Description

@LilithHafner

This bug was introduced by #45330 which tries to reduce the size of an allocated workspace to only what is needed. If sorting a v::AbstractVector on indices lo:hi, it allocates similar(v, hi) which has indices 1:hi, which may be insufficient if lo < 1. The right answer is to allocate similar(v, lo:hi), but that depends on loading OffsetArrays which does not happen in Base. Instead, we can use the simpler similar(v) to get a workspace that contains all of lo:hi (provided they are in bounds in the original vector).

julia> sort!(OffsetArray(rand(200), -10))
ERROR: InexactError: check_top_bit(UInt64, -9)
Stacktrace:
  [1] throw_inexacterror(f::Symbol, #unused#::Type{UInt64}, val::Int64)
    @ Core ./boot.jl:616
  [2] check_top_bit
    @ ./boot.jl:630 [inlined]
  [3] toUInt64
    @ ./boot.jl:741 [inlined]
  [4] UInt64
    @ ./boot.jl:771 [inlined]
  [5] convert
    @ ./number.jl:7 [inlined]
  [6] setindex!
    @ ./array.jl:959 [inlined]
  [7] radix_sort!(v::Base.ReinterpretArray{UInt64, 1, Float64, OffsetVector{Float64, Vector{Float64}}, false}, lo::Int64, hi::Int64, bits::UInt64, t::Base.ReinterpretArray{UInt64, 1, Float64, Vector{Float64}, false}, chunk_size::UInt8)
    @ Base.Sort ~/.julia/dev/julia_dm/base/sort.jl:699
  [8] radix_sort!
    @ ./sort.jl:685 [inlined]
  [9] sort!(v::OffsetVector{Float64, Vector{Float64}}, lo::Int64, hi::Int64, a::Base.Sort.AdaptiveSort{Base.Sort.QuickSortAlg}, o::Base.Sort.Float.Right, t::Nothing)
    @ Base.Sort ~/.julia/dev/julia_dm/base/sort.jl:859
 [10] fpsort!(v::OffsetVector{Float64, Vector{Float64}}, a::Base.Sort.AdaptiveSort{Base.Sort.QuickSortAlg}, o::Base.Order.ForwardOrdering, t::Nothing)
    @ Base.Sort.Float ~/.julia/dev/julia_dm/base/sort.jl:1541
 [11] sort!
    @ ./sort.jl:1551 [inlined]
 [12] #sort!#8
    @ ./sort.jl:927 [inlined]
 [13] sort!(v::OffsetVector{Float64, Vector{Float64}})
    @ Base.Sort ~/.julia/dev/julia_dm/base/sort.jl:920
 [14] top-level scope
    @ REPL[72]:1

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugIndicates an unexpected problem or unintended behaviorsortingPut things in order

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions