New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
proposal: unsafe: add Unreachable #30582
Comments
What happens if the assertion does not hold? |
The compiler may generate code that does all sorts of awful things. It is decidedly unsafe. |
To me, this sounds like "Assume". I would think "Assert" means if the assertion fails, the program crashes (more like the C assert function). |
@cherrymui thanks, proposal updated. |
Another approach would be if p == nil {
unsafe.Unreachable()
} else {
// Here the compiler knows that p != nil.
} and then at some point during code generation the compiler removes the |
@ianlancetaylor I like it. One nice thing about that is that it mirrors the not-unsafe way to write it: if p != nil {
panic("unreachable")
} becomes if p != nil {
unsafe.Unreachable()
} And the specification is simpler. The only downside I see is that it doesn't fit on one line. :P It also doesn't scream unsafe at me the way |
What happens if you ask the compiler to assume something it knows is false? Like something that reduces to
|
Then you're in UB world: It depends on the compiler and the details. I'm guessing that in practice, with cmd/compile right now, probably not too much. With gccgo, you probably start spewing random numbers until you generate the kubernetes code base. |
If the compiler doesn't know that |
Perhaps optionally? I think that a compiler that simply ignored |
I like this a lot for my code, I'm terrified of what happens if other people have it. |
I'm not sure we should go down this road. This is basically a "performance annotation" and it's one more thing everyone needs to understand. I'm happy to give up 5% in performance to never have to make (or see) any such annotations. There's a lot of other annotations people could want. If we do this I like Ian's API. |
@josharian could you clarify what part is expensive? The added code size? Or perhaps making some small functions non-inlineable with the current compiler? Another idea that comes to mind is if the compiler treated |
Change https://golang.org/cl/165358 mentions this issue: |
I wrote a rudimentary implementation so that I could experiment with it: https://golang.org/cl/165358
Some data points, for Going from my recently-optimized CLs to adding a few unsafe.Unreachable annotations:
Going from regular to an unrolled loop, which requires yet more annotations:
This gets us within striking distance of the hand-optimized assembly for small n. Going from my unrolled Go+Unreachable code to assembly:
And the main difference now is that the hand-rolled assembly can do I plan to do the ADC upgrade anyway. I'll report back once I've done it; might be a few days. None of the |
And if you want to see what the simple, hinted code looks like: func addVV_g(z, x, y []Word) (c Word) {
for i := 0; i < len(z); i++ {
if i >= len(x) || i >= len(y) {
// The calling code ensures that x and y are no longer than z.
// The compiler doesn't see this; this hint prevents bounds
// checks in the bits.Add call below.
unsafe.Unreachable()
}
zi, cc := bits.Add(uint(x[i]), uint(y[i]), uint(c))
z[i] = Word(zi)
c = Word(cc)
}
return
} |
Fair enough. That said, I think this is plausibly qualitatively different:
|
I'd be interested to see the benchmarks for func addVV_g(z, x, y []Word) (c Word) {
n := len(z)
x, y = x[:n:n], y[:n:n]
for i := 0; i < n; i++ {
zi, cc := bits.Add(uint(x[i]), uint(y[i]), uint(c))
z[i] = Word(zi)
c = Word(cc)
}
return
} I suspect the code using Also, if the compiler inlined code using I can see annotations like EDIT: dropped the length check panics, I don't think they are necessary for this use case and with them the function doesn't work when |
I did a few benchmarks on the generic code to see what I got. Hoisting the bounds check on y seemed to make very little difference. Which is interesting because they did remove the bounds check from the loop, implying the critical path is the carry chain (I am using an i5 3570k). Secondly, I tried applying David's for loop inlining experiment CL 148777. I still applied the bounds check hoisting change to get rid of the
I suspect the slightly slower speed limit is down to alignment noise or a similar effect. Patch to remove range statement and bounds check on y in the loop:--- a/src/math/big/arith.go
+++ b/src/math/big/arith.go
@@ -54,7 +54,9 @@ func divWW_g(u1, u0, v Word) (q, r Word) {
// The resulting carry c is either 0 or 1.
func addVV_g(z, x, y []Word) (c Word) {
- for i := range x[:len(z)] {
+ n := len(z)
+ x, y = x[:n:n], y[:n:n]
+ for i := 0; i < n; i++ {
zi, cc := bits.Add(uint(x[i]), uint(y[i]), uint(c))
z[i] = Word(zi)
c = Word(cc) |
DO NOT SUBMIT This is a rudimentary implementation, so that I can experiment with it. Updates golang#30582 Change-Id: I2e3a9e776490a9b01d4f166014b133625e419418
DO NOT SUBMIT This is a rudimentary implementation, so that I can experiment with it. Updates golang#30582 Change-Id: I2e3a9e776490a9b01d4f166014b133625e419418
DO NOT SUBMIT This is a rudimentary implementation, so that I can experiment with it. Updates golang#30582 Change-Id: I2e3a9e776490a9b01d4f166014b133625e419418
That seems dangerous to me: it adds a large space of undefined behavior (that is, any program that violates the assumption), but no way to validate that the program does not actually exhibit that behavior (contrast To me, the biggest advantage (by far!) of undefined behavior is that it can be sanitized: unlike a Go So instead, I would propose that the expression always be evaluated, and the result discarded except in sanitized (perhaps race-detector-enabled?) builds. That makes it possible to optimize away arithmetic expressions and pure functions (by far the common use-cases), but allows a sanitizer to verify the assumptions — without producing inconsistent behavior if the expression has side-effects. |
I apologize that my previous comment were a bit unclear. As you targeted this proposal at the This leads me to the leap that I made to turn this into a meaningful Firstly, let me clarify my expectations of assertions:
So, how can adding assertions make the code more optimized?
I realize this is essentially a counter-proposal to the spirit of the one you were proposing, and requires much deeper compiler inference to fully realize it’s full potential, but I think it can offer many of the gains you were looking for in a much safer way. I welcome your comments and would like to hear alternate viewpoints defending the original proposal as well. |
You can build Improving the compiler is always welcome. We do some of the things you suggest: we use the information provided by assertions when possible and (via inlining) we cull unnecessary assertions and checks. (These assertions take many forms, among them nil pointer checks, bounds checks, and many plain old branches.) We generate compile errors when some assertions are known to fail, such as indexing with a constant that is known to be out of bounds. But we can't increase the set of compilation errors much without it being a language change. Improving the compiler further isn't always an option. We may not have the time. We may not know how. We may decide that it isn't worth the concomitant compiler slowdown. And sometimes humans know things the compiler simply never will. This proposal is intended to act as a pressure release valve in such scenarios, when necessary for performance in critical sections of code. The question of whether there is sufficient value in adding a language construct for checked pre- and post-conditions is a very interesting one. But it is not this proposal, nor is it really an alternative to this proposal. From the compiler's perspective, you can simulate a checked pre-condition with an If you'd like to pursue your assertion proposal ideas further, I suggest you file a new issue to discuss them, and link to it here. |
@josharian, I agree with you on all points. I do think that it is worth pointing out where these two proposals do overlap:
I do concede this is a very small slice of the Ven diagram, and I expect your proposal to bear fruit long before the compiler’s static analysis subsystem is rich enough to make the goals I described above remotely achievable. I look forward to submit a compiler-aware assertion mechanism as a future proposal. Also, several ranged value type proposals that I have already read may dove-tail very nicely with these. |
I was thinking some more about the properties of
It occurs to me that we actually already have a statement that satisfies those properties: func Unreachable() {
go panic("unreachable")
} Since the On the other hand, since the new goroutine does not communicate or synchronize with any other goroutine in the program — and, in particular, does not have any happens-before relationship with any remaining statement in |
I'm simultaneously awed and horrified. Congratudolences? |
@bcmills that’s a very clever bit of language-lawyering. But I think I’d rather be explicit. And force importing unsafe, with all the signaling and extra-linguistic guardrails that come with that. |
Interesting, but the idea that there should be a difference between debug mode and release mode is false. I have spent years doing life critical software in a large, famous, company, and there the rule was the production binary must be the tested binary, which almost always meant the binary with debug information available, in order to be able to do postmortem analysis in case of a crash. Nevertheless |
We already have this: |
|
If I write your example above slightly differently (and encapsulate into a complete package so I can compile it): package main
import "math/bits"
type Word uint64
func addVV_g(z, x, y []Word) (c Word) {
if len(x) != len(z) || len(y) != len(z) {
panic("vector lengths don't match")
}
// lengths of x, y, z are the same
for i := 0; i < len(z); i++ {
zi, cc := bits.Add(uint(x[i]), uint(y[i]), uint(c))
z[i] = Word(zi)
c = Word(cc)
}
return
}
func main() {} It looks like the compiler is already smart enough to do the right thing. The inner loop appears to be:
or, copying from godbolt.org:
So at least for this code we may not have to do anything. |
This proposal has been added to the active column of the proposals project |
@griesemer points out that we added unsafe to provide the ability to do things that the language could not express but that needed to be available, specifically type-unsafe conversions. unsafe.Unreachable is different: it's purely a compiler optimization, not giving new expressive power. I worry a lot about debugability of buggy code, especially after years of suffering C and C++ compilers and "undefined behavior". In general Go's approach has been to prioritize safe code execution over absolute raw performance. C/C++ compilers have shown us where we end up when the compiler assumes things like "array indexes are always in bound" or "pointers are never null". It's true that unsafe.Unreachable would only produce more limited effects, since "always" and "never" are replaced by "in this specific instance". Even so, I fear that adding unsafe.Unreachable will encourage overuse for the sake of performance and lead to code that misbehaves in mysterious ways. Separately, the fact that the compiler is not smart enough to optimize away certain checks creates a constructive tension on developers that makes us search out new analyses or idioms that optimize better but are still safe. An example of this is the |
Based on the discussion above, this proposal seems like a likely decline. |
No change in consensus, so declined. |
When optimizing code, I often run up against cases in which the compiler is missing a key fact. Sometimes it could but does not infer it; sometimes there’s no reasonable way for the compiler to know.
In those cases, there is nothing to do but drop to assembly. (In normal code you could write
if !x { panic }
, but in many of these cases, that is prohibitively expense.)I propose that we add unsafe.Assume. It accepts a boolean expression. The expression is typechecked but never evaluated. However, the compiler may assume that it evaluates to true when compiling other code.
I imagine the most common uses would be things like
unsafe.Assume(p != nil)
,unsafe.Assume(0 <= i && i < len(s))
, andunsafe.Assume(x < 64)
, for nil checks, bounds checks, and shift amounts, respectively.The text was updated successfully, but these errors were encountered: