Skip to content
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

cmd/compile: unnecessary bounds check for global slices #30529

Open
dsnet opened this issue Mar 1, 2019 · 5 comments
Open

cmd/compile: unnecessary bounds check for global slices #30529

dsnet opened this issue Mar 1, 2019 · 5 comments

Comments

@dsnet
Copy link
Member

@dsnet dsnet commented Mar 1, 2019

Using go1.12

Suppose we have a unexported global variable:

var mySlice = make([]T, 4)

and none of the operations performed on this slice:

  • let a reference to the slice itself escape from the package (implies that the variable is unexported)
  • mutate the slice header itself (e.g., no assign to the variable)

For example, operations like element assignment (e.g., mySlice[3] = ...) and element addressing (e.g., &mySlice[3]) are permitted.

If the above conditions are met, I believe that indexes into the slice below the initial size could have the bounds check elided since the index is provably not going to exceed the bounds.


The use case for this is code like:

var globalMessageTypes = make([]protoimpl.MesageType, 2)

func (T) Type() protoreflect.MessageType {
    return &globalMessageTypes[0] // Desire no bounds check here
}

func (R) Type() protoreflect.MessageType {
    return &globalMessageTypes[1] // Desire no bounds check here
}

func init() {
    for i := range ... {
        globalMessageTypes[i] = ...
    }
}

We could use an array instead to avoid the bounds check, but that has other issues (see #30528).

@go101
Copy link

@go101 go101 commented Mar 2, 2019

Checking a variable is ever assigned to is a costly, and sometimes almost impossible.
But we can do this cheaply for the finals described in this proposal.

Another benefit of #29422.

@dsnet
Copy link
Member Author

@dsnet dsnet commented Mar 3, 2019

@go101, assuming you're claim that this is "costly, and sometimes almost impossible" is true, that doesn't bode well for your proposal which relies on this type of analysis being possible by the compiler (to enforce the proposed new language semantics).

I should also note that addressing this in the compiler need not a rigorous proof of correctness that a full blown proposal like #29422 would require. If the compiler is ever unsure whether the variable is mutated, it could always do the safe thing, which is to emit bounds checks.

@go101
Copy link

@go101 go101 commented Mar 3, 2019

I think there are really some cases where the author of the code can make sure a global value will never be modified but it is difficult for compilers to deduce the same conclusion.

For a simple example, if a global slices are passed as arguments to many functions, and these functions continue to pass the corresponding parameter to many other more functions. I would be costly for compilers to deduce whether of not the slice will be modified.

@go101
Copy link

@go101 go101 commented Mar 3, 2019

I mean it is not bad to let compilers to deduce some global slices are never modified (if the deduction work is not costly). However, it would be better also let code author to tag some values will never be modified.

@zdjones
Copy link
Contributor

@zdjones zdjones commented Apr 8, 2019

The optimization passes, including the removal of bounds checks, are done on each function independently. Have you tried an example where all aspects of your issue are in the same func?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants
You can’t perform that action at this time.