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.

@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

[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]

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