tree 5eca8742d985ef42aab2cbcbbc36d6c257eab1f7
parent bb807669a61aca6092d8137da1fab2150bb96ad7
author Tom Bergan <tombergan@google.com> 1487927759 -0800
committer Brad Fitzpatrick <bradfitz@golang.org> 1488221537 +0000

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
hpack.Encoder.searchTable:

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

Change-Id: Ib87d61b6415d9f0ff38874fe2a719b2f00351590
Reviewed-on: https://go-review.googlesource.com/37406
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>