From afe43f1e5e0d256341689195454527726b26ccae Mon Sep 17 00:00:00 2001 From: roudkerk Date: Mon, 19 Jul 2021 12:49:57 +0100 Subject: [PATCH] context: implement Context.Value using iteration rather than recursion MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit In profiles of a production server, 2.3% of CPU time is spent in runtime.newstack for stacks with 12 or more chained Context.Value calls. Using iteration will avoid some needless stack resizes. When calling Context.Value in the same goroutine (see DeepValueSameGoRoutine) , no stack resizing is needed (after warming up), and this change reduces time/op by around 10%. The time to start a new goroutine and call Context.Value (see DeepValueNewGoRoutine) is reduced by over 75% if a stack resize is needed. If you factor out the overhead of starting the goroutine (about 960ns) then, avoiding the stack resize saves about 95%. ``` name old time/op new time/op delta CommonParentCancel-12 960ns ± 1% 958ns ± 1% ~ (p=0.561 n=9+9) WithTimeout/concurrency=40-12 1.31µs ± 2% 1.29µs ± 6% ~ (p=0.305 n=9+10) WithTimeout/concurrency=4000-12 1.30µs ± 2% 1.30µs ± 2% ~ (p=0.343 n=10+10) WithTimeout/concurrency=400000-12 1.03µs ± 1% 1.02µs ± 2% ~ (p=0.213 n=9+9) CancelTree/depth=1/Root=Background-12 123ns ± 5% 126ns ± 2% +2.61% (p=0.023 n=10+9) CancelTree/depth=1/Root=OpenCanceler-12 781ns ± 4% 806ns ± 4% +3.20% (p=0.022 n=9+10) CancelTree/depth=1/Root=ClosedCanceler-12 370ns ± 4% 369ns ± 3% ~ (p=0.497 n=9+10) CancelTree/depth=10/Root=Background-12 4.74µs ± 4% 4.78µs ± 3% ~ (p=0.516 n=10+10) CancelTree/depth=10/Root=OpenCanceler-12 6.31µs ± 4% 6.29µs ± 4% ~ (p=1.000 n=10+10) CancelTree/depth=10/Root=ClosedCanceler-12 2.10µs ± 5% 2.09µs ± 5% ~ (p=0.839 n=10+10) CancelTree/depth=100/Root=Background-12 51.0µs ± 3% 51.2µs ± 2% ~ (p=0.631 n=10+10) CancelTree/depth=100/Root=OpenCanceler-12 60.8µs ± 1% 61.6µs ± 4% ~ (p=0.274 n=8+10) CancelTree/depth=100/Root=ClosedCanceler-12 19.3µs ± 2% 19.0µs ± 3% ~ (p=0.123 n=10+10) CancelTree/depth=1000/Root=Background-12 504µs ± 4% 512µs ± 4% ~ (p=0.123 n=10+10) CancelTree/depth=1000/Root=OpenCanceler-12 615µs ± 6% 619µs ± 4% ~ (p=1.000 n=10+10) CancelTree/depth=1000/Root=ClosedCanceler-12 190µs ± 2% 192µs ± 3% ~ (p=0.190 n=9+9) CheckCanceled/Err-12 12.1ns ± 2% 12.1ns ± 2% ~ (p=0.615 n=10+10) CheckCanceled/Done-12 7.27ns ± 1% 7.26ns ± 1% ~ (p=0.698 n=10+10) ContextCancelDone-12 1.03ns ± 1% 1.03ns ± 1% ~ (p=0.474 n=9+9) DeepValueNewGoRoutine/depth=10-12 1.02µs ± 3% 0.99µs ± 2% -3.41% (p=0.000 n=10+10) DeepValueNewGoRoutine/depth=20-12 1.11µs ± 3% 1.08µs ± 2% -2.51% (p=0.004 n=10+10) DeepValueNewGoRoutine/depth=30-12 5.55µs ±10% 1.17µs ± 4% -78.91% (p=0.000 n=10+10) DeepValueNewGoRoutine/depth=50-12 5.70µs ±13% 1.35µs ± 2% -76.31% (p=0.000 n=10+10) DeepValueNewGoRoutine/depth=100-12 9.69µs ± 4% 1.82µs ± 2% -81.18% (p=0.000 n=10+10) DeepValueSameGoRoutine/depth=10-12 54.2ns ± 2% 46.8ns ± 2% -13.71% (p=0.000 n=9+9) DeepValueSameGoRoutine/depth=20-12 109ns ± 2% 97ns ± 2% -11.11% (p=0.000 n=10+10) DeepValueSameGoRoutine/depth=30-12 155ns ± 3% 140ns ± 1% -9.49% (p=0.000 n=10+10) DeepValueSameGoRoutine/depth=50-12 256ns ± 2% 226ns ± 2% -11.83% (p=0.000 n=10+10) DeepValueSameGoRoutine/depth=100-12 492ns ± 3% 442ns ± 1% -10.15% (p=0.000 n=10+10) ``` Fixes #47292 Change-Id: I6bdeb234c979fb8fd6bfb91fd345cb5038f52c75 Reviewed-on: https://go-review.googlesource.com/c/go/+/335790 Run-TryBot: Ian Lance Taylor TryBot-Result: Go Bot Reviewed-by: Ian Lance Taylor Trust: Damien Neil --- src/context/benchmark_test.go | 36 +++++++++++++++++++++++++++++++++++ src/context/context.go | 30 +++++++++++++++++++++++++++-- 2 files changed, 64 insertions(+), 2 deletions(-) diff --git a/src/context/benchmark_test.go b/src/context/benchmark_test.go index 69d75fff18..144f473a44 100644 --- a/src/context/benchmark_test.go +++ b/src/context/benchmark_test.go @@ -152,3 +152,39 @@ func BenchmarkContextCancelDone(b *testing.B) { } }) } + +func BenchmarkDeepValueNewGoRoutine(b *testing.B) { + for _, depth := range []int{10, 20, 30, 50, 100} { + ctx := Background() + for i := 0; i < depth; i++ { + ctx = WithValue(ctx, i, i) + } + + b.Run(fmt.Sprintf("depth=%d", depth), func(b *testing.B) { + for i := 0; i < b.N; i++ { + var wg sync.WaitGroup + wg.Add(1) + go func() { + defer wg.Done() + ctx.Value(-1) + }() + wg.Wait() + } + }) + } +} + +func BenchmarkDeepValueSameGoRoutine(b *testing.B) { + for _, depth := range []int{10, 20, 30, 50, 100} { + ctx := Background() + for i := 0; i < depth; i++ { + ctx = WithValue(ctx, i, i) + } + + b.Run(fmt.Sprintf("depth=%d", depth), func(b *testing.B) { + for i := 0; i < b.N; i++ { + ctx.Value(-1) + } + }) + } +} diff --git a/src/context/context.go b/src/context/context.go index 733c5f56d9..a9e14703fd 100644 --- a/src/context/context.go +++ b/src/context/context.go @@ -352,7 +352,7 @@ func (c *cancelCtx) Value(key interface{}) interface{} { if key == &cancelCtxKey { return c } - return c.Context.Value(key) + return value(c.Context, key) } func (c *cancelCtx) Done() <-chan struct{} { @@ -563,5 +563,31 @@ func (c *valueCtx) Value(key interface{}) interface{} { if c.key == key { return c.val } - return c.Context.Value(key) + return value(c.Context, key) +} + +func value(c Context, key interface{}) interface{} { + for { + switch ctx := c.(type) { + case *valueCtx: + if key == ctx.key { + return ctx.val + } + c = ctx.Context + case *cancelCtx: + if key == &cancelCtxKey { + return c + } + c = ctx.Context + case *timerCtx: + if key == &cancelCtxKey { + return &ctx.cancelCtx + } + c = ctx.Context + case *emptyCtx: + return nil + default: + return c.Value(key) + } + } } -- 2.48.1