context: cancelCtx should avoid to use map to store child cancelers

[tdakkota]

What version of Go are you using (go version)?

$ go version
go version go1.17 windows/amd64

Does this issue reproduce with the latest release?

Yes.

What operating system and processor architecture are you using (go env)?

go env Output

$ go env
set GO111MODULE=on
set GOARCH=amd64
set GOBIN=
set GOCACHE=C:\Users\tdakkota\AppData\Local\go-build
set GOENV=C:\Users\tdakkota\AppData\Roaming\go\env
set GOEXE=.exe
set GOEXPERIMENT=
set GOFLAGS=
set GOHOSTARCH=amd64
set GOHOSTOS=windows
set GOINSECURE=
set GOMODCACHE=C:\Users\tdakkota\go\pkg\mod
set GOOS=windows
set GOPATH=C:\Users\tdakkota\go
set GOPROXY=https://proxy.golang.org,direct
set GOROOT=C:\Go
set GOSUMDB=sum.golang.org
set GOTMPDIR=
set GOTOOLDIR=C:\Go\pkg\tool\windows_amd64
set GOVCS=
set GOVERSION=go1.17
set GCCGO=gccgo
set AR=ar
set CC=gcc
set CXX=g++
set CGO_ENABLED=1
set CGO_CFLAGS=-g -O2
set CGO_CPPFLAGS=
set CGO_CXXFLAGS=-g -O2
set CGO_FFLAGS=-g -O2
set CGO_LDFLAGS=-g -O2
set PKG_CONFIG=pkg-config
set GOGCCFLAGS=-m64 -mthreads -fmessage-length=0 -fdebug-prefix-map=C:\Users\tdakkota\AppData\Local\Temp\go-build1627783593=/tmp/go-build -gno-record-gcc-switches

What did you do?

Currently, cancelCtx uses map to store all child contexts

go/src/context/context.go

Lines 265 to 275 in c85695a

	p.mu.Lock()
	if p.err != nil {
	// parent has already been canceled
	child.cancel(false, p.err)
	} else {
	if p.children == nil {
	p.children = make(map[canceler]struct{})
	}
	p.children[child] = struct{}{}
	}
	p.mu.Unlock()

But it causes map allocation and may be ineffective if there is only one child context. This case is quite common, at least in my projects.

I made a simple patch which stores first child in separate field (tdakkota@1c4f3b2) and see an improvement.
Benchmark result:

goos: windows
goarch: amd64
pkg: context
cpu: Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz

name                                          old time/op    new time/op    delta
CommonParentCancel-12                            631ns ± 2%     578ns ± 2%   -8.36%  (p=0.008 n=5+5)
WithTimeout/concurrency=40-12                   1.01µs ± 1%    1.08µs ± 2%   +6.04%  (p=0.008 n=5+5)
WithTimeout/concurrency=4000-12                 1.16µs ±40%    0.97µs ± 4%     ~     (p=0.548 n=5+5)
WithTimeout/concurrency=400000-12                917ns ±21%     863ns ± 1%     ~     (p=0.690 n=5+5)
CancelTree/depth=1/Root=Background-12           60.1ns ± 1%    71.2ns ± 1%  +18.35%  (p=0.008 n=5+5)
CancelTree/depth=1/Root=OpenCanceler-12          435ns ± 1%     296ns ± 1%  -31.88%  (p=0.008 n=5+5)
CancelTree/depth=1/Root=ClosedCanceler-12        217ns ± 1%     230ns ± 1%   +6.03%  (p=0.008 n=5+5)
CancelTree/depth=10/Root=Background-12          2.39µs ± 1%    1.44µs ± 1%  -39.65%  (p=0.008 n=5+5)
CancelTree/depth=10/Root=OpenCanceler-12        3.36µs ± 0%    1.98µs ± 1%  -40.95%  (p=0.008 n=5+5)
CancelTree/depth=10/Root=ClosedCanceler-12      1.23µs ± 1%    1.33µs ± 0%   +7.85%  (p=0.008 n=5+5)
CancelTree/depth=100/Root=Background-12         25.5µs ± 1%    15.3µs ± 2%  -40.05%  (p=0.008 n=5+5)
CancelTree/depth=100/Root=OpenCanceler-12       32.6µs ± 1%    19.6µs ±12%  -39.70%  (p=0.008 n=5+5)
CancelTree/depth=100/Root=ClosedCanceler-12     11.3µs ± 1%    12.2µs ± 1%   +7.57%  (p=0.008 n=5+5)
CancelTree/depth=1000/Root=Background-12         259µs ± 1%     152µs ± 0%  -41.38%  (p=0.008 n=5+5)
CancelTree/depth=1000/Root=OpenCanceler-12       324µs ± 0%     190µs ± 1%  -41.49%  (p=0.008 n=5+5)
CancelTree/depth=1000/Root=ClosedCanceler-12     111µs ± 1%     119µs ± 1%   +7.23%  (p=0.008 n=5+5)
CheckCanceled/Err-12                            11.7ns ± 1%    11.7ns ± 0%     ~     (p=0.722 n=5+5)
CheckCanceled/Done-12                           5.61ns ± 1%    5.84ns ± 1%   +4.18%  (p=0.008 n=5+5)
ContextCancelDone-12                            0.91ns ± 5%    0.92ns ± 6%     ~     (p=0.421 n=5+5)
[Geo mean]                                      1.32µs         1.11µs       -15.86%

name                                          old alloc/op   new alloc/op   delta
CommonParentCancel-12                            80.0B ± 0%     96.0B ± 0%  +20.00%  (p=0.008 n=5+5)
WithTimeout/concurrency=40-12                   2.08kB ± 0%    2.24kB ± 0%   +7.69%  (p=0.008 n=5+5)
WithTimeout/concurrency=4000-12                 2.08kB ± 0%    2.24kB ± 0%   +7.69%  (p=0.016 n=4+5)
WithTimeout/concurrency=400000-12               2.09kB ± 1%    2.24kB ± 0%   +7.45%  (p=0.008 n=5+5)
CancelTree/depth=1/Root=Background-12            80.0B ± 0%     96.0B ± 0%  +20.00%  (p=0.008 n=5+5)
CancelTree/depth=1/Root=OpenCanceler-12           448B ± 0%      288B ± 0%  -35.71%  (p=0.008 n=5+5)
CancelTree/depth=1/Root=ClosedCanceler-12         160B ± 0%      192B ± 0%  +20.00%  (p=0.008 n=5+5)
CancelTree/depth=10/Root=Background-12          3.39kB ± 0%    1.82kB ± 0%  -46.23%  (p=0.008 n=5+5)
CancelTree/depth=10/Root=OpenCanceler-12        3.76kB ± 0%    2.02kB ± 0%  -46.38%  (p=0.008 n=5+5)
CancelTree/depth=10/Root=ClosedCanceler-12        880B ± 0%     1056B ± 0%  +20.00%  (p=0.008 n=5+5)
CancelTree/depth=100/Root=Background-12         36.5kB ± 0%    19.1kB ± 0%  -47.68%  (p=0.008 n=5+5)
CancelTree/depth=100/Root=OpenCanceler-12       36.9kB ± 0%    19.3kB ± 0%  -47.68%  (p=0.008 n=5+5)
CancelTree/depth=100/Root=ClosedCanceler-12     8.08kB ± 0%    9.70kB ± 0%  +20.00%  (p=0.008 n=5+5)
CancelTree/depth=1000/Root=Background-12         368kB ± 0%     192kB ± 0%  -47.81%  (p=0.008 n=5+5)
CancelTree/depth=1000/Root=OpenCanceler-12       368kB ± 0%     192kB ± 0%  -47.81%  (p=0.008 n=5+5)
CancelTree/depth=1000/Root=ClosedCanceler-12    80.1kB ± 0%    96.1kB ± 0%  +20.00%  (p=0.008 n=5+5)
CheckCanceled/Err-12                             0.00B          0.00B          ~     (all equal)
CheckCanceled/Done-12                            0.00B          0.00B          ~     (all equal)
ContextCancelDone-12                             0.00B          0.00B          ~     (all equal)
[Geo mean]                                      4.06kB         3.37kB       -16.93%

name                                          old allocs/op  new allocs/op  delta
CommonParentCancel-12                             2.00 ± 0%      2.00 ± 0%     ~     (all equal)
WithTimeout/concurrency=40-12                     40.0 ± 0%      40.0 ± 0%     ~     (all equal)
WithTimeout/concurrency=4000-12                   40.0 ± 0%      40.0 ± 0%     ~     (all equal)
WithTimeout/concurrency=400000-12                 40.0 ± 0%      40.0 ± 0%     ~     (all equal)
CancelTree/depth=1/Root=Background-12             2.00 ± 0%      2.00 ± 0%     ~     (all equal)
CancelTree/depth=1/Root=OpenCanceler-12           7.00 ± 0%      5.00 ± 0%  -28.57%  (p=0.008 n=5+5)
CancelTree/depth=1/Root=ClosedCanceler-12         4.00 ± 0%      4.00 ± 0%     ~     (all equal)
CancelTree/depth=10/Root=Background-12            47.0 ± 0%      29.0 ± 0%  -38.30%  (p=0.008 n=5+5)
CancelTree/depth=10/Root=OpenCanceler-12          52.0 ± 0%      32.0 ± 0%  -38.46%  (p=0.008 n=5+5)
CancelTree/depth=10/Root=ClosedCanceler-12        22.0 ± 0%      22.0 ± 0%     ~     (all equal)
CancelTree/depth=100/Root=Background-12            497 ± 0%       299 ± 0%  -39.84%  (p=0.008 n=5+5)
CancelTree/depth=100/Root=OpenCanceler-12          502 ± 0%       302 ± 0%  -39.84%  (p=0.008 n=5+5)
CancelTree/depth=100/Root=ClosedCanceler-12        202 ± 0%       202 ± 0%     ~     (all equal)
CancelTree/depth=1000/Root=Background-12         5.00k ± 0%     3.00k ± 0%  -39.98%  (p=0.008 n=5+5)
CancelTree/depth=1000/Root=OpenCanceler-12       5.00k ± 0%     3.00k ± 0%  -39.98%  (p=0.008 n=5+5)
CancelTree/depth=1000/Root=ClosedCanceler-12     2.00k ± 0%     2.00k ± 0%     ~     (all equal)
CheckCanceled/Err-12                              0.00           0.00          ~     (all equal)
CheckCanceled/Done-12                             0.00           0.00          ~     (all equal)
ContextCancelDone-12                              0.00           0.00          ~     (all equal)
[Geo mean]                                        74.9           60.7       -18.85%

Any thoughts?

[tdakkota]

CC'ing @neild @Sajmani according to https://dev.golang.org/owners.