context: doc of WithValue should mention context is not data store

[gmichelo]

Hello everybody,

go/src/context/context.go

Lines 520 to 525 in 9195948

	func (c *valueCtx) Value(key interface{}) interface{} {
	if c.key == key {
	return c.val
	}
	return c.Context.Value(key)
	}

Implementation of valueCtx.Value in context package is recursive function. That means its performance decreases at least linearly with the number of values stored in the context. Moreover, it is easily subject to stack overflow if user stores way too many values.

Documentation does not give any advice on how context.WithValue should be used, especially w.r.t. performance. IMHO, it would be better to update the doc in order to:

1. Discourage the user from using the context.Context as data store;
2. Suggest the user to just store things like map or struct, which let the user decide how to store data without impacting valueCtx.Value performance.

CC @mvdan

[mvdan]

I agree that the godoc should more clearly suggest what to do here. One thread that seems to cover this is https://stackoverflow.com/questions/40379960/golang-context-withvalue-how-to-add-several-key-value-pairs.

[mvdan]

/cc @Sajmani @bradfitz as per https://dev.golang.org/owners

[ericlagergren]

Just a drive by question: is there a particular reason why it’s recursive and not a loop?

[johngibb]

@ericlagergren:

Just a drive by question: is there a particular reason why it’s recursive and not a loop?

I don't think it could be written as a loop, since there's no way to get a context's parent context.

[wuweiweiwu]

Hi! Can I pick this up?

[gmichelo]

@wuweiweiwu, that's fine for me.

@ericlagergren, I think they preferred to have a simple and maintainable implementation over an efficient one. As we should mention in doc, context.Context is not meant for efficient store and lookup.

Just for fun, I experimented with the code a bit and benchmarked few options. As far as I can see, there are thee alternative implementations, with different trade-offs in terms of performance. Here is a summary of my analysis.

1. Linked list of key-value pairs that links current Context to parent one and all the ancestors. Recursive call is substituted with a linear search on this list.

   • Pros: still simple implementation; O(1) insertion time in context.WithValue; O(N) lookup time in valueCtx.Value.
   • Cons: higher pressure on Garbage Collector; list traversal is not as efficient as slice would be.

2. Slice of key-value pairs that stores current Context's key-value pair and all the ancestors' ones. Recursive call is substituted with a linear search on this slice. Every time a new context.Context is created by context.WithValue, the parent context's slice is copied into a new one and new key-value pair is appended in it.

   • Pros: O(N) lookup time in valueCtx.Value; slice traversal is efficient.
   • Cons: O(N) insertion time in context.WithValue due to copy of previous slice; higher memory allocations and pressure on Garbage Collector.

3. Map of key-value pairs that stores current Context's key-value pair and all the ancestors' ones. Recursive call is substituted with a map lookup. Every time a new context.Context is created by context.WithValue, the parent context's map is copied into a new one and new key-value pair is inserted in it.

   • Pros: O(1) lookup time in valueCtx.Value.
   • Cons: O(N) insertion time in context.WithValue due to copy of previous map; higher memory allocations and pressure on Garbage Collector.

[Sajmani]

Hello, as others have mentioned, we could certainly optimize the Context value lookup if and when that becomes a demonstrated performance bottleneck. I think that's preferable to documenting the current O(depth of context tree) lookup behavior, which is an implementation detail.

[johngibb]

I just wanted to reiterate and elaborate on my prior point: because context.Context is an interface, it's going to be tricky to find a way to "optimize". There's no way using the current interface for context.WithValue to access the parent context's map, nor even enumerate all of the values present within it.