Remove BoundedHuffmanSize().
Benchmarks show that it is almost twice as fast as ExactHuffmanSize() for an
input entirely made up of characters that are encoded on 30 bits each, but takes
about five times as long for an input entirely made up of 'a'. Typical input is
expected to contain characters with short codes (that's how the Huffman table
was constructed), so ExactHuffmanSize() is a better choice on average.
Also rename ExactHuffmanSize() to HuffmanSize().
Also remove obsolete TODO about binary literals.
PiperOrigin-RevId: 335412149
Change-Id: I526e04417298468f5b83f3f26dc40ab62ecb1960
diff --git a/http2/hpack/huffman/hpack_huffman_decoder.cc b/http2/hpack/huffman/hpack_huffman_decoder.cc
index 18bff72..3270496 100644
--- a/http2/hpack/huffman/hpack_huffman_decoder.cc
+++ b/http2/hpack/huffman/hpack_huffman_decoder.cc
@@ -26,8 +26,6 @@
// is 5 bits long, and the last canonical is EOS, which is the last
// of the symbols whose code is 30 bits long.
-// TODO(jamessynge): Remove use of binary literals, that is a C++ 14 feature.
-
namespace http2 {
namespace {
diff --git a/http2/hpack/huffman/hpack_huffman_encoder.cc b/http2/hpack/huffman/hpack_huffman_encoder.cc
index 77b32bd..4331f1c 100644
--- a/http2/hpack/huffman/hpack_huffman_encoder.cc
+++ b/http2/hpack/huffman/hpack_huffman_encoder.cc
@@ -7,11 +7,9 @@
#include "net/third_party/quiche/src/http2/hpack/huffman/huffman_spec_tables.h"
#include "net/third_party/quiche/src/http2/platform/api/http2_logging.h"
-// TODO(jamessynge): Remove use of binary literals, that is a C++ 14 feature.
-
namespace http2 {
-size_t ExactHuffmanSize(quiche::QuicheStringPiece plain) {
+size_t HuffmanSize(quiche::QuicheStringPiece plain) {
size_t bits = 0;
for (const uint8_t c : plain) {
bits += HuffmanSpecTables::kCodeLengths[c];
@@ -19,48 +17,6 @@
return (bits + 7) / 8;
}
-size_t BoundedHuffmanSize(quiche::QuicheStringPiece plain) {
- // TODO(jamessynge): Determine whether we should set the min size for Huffman
- // encoding much higher (i.e. if less than N, then the savings isn't worth
- // the cost of encoding and decoding). Of course, we need to decide on a
- // value function, which might be throughput on a full load test, or a
- // microbenchmark of the time to encode and then decode a HEADERS frame,
- // possibly with the cost of crypto included (i.e. crypto is going to have
- // a fairly constant per-byte cost, so reducing the number of bytes in-transit
- // reduces the number that must be encrypted and later decrypted).
- if (plain.size() < 3) {
- // Huffman encoded string can't be smaller than the plain size for very
- // short strings.
- return plain.size();
- }
- // TODO(jamessynge): Measure whether this can be done more efficiently with
- // nested loops (e.g. make exact measurement of 8 bytes, then check if min
- // remaining is too long).
- // Compute the number of bits in an encoding that is shorter than the plain
- // string (i.e. the number of bits in a string 1 byte shorter than plain),
- // and use this as the limit of the size of the encoding.
- const size_t limit_bits = (plain.size() - 1) * 8;
- // The shortest code length in the Huffman table of the HPACK spec has 5 bits
- // (e.g. for 0, 1, a and e).
- const size_t min_code_length = 5;
- // We can therefore say that all plain text bytes whose code length we've not
- // yet looked up will take at least 5 bits.
- size_t min_bits_remaining = plain.size() * min_code_length;
- size_t bits = 0;
- for (const uint8_t c : plain) {
- bits += HuffmanSpecTables::kCodeLengths[c];
- min_bits_remaining -= min_code_length;
- // If our minimum estimate of the total number of bits won't yield an
- // encoding shorter the plain text, let's bail.
- const size_t minimum_bits_total = bits + min_bits_remaining;
- if (minimum_bits_total > limit_bits) {
- bits += min_bits_remaining;
- break;
- }
- }
- return (bits + 7) / 8;
-}
-
void HuffmanEncode(quiche::QuicheStringPiece plain,
size_t encoded_size,
std::string* huffman) {
diff --git a/http2/hpack/huffman/hpack_huffman_encoder.h b/http2/hpack/huffman/hpack_huffman_encoder.h
index fd9912c..a6597db 100644
--- a/http2/hpack/huffman/hpack_huffman_encoder.h
+++ b/http2/hpack/huffman/hpack_huffman_encoder.h
@@ -17,29 +17,20 @@
namespace http2 {
// Returns the size of the Huffman encoding of |plain|, which may be greater
-// than plain.size(). Mostly present for testing.
-QUICHE_EXPORT_PRIVATE size_t ExactHuffmanSize(quiche::QuicheStringPiece plain);
-
-// Returns the size of the Huffman encoding of |plain|, unless it is greater
-// than or equal to plain.size(), in which case a value greater than or equal to
-// plain.size() is returned. The advantage of this over ExactHuffmanSize is that
-// it doesn't read as much of the input string in the event that the string is
-// not compressible by HuffmanEncode (i.e. when the encoding is longer than the
-// original string, it stops reading the input string as soon as it knows that).
-QUICHE_EXPORT_PRIVATE size_t
-BoundedHuffmanSize(quiche::QuicheStringPiece plain);
+// than plain.size().
+QUICHE_EXPORT_PRIVATE size_t HuffmanSize(quiche::QuicheStringPiece plain);
// Encode the plain text string |plain| with the Huffman encoding defined in the
// HPACK RFC, 7541. |encoded_size| is used to pre-allocate storage and it
-// should be the value returned by ExactHuffmanSize(). |*huffman| does not have
-// to be empty, it is cleared at the beginning of this function. This allows
+// should be the value returned by HuffmanSize(). |*huffman| does not have to
+// be empty, it is cleared at the beginning of this function. This allows
// reusing the same string object across multiple invocations.
QUICHE_EXPORT_PRIVATE void HuffmanEncode(quiche::QuicheStringPiece plain,
size_t encoded_size,
std::string* huffman);
// Encode |input| with the Huffman encoding defined RFC7541, used in HPACK and
-// QPACK. |encoded_size| must be the value returned by ExactHuffmanSize().
+// QPACK. |encoded_size| must be the value returned by HuffmanSize().
// Appends the result to the end of |*output|.
QUICHE_EXPORT_PRIVATE void HuffmanEncodeFast(quiche::QuicheStringPiece input,
size_t encoded_size,
diff --git a/http2/hpack/huffman/hpack_huffman_encoder_benchmark.cc b/http2/hpack/huffman/hpack_huffman_encoder_benchmark.cc
index 2870bec..370eb72 100644
--- a/http2/hpack/huffman/hpack_huffman_encoder_benchmark.cc
+++ b/http2/hpack/huffman/hpack_huffman_encoder_benchmark.cc
@@ -59,7 +59,7 @@
":method", ":path", "cookie", "set-cookie", "vary", "accept-encoding"};
for (auto s : state) {
for (const auto& input : inputs) {
- size_t encoded_size = ExactHuffmanSize(input);
+ size_t encoded_size = HuffmanSize(input);
std::string result;
HuffmanEncode(input, encoded_size, &result);
}
@@ -71,7 +71,7 @@
":method", ":path", "cookie", "set-cookie", "vary", "accept-encoding"};
for (auto s : state) {
for (const auto& input : inputs) {
- size_t encoded_size = ExactHuffmanSize(input);
+ size_t encoded_size = HuffmanSize(input);
std::string result;
HuffmanEncodeFast(input, encoded_size, &result);
}
@@ -81,7 +81,7 @@
void BM_EncodeLargeString(benchmark::State& state) {
const std::string input(state.range(0), 'a');
for (auto s : state) {
- size_t encoded_size = ExactHuffmanSize(input);
+ size_t encoded_size = HuffmanSize(input);
std::string result;
HuffmanEncode(input, encoded_size, &result);
}
@@ -90,7 +90,7 @@
void BM_EncodeLargeStringFast(benchmark::State& state) {
const std::string input(state.range(0), 'a');
for (auto s : state) {
- size_t encoded_size = ExactHuffmanSize(input);
+ size_t encoded_size = HuffmanSize(input);
std::string result;
HuffmanEncodeFast(input, encoded_size, &result);
}
@@ -103,7 +103,7 @@
void BM_EncodeLongCode(benchmark::State& state) {
const std::string input(state.range(0), 13);
for (auto s : state) {
- size_t encoded_size = ExactHuffmanSize(input);
+ size_t encoded_size = HuffmanSize(input);
std::string result;
HuffmanEncode(input, encoded_size, &result);
}
@@ -112,7 +112,7 @@
void BM_EncodeLongCodeFast(benchmark::State& state) {
const std::string input(state.range(0), 13);
for (auto s : state) {
- size_t encoded_size = ExactHuffmanSize(input);
+ size_t encoded_size = HuffmanSize(input);
std::string result;
HuffmanEncodeFast(input, encoded_size, &result);
}
diff --git a/http2/hpack/huffman/hpack_huffman_encoder_test.cc b/http2/hpack/huffman/hpack_huffman_encoder_test.cc
index d73179c..a5ad105 100644
--- a/http2/hpack/huffman/hpack_huffman_encoder_test.cc
+++ b/http2/hpack/huffman/hpack_huffman_encoder_test.cc
@@ -30,7 +30,7 @@
TEST_P(HuffmanEncoderTest, Empty) {
std::string empty("");
- size_t encoded_size = ExactHuffmanSize(empty);
+ size_t encoded_size = HuffmanSize(empty);
EXPECT_EQ(0u, encoded_size);
std::string buffer;
@@ -52,9 +52,8 @@
for (size_t i = 0; i != QUICHE_ARRAYSIZE(test_table); i += 2) {
const std::string& huffman_encoded(test_table[i]);
const std::string& plain_string(test_table[i + 1]);
- size_t encoded_size = ExactHuffmanSize(plain_string);
+ size_t encoded_size = HuffmanSize(plain_string);
EXPECT_EQ(huffman_encoded.size(), encoded_size);
- EXPECT_EQ(BoundedHuffmanSize(plain_string), encoded_size);
std::string buffer;
buffer.reserve();
Encode(plain_string, encoded_size, &buffer);
@@ -84,9 +83,8 @@
for (size_t i = 0; i != QUICHE_ARRAYSIZE(test_table); i += 2) {
const std::string& huffman_encoded(test_table[i]);
const std::string& plain_string(test_table[i + 1]);
- size_t encoded_size = ExactHuffmanSize(plain_string);
+ size_t encoded_size = HuffmanSize(plain_string);
EXPECT_EQ(huffman_encoded.size(), encoded_size);
- EXPECT_EQ(BoundedHuffmanSize(plain_string), encoded_size);
std::string buffer;
Encode(plain_string, encoded_size, &buffer);
EXPECT_EQ(buffer, huffman_encoded) << "Error encoding " << plain_string;
@@ -110,22 +108,20 @@
for (size_t i = 0; i != QUICHE_ARRAYSIZE(test_table); ++i) {
const std::string& plain_string = test_table[i];
- size_t encoded_size = ExactHuffmanSize(plain_string);
+ size_t encoded_size = HuffmanSize(plain_string);
std::string huffman_encoded;
Encode(plain_string, encoded_size, &huffman_encoded);
EXPECT_EQ(encoded_size, huffman_encoded.size());
- EXPECT_LE(BoundedHuffmanSize(plain_string), plain_string.size());
- EXPECT_LE(BoundedHuffmanSize(plain_string), ExactHuffmanSize(plain_string));
}
}
TEST_P(HuffmanEncoderTest, AppendToOutput) {
- size_t encoded_size = ExactHuffmanSize("foo");
+ size_t encoded_size = HuffmanSize("foo");
std::string buffer;
Encode("foo", encoded_size, &buffer);
EXPECT_EQ(Http2HexDecode("94e7"), buffer);
- encoded_size = ExactHuffmanSize("bar");
+ encoded_size = HuffmanSize("bar");
Encode("bar", encoded_size, &buffer);
if (use_fast_encoder_) {
diff --git a/http2/hpack/huffman/hpack_huffman_transcoder_test.cc b/http2/hpack/huffman/hpack_huffman_transcoder_test.cc
index 329f193..e761964 100644
--- a/http2/hpack/huffman/hpack_huffman_transcoder_test.cc
+++ b/http2/hpack/huffman/hpack_huffman_transcoder_test.cc
@@ -73,7 +73,7 @@
AssertionResult TranscodeAndValidateSeveralWays(
quiche::QuicheStringPiece plain,
quiche::QuicheStringPiece expected_huffman) {
- size_t encoded_size = ExactHuffmanSize(plain);
+ size_t encoded_size = HuffmanSize(plain);
std::string encoded;
HuffmanEncode(plain, encoded_size, &encoded);
VERIFY_EQ(encoded_size, encoded.size());
diff --git a/http2/hpack/huffman/huffman_spec_tables.cc b/http2/hpack/huffman/huffman_spec_tables.cc
index 2b1d8bd..f93d9a5 100644
--- a/http2/hpack/huffman/huffman_spec_tables.cc
+++ b/http2/hpack/huffman/huffman_spec_tables.cc
@@ -44,8 +44,6 @@
30, // 256
};
-// TODO(jamessynge): Remove use of binary literals, that is a C++ 14 feature.
-
// The encoding of each symbol, left justified (as printed), which means that
// the first bit of the encoding is the high-order bit of the uint32.
// static
diff --git a/quic/core/qpack/qpack_instruction_encoder.cc b/quic/core/qpack/qpack_instruction_encoder.cc
index 7255216..6a15db8 100644
--- a/quic/core/qpack/qpack_instruction_encoder.cc
+++ b/quic/core/qpack/qpack_instruction_encoder.cc
@@ -135,7 +135,7 @@
string_to_write_ =
(field_->type == QpackInstructionFieldType::kName) ? name : value;
- size_t encoded_size = http2::ExactHuffmanSize(string_to_write_);
+ size_t encoded_size = http2::HuffmanSize(string_to_write_);
if (encoded_size < string_to_write_.size()) {
DCHECK_EQ(0, byte_ & (1 << field_->param));
