[go] context: implement Context.Value using iteration rather than recursion
Richard Oudkerk (Gerrit)
Richard Oudkerk has uploaded this change for review.
context: implement Context.Value using iteration rather than recursion
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)
Change-Id: I6bdeb234c979fb8fd6bfb91fd345cb5038f52c75
---
M src/context/context.go
1 file changed, 28 insertions(+), 2 deletions(-)
diff --git a/src/context/context.go b/src/context/context.go
index 733c5f5..57de5eb 100644
--- a/src/context/context.go
+++ b/src/context/context.go
@@ -352,7 +352,7 @@
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 @@
if c.key == key {
return c.val
}
- return c.Context.Value(key)
+ return value(c.Context, key)
+}
+
+func value(ctx Context, key interface{}) interface{} {
+ for {
+ switch tCtx := ctx.(type) {
+ case *valueCtx:
+ if key == tCtx.key {
+ return tCtx.val
+ }
+ ctx = tCtx.Context
+ case *cancelCtx:
+ if key == &cancelCtxKey {
+ return (*cancelCtx)(tCtx) // Redundant cast to confirm underlying type.
+ }
+ ctx = tCtx.Context
+ case *timerCtx:
+ if key == &cancelCtxKey {
+ return (*cancelCtx)(&tCtx.cancelCtx) // Redundant cast to confirm underlying type.
+ }
+ ctx = tCtx.Context
+ case *emptyCtx:
+ return nil
+ default:
+ return ctx.Value(key)
+ }
+ }
}
To view, visit change 335790. To unsubscribe, or for help writing mail filters, visit settings.
Richard Oudkerk (Gerrit)
Richard Oudkerk uploaded patch set #2 to this change.
Fixes #47292
Change-Id: I6bdeb234c979fb8fd6bfb91fd345cb5038f52c75
---
M src/context/context.go
1 file changed, 28 insertions(+), 2 deletions(-)
To view, visit change 335790. To unsubscribe, or for help writing mail filters, visit settings.
Ian Lance Taylor (Gerrit)
Attention is currently required from: Richard Oudkerk, Damien Neil, Sameer Ajmani.
Patch set 2:Run-TryBot +1
Rob Pike (Gerrit)
Attention is currently required from: Richard Oudkerk, Damien Neil, Sameer Ajmani.
Patch set 2:Code-Review -1
1 comment:
Patchset:
See comment on issue.
To view, visit change 335790. To unsubscribe, or for help writing mail filters, visit settings.
Damien Neil (Gerrit)
Attention is currently required from: Rob Pike, Sameer Ajmani.
Patch set 2:Run-TryBot +1Code-Review +1Trust +1
1 comment:
Patchset:
Are you still -1 on this, Rob?
I agree that we don't want to avoid recursion in general, but I think the iterative approach is reasonable in this case.
To view, visit change 335790. To unsubscribe, or for help writing mail filters, visit settings.
Rob Pike (Gerrit)
Attention is currently required from: Rob Pike, Sameer Ajmani.
Rob Pike removed a vote from this change.
To view, visit change 335790. To unsubscribe, or for help writing mail filters, visit settings.
Ian Lance Taylor (Gerrit)
Attention is currently required from: Richard Oudkerk, Rob Pike, Sameer Ajmani.
4 comments:
File src/context/context.go:
Patch Set #2, Line 569:
func value(ctx Context, key interface{}) interface{} {In this file variables of type Context appear to be named c. I know that's not the convention in other packages, but it seems that we should do the same here.
Patch Set #2, Line 571:
switch tCtx := ctx.(type) {In this kind of type switch it's routine to write
switch ctx := ctx.(type)
or given the above commentswitch c := c.(type)
and then only refer to ctx below. This ensures that there is no possible confusion between the general ctx and the type-specific one.
Patch Set #2, Line 579:
return (*cancelCtx)(tCtx) // Redundant cast to confirm underlying type.This type conversion is truly redundant. The type switch ensures that the type of tCtx here is *cancelCtx. I think we should remove the type conversion and the comment.
Patch Set #2, Line 584:
return (*cancelCtx)(&tCtx.cancelCtx) // Redundant cast to confirm underlying type.Here again the type conversion is not needed.
To view, visit change 335790. To unsubscribe, or for help writing mail filters, visit settings.
Richard Oudkerk (Gerrit)
Attention is currently required from: Richard Oudkerk, Rob Pike, Sameer Ajmani.
Richard Oudkerk uploaded patch set #3 to this change.
context: implement Context.Value using iteration rather than recursion
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
M src/context/benchmark_test.go
2 files changed, 121 insertions(+), 2 deletions(-)
To view, visit change 335790. To unsubscribe, or for help writing mail filters, visit settings.
Richard Oudkerk (Gerrit)
Attention is currently required from: Ian Lance Taylor, Rob Pike, Sameer Ajmani.
5 comments:
Patchset:
I have folded the benchmarks from https://go-review.googlesource.com/c/go/+/335789/1 into this change.
File src/context/context.go:
Patch Set #2, Line 569:
func value(ctx Context, key interface{}) interface{} {
In this file variables of type Context appear to be named c. […]
Done
Patch Set #2, Line 571:
switch tCtx := ctx.(type) {
In this kind of type switch it's routine to write […]
On lines 576, 581, 586 we need to update the ctx variable. But we can't if we shadow it inside the switch.
I have renamed the function parameter to c and the switch variable to ctx.
Patch Set #2, Line 579:
return (*cancelCtx)(tCtx) // Redundant cast to confirm underlying type.
This type conversion is truly redundant. […]
Done
Patch Set #2, Line 584:
return (*cancelCtx)(&tCtx.cancelCtx) // Redundant cast to confirm underlying type.Here again the type conversion is not needed.
Done
To view, visit change 335790. To unsubscribe, or for help writing mail filters, visit settings.
Ian Lance Taylor (Gerrit)
Attention is currently required from: Richard Oudkerk, Rob Pike, Sameer Ajmani.
Patch set 3:Run-TryBot +1
Ian Lance Taylor (Gerrit)
Attention is currently required from: Richard Oudkerk, Rob Pike, Sameer Ajmani.
Patch set 3:Code-Review +2
1 comment:
Patchset:
Thanks.
To view, visit change 335790. To unsubscribe, or for help writing mail filters, visit settings.
Ian Lance Taylor (Gerrit)
Ian Lance Taylor submitted this change.
Reviewed-on: https://go-review.googlesource.com/c/go/+/335790
Run-TryBot: Ian Lance Taylor <ia...@golang.org>
TryBot-Result: Go Bot <go...@golang.org>
Reviewed-by: Ian Lance Taylor <ia...@golang.org>
Trust: Damien Neil <dn...@google.com>
---
M src/context/context.go
M src/context/benchmark_test.go
2 files changed, 126 insertions(+), 2 deletions(-)
diff --git a/src/context/benchmark_test.go b/src/context/benchmark_test.go
index 69d75ff..144f473 100644
--- a/src/context/benchmark_test.go
+++ b/src/context/benchmark_test.go
@@ -152,3 +152,39 @@
}
})
}
+
+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 733c5f5..a9e1470 100644
--- a/src/context/context.go
+++ b/src/context/context.go
@@ -352,7 +352,7 @@
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 @@
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)
+ }
+ }
}
To view, visit change 335790. To unsubscribe, or for help writing mail filters, visit settings.