http2: 64-bit register bit-accumulator Huffman encoder. Maintains a 64-bit CPU register bit-accumulator and flushes 32-bit big-endian words via `std::memcpy` (`quiche::QuicheEndian::HostToNet32`) under `quiche_reloadable_flag_hpack_huffman_encoder_64bit_accumulator`, eliminating inner loop branches and byte-level memory OR stores. An escape hatch is added to bypass the 64-bit optimization for inputs smaller than 25 bytes to avoid a small performance regression. Benchmark Results (64-bit accumulator vs 32-bit baseline): - < 25 bytes (bypassed): 0% change (no regression). - 100 bytes: ~37% CPU time reduction. - 1000 bytes: ~53% CPU time reduction. - 10K+ bytes: ~16% to ~57% CPU time reduction (larger gains for compressible data). Sponge: http://sponge2/6528bc11-27fa-4e50-9d7b-c2e1074b06e3 Protected by FLAGS_quiche_reloadable_flag_hpack_huffman_encoder_64bit_accumulator. PiperOrigin-RevId: 967313794
diff --git a/quiche/common/quiche_feature_flags_list.h b/quiche/common/quiche_feature_flags_list.h index 057425e..a327eca 100755 --- a/quiche/common/quiche_feature_flags_list.h +++ b/quiche/common/quiche_feature_flags_list.h
@@ -10,6 +10,7 @@ QUICHE_FLAG(bool, quiche_reloadable_flag_enable_h3_origin_frame, false, true, "If true, enables support for parsing HTTP/3 ORIGIN frames.") QUICHE_FLAG(bool, quiche_reloadable_flag_hpack_huffman_decoder_optimizations, false, false, "If true, enables a few optimizations in HpackHuffmanDecoder.") +QUICHE_FLAG(bool, quiche_reloadable_flag_hpack_huffman_encoder_64bit_accumulator, false, false, "If true, use 64-bit bit accumulator for HPACK Huffman encoding.") QUICHE_FLAG(bool, quiche_reloadable_flag_quic_act_upon_invalid_header, true, true, "If true, reject or send error response code upon receiving invalid request or response headers.") QUICHE_FLAG(bool, quiche_reloadable_flag_quic_add_stream_info_to_idle_close_detail, false, true, "If true, include stream information in idle timeout connection close detail.") QUICHE_FLAG(bool, quiche_reloadable_flag_quic_bandwidth_sampler_guard_rtt_subtraction, false, false, "When true, BandwidthSampler::OnPacketAcknowledgedInner() will return early rather than compute a negative RTT.")
diff --git a/quiche/http2/hpack/huffman/hpack_huffman_encoder.cc b/quiche/http2/hpack/huffman/hpack_huffman_encoder.cc index 277254f..f17410f 100644 --- a/quiche/http2/hpack/huffman/hpack_huffman_encoder.cc +++ b/quiche/http2/hpack/huffman/hpack_huffman_encoder.cc
@@ -6,15 +6,29 @@ #include <cstddef> #include <cstdint> +#include <cstring> #include <limits> #include <string> #include "absl/strings/string_view.h" #include "quiche/http2/hpack/huffman/huffman_spec_tables.h" +#include "quiche/common/platform/api/quiche_flag_utils.h" +#include "quiche/common/platform/api/quiche_flags.h" #include "quiche/common/platform/api/quiche_logging.h" +#include "quiche/common/quiche_endian.h" namespace http2 { +namespace { + +void FlushAccumulator(uint64_t accumulator, size_t to_write, char* dest) { + const uint32_t word = static_cast<uint32_t>(accumulator >> 32); + const uint32_t net_word = quiche::QuicheEndian::HostToNet32(word); + std::memcpy(dest, &net_word, to_write); +} + +} // namespace + size_t HuffmanSize(absl::string_view plain) { uint64_t bits = 0; for (const uint8_t c : plain) { @@ -29,11 +43,62 @@ void HuffmanEncode(absl::string_view input, size_t encoded_size, std::string* output) { + // Uses the 64-bit accumulator path for inputs >= 25 bytes. For smaller + // inputs, the overhead outweighs the benefits, causing a regression. + if (input.size() >= 25 && + GetQuicheReloadableFlag(hpack_huffman_encoder_64bit_accumulator)) { + QUICHE_RELOADABLE_FLAG_COUNT(hpack_huffman_encoder_64bit_accumulator); + const size_t original_size = output->size(); + // The destination must be large enough to contain the original `output` as + // well as the new encoded data. + const size_t final_size = original_size + encoded_size; + // Reserve an extra four bytes to avoid accessing unallocated memory (even + // though it would only be OR'd with zeros and thus not modified). + output->resize(final_size + sizeof(uint32_t), 0); + + char* dest = output->data() + original_size; + // Maintains the bits to be written. The next code is shifted and OR'd + // into the accumulator. + uint64_t accumulator = 0; + // Number of bits currently in the accumulator. + int count = 0; + + for (const uint8_t c : input) { + const uint32_t left_code = HuffmanSpecTables::kLeftCodes[c]; + const uint8_t len = HuffmanSpecTables::kCodeLengths[c]; + // Shifts the 32-bit left-aligned code to the right by the current bit + // count and merges it into the 64-bit accumulator. + accumulator |= (static_cast<uint64_t>(left_code) << 32) >> count; + count += len; + // When the accumulator has at least 32 bits, flushes them as a 32-bit + // big-endian word. + if (count >= 32) { + FlushAccumulator(accumulator, sizeof(uint32_t), dest); + dest += sizeof(uint32_t); + accumulator <<= 32; + count -= 32; + } + } + + // Writes the remaining bits (up to 31 bits). + if (count > 0) { + // HPACK requires end-of-stream padding to be 1s. + accumulator |= (~0ULL >> count); + const size_t remaining_bytes = (count + 7) / 8; + FlushAccumulator(accumulator, remaining_bytes, dest); + } + + output->resize(final_size); + return; + } + const size_t original_size = output->size(); + // The destination must be large enough to contain the original `output` as + // well as the new encoded data. const size_t final_size = original_size + encoded_size; // Reserve an extra four bytes to avoid accessing unallocated memory (even // though it would only be OR'd with zeros and thus not modified). - output->resize(final_size + 4, 0); + output->resize(final_size + sizeof(uint32_t), 0); // Pointer to first appended byte. char* const first = &*output->begin() + original_size;
diff --git a/quiche/http2/hpack/huffman/hpack_huffman_encoder_test.cc b/quiche/http2/hpack/huffman/hpack_huffman_encoder_test.cc index d6774cf..ebeb83b 100644 --- a/quiche/http2/hpack/huffman/hpack_huffman_encoder_test.cc +++ b/quiche/http2/hpack/huffman/hpack_huffman_encoder_test.cc
@@ -9,19 +9,24 @@ #include "absl/base/macros.h" #include "absl/strings/escaping.h" +#include "quiche/common/platform/api/quiche_flags.h" #include "quiche/common/platform/api/quiche_test.h" namespace http2 { namespace { TEST(HuffmanEncoderTest, Empty) { - std::string empty(""); - size_t encoded_size = HuffmanSize(empty); - EXPECT_EQ(0u, encoded_size); + for (bool flag_value : {false, true}) { + SetQuicheReloadableFlag(hpack_huffman_encoder_64bit_accumulator, + flag_value); + std::string empty(""); + size_t encoded_size = HuffmanSize(empty); + EXPECT_EQ(0u, encoded_size); - std::string buffer; - HuffmanEncode(empty, encoded_size, &buffer); - EXPECT_EQ("", buffer); + std::string buffer; + HuffmanEncode(empty, encoded_size, &buffer); + EXPECT_EQ("", buffer); + } } TEST(HuffmanEncoderTest, SpecRequestExamples) { @@ -38,16 +43,20 @@ "25a849e95bb8e8b4bf", "custom-value", }; - for (size_t i = 0; i != ABSL_ARRAYSIZE(test_table); i += 2) { - std::string huffman_encoded; - ASSERT_TRUE(absl::HexStringToBytes(test_table[i], &huffman_encoded)); - const std::string& plain_string(test_table[i + 1]); - size_t encoded_size = HuffmanSize(plain_string); - EXPECT_EQ(huffman_encoded.size(), encoded_size); - std::string buffer; - buffer.reserve(huffman_encoded.size()); - HuffmanEncode(plain_string, encoded_size, &buffer); - EXPECT_EQ(buffer, huffman_encoded) << "Error encoding " << plain_string; + for (bool flag_value : {false, true}) { + SetQuicheReloadableFlag(hpack_huffman_encoder_64bit_accumulator, + flag_value); + for (size_t i = 0; i != ABSL_ARRAYSIZE(test_table); i += 2) { + std::string huffman_encoded; + ASSERT_TRUE(absl::HexStringToBytes(test_table[i], &huffman_encoded)); + const std::string& plain_string(test_table[i + 1]); + size_t encoded_size = HuffmanSize(plain_string); + EXPECT_EQ(huffman_encoded.size(), encoded_size); + std::string buffer; + buffer.reserve(huffman_encoded.size()); + HuffmanEncode(plain_string, encoded_size, &buffer); + EXPECT_EQ(buffer, huffman_encoded) << "Error encoding " << plain_string; + } } } @@ -69,15 +78,19 @@ "03ed4ee5b1063d5007", "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", }; - for (size_t i = 0; i != ABSL_ARRAYSIZE(test_table); i += 2) { - std::string huffman_encoded; - ASSERT_TRUE(absl::HexStringToBytes(test_table[i], &huffman_encoded)); - const std::string& plain_string(test_table[i + 1]); - size_t encoded_size = HuffmanSize(plain_string); - EXPECT_EQ(huffman_encoded.size(), encoded_size); - std::string buffer; - HuffmanEncode(plain_string, encoded_size, &buffer); - EXPECT_EQ(buffer, huffman_encoded) << "Error encoding " << plain_string; + for (bool flag_value : {false, true}) { + SetQuicheReloadableFlag(hpack_huffman_encoder_64bit_accumulator, + flag_value); + for (size_t i = 0; i != ABSL_ARRAYSIZE(test_table); i += 2) { + std::string huffman_encoded; + ASSERT_TRUE(absl::HexStringToBytes(test_table[i], &huffman_encoded)); + const std::string& plain_string(test_table[i + 1]); + size_t encoded_size = HuffmanSize(plain_string); + EXPECT_EQ(huffman_encoded.size(), encoded_size); + std::string buffer; + HuffmanEncode(plain_string, encoded_size, &buffer); + EXPECT_EQ(buffer, huffman_encoded) << "Error encoding " << plain_string; + } } } @@ -96,28 +109,36 @@ test_table[ABSL_ARRAYSIZE(test_table) - 1][i] = static_cast<char>(i); } - for (size_t i = 0; i != ABSL_ARRAYSIZE(test_table); ++i) { - const std::string& plain_string = test_table[i]; - size_t encoded_size = HuffmanSize(plain_string); - std::string huffman_encoded; - HuffmanEncode(plain_string, encoded_size, &huffman_encoded); - EXPECT_EQ(encoded_size, huffman_encoded.size()); + for (bool flag_value : {false, true}) { + SetQuicheReloadableFlag(hpack_huffman_encoder_64bit_accumulator, + flag_value); + for (size_t i = 0; i != ABSL_ARRAYSIZE(test_table); ++i) { + const std::string& plain_string = test_table[i]; + size_t encoded_size = HuffmanSize(plain_string); + std::string huffman_encoded; + HuffmanEncode(plain_string, encoded_size, &huffman_encoded); + EXPECT_EQ(encoded_size, huffman_encoded.size()); + } } } // Test that encoding appends to output without overwriting it. TEST(HuffmanEncoderTest, AppendToOutput) { - size_t encoded_size = HuffmanSize("foo"); - std::string buffer; - HuffmanEncode("foo", encoded_size, &buffer); - std::string expected_encoding; - ASSERT_TRUE(absl::HexStringToBytes("94e7", &expected_encoding)); - EXPECT_EQ(expected_encoding, buffer); + for (bool flag_value : {false, true}) { + SetQuicheReloadableFlag(hpack_huffman_encoder_64bit_accumulator, + flag_value); + size_t encoded_size = HuffmanSize("foo"); + std::string buffer; + HuffmanEncode("foo", encoded_size, &buffer); + std::string expected_encoding; + ASSERT_TRUE(absl::HexStringToBytes("94e7", &expected_encoding)); + EXPECT_EQ(expected_encoding, buffer); - encoded_size = HuffmanSize("bar"); - HuffmanEncode("bar", encoded_size, &buffer); - ASSERT_TRUE(absl::HexStringToBytes("94e78c767f", &expected_encoding)); - EXPECT_EQ(expected_encoding, buffer); + encoded_size = HuffmanSize("bar"); + HuffmanEncode("bar", encoded_size, &buffer); + ASSERT_TRUE(absl::HexStringToBytes("94e78c767f", &expected_encoding)); + EXPECT_EQ(expected_encoding, buffer); + } } } // namespace