JuliaArrays / OffsetArrays.jl

Fortran-like arrays with arbitrary, zero or negative starting indices.
Other
195 stars 40 forks source link

Reduce invalidation by not specializing lastindex/axes1 #311

Closed jishnub closed 1 year ago

jishnub commented 1 year ago

I don't see any speedup from specializing these on recent Julia versions, and this PR reduces invalidation. On master (Julia v1.8.2)

julia> r = OffsetArrays.IdOffsetRange(3:10000);

julia> @btime firstindex($(Ref(r))[]);
  2.935 ns (0 allocations: 0 bytes)

julia> @btime lastindex($(Ref(r))[]);
  3.354 ns (0 allocations: 0 bytes)

This PR

julia> @btime firstindex($(Ref(r))[]);
  2.935 ns (0 allocations: 0 bytes)

julia> @btime lastindex($(Ref(r))[]);
  2.942 ns (0 allocations: 0 bytes)

Similarly, for axes1. On Julia v1.9, and using the master branch for OffsetArrays:

julia> using SnoopCompileCore

julia> invalidations = @snoopr using OffsetArrays;

julia> using SnoopCompile

julia> trees = invalidation_trees(invalidations)
3-element Vector{SnoopCompile.MethodInvalidations}:
 inserting similar(::Type{T}, shape::Tuple{Union{Integer, AbstractUnitRange}, Vararg{Union{Integer, AbstractUnitRange}}}) where T<:AbstractArray @ OffsetArrays ~/Dropbox/JuliaPackages/OffsetArrays.jl/src/OffsetArrays.jl:331 invalidated:
   mt_backedges: 1: signature Tuple{typeof(similar), Type{Array{Union{Int64, Symbol}, _A}} where _A, Tuple{Union{Integer, AbstractUnitRange}}} triggered MethodInstance for similar(::Type{Array{Union{Int64, Symbol}, _A}}, ::Union{Integer, AbstractUnitRange}) where _A (0 children)
                 2: signature Tuple{typeof(similar), Type{Array{Base.PkgId, _A}} where _A, Tuple{Union{Integer, AbstractUnitRange}}} triggered MethodInstance for similar(::Type{Array{Base.PkgId, _A}}, ::Union{Integer, AbstractUnitRange}) where _A (0 children)

 inserting lastindex(r::OffsetArrays.IdOffsetRange) @ OffsetArrays ~/Dropbox/JuliaPackages/OffsetArrays.jl/src/axes.jl:192 invalidated:
   backedges: 1: superseding lastindex(a::AbstractArray) @ Base abstractarray.jl:411 with MethodInstance for lastindex(::AbstractVector) (4 children)
   3 mt_cache

 inserting axes1(r::OffsetArrays.IdOffsetRange) @ OffsetArrays ~/Dropbox/JuliaPackages/OffsetArrays.jl/src/axes.jl:174 invalidated:
   backedges: 1: superseding axes1(A::AbstractArray) @ Base abstractarray.jl:133 with MethodInstance for Base.axes1(::AbstractVector{UInt8}) (37 children)

This PR

julia> trees = invalidation_trees(invalidations)
1-element Vector{SnoopCompile.MethodInvalidations}:
 inserting similar(::Type{T}, shape::Tuple{Union{Integer, AbstractUnitRange}, Vararg{Union{Integer, AbstractUnitRange}}}) where T<:AbstractArray @ OffsetArrays ~/Dropbox/JuliaPackages/OffsetArrays.jl/src/OffsetArrays.jl:331 invalidated:
   mt_backedges: 1: signature Tuple{typeof(similar), Type{Array{Union{Int64, Symbol}, _A}} where _A, Tuple{Union{Integer, AbstractUnitRange}}} triggered MethodInstance for similar(::Type{Array{Union{Int64, Symbol}, _A}}, ::Union{Integer, AbstractUnitRange}) where _A (0 children)
                 2: signature Tuple{typeof(similar), Type{Array{Base.PkgId, _A}} where _A, Tuple{Union{Integer, AbstractUnitRange}}} triggered MethodInstance for similar(::Type{Array{Base.PkgId, _A}}, ::Union{Integer, AbstractUnitRange}) where _A (0 children)
codecov[bot] commented 1 year ago

Codecov Report

Merging #311 (fa09c29) into master (13c13f9) will increase coverage by 0.00%. The diff coverage is 100.00%.

@@           Coverage Diff           @@
##           master     #311   +/-   ##
=======================================
  Coverage   96.44%   96.45%           
=======================================
  Files           5        5           
  Lines         450      451    +1     
=======================================
+ Hits          434      435    +1     
  Misses         16       16           
Impacted Files Coverage Δ
src/axes.jl 100.00% <100.00%> (ø)

:mega: We’re building smart automated test selection to slash your CI/CD build times. Learn more

jishnub commented 1 year ago

We may reduce another set of invalidation by not specializing Base.axes1 for IdOffsetRange, which seems redundant as well on recent Julia versions.