Pre-allocate storage in http2::HuffmanEncode().
Also, do not call http2::HuffmanEncode() in
QpackInstructionEncoder::DoStartString() if it does not result in size savings.
Note that performance gets worse for short strings, presumably because
std::string::reserve() for small values is a no-op due to small string
optimization. However, I plan to modify http2::HuffmanEncode() not to clear the
output string and modify QpackInstructionEncoder to avoid copying, which should
result in a performance improvement overall.
Also I'll add a slightly faster implementation in the next CL, so this is really
only to change the API to make tests simpler.
PiperOrigin-RevId: 334909897
Change-Id: Idd7414c0dcaa56fc62d0822ec06250d480d2972c
diff --git a/http2/hpack/huffman/hpack_huffman_encoder.cc b/http2/hpack/huffman/hpack_huffman_encoder.cc
index 8b3f29f..305bb5a 100644
--- a/http2/hpack/huffman/hpack_huffman_encoder.cc
+++ b/http2/hpack/huffman/hpack_huffman_encoder.cc
@@ -61,9 +61,12 @@
return (bits + 7) / 8;
}
-void HuffmanEncode(quiche::QuicheStringPiece plain, std::string* huffman) {
+void HuffmanEncode(quiche::QuicheStringPiece plain,
+ size_t encoded_size,
+ std::string* huffman) {
DCHECK(huffman != nullptr);
huffman->clear(); // Note that this doesn't release memory.
+ huffman->reserve(encoded_size);
uint64_t bit_buffer = 0; // High-bit is next bit to output. Not clear if that
// is more performant than having the low-bit be the
// last to be output.
diff --git a/http2/hpack/huffman/hpack_huffman_encoder.h b/http2/hpack/huffman/hpack_huffman_encoder.h
index 2ee4de2..b7012b4 100644
--- a/http2/hpack/huffman/hpack_huffman_encoder.h
+++ b/http2/hpack/huffman/hpack_huffman_encoder.h
@@ -29,11 +29,13 @@
QUICHE_EXPORT_PRIVATE size_t
BoundedHuffmanSize(quiche::QuicheStringPiece plain);
-// Encode the plain text string |plain| with the Huffman encoding defined in
-// the HPACK RFC, 7541. |*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.
+// 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
+// reusing the same string object across multiple invocations.
QUICHE_EXPORT_PRIVATE void HuffmanEncode(quiche::QuicheStringPiece plain,
+ size_t encoded_size,
std::string* huffman);
} // namespace http2
diff --git a/http2/hpack/huffman/hpack_huffman_encoder_benchmark.cc b/http2/hpack/huffman/hpack_huffman_encoder_benchmark.cc
index 1f365c6..9e4163f 100644
--- a/http2/hpack/huffman/hpack_huffman_encoder_benchmark.cc
+++ b/http2/hpack/huffman/hpack_huffman_encoder_benchmark.cc
@@ -9,14 +9,14 @@
//
// Benchmark Time(ns) CPU(ns) Allocs Iterations
// -----------------------------------------------------------------------------
-// BM_EncodeSmallStrings 239 239 0 2456085 0.000B peak-mem
-// BM_EncodeLargeString/1k 4560 4561 5 153325 1.125kB peak-mem
-// BM_EncodeLargeString/4k 18787 18788 7 38430 4.500kB peak-mem
-// BM_EncodeLargeString/32k 147680 147657 10 4664 36.000kB peak-mem
-// BM_EncodeLargeString/256k 1161688 1161511 13 601 288.000kB peak-mem
-// BM_EncodeLargeString/2M 10042722 10036764 16 75 2.250MB peak-mem
-// BM_EncodeLargeString/16M 76127338 76138839 19 9 18.000MB peak-mem
-// BM_EncodeLargeString/128M 640008098 640154859 22 1 144.000MB peak-mem
+// BM_EncodeSmallStrings 256 256 0 2614132 0.000B peak-mem
+// BM_EncodeLargeString/1k 4295 4296 1 164072 656.000B peak-mem
+// BM_EncodeLargeString/4k 17077 17078 1 40336 2.516kB peak-mem
+// BM_EncodeLargeString/32k 136586 136584 1 5126 20.016kB peak-mem
+// BM_EncodeLargeString/256k 1094913 1094867 1 632 160.016kB peak-mem
+// BM_EncodeLargeString/2M 8771916 8773555 1 80 1.250MB peak-mem
+// BM_EncodeLargeString/16M 72575563 72590767 1 10 10.000MB peak-mem
+// BM_EncodeLargeString/128M 602461676 602487805 1 1 80.000MB peak-mem
//
#include <string>
@@ -37,9 +37,9 @@
":method", ":path", "cookie", "set-cookie", "vary", "accept-encoding"};
for (auto s : state) {
for (const auto& input : inputs) {
+ size_t encoded_size = ExactHuffmanSize(input);
std::string result;
- ExactHuffmanSize(input);
- HuffmanEncode(input, &result);
+ HuffmanEncode(input, encoded_size, &result);
}
}
}
@@ -47,9 +47,9 @@
void BM_EncodeLargeString(benchmark::State& state) {
const std::string input(state.range(0), 'a');
for (auto s : state) {
+ size_t encoded_size = ExactHuffmanSize(input);
std::string result;
- ExactHuffmanSize(input);
- HuffmanEncode(input, &result);
+ HuffmanEncode(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 0c0968b..5528408 100644
--- a/http2/hpack/huffman/hpack_huffman_encoder_test.cc
+++ b/http2/hpack/huffman/hpack_huffman_encoder_test.cc
@@ -25,11 +25,12 @@
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]);
- EXPECT_EQ(ExactHuffmanSize(plain_string), huffman_encoded.size());
- EXPECT_EQ(BoundedHuffmanSize(plain_string), huffman_encoded.size());
+ size_t encoded_size = ExactHuffmanSize(plain_string);
+ EXPECT_EQ(huffman_encoded.size(), encoded_size);
+ EXPECT_EQ(BoundedHuffmanSize(plain_string), encoded_size);
std::string buffer;
buffer.reserve();
- HuffmanEncode(plain_string, &buffer);
+ HuffmanEncode(plain_string, encoded_size, &buffer);
EXPECT_EQ(buffer, huffman_encoded) << "Error encoding " << plain_string;
}
}
@@ -56,14 +57,12 @@
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]);
- EXPECT_EQ(ExactHuffmanSize(plain_string), huffman_encoded.size());
- EXPECT_EQ(BoundedHuffmanSize(plain_string), huffman_encoded.size());
+ size_t encoded_size = ExactHuffmanSize(plain_string);
+ EXPECT_EQ(huffman_encoded.size(), encoded_size);
+ EXPECT_EQ(BoundedHuffmanSize(plain_string), encoded_size);
std::string buffer;
- buffer.reserve(huffman_encoded.size());
- const size_t capacity = buffer.capacity();
- HuffmanEncode(plain_string, &buffer);
+ HuffmanEncode(plain_string, encoded_size, &buffer);
EXPECT_EQ(buffer, huffman_encoded) << "Error encoding " << plain_string;
- EXPECT_EQ(capacity, buffer.capacity());
}
}
@@ -84,9 +83,10 @@
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);
std::string huffman_encoded;
- HuffmanEncode(plain_string, &huffman_encoded);
- EXPECT_EQ(huffman_encoded.size(), ExactHuffmanSize(plain_string));
+ HuffmanEncode(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));
}
diff --git a/http2/hpack/huffman/hpack_huffman_transcoder_test.cc b/http2/hpack/huffman/hpack_huffman_transcoder_test.cc
index 1123d26..329f193 100644
--- a/http2/hpack/huffman/hpack_huffman_transcoder_test.cc
+++ b/http2/hpack/huffman/hpack_huffman_transcoder_test.cc
@@ -73,8 +73,10 @@
AssertionResult TranscodeAndValidateSeveralWays(
quiche::QuicheStringPiece plain,
quiche::QuicheStringPiece expected_huffman) {
+ size_t encoded_size = ExactHuffmanSize(plain);
std::string encoded;
- HuffmanEncode(plain, &encoded);
+ HuffmanEncode(plain, encoded_size, &encoded);
+ VERIFY_EQ(encoded_size, encoded.size());
if (expected_huffman.size() > 0 || plain.empty()) {
VERIFY_EQ(encoded, expected_huffman);
}
diff --git a/quic/core/qpack/qpack_instruction_encoder.cc b/quic/core/qpack/qpack_instruction_encoder.cc
index 41e2d76..7255216 100644
--- a/quic/core/qpack/qpack_instruction_encoder.cc
+++ b/quic/core/qpack/qpack_instruction_encoder.cc
@@ -135,12 +135,14 @@
string_to_write_ =
(field_->type == QpackInstructionFieldType::kName) ? name : value;
- http2::HuffmanEncode(string_to_write_, &huffman_encoded_string_);
+ size_t encoded_size = http2::ExactHuffmanSize(string_to_write_);
- if (huffman_encoded_string_.size() < string_to_write_.size()) {
+ if (encoded_size < string_to_write_.size()) {
DCHECK_EQ(0, byte_ & (1 << field_->param));
-
byte_ |= (1 << field_->param);
+
+ http2::HuffmanEncode(string_to_write_, encoded_size,
+ &huffman_encoded_string_);
string_to_write_ = huffman_encoded_string_;
}
