[net] http2/hpack: key the encoder lookup table on the name alone
0 views
Skip to first unread message
Gerrit Bot (Gerrit)
7:11 PM (3 hours ago) 7:11 PM
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Gerrit Bot has uploaded the change for review![]( "Open in Gerrit")
Commit message
http2/hpack: key the encoder lookup table on the name alone
The encoder's lookup table kept two maps, one keyed on the header name and one
on the name/value pair, and `search` consulted both. A field whose name is in
the table but whose value is not hashes the name twice and the value once —
the shape most response headers take, since `content-type`, `content-length`,
`date` and `server` all match a static-table name and carry a value that is not
there.
Holding the entries for a name in one slice lets a lookup hash the name once and
settle the value by comparison, which is cheap because a name holds few entries:
the widest in the static table is `:status`, with seven.
```
goos: darwin
goarch: arm64
pkg: golang.org/x/net/http2/hpack
cpu: Apple M4
│ old │ new │
│ sec/op │ sec/op vs base │
EncoderSearchTable-10 4.364µ ± ∞ ¹ 3.538µ ± ∞ ¹ -18.93% (p=0.008 n=5)
EncoderWriteFieldResponse-10 176.9n ± ∞ ¹ 144.5n ± ∞ ¹ -18.32% (p=0.008 n=5)
```
`EncoderWriteFieldResponse` is added here: it encodes the block a server sends
for an ordinary response.
Allocation stays at zero, and one map replacing two removes 51 lines net across
the table, `buildMaps`, `addEntry`, `evictOldest`, the generator and the
generated static table.
Verified with the package's own tests, `-race`, and a temporary differential
test that drove a table through 300 rounds of random adds, evictions and
lookups, comparing `search` against a plain scan of `ents` on every step.
Fixes golang/go#80787
Change-Id: I20221c5f9eeacfd987e80330ff89880a8fa20586
GitHub-Last-Rev: 740b8598810d664c4fa1c6613ce0feb2aa9b838b
GitHub-Pull-Request: golang/net#257
Change diff
diff --git a/http2/hpack/encode_test.go b/http2/hpack/encode_test.go
index 05f12db..dacb71a 100644
--- a/http2/hpack/encode_test.go
+++ b/http2/hpack/encode_test.go
@@ -384,3 +384,28 @@
}
}
}
+
+// BenchmarkEncoderWriteFieldResponse encodes the header block a server sends
+// for an ordinary response, where most names are in the static table but their
+// values are not.
+func BenchmarkEncoderWriteFieldResponse(b *testing.B) {
+ fields := []HeaderField{
+ {Name: ":status", Value: "200"},
+ {Name: "content-type", Value: "text/plain; charset=utf-8"},
+ {Name: "content-length", Value: "13"},
+ {Name: "date", Value: "Mon, 08 Aug 2026 06:00:00 GMT"},
+ {Name: "server", Value: "example"},
+ {Name: "x-request-id", Value: "01HQ8Z7K3N5P9R2T4V6W8Y0A1B"},
+ }
+ var buf bytes.Buffer
+ e := NewEncoder(&buf)
+ b.ReportAllocs()
+ for i := 0; i < b.N; i++ {
+ buf.Reset()
+ for _, f := range fields {
+ if err := e.WriteField(f); err != nil {
+ b.Fatal(err)
+ }
+ }
+ }
+}
diff --git a/http2/hpack/gen.go b/http2/hpack/gen.go
index 0efa8e5..fd5aba7 100644
--- a/http2/hpack/gen.go
+++ b/http2/hpack/gen.go
@@ -81,26 +81,22 @@
{Name: "www-authenticate"},
}
-type pairNameValue struct {
- name, value string
+type tableEntry struct {
+ value string
+ id uint64
}
type byNameItem struct {
- name string
- id uint64
-}
-
-type byNameValueItem struct {
- pairNameValue
- id uint64
+ name string
+ entries []tableEntry
}
func headerFieldToString(f hpack.HeaderField) string {
return fmt.Sprintf("{Name: \"%s\", Value:\"%s\", Sensitive: %t}", f.Name, f.Value, f.Sensitive)
}
-func pairNameValueToString(v pairNameValue) string {
- return fmt.Sprintf("{name: \"%s\", value:\"%s\"}", v.name, v.value)
+func tableEntryToString(e tableEntry) string {
+ return fmt.Sprintf("{value: \"%s\", id: %d}", e.value, e.id)
}
const header = `
@@ -111,31 +107,30 @@
var staticTable = &headerFieldTable{
evictCount: 0,
- byName: map[string]uint64{
+ byName: map[string][]tableEntry{
`
//go:generate go run gen.go
func main() {
var bb bytes.Buffer
fmt.Fprintf(&bb, header)
- byName := make(map[string]uint64)
- byNameValue := make(map[pairNameValue]uint64)
+ byName := make(map[string][]tableEntry)
for index, entry := range staticTableEntries {
id := uint64(index) + 1
- byName[entry.Name] = id
- byNameValue[pairNameValue{entry.Name, entry.Value}] = id
+ byName[entry.Name] = append(byName[entry.Name], tableEntry{entry.Value, id})
}
- // Sort maps for deterministic generation.
+ // Sort for deterministic generation.
byNameItems := sortByName(byName)
- byNameValueItems := sortByNameValue(byNameValue)
for _, item := range byNameItems {
- fmt.Fprintf(&bb, "\"%s\":%d,\n", item.name, item.id)
- }
- fmt.Fprintf(&bb, "},\n")
- fmt.Fprintf(&bb, "byNameValue: map[pairNameValue]uint64{\n")
- for _, item := range byNameValueItems {
- fmt.Fprintf(&bb, "%s:%d,\n", pairNameValueToString(item.pairNameValue), item.id)
+ fmt.Fprintf(&bb, "\"%s\": {", item.name)
+ for k, e := range item.entries {
+ if k > 0 {
+ fmt.Fprintf(&bb, ", ")
+ }
+ fmt.Fprintf(&bb, "%s", tableEntryToString(e))
+ }
+ fmt.Fprintf(&bb, "},\n")
}
fmt.Fprintf(&bb, "},\n")
fmt.Fprintf(&bb, "ents: []HeaderField{\n")
@@ -147,24 +142,13 @@
genFile("static_table.go", &bb)
}
-func sortByNameValue(byNameValue map[pairNameValue]uint64) []byNameValueItem {
- var byNameValueItems []byNameValueItem
- for k, v := range byNameValue {
- byNameValueItems = append(byNameValueItems, byNameValueItem{k, v})
- }
- sort.Slice(byNameValueItems, func(i, j int) bool {
- return byNameValueItems[i].id < byNameValueItems[j].id
- })
- return byNameValueItems
-}
-
-func sortByName(byName map[string]uint64) []byNameItem {
+func sortByName(byName map[string][]tableEntry) []byNameItem {
var byNameItems []byNameItem
for k, v := range byName {
byNameItems = append(byNameItems, byNameItem{k, v})
}
sort.Slice(byNameItems, func(i, j int) bool {
- return byNameItems[i].id < byNameItems[j].id
+ return byNameItems[i].entries[0].id < byNameItems[j].entries[0].id
})
return byNameItems
}
diff --git a/http2/hpack/static_table.go b/http2/hpack/static_table.go
index 754a1eb..95b66c8 100644
--- a/http2/hpack/static_table.go
+++ b/http2/hpack/static_table.go
@@ -5,122 +5,59 @@
var staticTable = &headerFieldTable{
evictCount: 0,
- byName: map[string]uint64{
- ":authority": 1,
- ":method": 3,
- ":path": 5,
- ":scheme": 7,
- ":status": 14,
- "accept-charset": 15,
- "accept-encoding": 16,
- "accept-language": 17,
- "accept-ranges": 18,
- "accept": 19,
- "access-control-allow-origin": 20,
- "age": 21,
- "allow": 22,
- "authorization": 23,
- "cache-control": 24,
- "content-disposition": 25,
- "content-encoding": 26,
- "content-language": 27,
- "content-length": 28,
- "content-location": 29,
- "content-range": 30,
- "content-type": 31,
- "cookie": 32,
- "date": 33,
- "etag": 34,
- "expect": 35,
- "expires": 36,
- "from": 37,
- "host": 38,
- "if-match": 39,
- "if-modified-since": 40,
- "if-none-match": 41,
- "if-range": 42,
- "if-unmodified-since": 43,
- "last-modified": 44,
- "link": 45,
- "location": 46,
- "max-forwards": 47,
- "proxy-authenticate": 48,
- "proxy-authorization": 49,
- "range": 50,
- "referer": 51,
- "refresh": 52,
- "retry-after": 53,
- "server": 54,
- "set-cookie": 55,
- "strict-transport-security": 56,
- "transfer-encoding": 57,
- "user-agent": 58,
- "vary": 59,
- "via": 60,
- "www-authenticate": 61,
- },
- byNameValue: map[pairNameValue]uint64{
- {name: ":authority", value: ""}: 1,
- {name: ":method", value: "GET"}: 2,
- {name: ":method", value: "POST"}: 3,
- {name: ":path", value: "/"}: 4,
- {name: ":path", value: "/index.html"}: 5,
- {name: ":scheme", value: "http"}: 6,
- {name: ":scheme", value: "https"}: 7,
- {name: ":status", value: "200"}: 8,
- {name: ":status", value: "204"}: 9,
- {name: ":status", value: "206"}: 10,
- {name: ":status", value: "304"}: 11,
- {name: ":status", value: "400"}: 12,
- {name: ":status", value: "404"}: 13,
- {name: ":status", value: "500"}: 14,
- {name: "accept-charset", value: ""}: 15,
- {name: "accept-encoding", value: "gzip, deflate"}: 16,
- {name: "accept-language", value: ""}: 17,
- {name: "accept-ranges", value: ""}: 18,
- {name: "accept", value: ""}: 19,
- {name: "access-control-allow-origin", value: ""}: 20,
- {name: "age", value: ""}: 21,
- {name: "allow", value: ""}: 22,
- {name: "authorization", value: ""}: 23,
- {name: "cache-control", value: ""}: 24,
- {name: "content-disposition", value: ""}: 25,
- {name: "content-encoding", value: ""}: 26,
- {name: "content-language", value: ""}: 27,
- {name: "content-length", value: ""}: 28,
- {name: "content-location", value: ""}: 29,
- {name: "content-range", value: ""}: 30,
- {name: "content-type", value: ""}: 31,
- {name: "cookie", value: ""}: 32,
- {name: "date", value: ""}: 33,
- {name: "etag", value: ""}: 34,
- {name: "expect", value: ""}: 35,
- {name: "expires", value: ""}: 36,
- {name: "from", value: ""}: 37,
- {name: "host", value: ""}: 38,
- {name: "if-match", value: ""}: 39,
- {name: "if-modified-since", value: ""}: 40,
- {name: "if-none-match", value: ""}: 41,
- {name: "if-range", value: ""}: 42,
- {name: "if-unmodified-since", value: ""}: 43,
- {name: "last-modified", value: ""}: 44,
- {name: "link", value: ""}: 45,
- {name: "location", value: ""}: 46,
- {name: "max-forwards", value: ""}: 47,
- {name: "proxy-authenticate", value: ""}: 48,
- {name: "proxy-authorization", value: ""}: 49,
- {name: "range", value: ""}: 50,
- {name: "referer", value: ""}: 51,
- {name: "refresh", value: ""}: 52,
- {name: "retry-after", value: ""}: 53,
- {name: "server", value: ""}: 54,
- {name: "set-cookie", value: ""}: 55,
- {name: "strict-transport-security", value: ""}: 56,
- {name: "transfer-encoding", value: ""}: 57,
- {name: "user-agent", value: ""}: 58,
- {name: "vary", value: ""}: 59,
- {name: "via", value: ""}: 60,
- {name: "www-authenticate", value: ""}: 61,
+ byName: map[string][]tableEntry{
+ ":authority": {{value: "", id: 1}},
+ ":method": {{value: "GET", id: 2}, {value: "POST", id: 3}},
+ ":path": {{value: "/", id: 4}, {value: "/index.html", id: 5}},
+ ":scheme": {{value: "http", id: 6}, {value: "https", id: 7}},
+ ":status": {{value: "200", id: 8}, {value: "204", id: 9}, {value: "206", id: 10}, {value: "304", id: 11}, {value: "400", id: 12}, {value: "404", id: 13}, {value: "500", id: 14}},
+ "accept-charset": {{value: "", id: 15}},
+ "accept-encoding": {{value: "gzip, deflate", id: 16}},
+ "accept-language": {{value: "", id: 17}},
+ "accept-ranges": {{value: "", id: 18}},
+ "accept": {{value: "", id: 19}},
+ "access-control-allow-origin": {{value: "", id: 20}},
+ "age": {{value: "", id: 21}},
+ "allow": {{value: "", id: 22}},
+ "authorization": {{value: "", id: 23}},
+ "cache-control": {{value: "", id: 24}},
+ "content-disposition": {{value: "", id: 25}},
+ "content-encoding": {{value: "", id: 26}},
+ "content-language": {{value: "", id: 27}},
+ "content-length": {{value: "", id: 28}},
+ "content-location": {{value: "", id: 29}},
+ "content-range": {{value: "", id: 30}},
+ "content-type": {{value: "", id: 31}},
+ "cookie": {{value: "", id: 32}},
+ "date": {{value: "", id: 33}},
+ "etag": {{value: "", id: 34}},
+ "expect": {{value: "", id: 35}},
+ "expires": {{value: "", id: 36}},
+ "from": {{value: "", id: 37}},
+ "host": {{value: "", id: 38}},
+ "if-match": {{value: "", id: 39}},
+ "if-modified-since": {{value: "", id: 40}},
+ "if-none-match": {{value: "", id: 41}},
+ "if-range": {{value: "", id: 42}},
+ "if-unmodified-since": {{value: "", id: 43}},
+ "last-modified": {{value: "", id: 44}},
+ "link": {{value: "", id: 45}},
+ "location": {{value: "", id: 46}},
+ "max-forwards": {{value: "", id: 47}},
+ "proxy-authenticate": {{value: "", id: 48}},
+ "proxy-authorization": {{value: "", id: 49}},
+ "range": {{value: "", id: 50}},
+ "referer": {{value: "", id: 51}},
+ "refresh": {{value: "", id: 52}},
+ "retry-after": {{value: "", id: 53}},
+ "server": {{value: "", id: 54}},
+ "set-cookie": {{value: "", id: 55}},
+ "strict-transport-security": {{value: "", id: 56}},
+ "transfer-encoding": {{value: "", id: 57}},
+ "user-agent": {{value: "", id: 58}},
+ "vary": {{value: "", id: 59}},
+ "via": {{value: "", id: 60}},
+ "www-authenticate": {{value: "", id: 61}},
},
ents: []HeaderField{
{Name: ":authority", Value: "", Sensitive: false},
diff --git a/http2/hpack/tables.go b/http2/hpack/tables.go
index 3bd7eb7..4c7c247 100644
--- a/http2/hpack/tables.go
+++ b/http2/hpack/tables.go
@@ -29,37 +29,32 @@
ents []HeaderField
evictCount uint64
- // byName maps a HeaderField name to the unique id of the newest entry with
- // the same name. See above for a definition of "unique id".
+ // byName maps a HeaderField name to the entries carrying it, oldest first.
+ // See above for a definition of "unique id".
//
- // byName and byNameValue are used only by search, which is only called
- // for tables used by encoders. For tables used only by decoders, the
- // maps are never built, as a memory optimization for servers with many
- // mostly-idle connections, each pinning a dynamic table. The maps are
- // built lazily by the first search call and are nil until then. The two
- // maps are always both nil or both non-nil.
- byName map[string]uint64
-
- // byNameValue maps a HeaderField name/value pair to the unique id of the newest
- // entry with the same name and value. See above for a definition of "unique id".
- // See byName for when this map is non-nil.
- byNameValue map[pairNameValue]uint64
+ // Keying on the name alone lets search hash a string once and settle the
+ // value by comparison. A name holds few entries, and most lookups either
+ // miss the name outright or match a name whose value is not in the table.
+ //
+ // byName is used only by search, which is only called for tables used by
+ // encoders. For tables used only by decoders, the map is never built, as a
+ // memory optimization for servers with many mostly-idle connections, each
+ // pinning a dynamic table. The map is built lazily by the first search call
+ // and is nil until then.
+ byName map[string][]tableEntry
}
-type pairNameValue struct {
- name, value string
+// tableEntry is one value held under a name, with the unique id of its entry.
+type tableEntry struct {
+ value string
+ id uint64
}
-// buildMaps initializes byName and byNameValue from ents.
+// buildMaps initializes byName from ents.
func (t *headerFieldTable) buildMaps() {
- t.byName = make(map[string]uint64, len(t.ents))
- t.byNameValue = make(map[pairNameValue]uint64, len(t.ents))
+ t.byName = make(map[string][]tableEntry, len(t.ents))
for k, f := range t.ents {
- // Map to the newest matching entry: later (newer) entries
- // overwrite earlier ones, matching addEntry's behavior.
- id := t.evictCount + uint64(k) + 1
- t.byName[f.Name] = id
- t.byNameValue[pairNameValue{f.Name, f.Value}] = id
+ t.byName[f.Name] = append(t.byName[f.Name], tableEntry{f.Value, t.evictCount + uint64(k) + 1})
}
}
@@ -72,8 +67,7 @@
func (t *headerFieldTable) addEntry(f HeaderField) {
if t.byName != nil {
id := uint64(t.len()) + t.evictCount + 1
- t.byName[f.Name] = id
- t.byNameValue[pairNameValue{f.Name, f.Value}] = id
+ t.byName[f.Name] = append(t.byName[f.Name], tableEntry{f.Value, id})
}
t.ents = append(t.ents, f)
}
@@ -87,11 +81,15 @@
for k := 0; k < n; k++ {
f := t.ents[k]
id := t.evictCount + uint64(k) + 1
- if t.byName[f.Name] == id {
- delete(t.byName, f.Name)
- }
- if p := (pairNameValue{f.Name, f.Value}); t.byNameValue[p] == id {
- delete(t.byNameValue, p)
+ // The oldest entries go first, so the ones being dropped sit at the
+ // front of the name's list.
+ entries := t.byName[f.Name]
+ if len(entries) > 0 && entries[0].id == id {
+ if len(entries) == 1 {
+ delete(t.byName, f.Name)
+ } else {
+ t.byName[f.Name] = entries[1:]
+ }
}
}
}
@@ -123,15 +121,19 @@
if t.byName == nil {
t.buildMaps()
}
+ entries := t.byName[f.Name]
+ if len(entries) == 0 {
+ return 0, false
+ }
if !f.Sensitive {
- if id := t.byNameValue[pairNameValue{f.Name, f.Value}]; id != 0 {
- return t.idToIndex(id), true
+ // Newest first: a repeated name keeps its most recent entry.
+ for k := len(entries) - 1; k >= 0; k-- {
+ if entries[k].value == f.Value {
+ return t.idToIndex(entries[k].id), true
+ }
}
}
- if id := t.byName[f.Name]; id != 0 {
- return t.idToIndex(id), false
- }
- return 0, false
+ return t.idToIndex(entries[len(entries)-1].id), false
}
// idToIndex converts a unique id to an HPACK index.
diff --git a/http2/hpack/tables_test.go b/http2/hpack/tables_test.go
index 4450a5f..13e7cec 100644
--- a/http2/hpack/tables_test.go
+++ b/http2/hpack/tables_test.go
@@ -111,9 +111,6 @@
t.Errorf("len(table.byName) = %d, want 0", l)
}
- if l := len(table.byNameValue); l > 0 {
- t.Errorf("len(table.byNameValue) = %d, want 0", l)
- }
}
// TestHeaderFieldTable_MapsBuiltLazily verifies that a table used without
@@ -126,8 +123,8 @@
table.addEntry(pair("key1", "value1-2"))
table.evictOldest(1)
- if table.byName != nil || table.byNameValue != nil {
- t.Fatalf("lookup maps allocated without search")
+ if table.byName != nil {
+ t.Fatalf("lookup map allocated without search")
}
// The first search builds the maps from the surviving entries.
@@ -143,9 +140,6 @@
if got, want := len(table.byName), 2; got != want {
t.Errorf("len(byName) = %d, want %d", got, want)
}
- if got, want := len(table.byNameValue), 2; got != want {
- t.Errorf("len(byNameValue) = %d, want %d", got, want)
- }
// Entries added after the maps exist keep them up to date.
table.addEntry(pair("key3", "value3-1"))
@@ -249,7 +243,14 @@
if got, want := staticTable.ents[i-1].Sensitive, false; got != want {
t.Errorf("header index %d sensitive = %t; want %t", i, got, want)
}
- if got, want := strconv.Itoa(int(staticTable.byNameValue[pairNameValue{name: m[2], value: m[3]}])), m[1]; got != want {
+ var id uint64
+ for _, e := range staticTable.byName[m[2]] {
+ if e.value == m[3] {
+ id = e.id
+ break
+ }
+ }
+ if got, want := strconv.Itoa(int(id)), m[1]; got != want {
t.Errorf("header by name %s value %s index = %s; want %s", m[2], m[3], got, want)
}
}
Change information
Files:
- M http2/hpack/encode_test.go
- M http2/hpack/gen.go
- M http2/hpack/static_table.go
- M http2/hpack/tables.go
- M http2/hpack/tables_test.go
Change size: L
Delta: 5 files changed, 148 insertions(+), 199 deletions(-)
Related details
Attention set is empty
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gopher Robot (Gerrit)
7:11 PM (3 hours ago) 7:11 PM
to Gerrit Bot, goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Gopher Robot added 1 comment![]( "Open in Gerrit")
Patchset-level comments
File-level comment, Patchset 1 (Latest):
Gopher Robot . unresolved
I spotted some possible problems with your PR:
1. It looks like you are using markdown in the commit message. If so, please remove it. Be sure to double-check the plain text shown in the Gerrit commit message above for any markdown backticks, markdown links, or other markdown formatting.
Please address any problems by updating the GitHub PR.
When complete, mark this comment as 'Done' and click the [blue 'Reply' button](https://go.dev/wiki/GerritBot#i-left-a-reply-to-a-comment-in-gerrit-but-no-one-but-me-can-see-it) above. These findings are based on heuristics; if a finding does not apply, briefly reply here saying so.
To update the commit title or commit message body shown here in Gerrit, you must edit the GitHub PR title and PR description (the first comment) in the GitHub web interface using the 'Edit' button or 'Edit' menu entry there. Note: pushing a new commit to the PR will not automatically update the commit message used by Gerrit.
For more details, see:
- [how to update commit messages](https://go.dev/wiki/GerritBot/#how-does-gerritbot-determine-the-final-commit-message) for PRs imported into Gerrit.
- the Go project's [conventions for commit messages](https://go.dev/doc/contribute#commit_messages) that you should follow.
(In general for Gerrit code reviews, the change author is expected to [log in to Gerrit](https://go-review.googlesource.com/login/) with a Gmail or other Google account and then close out each piece of feedback by marking it as 'Done' if implemented as suggested or otherwise reply to each review comment. See the [Review](https://go.dev/doc/contribute#review) section of the Contributing Guide for details.)
Related details
Attention set is empty
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Reply all
Reply to author
Forward
0 new messages