Unrolled.jl invalidates quite a lot

[ranocha]

Thirst of all, thanks for the nice package! I get the following result with Julia v1.8:

julia> using Pkg; Pkg.activate(temp=true); Pkg.add("Unrolled")
  Activating new project at `/tmp/jl_n64URx`
    Updating registry at `~/.julia/registries/General.toml`
   Resolving package versions...
    Updating `/tmp/jl_n64URx/Project.toml`
  [9602ed7d] + Unrolled v0.1.3
    Updating `/tmp/jl_n64URx/Manifest.toml`
  [1914dd2f] + MacroTools v0.5.9
  [9602ed7d] + Unrolled v0.1.3
  [2a0f44e3] + Base64
  [b77e0a4c] + InteractiveUtils
  [56ddb016] + Logging
  [d6f4376e] + Markdown
  [9a3f8284] + Random
  [ea8e919c] + SHA v0.7.0
  [9e88b42a] + Serialization
  [8dfed614] + Test

julia> using SnoopCompileCore; invalidations = @snoopr(using Unrolled); using SnoopCompile

julia> trees = invalidation_trees(invalidations);

julia> length(uinvalidated(invalidations))
795

julia> trees
1-element Vector{SnoopCompile.MethodInvalidations}:
 inserting getindex(seq, ::FixedRange{A, B}) where {A, B} in Unrolled at /home/hendrik/.julia/packages/Unrolled/26uDc/src/range.jl:23 invalidated:
   mt_backedges: 1: signature Tuple{typeof(getindex), Base.Broadcast.Broadcasted, Any} triggered MethodInstance for Base.Broadcast.copyto_nonleaf!(::Array, ::Base.Broadcast.Broadcasted, ::Base.OneTo, ::Int64, ::Int64) (0 children)
                 2: signature Tuple{typeof(getindex), Base.Broadcast.Broadcasted, Any} triggered MethodInstance for Base.Broadcast.copyto_nonleaf!(::BitArray, ::Base.Broadcast.Broadcasted, ::Base.OneTo, ::Int64, ::Int64) (0 children)
                 3: signature Tuple{typeof(getindex), Base.Broadcast.Broadcasted, Any} triggered MethodInstance for Base.Broadcast.copyto_nonleaf!(::Any, ::Base.Broadcast.Broadcasted, ::Base.OneTo, ::Any, ::Int64) (93 children)
   backedges: 1: superseding getindex(wkh::WeakKeyDict{K}, key) where K in Base at weakkeydict.jl:185 with MethodInstance for getindex(::WeakKeyDict{Any, Any}, ::Any) (1 children)
              2: superseding getindex(::Type{Any}, vals...) in Base at array.jl:419 with MethodInstance for getindex(::Type{Any}, ::Vararg{Any}) (2 children)
              3: superseding getindex(h::Dict{K, V}, key) where {K, V} in Base at dict.jl:496 with MethodInstance for getindex(::Dict{String, Set{String}}, ::Any) (10 children)
              4: superseding getindex(::Type{T}, vals...) where T in Base at array.jl:403 with MethodInstance for getindex(::Type{String}, ::Any) (51 children)
              5: superseding getindex(d::IdDict{K, V}, key) where {K, V} in Base at iddict.jl:106 with MethodInstance for getindex(::IdDict{Any, Any}, ::Any) (175 children)
              6: superseding getindex(::Type{Any}, vals...) in Base at array.jl:419 with MethodInstance for getindex(::Type{Any}, ::Any) (903 children)
   7 mt_cache

It would be great to fix these invalidations. However, I am not sure what the best approach would be. Any suggestions?

[ranocha]

After looking a bit at the code, I couldn't find a usage of anything in range.jl in the remaining part of Unrolled.jl. Moreover,

export FixedRange, FixedEnd, @fixed_range

are not documented. Can range.jl just be removed completely?

[cstjean]

Maybe try this:

Base.getindex(seq, fr::FixedRange{A, B}) where {A, B} = _getindex(seq, fr)::NTuple{B-A+1, etlype(seq))

@generated _getindex(seq, ::FixedRange{A, B}) where {A, B} =
    :(tuple($((:(seq[$i]) for i in replace_end(A, seq):replace_end(B, seq))...)))

@fixed_range isn't documented in Unrolled per se, but I've used it before, and wouldn't be super happy to delete it in the name of invalidation...

[cstjean]

At least, not without trying to fix things otherwise!

[ranocha]

With the change you suggested, I get

julia> using Pkg; Pkg.activate(temp=true); Pkg.develop("Unrolled")
  Activating new project at `/tmp/jl_dG09sW`
   Resolving package versions...
    Updating `/tmp/jl_dG09sW/Project.toml`
  [9602ed7d] + Unrolled v0.0.0 `~/.julia/dev/Unrolled`
    Updating `/tmp/jl_dG09sW/Manifest.toml`
  [1914dd2f] + MacroTools v0.5.9
  [9602ed7d] + Unrolled v0.0.0 `~/.julia/dev/Unrolled`
  [2a0f44e3] + Base64
  [d6f4376e] + Markdown
  [9a3f8284] + Random
  [ea8e919c] + SHA v0.7.0
  [9e88b42a] + Serialization

julia> using SnoopCompileCore; invalidations = @snoopr(using Unrolled); using SnoopCompile

julia> trees = invalidation_trees(invalidations);

julia> length(uinvalidated(invalidations))
784

julia> trees
1-element Vector{SnoopCompile.MethodInvalidations}:
 inserting getindex(seq, fr::FixedRange{A, B}) where {A, B} in Unrolled at ~/.julia/dev/Unrolled/src/range.jl:23 invalidated:
   mt_backedges: 1: signature Tuple{typeof(getindex), Base.Broadcast.Broadcasted, Any} triggered MethodInstance for Base.Broadcast.copyto_nonleaf!(::Array, ::Base.Broadcast.Broadcasted, ::Base.OneTo, ::Int64, ::Int64) (0 children)
                 2: signature Tuple{typeof(getindex), Base.Broadcast.Broadcasted, Any} triggered MethodInstance for Base.Broadcast.copyto_nonleaf!(::BitArray, ::Base.Broadcast.Broadcasted, ::Base.OneTo, ::Int64, ::Int64) (0 children)
                 3: signature Tuple{typeof(getindex), Base.Broadcast.Broadcasted, Any} triggered MethodInstance for Base.Broadcast.copyto_nonleaf!(::Any, ::Base.Broadcast.Broadcasted, ::Base.OneTo, ::Any, ::Int64) (97 children)
   backedges: 1: superseding getindex(wkh::WeakKeyDict{K}, key) where K in Base at weakkeydict.jl:185 with MethodInstance for getindex(::WeakKeyDict{Any, Any}, ::Any) (1 children)
              2: superseding getindex(::Type{Any}, vals...) in Base at array.jl:419 with MethodInstance for getindex(::Type{Any}, ::Vararg{Any}) (2 children)
              3: superseding getindex(h::Dict{K, V}, key) where {K, V} in Base at dict.jl:496 with MethodInstance for getindex(::Dict{String, Set{String}}, ::Any) (10 children)
              4: superseding getindex(::Type{T}, vals...) where T in Base at array.jl:403 with MethodInstance for getindex(::Type{String}, ::Any) (45 children)
              5: superseding getindex(d::IdDict{K, V}, key) where {K, V} in Base at iddict.jl:106 with MethodInstance for getindex(::IdDict{Any, Any}, ::Any) (174 children)
              6: superseding getindex(::Type{Any}, vals...) in Base at array.jl:419 with MethodInstance for getindex(::Type{Any}, ::Any) (890 children)
   7 mt_cache

on Julia v1.8. Thus, it looks a bit better but not much.

[ranocha]

I will have a deeper look at the invalidations. Maybe there is some other way to fix them.

[ranocha]

Can you somehow restrict seq in Base.getindex(seq, fr::FixedRange)? Some problem occur because of something like

Any[some_variable_only_inferred_to_any]

[ranocha]

Looking at the code, I guess you may be fine with tuples and abstract arrays for seq? Or do you need anything else?