Go's net/http.Headers

One probably knows that net/http.Headers is no more than map[string][]string with extra specific methods. A usual way to initialize and populate such data-structure from an external representation is something like that:

type Header map[string][]string

func (h Header) Add(key, val string) {
    if val == "" {
        return
    }
    h[key] = append(h[key], val)
}

func main() {
    h := make(Header)
    h.Add("Host", "example.com")
    h.Add("Via", "a.example.com")
    h.Add("Via", "b.example.com")
}

From the code above, one can notice that we allocated a new slice of strings for every unique key that we added to headers. For things like HTTP headers, that’re automatically parsed for every incoming request, this bunch of tiny allocations is something we’d like to avoid.

I was curious to know if Go’s standard library cares about that.

Looking at the implementation of net/textproto.Reader.ReadMIMEHeader(), which is used in the standard HTTP server, or Go 1.13’s new net/http.Header.Clone(), it turned out they solve the problem quite elegantly.

We know that for a majority of cases, HTTP headers are an immutable key-value pair, where most of the keys have a single value. Instead of allocating a separate slice for a unique key, Go pre-allocates a continues slice for values and refers to a sub-slice of this slice for all keys.

Knowing that, we can refactor the initial Header.Add as the following:

type Header map[string][]string

func (h Header) add(vv []string, key, val string) []string {
    if val == "" { ··· }

    // fast path for KV pair of a single value
    if h[key] == nil {
        vv = append(vv, value)
        h[key] = vv[:1:1]
        return vv[1:]
    }

    // slow path, when KV pair has two or more values
    h[key] = append(h[key], val)
    return vv
}

func main() {
    h := make(Header)
    // net/textprotocol pre-counts total number of request's headers
    // to allocate the slice of known capacity
    vv := make([]string, 0)

    vv = h.add(vv, "Host", "example.com")
    vv = h.add(vv, "Via", "a.example.com")
}

Note that we use vv[:1:1] to create a sub-slice of a fixed capacity (length 1, capacity 1).

If there is a KV-pair that has several values, e.g. “Via” header, Add will allocate a separate slice for that key, doubling its capacity.