cmd/compile: swapping two elements of a slice generates double the necessary boundary checks #10131
Comments
|
Another example: type slice []int
func swap(x slice) {
x[0], x[1] = x[1], x[0]
}Should generate a single boundary check, not 4. |
|
This may be worthwhile a custom optimization. It would seem that this should have a significant impact on the performance of sort.Sort calls. |
|
Go 1.6 SSA middle-end should get rid of the redundant bound checks
easily.
Please note that bound check also checks for negative indices too (the
assembly uses unsigned comparison, so one instruction checks both
directions)
Thus, when bound checking i and j, not only do we need to check
max(i, j) < len, we also need to check min(i, j) >= 0. It's not a clear gain
as compared to check 0 <= i < len in one instruction and 0 <= j < len in
another instruction. (We might be able to group bound check of i and
j together and use some branch elimination techniques though.)
|
|
I'm aware of the single unsigned compare trick. I also expect that a good SSA backend would take care of it. But it may be worthwhile a custom optimization in the meantime; depending on the gain (perhaps it's not significant) and the importance of sorting. |
|
gri, the last two paragraphs of my last reply is mostly to the OP about the
idea that we should check for max(i, j) < len instead of separately check
i and j are within range. Apologies if I'm not clear. You're certainly
aware of
this trick. ;)
Regarding custom optimization, do you mean that the compiler checks
for the swap idiom and generate better code for it?
|
|
Yes, the latter (compiler checks for swap idiom). I know that we generally eschew these kinds of optimizations (in favor of more general optimizations), but it may be easy enough (not sure though) and perhaps the win is high (sorting is reasonably important). Or in other words: I'm advocating it's worthwhile an experiment for somebody who wants to play with it. The outcome of that experiment may inform us about whether it's worthwhile or not keeping the optimization. |
|
With the unsigned trick |
mikioh
changed the title
mikioh
changed the title
rsc
changed the title
|
Too late for Go 1.5. |
|
This is fixed now. Only two bound checks are generated. |
For the following code:
x86 6g 1.4.1 generates:
This is double than the necessary boundary checks. Moreover, in the best case there should be only a boundary check for max(i, j).
The text was updated successfully, but these errors were encountered: