runtime: online slice/map pre-sizing #64703
Description
The goal here is to reduce excessive time spent growing slices and maps.
The idea would be to track slice/map declaration/allocation sites (by PC, perhaps including N frames of caller context for additional precision) and the typical (approximate median?) maximum size of containers from that allocation site. Future allocations would use the median to allocate the expected size up front, thus avoid grow work.
Some thoughts from initial discussions:
- Perhaps rather than tracking allocation sites, we track grow sites. Containers would still need to grow once, but we'd expect the first growth to jump up to the expected maximum size.
- Slice allocations that specify a capacity likely need to skip this optimization in order to maintain compatibility. IMO, this is a good idea anyway, as it provides as way for authors to specify a precise capacity when they know more precisely than the median (e.g., a capacity based on the length of another slice, such as in cmd/compile: pre-allocate a slice of provable length #64595).
Partially related to this: when growing, should we always align up to fill the entire size class. Leaving extra space in the size class is pure waste.-> already done: https://cs.opensource.google/go/go/+/master:src/runtime/slice.go;l=218;drc=d6ef98b8fa4851f025779ef4ade084d63290de2a