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
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone

Comments

@dsnet
Copy link
Member

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).

@bcmills bcmills added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Mar 2, 2019
@bcmills bcmills added this to the Unplanned milestone Mar 2, 2019
@go101
Copy link

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 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 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 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 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?

@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
None yet
Development

No branches or pull requests

5 participants