runtime/pprof: reduce label overhead

Switch labelMap from map[string]string to use LabelSet as a data
structure. Optimize Labels() for the case where the keys are given in
sorted order without duplicates.

This is primarily motivated by reducing the overhead of distributed
tracing systems that use pprof labels. We have encountered cases where
users complained about the overhead relative to the rest of our
distributed tracing library code. Additionally, we see this as an
opportunity to free up hundreds of CPU cores across our fleet.

A secondary motivation is eBPF profilers that try to access pprof
labels. The current map[string]string requires them to implement Go map
access in eBPF, which is non-trivial. With the enablement of swiss maps,
this complexity is only increasing. The slice data structure introduced
in this CL will greatly lower the implementation complexity for eBPF
profilers in the future. But to be clear: This change does not imply
that the pprof label mechanism is now a stable ABI. They are still an
implementation detail and may change again in the future.

goos: darwin
goarch: arm64
pkg: runtime/pprof
cpu: Apple M1 Max
                                   │ baseline.txt │             patch1.txt              │
                                   │    sec/op    │   sec/op     vs base                │
Labels/set-one-10                    153.50n ± 3%   75.00n ± 1%  -51.14% (p=0.000 n=10)
Labels/merge-one-10                   187.8n ± 1%   128.8n ± 1%  -31.42% (p=0.000 n=10)
Labels/overwrite-one-10               193.1n ± 2%   102.0n ± 1%  -47.18% (p=0.000 n=10)
Labels/ordered/set-many-10            502.6n ± 4%   146.1n ± 2%  -70.94% (p=0.000 n=10)
Labels/ordered/merge-many-10          516.3n ± 2%   238.1n ± 1%  -53.89% (p=0.000 n=10)
Labels/ordered/overwrite-many-10      569.3n ± 4%   247.6n ± 2%  -56.51% (p=0.000 n=10)
Labels/unordered/set-many-10          488.9n ± 2%   308.3n ± 3%  -36.94% (p=0.000 n=10)
Labels/unordered/merge-many-10        523.6n ± 1%   258.5n ± 1%  -50.64% (p=0.000 n=10)
Labels/unordered/overwrite-many-10    571.4n ± 1%   412.1n ± 2%  -27.89% (p=0.000 n=10)
geomean                               366.8n        186.9n       -49.05%

                                   │ baseline.txt │             patch1b.txt              │
                                   │     B/op     │     B/op      vs base                │
Labels/set-one-10                      424.0 ± 0%     104.0 ± 0%  -75.47% (p=0.000 n=10)
Labels/merge-one-10                    424.0 ± 0%     200.0 ± 0%  -52.83% (p=0.000 n=10)
Labels/overwrite-one-10                424.0 ± 0%     136.0 ± 0%  -67.92% (p=0.000 n=10)
Labels/ordered/set-many-10            1344.0 ± 0%     392.0 ± 0%  -70.83% (p=0.000 n=10)
Labels/ordered/merge-many-10          1184.0 ± 0%     712.0 ± 0%  -39.86% (p=0.000 n=10)
Labels/ordered/overwrite-many-10      1056.0 ± 0%     712.0 ± 0%  -32.58% (p=0.000 n=10)
Labels/unordered/set-many-10          1344.0 ± 0%     712.0 ± 0%  -47.02% (p=0.000 n=10)
Labels/unordered/merge-many-10        1184.0 ± 0%     712.0 ± 0%  -39.86% (p=0.000 n=10)
Labels/unordered/overwrite-many-10   1.031Ki ± 0%   1.008Ki ± 0%   -2.27% (p=0.000 n=10)
geomean                                843.1          405.1       -51.95%

                                   │ baseline.txt │             patch1b.txt              │
                                   │  allocs/op   │ allocs/op   vs base                  │
Labels/set-one-10                      5.000 ± 0%   3.000 ± 0%  -40.00% (p=0.000 n=10)
Labels/merge-one-10                    5.000 ± 0%   5.000 ± 0%        ~ (p=1.000 n=10) ¹
Labels/overwrite-one-10                5.000 ± 0%   4.000 ± 0%  -20.00% (p=0.000 n=10)
Labels/ordered/set-many-10             8.000 ± 0%   3.000 ± 0%  -62.50% (p=0.000 n=10)
Labels/ordered/merge-many-10           8.000 ± 0%   5.000 ± 0%  -37.50% (p=0.000 n=10)
Labels/ordered/overwrite-many-10       7.000 ± 0%   4.000 ± 0%  -42.86% (p=0.000 n=10)
Labels/unordered/set-many-10           8.000 ± 0%   4.000 ± 0%  -50.00% (p=0.000 n=10)
Labels/unordered/merge-many-10         8.000 ± 0%   5.000 ± 0%  -37.50% (p=0.000 n=10)
Labels/unordered/overwrite-many-10     7.000 ± 0%   5.000 ± 0%  -28.57% (p=0.000 n=10)
geomean                                6.640        4.143       -37.60%
¹ all samples are equal

Change-Id: Ie68e960a25c2d97bcfb6239dc481832fa8a39754
Reviewed-on: https://go-review.googlesource.com/c/go/+/574516
Reviewed-by: Michael Knyszek <mknyszek@google.com>
Auto-Submit: Felix Geisendörfer <felix.geisendoerfer@datadoghq.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Michael Pratt <mpratt@google.com>

1 files changed, 2 insertions, 2 deletions

diff --git a/src/runtime/pprof/pprof.go b/src/runtime/pprof/pprof.go
index b8458367f8..f6b4a5c367 100644
--- a/src/runtime/pprof/pprof.go
+++ b/src/runtime/pprof/pprof.go
@@ -516,8 +516,8 @@ func printCountProfile(w io.Writer, debug int, name string, p countProfile) erro
 		var labels func()
 		if p.Label(idx) != nil {
 			labels = func() {
-				for k, v := range *p.Label(idx) {
-					b.pbLabel(tagSample_Label, k, v, 0)
+				for _, lbl := range p.Label(idx).list {
+					b.pbLabel(tagSample_Label, lbl.key, lbl.value, 0)
 				}
 			}
 		}