Because the value you’re branching on is a runtime value, you can’t do better than a runtime branch. You can avoid dynamic dispatch by explicitly branching via if, but that means you either write the specialized code manually, or get a generic version that works for any n. The way to get a specialized version automatically is to go through a type containing the runtime value, like Val or StaticInt, to be able to dispatch to a specialized version (instead of manually branching).
This is what we’re talking about - the constant-ness of a value (or lack thereof) is not part of the type system; hence, it is not dispatchable information.
@Sukera you appear to not be understanding the proposal here. This has nothing to do with Create staticint.jl by Tokazama · Pull Request #44538 · JuliaLang/julia · GitHub or using other types to lift values to the type system. This is not a type level dispatch feature they want, but code generation that’s specialized on whether or not a variable has a constant value known to the compiler.
@Mason I understand what they’re asking for - I brought up exactly the same thing on triage when staticint.jl was proposed & discussed. The reasoning was the same though - just knowing that a value is a constant doesn’t really help you; you need to know the value as well to do something useful, in which case you don’t get around lifting the value to the type domain. Exposing whether a value is a propagated constant or not is not something core devs are favorable to though, which is why I linked the thread:
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.
Apologies for not linking directly to the quote originally - I was on my phone when I answered.
So in combination with first trying to make the existing Array more amicable to constant propagation by using the buffer type, I think the incentive to add explicit “constness” querying is of lower priority Constant propagation, just like type inference, is allowed to fail after all, so I’m doubtful that propagating “deep into a library” as @user664303 requests is going to realistically happen - constant propagation for that kind of stuff is just too brittle to use reliably.
Ok, but the question is - where did that v come from? If it’s from some other computed value like length(arr) or similar, you’re stuck with dynamic dispatch again. It’s not like array lengths are tracked/constant propagated through constructors of those arrays, since arrays can change size (which a potential fixed size array based on the linked buffer discussion would not do, so it could be constant propagated/inferred through there).
When we say constant here, we mean that its runtime value is known to the compiler at compiletime, typically represented interally with Core.Const:
julia> code_warntype((Float64,)) do x
y = sin(3/2)
x + y
end
MethodInstance for (::var"#22#23")(::Float64)
from (::var"#22#23")(x) @ Main REPL[7]:2
Arguments
#self#::Core.Const(var"#22#23"())
x::Float64
Locals
y::Float64
Body::Float64
1 ─ %1 = (3 / 2)::Core.Const(1.5)
│ (y = Main.sin(%1))
│ %3 = (x + y::Core.Const(0.9974949866040544))::Float64
└── return %3
This information is present and usable, just not accessible to anyone outside of the compiler.
Ah okay I see the relevance now. I think there’s still some room here though. This quote from Jeff is specifically about adding that to the lattice and tracking it in arrays which is a bit different and pretty understandable that Jeff is hesitant to do that.
Rather, what could be done in this instance (I’d imagine anyways) is that you have some function
function f(len)
if @constant len
v = SVector{len}( ... )
g(v) # Do something with that statically sized array
else
v = Vector( ... )
g(v) # Do something with the dynamically sized array
end
end
This can be done even if lengths of arrays can’t be constant propagated because it’s actually the other way around, the maybe-constant-propagated variable determines the array length.
Yes, there are cases where this wouldn’t work because we don’t constant propagate array lengths (well, we do constant prop multidimensional array sizes, just not vector lengths, but that’s just a sidenote), but there’s still lots of things that could be done with a feature like this that wouldn’t require any new lattice elements be added, or modifying how we reason about arrays, just using the current lattice.
Yes, the quote doesn’t quite fit, but I think the greater message about “excessive compile times” still applies; making constant propagation/that part of inference observable is bound to bring difficulties. There’s also a lot of other related points in that thread (they’re trying to solve much the same problem after all), this is just the first/one that most closely fit the general question in here.
Here’s another subtlety - currently, constant propagation and concrete evaluation are two subtly different things. Are all values in a constant foldable function automatically known constants, even if they weren’t the result of constant propagation but rather of concrete evaluation? What about branches that weren’t taken?
It’s not so simple as saying “just give me whether inference was able to infer some Core.Const”, I don’t think. Hence, making the standard Array more amicable to constant propagation & concrete evaluation (thereby potentially eliminating the need for StaticArrays entirely) seems like a more general approach that solves more than just this issue. If this turns out to be wrong (which my gut says it won’t, but we’ll see), we can still discuss whether making that part of inference observable API or not is a good idea (as it’s a part of inference though, I’m pretty sure the answer is going to be “no”, because that’s historically what the stance of core devs regarding making inference more visible has been).
To clarify though, even if this constant propagation branch existed, it still doesn’t seem like it improves things. Taking the pretty good example function earlier, right now we have
myfunc(Val(1)) : we had a hard-coded constant type parameter, so this optimized method call is statically dispatched. If the compiler thinks it’s cheap enough it will compute it at compile-time, though if you want a guarantee, run it in the global scope beforehand and access it via a const global variable.
myfunc(Val(a)) : the runtime value varies so there’s a dynamic dispatch of myfunc, but the compiled myfunc does have that value as a constant so the call is still optimized.
myfunc(a) : separate method that does not on any level compile specifically for the value of a. It’s statically dispatched on the type of a::Int, so this could run faster than (2) if the algorithm is so cheap that just 1 dynamic dispatch overshadows value optimization.
(The obvious missing possibility is myfunc(1). It has the same performance as (3), but the compiler may run it at compile-time if it’s cheap enough.)
With a @constant-branched myfunc we have:
myfunc(1) : hard coded constant branches to @constant branch, same code as (1) before
myfunc(a) : branches to else branch, same code as (3) before
It actually seems worse now we lost the ability to write myfunc(Val(a)) instead of myfunc(a). We can’t dynamically dispatch to a function barrier if we wanted to, and we can’t do anything about the compiler doing extra work to figure out the branch every time it runs into this method, which could be a combinatorial explosion with more @constant-branching callees. Earlier we had remarked that we want more control of dispatch in the end-user’s hands, this feels like going in the opposite direction.
This approach requires you, the programmer to know at the callsite of myfunc if x is a constant or not, but this is often not information you know just from writing the function because whether x is a constant depends on compiler heuristics! With if @constant, you can let the compiler decide if it’s best to do specialization or not.
Sure, sometimes Val is useful, but othertimes we just want the compiler to do value specific specialization only if the compiler statically knows the value, and otherwise, we want it to hit fallback code.
You’re spinning the dynamic dispatch as an advantage here, but that dynamic dispatch is actually something many people would rather avoid, and would rather that they don’t dynamically do code generation and instead hit fallback, but we don’t currently have a tool to know if we can avoid that dynamic dispatch or not.
Nobody in this thread said anything about removing Val, that would be ridiculous. There wouldn’t be any loss of capabilities here, only a new tool in the toolkit.
No, I don’t think that’s an accurate picture of how this would work. The @constant branches would only run if a constant gets propagated to them. It does not force the constant to get propagated, so the compiler is always free to use its already existing heruistics to avoid any compile time blowups that may be lurking.
This is a significant advantage over using Val and @generated because they force codegen and value specialization to happen in a way that you have no control over.
I suppose I can’t know if the compiler decides something is cheap enough to compute at compile-time, so an example could be x = foo(1); y = bar(x).
But that was only half my point, my full point is that there’s a tradeoff of optimized function barriers and dynamic dispatches in the caller function. To avoid that dynamic dispatch given a non-constant runtime value, choose (3) myfunc(a). That’s the more common choice, it’s fairly rare that optimizing a function barrier on Val{a} is worth it.
You misunderstood, I wasn’t saying that anybody wanted to remove Val from the language, but it would not be used in a @constant branched function, so it’s not written in the calls.
Good point, if the compiler gets to decide if a function call is cheap enough to run at compile-time, it can also decide if doing more constant propagation is worth it. However, if it tries to approach current compile times and memory usage, it may often decide it’s not worth it. If it does that based on how many times it compiled @constant branches before, it may be harder to deterministically profile performance. For example if it has a limit of 3, the order in which the compiler encounters the scattered calls foo(1), foo(2), foo(3), foo(4) determines which one is left out of the @constant optimization.
That’s why I lean in favor of Val because you at least decide when the compiler dives into no-holds-barred codegen, and I think OP also wanted guarantees, not optional compiler decisions. Still, I see that Val is an easy choice between (1) and (2) e.g. x = foo(1); y = bar(Val(x)), not (1) and (3).
Exactly. The isconstant macro would (in my use case) be selecting between options 1 and 3, since option 2 has such terrible performance, and is the thing we’re trying to avoid.
(3) is pretty good right now, in a = foo(1); myfunc(a), if the compiler decides that foo(1) is cheap enough to compute at the caller function’s compile-time, it opens up myfunc(a) being computed at compile-time if it’s cheap enough too (hence constant propagation). Push comes to shove, you could run it in advance and store in a const global.
That’s just for optimization though. On the topic of determinism, if a constant is not decided by you (hard-coded literals, type parameters, const globals) but by the compiler like a above, wouldn’t a @constant branch in myfunc break backward compatibility? The compiler is free to change how it decides constant propagation across versions, so it could select the @constant branch in some versions but not the others.
Here’s another example that complicates this further:
function foo(a::Int)
if @constant a
"foo"
else
2.0
end
end
What should the inferred return type of this be? And I mean specifically in the standalone case, i.e. code_warntype(foo, (Int,)), not in context of another call like f() = foo(1) - constant propagation making type unstable code type stable is well known, and more or less why a.foo appears to be type stable.
The idea that the return type of a function changes purely based on whether its argument was a known constant or not seems incredibly dangerous to me, since there more or less are no guarantees on what is propagated or how far constants are propagated (or when they only appear to be constant due to concrete evaluation, which is distinct, as mentioned above). If the compiler “fails” to propagate the constant there, a developer can’t really do anything to “fix” the issue; it’s not actionable at all.
It would be Union{Float64, String}. However, this is not how the if @constant statement would be intended to be used. Just as with if @generated, the documentation would clearly state that “it is essential for the two implementations to behave identically.”
Just because the intention is different, doesn’t mean that people won’t try to use it in that way. It’s good to think about these things and the implications it has before we put it into the language.
Julia already has a number of features will cause strange and unexpected results if people would try to use them in a way that the manual warns against. Besides @generated functions that were already mentioned, there’s also @inbounds and @assume_effects (and before that @pure).
So I don’t think that “people who don’t read the manual might get into trouble” is a reason for taking a performance improvement off the table.
But we don’t want the branches to behave identically. Would same return type and side effects be more sensible as a condition? Not sure if different allocations means different side effects, or if it’s enough to solve the problem of different compiler versions selecting different branches.
I mean, that was my point. And the rest of the thread showed that we’re considering the branches to behave differently, use different data structures and call different methods. You’re the first to suggest they should behave the same.
Constant propagation, just like type inference, is allowed to fail after all, so I’m doubtful that propagating “deep into a library” as