http2/hpack: speedup Encoder.searchTable

The previous algorithm was linear in the size of the table.
The new algorithm is O(1). The new algorithm should behave exactly
like the old algorthm, except for one unimportant change that
triggered small updates to tests in encode_test.go:

When encoding "Field: Value" where the table has two entries,
[0]={"Field", "X"} and [1]={"Field", "Y"}, we can encode the field
name using either table entry. Previously, we selected the oldest
entry, but now we select the newest entry. The new implementation
should actually generate very slightly better compression because
new entries are encoded with smaller integers than old entries, and
HPACK uses a varint encoding for integers where smaller integers
are encoded in fewer bytes.

I added a synthetic microbenchmark which shows a big speedup in

BenchmarkEncoderSearchTable-40  100000 127440 ns/op  # before
BenchmarkEncoderSearchTable-40   50000  25121 ns/op  # after

Change-Id: Ib87d61b6415d9f0ff38874fe2a719b2f00351590
Reviewed-by: Brad Fitzpatrick <>
6 files changed