JuliaLang
Create staticint.jl
If there is nothing in Base that uses this, why would it not be a package?
If there is nothing in Base that uses this, why would it not be a package?
There currently isn't, but the idea is there should be. For example, if we had support for this in ranges eachindex(::IndexLinear, x::AbstractArray...) could return a statically sized set of indices if any of the arrays had them. I figured this would be a good start before trying to add everything at once.
EDIT: Or rather, there should be if we can't expect the compiler to soon provide support for problems discussed here https://github.com/JuliaLang/julia/discussions/44519. If solves this stuff in the compiler then I'm open to that being used instead.
Could we define eachindex in Base specialize eachindex for StaticArrays in StaticArrays.jl, and have StaticArrays.jl depend on StaticInts.jl?
I know of four uses for Val in Base: tuples, array dimensions, literal exponentiation, and base/special which I think does fancy mth optimizations. Of these, the first three use cases could all be entirely replaced by StaticInt while the usage in base/special includes things of the form logbL(::Type{Float64},::Val{:ℯ}) = 0.0 which cannot be.
It would be so nice if we could use Int instead of StaticInt. I'm rooting for the compiler people here, but in the interim, I think this solution fits a real-world use case in base and elsewhere.
Could we define
eachindexin Base specializeeachindexforStaticArraysinStaticArrays.jl, and haveStaticArrays.jldepend onStaticInts.jl?
This is a good concrete example of where it's nice have this in Base. If you take the definition you're interested in here it's a bit hard to ensure that we propagate static info without jumping through some hoops (define methods for nested static arrays and methods where statically sized arrays are first, second or third).
Now take the approach of ArrayInterface.indices. It's using _pick_range internally to propagate static lengths.
Pretty much anywhere there's a new array created or subsequent calls depend on eachindex or axes is a place we could improve on if we were aware of this info.
It would be so nice if we could use
Intinstead ofStaticInt. I'm rooting for the compiler people here, but in the interim, I think this solution fits a real-world use case in base and elsewhere.
This is pretty close to how I feel about it. Hopefully this comment makes it more clear what we would need from the compiler for this sort of thing to be unnecessary.
I know of four uses for
ValinBase: tuples, array dimensions, literal exponentiation, and base/special which I think does fancy mth optimizations. Of these, the first three use cases could all be entirely replaced byStaticIntwhile the usage in base/special includes things of the formlogbL(::Type{Float64},::Val{:ℯ}) = 0.0which cannot be.
Val is a bit of a footgun approach to propagating information when the only types that need to be in the type domain are Int, Symbol, and Bool. Val doesn't subtype any of these so people just keep putting things in the type domain next to other stuff it interacts with. That's the entirety of StaticArrays, putting the size information next to a buffer. A lot of traits I've seen out in the wild could just be a static true and false instead of a whole new set of types. The type system is fun to play with but it would probably be better if most people didn't worry about manually putting these things in the type domain. Corresponding types in base could be a more structured way of talking to the compiler, but there's a lot going on there and perhaps there's a more robust workflow in development.
Pretty much anywhere there's a new array created or subsequent calls depend on
eachindexoraxesis a place we could improve on if we were aware of this info.
I'm not sure how the folks at StaticArrays are doing it, but I think it is hard to improve on the constant propigation going on in this specific case where subsequent calls depend on eachindex and axis:
a = @SVector rand(100);
b = @SVector rand(100);
f(a, b) = sum(eachindex(a, b)) + sum(sum.(axes(a)))
@code_llvm f(a, b)
; @ none:1 within `f`
define i64 @julia_f_11329([1 x [100 x double]]* nocapture nonnull readonly align 8 dereferenceable(800) %0, [1 x [100 x double]]* nocapture nonnull readonly align 8 dereferenceable(800) %1) #0 {
top:
ret i64 10100
}
Pretty much anywhere there's a new array created or subsequent calls depend on
eachindexoraxesis a place we could improve on if we were aware of this info.I'm not sure how the folks at StaticArrays are doing it, but I think it is hard to improve on the constant propigation going on in this specific case where subsequent calls depend on
eachindexandaxis:a = @SVector rand(100); b = @SVector rand(100); f(a, b) = sum(eachindex(a, b)) + sum(sum.(axes(a))) @code_llvm f(a, b) ; @ none:1 within `f` define i64 @julia_f_11329([1 x [100 x double]]* nocapture nonnull readonly align 8 dereferenceable(800) %0, [1 x [100 x double]]* nocapture nonnull readonly align 8 dereferenceable(800) %1) #0 { top: ret i64 10100 }
But eachindex(rand(100), a) returns OneTo and other methods will produce a dynamically sized array when it could be inferred as statically sized. Similarly, combining axes when broadcasting can be tricky. If we can get the same code generated without @SVector then we don't need statically sized arrays and don't need to worry about static types at all.
eachindex(rand(100), a)returnsOneTo
That's because eachindex performs bounds checking and then returns its first argument (i.e. eachindex(a, rand(100)) === SOneTo(100) and eachindex(rand(100), a) === Base.OneTo(100)) How would switching to StaticInt fix this?
If we can get the same code generated without
@SVector
How would this work? Would we parse 100 as a StaticInt?
eachindex(rand(100), a)returnsOneToThat's because
eachindexperforms bounds checking and then returns its first argument (i.e.eachindex(a, rand(100)) === SOneTo(100)andeachindex(rand(100), a) === Base.OneTo(100)) How would switching toStaticIntfix this? The link above toArrayInterface.indicesis essentiallyeachindexbeing aware of staticness. In order foreachindexto combine these appropriately it has to be aware that static sizing is even a thing.
If we can get the same code generated without
@SVectorHow would this work? Would we parse
100as aStaticInt?
I'm not saying that example is solved with StaticInt. If StaticInt were in base perhaps you could pass something like rand(StaticInt(100)), but I was trying to keep this PR succinct so it was easy to discuss what's here. I could add in some of the traits and range related behavior if it helps to see some more concrete applications.
My point was just that if the same code is generated without the size in the type domain then we wouldn't need SVector and might not need StaticInt.
In theory the compiler could add a lattice element for an array with known size, and propagate constants to know the size of rand(100) at compile time. The only problem is that we'd then do it for every constant array size, which would likely cause excessive compile times. It is possible there aren't that many constant-size arrays, and that the size being a constant is a hint we should specialize on it, so I'm not sure. Very much an empirical question. But then, you still need a way to request size specialization even when the size is non-constant, and rand(StaticInt(n)) might be a good way to do that.
What if we had static to take anything into the compile-time domain. With TypedVal{T,x} <: T, static(x) === TypedVal{typeof(x), x}(), and TypedVal{T,x}() == x.
EDIT: I'm not sure about this idea. One problem is that for concrete types T we'd be trying to subtype a concrete type.
In theory the compiler could add a lattice element for an array with known size, and propagate constants to know the size of
rand(100)at compile time. The only problem is that we'd then do it for every constant array size, which would likely cause excessive compile times. It is possible there aren't that many constant-size arrays, and that the size being a constant is a hint we should specialize on it, so I'm not sure. Very much an empirical question. But then, you still need a way to request size specialization even when the size is non-constant, andrand(StaticInt(n))might be a good way to do that.
I figured that this was the case. In addition to making it so more methods actually can propagate static info, there might be some more intelligent codegen the compiler can be aware of if there's a dedicated type for this. For example, perhaps foo(x::Integer) could avoid generating an additional method unless it's explicitly foo(::StaticInt{N}) where {N}.
Newest changes have the basic types and traits that we've found useful over in ArrayInterface so far. These don't necessarily need to be a part of this PR or have have the current names. I just thought it would be helpful to provide a little more context. Some places where this is helpful to have in base are Broadcast.combine_axes, promote_shape, and eachindex.
Triage discussed this but we don't have any hard conclusions yet.
Really appreciate the update. Just let me know if there's anything else that's needed from me to help solve this issue (whether it be StaticInt or some entirely different solution). I know there's a lot of things being worked on right now that may be more urgent, but a lot of what I'm working on in Julia is related and I just want to make sure this continues to have some momentum.
For example, if we had support for this in ranges …
Couldn't that be done in a package as well?
Normally, one would create a package first to experiment with a feature like this and to see if people find it useful. Since it introduces a new type, there is no type piracy required to extend Base functions with it.
We have this as a range type in ArrayInterface so it's not an issue of wanting someone else to make those types.This isn't an exhaustive PR that fixes all related issues. More would need to follow. The point of most of these comments and the linked discussion has been that we still have a lot of places where we use awkward foot guns to get around this not being in base.
we still have a lot of places where we use awkward foot guns to get around this not being in base.
Can you give an example of such an "awkward foot gun"? So far, I haven't seen any examples that couldn't be implemented just as well in a package.
(Note that we can't replace Val with StaticInt in Base's public API, because that would be a breaking change. So you'd have to add StaticInt methods in addition to the existing Val methods, which is just as easy to do in a package.)
@stevengj
Normally, one would create a package first to experiment with a feature like this and to see if people find it useful. Since it introduces a new type, there is no type piracy required to extend Base functions with it.
A number of currently open PRs don't follow that policy (just for example https://github.com/JuliaLang/julia/pull/39071, https://github.com/JuliaLang/julia/pull/43334, https://github.com/JuliaLang/julia/pull/43557). Current practice seems to be more ad hoc, afaict.
Just because we sometimes accept new features into Base doesn't mean that we always do; it's a judgement call. But pointing to unrelated PRs that got merged (or not) is not a productive line of discussion.
On the one hand, this is already in a package and works fine in that form (especially since it is bundled with several other "static" types), and it wouldn't be terrible to leave it as an external package. On the other hand, this is rather basic functionality, being a replacement for many uses of Val as opposed to an adjunct, and a bunch of packages have already seemed to find it useful, and it could be used instead of Val in a bunch of Base functions, so that might be an argument for putting it in Base. On the third hand, we already have Val in Base and it's not going away, so we'd want to think carefully before introducing a type with significantly overlapping utility...there's a price in complexity to having multiple competing mechanisms in Base.
The point isn't that we are replacing Val. I've mentioned several methods that would really need to have an internal concept of static sizing to be implemented in a generic way. As far as foot guns, StaticArrays.similar_type seems like a good solution at first but isn't the right choice for anything that isn't absolutely a static array and isn't generic. Now look at how many packages depend on Static arrays just for compatibility and don't implement any static array types.
I think we've already established that the packaged solution isn't sufficient and we are just waiting to see if the compiler team has a better alternate solution.
@stevengj
Normally, one would create a package first to experiment with a feature like this and to see if people find it useful. Since it introduces a new type, there is no type piracy required to extend Base functions with it.
A number of currently open PRs don't follow that policy (just for example #39071, #43334, #43557). Current practice seems to be more ad hoc, afaict.
It would be nice to have a more clear set of rules in what gets added to base, but let's leave addressing that issue elsewhere. I largely agree with @stevengj criticisms for additions to base, but I think we've made it clear that this is something that we could uniquely benefit from being in base.
Just to chime in that @Tokazama is correct, having this in Base is not the same as having it in a package. A key difference is invalidation: loading Static.jl invalidates poorly-inferred code operating on Integer because it defines a new Integer subtype. In contrast, if we define StaticInt as a subtype of Integer early, then we don't invalidate a bunch of compiled code merely by loading Static.jl.
If all type-inference problems can be solved exhaustively everywhere, this wouldn't be necessary, but that's not a world we live in. That's not to say that there aren't alternative ways to solve this problem: allowing developers to turn off "world-splitting" might be another. So like other core devs, I still remain ever so slightly on the fence about this, but I do think we should drop the discussion of "why can't this just be in a package?" Unless we do other things to improve the compiler, it really should move into Base.
The invalidations are certainly annoying, and do hinder its use as a package because it's a pretty basic utility to also end up with a bunch of invalidations for downstream developers.
I'd also add that even if we did fix invalidations, much of the code in ArrayInterface is just redefining methods from base so that they are aware of static information. I'm not saying we just redefine all those methods in base right now and try to tip-toe around breaking changes. But it does demonstrate that we may have missed the boat on a lot of methods generically propagating this information until 2.0. It would be a shame to keep doing so.
Is there anything I can do at the moment to push this forward or help with some alternate solution the core team has in mind?
The invalidation issue is a big one. This does not work in a package. It gives like a 0.4 sec runtime cost to every downstream package that uses anything that uses it, which is now over 1000 packages indirectly using it or about 1/6 of the ecosystem. It's a very basic utility which isn't subject to really change much, it's something that should be suggested to be used instead of Val in many cases because it has good ergonomics, and there's many suggestions for Base functionality which should be using it. So in terms of:
Normally, one would create a package first to experiment with a feature like this and to see if people find it useful. Since it introduces a new type, there is no type piracy required to extend Base functions with it.
I think it's very clear that it has passed this criteria, while simultaneously:
On the one hand, this is already in a package and works fine in that form (especially since it is bundled with several other "static" types), and it wouldn't be terrible to leave it as an external package.
it does not work fine in a package form, but has been useful enough that some very large percentage of Julia users now enjoy a whole host of their system invalidation because packages find the cost of this utility overcome by its benefit.
To me, this makes a very good case for it to be in Base unless constant propagation has a serious chance to eliminate it any time soon, but @JeffBezanson has suggested in this thread that we would likely receive compile times that are unbearably high from that and thus require an opt-in (instead of an opt-out), and StaticInt would be a good way to opt-in.
Given this uncertainty with constant propagation, I would suggest adding it to Experimental if that breaks the deadlock. It would achieve its purpose of being able to be in the system image and not invalidate everyone's code, but for those heavy believers in constant propagation fixing all static declarations, this would allow it to be deleted in that glorious future.
A key difference is invalidation: loading Static.jl invalidates poorly-inferred code operating on Integer because it defines a new Integer subtype. In contrast, if we define StaticInt as a subtype of Integer early, then we don't invalidate a bunch of compiled code merely by loading Static.jl.
But surely the solution can clearly not be to put everything that defines a new Integer into Base.
The invalidation issue is a big one. This does not work in a package. It gives like a 0.4 sec runtime cost to every downstream package that uses anything that uses it, which is now over 1000 packages indirectly using it or about 1/6 of the ecosystem. It's
I've seen cases where packages of dubious quality have been made into dependencies of very core packages and then have used that to argue that it should somehow get special treatment. I don't think that is a good way of doing things.
Putting it in Experimental is pointless because it would never be allowed to be removed "oh this will break the whole ecosystem, you can't remove it!". Any usage from Experimental should be such that the whole Experimental module can be removed without any disruption to the ecosystem. I doubt that will be the case here.
Invalidations arent the only reason this should be in base and I believe that's the first comment that specifically mentioned widespread use as a motivation. We're simply accumulating additional points in favor of adding this until someone provides an alternative solution.