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.

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

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

@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.

Hi! Can I pick this up?

@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.

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.

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.