go /
net /
bce15e71618b27abb281288615ab0881d8a04433 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>
6 files changed
