Should StaticInt be in Base?

[Tokazama]

Would struct StaticInt{N::Int} <: Integer end be a welcome addition here? Most of what it would involve is found here.

It's helpful to have it specifically be a subtype of Integer so that it can provide optionally static ranges without the user having to worry about explicitly propagating static information from something like SArray or making the dim argument of something like f(A, dim) type stable. There are also times it can reduce the number of unique types generated for trait systems. For example contiguous_axis returns a StaticInt instead of ContiguousAxis{N}. The benefit of having it in base would be better native support, integration, and propagation of types/traits that use StaticInt

I understand there may be some concern that this overextends the intended use of the type system, and instead the focus should be better constant propagation on the compiler side of things so that something like SArray doesn't need this. I'm not sure if the other use cases are also better handled by some future compiler wizardry but I thought I'd at least put it forward.

EDIT:
If we ultimately don't go forward with this because the utility of StaticInt will be replaced with more appropriate compiler optimizations, it would be nice to have some clarity on how that will effect code development moving forward. For example, Base.OneTo indexing another array is explicitly written to only check the upper bound is in bounds. StaticArrays.SOneTo does everything in the type domain so nothing is done at run time. ArrayInterface.OptionallyStaticUnitRange uses Int or StaticInt to potentially allow either of those optimizations. Will optimizations to the compiler allow the same benefits without using type information. In other words, will the compiler turn this line into this line? If that's not an anticipated benefit of compiler work then how do we appropriately approach problems like these without abusing the type system?

@chriselrod is familiar with the StaticInt implementation in Static.jl and may have more to add to the discussion.
I think @timholy at one point expressed some support for this being in base.
@Keno probably has an opinion on whether this will eventually not be useful to maintain in base given more internal development.

[chriselrod]

I understand there may be some concern that this overextends the intended use of the type system, and instead the focus should be better constant propagation on the compiler side of things so that something like SArray doesn't need this. I'm not sure if the other use cases are also better handled by some future compiler wizardry but I thought I'd at least put it forward.

Heavy use of Static.jl was cited as one of the reasons for LoopVectorization.jl's bad compile times.
Currently, LoopVectorization.jl does a lot of its code generation through leveraging Julia's type system (both in dispatches, and in using StaticInt to tell @generated functions inside VectorizationBase what they should be doing), when it'd be better off doing all of its code generation itself.

Given that latency is perhaps the number one problem with Julia, I do think people should be wary of investing too much in this approach, as they're likely to suffer consequences when they take it far.
I am working on getting a replacement to LoopVectorization that avoids these issues and does not use Static.jl.

[cscherrer]

@chriselrod it's important to avoid problems like this, but this approach sounds a little like reinventing the wheel. Since it comes up so often, wouldn't it be better to have a reusable solution, so we don't have to solve each instance independently? I might well be misunderstanding, since I haven't seen details of the replacement you're working on.

[Tokazama]

If the replacement completely removes the need to encode the size at the type level for something like SArray that would certainly be helpful but even then I'm assuming these compiler passes would only apply to specific array operations. We'd still have a bunch of use cases for things like Base.OneTo where we want to optimize on some known information and it is encoded at the type level. Or perhaps even that is solvable with future development?

[chriselrod]

Sorry, to be clear, it's a replacement for LoopVectorization.
What I was trying to warn is, someone going down that road may find themselves rewriting later to avoid these problems.

[AriMKatz]

The replacement is to rewrite in c++ IIUC, right? Presumably we'd like to have whatever it is that makes C++ more amenable to this, In Julia

[chriselrod]

That part (generating Expr or some IR without using the type system to do it) could of course be done in Julia as well.

There's lots of other reasons to favor C++ for this, some more easily addressable (e.g. as poorly as LLVM is documented, it is still much better documented than Julia's compiler) than others (e.g. wanting to run as late as possible in the compiler pipeline, when code is at its cleanest/simplest point).

[Tokazama]

If it's decided this shouldn't be in base I'm hoping to get an idea of where the rest of the community should be going with things like traits and corresponding optimizations. Compiler work is super important but I'm worried about requiring any similar additions in the future to be through the compiler. Perhaps this will change, but that sort of coding seems like it requires a lot of extra knowledge to do right.

[AriMKatz]

The other thing about compiler work is that sometimes it's unclear how to hit the right semantics to get the compiler to optimize stuff, tbecause we don't have static typing or when what we ask of the compiler has outrun the semantics of the language( which were initially co-designed with a much less demanding set of expectations, but now there are GPUs ad, etc )

[AriMKatz]

Also, this isn't strictly necessary, but the nice thing about having things in the type domain is that it helps with correctness

[AriMKatz]

This is also important for things like #43642 and related compiler optimizations.

@Tokazama What about named dimensions or ragged arrays?

xref discussion here https://discourse.julialang.org/t/is-my-understanding-of-julia-correct/76924/33

[Tokazama]

I'm sure there are other collections than dense arrays that could be optimized for some operations and it would be a shame if that could only ever happen in the compiler. If we don't need to worry about static values then it would be great to have named dimensions just be a Symbol and not worry about them at the type level, but I'm still not sure how that would work. How do we go past constant propagation and follow something throughout the entire call graph for optimization?

I'm not saying that using StaticInt solves these problems, but it seems to be a good user facing way of ensuring a value is statically known to the compiler. A lot of use cases of Val can be replaced with a StaticInt, and a proper subtype is helpful in those values propagating through other functions without writing extra code.

[AriMKatz]

Agreed. I highly recommend you check out https://youtu.be/npDCCVIaSVQ to see how a from scratch re-design of array typing solves these issues. I wonder how much we can adapt from that into julia.

There are also the issues of making these arrays play nicely with GPU and AD (and as a bonus, shape checking) , which Dex's type system takes into account

[Tokazama]

That video is pretty interesting and I can see how Julia has similar solutions for some parts (e.g., using eachindex(A) to produce OneTo where we don't need to check for one based indexing). I'm going to update my first comment with some of that in perspective.

[timholy]

It's a tough call. But I guess I fall into the camp of thinking that since it's not yet been made unnecessary by compiler optimizations, it seems to be asking for trouble to trust that it will (soon) be. For that reason, I'd suggest we submit this to Base, and give people until a month or so before the 1.9 feature freeze to implement compiler optimizations that make it unnecessary. If that doesn't happen, then I say we merge it (along with other traits that have been found generically useful).

[Tokazama]

Here's the PR.

[JeffBezanson]

will the compiler turn this line into this line?

I don't think that specifically could happen, since the compiler cannot switch a UnitRange to a OneTo. But, it can constant propagate it:

julia> f() = intersect(1:3, 2:4)

julia> @code_typed f()
CodeInfo(
1 ─     return $(QuoteNode(2:3))
) => UnitRange{Int64}

So I would like to understand better what is needed from the compiler.

[chriselrod]

I often have to resort to @generated, e.g. JuliaArrays/ArrayInterface.jl@d497de8 is the most recent example.
Although that example requires Julia 1.6. It already inferred on 1.7 and 1.8 before the fix, meaning it isn't exactly an example someone from the compiler team can look at to fix.

[chriselrod]

If you do want an example from Julia nightly, ArrayInterface tests are currently failing there:

 dimnames: Error During Test at /home/runner/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:96
  Test threw exception
  Expression: #= /home/runner/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:96 =# @inferred(ArrayInterface.has_dimnames(x)) == true
  return type True does not match inferred return type Union{False, True}
  Stacktrace:
   [1] error(s::String)
     @ Base ./error.jl:35
   [2] macro expansion
     @ /opt/hostedtoolcache/julia/nightly/x64/share/julia/stdlib/v1.9/Test/src/Test.jl:464 [inlined]
   [3] macro expansion
     @ ~/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:96 [inlined]
   [4] macro expansion
     @ /opt/hostedtoolcache/julia/nightly/x64/share/julia/stdlib/v1.9/Test/src/Test.jl:1357 [inlined]
   [5] macro expansion
     @ ~/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:91 [inlined]
   [6] macro expansion
     @ /opt/hostedtoolcache/julia/nightly/x64/share/julia/stdlib/v1.9/Test/src/Test.jl:1357 [inlined]
   [7] top-level scope
     @ ~/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:8
dimnames: Error During Test at /home/runner/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:98
  Test threw exception
  Expression: #= /home/runner/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:98 =# @inferred(ArrayInterface.has_dimnames(ones(2, 2))) == false
  return type False does not match inferred return type Union{False, True}
  Stacktrace:
   [1] error(s::String)
     @ Base ./error.jl:35
   [2] macro expansion
     @ /opt/hostedtoolcache/julia/nightly/x64/share/julia/stdlib/v1.9/Test/src/Test.jl:464 [inlined]
   [3] macro expansion
     @ ~/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:98 [inlined]
   [4] macro expansion
     @ /opt/hostedtoolcache/julia/nightly/x64/share/julia/stdlib/v1.9/Test/src/Test.jl:1357 [inlined]
   [5] macro expansion
     @ ~/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:91 [inlined]
   [6] macro expansion
     @ /opt/hostedtoolcache/julia/nightly/x64/share/julia/stdlib/v1.9/Test/src/Test.jl:1357 [inlined]
   [7] top-level scope
     @ ~/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:8
dimnames: Error During Test at /home/runner/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:99
  Test threw exception
  Expression: #= /home/runner/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:99 =# @inferred(ArrayInterface.has_dimnames(Array{Int, 2})) == false
  return type False does not match inferred return type Union{False, True}
  Stacktrace:
   [1] error(s::String)
     @ Base ./error.jl:35
   [2] macro expansion
     @ /opt/hostedtoolcache/julia/nightly/x64/share/julia/stdlib/v1.9/Test/src/Test.jl:464 [inlined]
   [3] macro expansion
     @ ~/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:99 [inlined]
   [4] macro expansion
     @ /opt/hostedtoolcache/julia/nightly/x64/share/julia/stdlib/v1.9/Test/src/Test.jl:1357 [inlined]
   [5] macro expansion
     @ ~/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:91 [inlined]
   [6] macro expansion
     @ /opt/hostedtoolcache/julia/nightly/x64/share/julia/stdlib/v1.9/Test/src/Test.jl:1357 [inlined]
   [7] top-level scope
     @ ~/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:8
dimnames: Error During Test at /home/runner/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:100
  Test threw exception
  Expression: #= /home/runner/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:100 =# @inferred(ArrayInterface.has_dimnames(typeof(x))) == true
  return type True does not match inferred return type Union{False, True}
  Stacktrace:
   [1] error(s::String)
     @ Base ./error.jl:35
   [2] macro expansion
     @ /opt/hostedtoolcache/julia/nightly/x64/share/julia/stdlib/v1.9/Test/src/Test.jl:464 [inlined]
   [3] macro expansion
     @ ~/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:100 [inlined]
   [4] macro expansion
     @ /opt/hostedtoolcache/julia/nightly/x64/share/julia/stdlib/v1.9/Test/src/Test.jl:1357 [inlined]
   [5] macro expansion
     @ ~/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:91 [inlined]
   [6] macro expansion
     @ /opt/hostedtoolcache/julia/nightly/x64/share/julia/stdlib/v1.9/Test/src/Test.jl:1357 [inlined]
   [7] top-level scope
     @ ~/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:8
dimnames: Error During Test at /home/runner/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:101
  Test threw exception
  Expression: #= /home/runner/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:101 =# @inferred(ArrayInterface.has_dimnames(typeof(view(x, :, 1, :)))) == true
  return type True does not match inferred return type Union{False, True}
  Stacktrace:
   [1] error(s::String)
     @ Base ./error.jl:35
   [2] macro expansion
     @ /opt/hostedtoolcache/julia/nightly/x64/share/julia/stdlib/v1.9/Test/src/Test.jl:464 [inlined]
   [3] macro expansion
     @ ~/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:101 [inlined]
   [4] macro expansion
     @ /opt/hostedtoolcache/julia/nightly/x64/share/julia/stdlib/v1.9/Test/src/Test.jl:1357 [inlined]
   [5] macro expansion
     @ ~/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:91 [inlined]
   [6] macro expansion
     @ /opt/hostedtoolcache/julia/nightly/x64/share/julia/stdlib/v1.9/Test/src/Test.jl:1357 [inlined]
   [7] top-level scope
     @ ~/work/ArrayInterface.jl/ArrayInterface.jl/test/dimensions.jl:8

several of the inference tests are failing there (but pass on Julia 1.6 and 1.7).
Relying on inference/const prop often feels like asking for trouble/heavy maintenance burden due to needing to check and fix things on each new release.
Relying more on StaticInts is worse for compile times (assuming const prop works instead of causing inference failures that'd then make not using StaticInt worse for compile and runtime), but generally seems more robust.

[AriMKatz]

Relying more on StaticInts is worse for compile times (assuming const prop works instead of causing inference failures that'd then make not using StaticInt worse for compile and runtime), but generally seems more robust.

Yeah so this is a good example of what I was talking about. If the compiler is never going to be as reliable, and they're always going to be new weird type domain / static computations that soss and catlab etc are doing, is there some generic solution to doing this without blowing up compile times or without having to write your own walled garden DSL and compiler?

[timholy]

Some of these problems can be solved by moving the tests into Julia's own test suite...that way, people working to improve inference will get immediate feedback about having made your life worse, and make fixes before merging to master. Since 1.9 is starting, one could take the best results obtained across 1.6-1.8 and commit them, using @test_broken if necessary to flag them as a challenge for future inference improvements.

I'm not saying this to try to discourage migration of StaticInt into Base, but a clear vision about what does and doesn't work can serve as a roadmap for future work that may have widespread benefits.

[Tokazama]

will the compiler turn this line into this line?

I don't think that specifically could happen, since the compiler cannot switch a UnitRange to a OneTo. But, it can constant propagate it:

julia> f() = intersect(1:3, 2:4)

julia> @code_typed f()
CodeInfo(
1 ─     return $(QuoteNode(2:3))
) => UnitRange{Int64}

So I would like to understand better what is needed from the compiler.

If we are close to a point where we can just remove OneTo entirely because the compiler can elide related computations, then we don't really need StaticInt. However, my understanding is we will still need to store size in the type domain for things like SArray and find ways of propagating that information between array methods.

So it's less about the compiler being able to convert between types than it is about whether we can get rid of these highly specific types entirely because the compiler will infer related optimizations.