[go] internal/runtime/maps: use KKKKVVVV slot order
Jake Bailey (Gerrit)
Jake Bailey voted Commit-Queue+1![]( "Open in Gerrit")
| Commit-Queue | +1 |
Related details
- Michael Pratt
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jake Bailey (Gerrit)
Jake Bailey added 1 comment![]( "Open in Gerrit")
off += 9*arch.PtrSize + 4 // internal/abi.MapTypeI spent weeks staring at this CL trying to figure out why it was crashing, only to eventually find this hardcoded sizeof; probably worth a comment or something somewhere, though I don't know why this isn't derived from reflectdata or types or something...
Related details
- Michael Pratt
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jake Bailey (Gerrit)
Jake Bailey added 3 comments![]( "Open in Gerrit")
ElemSize uintptr // size of elemI need to update the doc or even field name to better indicate that this is what's in the array (e.g. a pointer after a certain size), not just `Key.Size()`.
ctrlGroupsSize = unsafe.Sizeof(ctrlGroup(0))This is no longer required; if I'm having to store an offset for the type relative to the group anyway, there's no reason to have an extra add.
var i uintptrI didn't like that I did this, but I later realized that this should still use the same number of variables given slotSize in the previous code was also variable. but, it is one more add in the loop.
Related details
- Michael Pratt
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jake Bailey (Gerrit)
Jake Bailey added 1 comment![]( "Open in Gerrit")
This appears to fail testing because the map layout is encoded in the debugger. Probably, this means my other CL is wrong because it did not update those. Fun.
Related details
- Michael Pratt
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jake Bailey (Gerrit)
New activity on the change![]( "Open in Gerrit")
Related details
- Michael Pratt
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Michael Pratt (Gerrit)
Michael Pratt added 1 comment![]( "Open in Gerrit")
For reference, microbenchmark results are available at https://gist.github.com/prattmic/f280e118962fbe353b201f20b16e3a66
Related details
- Jake Bailey
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jake Bailey (Gerrit)
Jake Bailey uploaded new patchset![]( "Open in Gerrit")
- TryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI
Related details
- Jake Bailey
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jake Bailey (Gerrit)
Jake Bailey voted Commit-Queue+1![]( "Open in Gerrit")
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jake Bailey (Gerrit)
Jake Bailey uploaded new patchset![]( "Open in Gerrit")
- TryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Michael Pratt (Gerrit)
Michael Pratt added 11 comments![]( "Open in Gerrit")
Thanks! This looks good to me. My only worry is whether the removal of the ElemOff optimizations is measurable. I'm running a new microbenchmark run to see if I can measure a difference.
internal/runtime/maps: use KKKKVVVV slot orderLet's make the fact that this is off by default for now more obvious by mentioning the experiment.
```suggestion
internal/runtime/maps: add GOEXPERIMENT=mapsplitgroup for KKKKVVVV slot order
```
Fixes #71368`Updates`, since it isn't enabled yet.
keysOff := gtyp.Field(1).OffsetEven though this is common between both types, I think it would be cleaner to put it in both branches since the !MapSplitGroup has a separate explanation below for this value.
If you change this, please change reflect/map.go as well.
keySize = gtyp.Field(1).Type.Elem().Size()This is fine, but `t.Key().Size()` might be more obvious. Same with elem below.
I spent weeks staring at this CL trying to figure out why it was crashing, only to eventually find this hardcoded sizeof; probably worth a comment or something somewhere, though I don't know why this isn't derived from reflectdata or types or something...
Please do add a comment to internal/abi and/or reflectdata. I also tend to forget this is here.
It isn't derived from reflectdata because the size of MapType is always constant, it doesn't depend on the actual types passed into reflectdata. It would be nice if we could easily assert that the size here is correct or something.
ElemSize uintptr // size of elemI need to update the doc or even field name to better indicate that this is what's in the array (e.g. a pointer after a certain size), not just `Key.Size()`.
I don't quite follow what you're getting at now, but I think things are pretty clear now with the expanded comments.
KeySize uintptrWhile I think this name is fine if we keep `GOEXPERIMENT=mapsplitgroup` permanently, it's confusing for interleaved slots, where the name strongly implies it is the same as `Key.Size()`. I worry we may introduce a bug by forgetting that it's not.
Perhaps call these fields `KeyStride` and `ElemStride`? IMO, that has a natural meaning in both cases (it just turns out that the stride == size for the split layout).
slotElem := unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)This is a micro-optimization we added to shave off a few instructions. We'll see if my benchmarks (currently running) can measure removing it.
If it is, we could keep `typ.ElemOff`. The offset between a key and its elem is the same for every key even in the split layout.
var i uintptrI didn't like that I did this, but I later realized that this should still use the same number of variables given slotSize in the previous code was also variable. but, it is one more add in the loop.
Seeing the loop change here makes me lean more towards my previous suggestion that we keep `typ.ElemOff`.
keyStride = 4 // keys are contiguous in split layouttyp.KeySize will be 4 here as well. Did you do this for the constant propagation effects?
Related details
- Jake Bailey
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Michael Pratt (Gerrit)
Michael Pratt voted Commit-Queue+1![]( "Open in Gerrit")
| Commit-Queue | +1 |
Related details
- Jake Bailey
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jake Bailey (Gerrit)
Jake Bailey added 2 comments![]( "Open in Gerrit")
keySize = gtyp.Field(1).Type.Elem().Size()This is fine, but `t.Key().Size()` might be more obvious. Same with elem below.
t.Key().Size() doesn't work, because the size will change if it exceeds `MapMaxKeyBytes`.
ElemSize uintptr // size of elemMichael PrattI need to update the doc or even field name to better indicate that this is what's in the array (e.g. a pointer after a certain size), not just `Key.Size()`.
I don't quite follow what you're getting at now, but I think things are pretty clear now with the expanded comments.
- Michael Pratt
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jake Bailey (Gerrit)
Jake Bailey uploaded new patchset![]( "Open in Gerrit")
- TryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI
Related details
- Michael Pratt
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jake Bailey (Gerrit)
Jake Bailey voted and added 3 comments![]( "Open in Gerrit")
Votes added by Jake Bailey
| Commit-Queue | +1 |
3 comments
Let's make the fact that this is off by default for now more obvious by mentioning the experiment.
```suggestion
internal/runtime/maps: add GOEXPERIMENT=mapsplitgroup for KKKKVVVV slot order
```
Done
`Updates`, since it isn't enabled yet.
Done
While I think this name is fine if we keep `GOEXPERIMENT=mapsplitgroup` permanently, it's confusing for interleaved slots, where the name strongly implies it is the same as `Key.Size()`. I worry we may introduce a bug by forgetting that it's not.
Perhaps call these fields `KeyStride` and `ElemStride`? IMO, that has a natural meaning in both cases (it just turns out that the stride == size for the split layout).
Done
Related details
- Michael Pratt
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jake Bailey (Gerrit)
Jake Bailey added 1 comment![]( "Open in Gerrit")
var i uintptrMichael PrattI didn't like that I did this, but I later realized that this should still use the same number of variables given slotSize in the previous code was also variable. but, it is one more add in the loop.
Seeing the loop change here makes me lean more towards my previous suggestion that we keep `typ.ElemOff`.
Meaning, add another field to the map type and make everything conditional?
Related details
- Michael Pratt
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Michael Pratt (Gerrit)
Michael Pratt added 2 comments![]( "Open in Gerrit")
Thanks! This looks good to me. My only worry is whether the removal of the ElemOff optimizations is measurable. I'm running a new microbenchmark run to see if I can measure a difference.
Unfortunately the difference is definitely measurable: https://gist.github.com/prattmic/e369df6d6db282b6b04f761bbd0cb009
I only looked closely at MapFirst/4. At least for that one, the ElemOff change is what made the difference. Adding that back in as in https://go.dev/cl/747260 fixes the regression (though it's ugly).
For the mapsplitgroup case, I also want to try incremently computing slotElem the same way we do slotKey, rather than using the multiply. IIRC, I tried this in the original implementation and it was worse, but it's worth trying again.
var i uintptrMichael PrattI didn't like that I did this, but I later realized that this should still use the same number of variables given slotSize in the previous code was also variable. but, it is one more add in the loop.
Jake BaileySeeing the loop change here makes me lean more towards my previous suggestion that we keep `typ.ElemOff`.
Meaning, add another field to the map type and make everything conditional?
The suggestion I was thinking didn't actually make any sense, but yes adding another field works. As in https://go.dev/cl/747260.
Related details
- Jake Bailey
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Michael Pratt (Gerrit)
Michael Pratt voted and added 4 comments![]( "Open in Gerrit")
Votes added by Michael Pratt
| Commit-Queue | +1 |
Michael PrattThanks! This looks good to me. My only worry is whether the removal of the ElemOff optimizations is measurable. I'm running a new microbenchmark run to see if I can measure a difference.
Unfortunately the difference is definitely measurable: https://gist.github.com/prattmic/e369df6d6db282b6b04f761bbd0cb009
I only looked closely at MapFirst/4. At least for that one, the ElemOff change is what made the difference. Adding that back in as in https://go.dev/cl/747260 fixes the regression (though it's ugly).
For the mapsplitgroup case, I also want to try incremently computing slotElem the same way we do slotKey, rather than using the multiply. IIRC, I tried this in the original implementation and it was worse, but it's worth trying again.
I expanded https://go.dev/cl/747260 to all of the previous sites and ran all the benchmarks: https://gist.github.com/prattmic/bd471836570fdcda6f435af481d2d415
It looks like this basically resolve all of the differences in the nomapsplitgroup case, so I think it should be incorporated into this CL (though unfortunately it is kind of ugly).
Overall, mapsplitgroup results look fine. The most obvious regression is in the same small benchmarks, due to the multiplication in g.elem. I tried my suggestion above of computing slotElem incrementally in each loop iteration to avoid the multiplication. But unsurprisingly it didn't perform better. It would be nice to do something here, but I don't see how, this layout is just not amenable to this kind of optimization.
keySize = gtyp.Field(1).Type.Elem().Size()Jake BaileyThis is fine, but `t.Key().Size()` might be more obvious. Same with elem below.
t.Key().Size() doesn't work, because the size will change if it exceeds `MapMaxKeyBytes`.
Right, thanks
var i uintptrMichael PrattI didn't like that I did this, but I later realized that this should still use the same number of variables given slotSize in the previous code was also variable. but, it is one more add in the loop.
Jake BaileySeeing the loop change here makes me lean more towards my previous suggestion that we keep `typ.ElemOff`.
Michael PrattMeaning, add another field to the map type and make everything conditional?
The suggestion I was thinking didn't actually make any sense, but yes adding another field works. As in https://go.dev/cl/747260.
Acknowledged
if (typ.KeySize + typ.ElemSize) > 32 {Michael PrattThis feels kind of bogus; not sure what this code should be now that keys and elems are separated.
It seems OK to me, it is the total size that we need to read+write.
Related details
- Jake Bailey
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jake Bailey (Gerrit)
Jake Bailey added 1 comment![]( "Open in Gerrit")
Michael PrattThanks! This looks good to me. My only worry is whether the removal of the ElemOff optimizations is measurable. I'm running a new microbenchmark run to see if I can measure a difference.
Michael PrattUnfortunately the difference is definitely measurable: https://gist.github.com/prattmic/e369df6d6db282b6b04f761bbd0cb009
I only looked closely at MapFirst/4. At least for that one, the ElemOff change is what made the difference. Adding that back in as in https://go.dev/cl/747260 fixes the regression (though it's ugly).
For the mapsplitgroup case, I also want to try incremently computing slotElem the same way we do slotKey, rather than using the multiply. IIRC, I tried this in the original implementation and it was worse, but it's worth trying again.
I expanded https://go.dev/cl/747260 to all of the previous sites and ran all the benchmarks: https://gist.github.com/prattmic/bd471836570fdcda6f435af481d2d415
It looks like this basically resolve all of the differences in the nomapsplitgroup case, so I think it should be incorporated into this CL (though unfortunately it is kind of ugly).
Overall, mapsplitgroup results look fine. The most obvious regression is in the same small benchmarks, due to the multiplication in g.elem. I tried my suggestion above of computing slotElem incrementally in each loop iteration to avoid the multiplication. But unsurprisingly it didn't perform better. It would be nice to do something here, but I don't see how, this layout is just not amenable to this kind of optimization.
Is the next step for me to pull your CL into this one, then? What is left?
Related details
- Michael Pratt
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Michael Pratt (Gerrit)
Michael Pratt added 1 comment![]( "Open in Gerrit")
Michael PrattThanks! This looks good to me. My only worry is whether the removal of the ElemOff optimizations is measurable. I'm running a new microbenchmark run to see if I can measure a difference.
Michael PrattUnfortunately the difference is definitely measurable: https://gist.github.com/prattmic/e369df6d6db282b6b04f761bbd0cb009
I only looked closely at MapFirst/4. At least for that one, the ElemOff change is what made the difference. Adding that back in as in https://go.dev/cl/747260 fixes the regression (though it's ugly).
For the mapsplitgroup case, I also want to try incremently computing slotElem the same way we do slotKey, rather than using the multiply. IIRC, I tried this in the original implementation and it was worse, but it's worth trying again.
Jake BaileyI expanded https://go.dev/cl/747260 to all of the previous sites and ran all the benchmarks: https://gist.github.com/prattmic/bd471836570fdcda6f435af481d2d415
It looks like this basically resolve all of the differences in the nomapsplitgroup case, so I think it should be incorporated into this CL (though unfortunately it is kind of ugly).
Overall, mapsplitgroup results look fine. The most obvious regression is in the same small benchmarks, due to the multiplication in g.elem. I tried my suggestion above of computing slotElem incrementally in each loop iteration to avoid the multiplication. But unsurprisingly it didn't perform better. It would be nice to do something here, but I don't see how, this layout is just not amenable to this kind of optimization.
Is the next step for me to pull your CL into this one, then? What is left?
- Jake Bailey
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jake Bailey (Gerrit)
Jake Bailey uploaded new patchset![]( "Open in Gerrit")
- TryBots-Pass: LUCI-TryBot-Result-1 by Go LUCI
Related details
- Jake Bailey
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jake Bailey (Gerrit)
Jake Bailey voted and added 1 comment![]( "Open in Gerrit")
Votes added by Jake Bailey
| Commit-Queue | +1 |
Michael PrattThanks! This looks good to me. My only worry is whether the removal of the ElemOff optimizations is measurable. I'm running a new microbenchmark run to see if I can measure a difference.
Michael PrattUnfortunately the difference is definitely measurable: https://gist.github.com/prattmic/e369df6d6db282b6b04f761bbd0cb009
I only looked closely at MapFirst/4. At least for that one, the ElemOff change is what made the difference. Adding that back in as in https://go.dev/cl/747260 fixes the regression (though it's ugly).
For the mapsplitgroup case, I also want to try incremently computing slotElem the same way we do slotKey, rather than using the multiply. IIRC, I tried this in the original implementation and it was worse, but it's worth trying again.
Jake BaileyI expanded https://go.dev/cl/747260 to all of the previous sites and ran all the benchmarks: https://gist.github.com/prattmic/bd471836570fdcda6f435af481d2d415
It looks like this basically resolve all of the differences in the nomapsplitgroup case, so I think it should be incorporated into this CL (though unfortunately it is kind of ugly).
Overall, mapsplitgroup results look fine. The most obvious regression is in the same small benchmarks, due to the multiplication in g.elem. I tried my suggestion above of computing slotElem incrementally in each loop iteration to avoid the multiplication. But unsurprisingly it didn't perform better. It would be nice to do something here, but I don't see how, this layout is just not amenable to this kind of optimization.
Michael PrattIs the next step for me to pull your CL into this one, then? What is left?
Yes, that's all.
- Michael Pratt
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jake Bailey (Gerrit)
Jake Bailey voted Commit-Queue+1![]( "Open in Gerrit")
| Commit-Queue | +1 |
Related details
- Michael Pratt
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |