Expands the fast-path lookup table in `HpackHuffmanDecoder` to 8 bits. Expands `kShortCodeTable` from 7 bits (124 entries) to 8 bits (254 entries), allowing all 5, 6, 7, and 8-bit HPACK Huffman codes (covering standard ASCII letters, digits, and common HTTP header punctuation) to be decoded in a single fast-path lookup step. This 508-byte lookup table is still compact enough to be CPU cache efficient. Based on benchmark runs against the current state, here is how this optimization compares: - **Overall Performance (`geomean`)**: **+5.44%** increase in throughput (from `95.22 MiB/s` to `100.4 MiB/s`). - **Largest Gains**: - `BM_DecodeChunkedInput/16`: **+13.58%** - `BM_DecodeLargeString/4k`: **+12.20%** - `BM_DecodeChunkedInput/64`: **+11.86%** - `BM_DecodeLargeString/1k`: **+11.63%** This optimization was generated by Gemini. The performance investigation that led to this improvement was motiviated by an article by the folks at Apoxy. * https://apoxy.dev/blog/oghttp2-vs-nghttp2 Protected by FLAGS_gfe2_reloadable_flag_hpack_huffman_decoder_optimizations. PiperOrigin-RevId: 962946960
diff --git a/quiche/common/quiche_feature_flags_list.h b/quiche/common/quiche_feature_flags_list.h index 412762e..ace0c66 100755 --- a/quiche/common/quiche_feature_flags_list.h +++ b/quiche/common/quiche_feature_flags_list.h
@@ -9,6 +9,7 @@ #if defined(QUICHE_FLAG) 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_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_decoder.cc b/quiche/http2/hpack/huffman/hpack_huffman_decoder.cc index 71abbbb..21b411d 100644 --- a/quiche/http2/hpack/huffman/hpack_huffman_decoder.cc +++ b/quiche/http2/hpack/huffman/hpack_huffman_decoder.cc
@@ -10,6 +10,8 @@ #include <sstream> #include <string> +#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" // Terminology: @@ -215,11 +217,101 @@ }; // clang-format on -constexpr size_t kShortCodeTableSize = 124; struct ShortCodeInfo { uint8_t symbol; uint8_t length; -} kShortCodeTable[kShortCodeTableSize] = { +}; + +constexpr size_t kShortCodeTableSize = 254; +constexpr ShortCodeInfo kShortCodeTable[kShortCodeTableSize] = { + {0x30, 5}, {0x30, 5}, {0x30, 5}, {0x30, 5}, + {0x30, 5}, {0x30, 5}, {0x30, 5}, {0x30, 5}, // 0b00000xxx ('0') + {0x31, 5}, {0x31, 5}, {0x31, 5}, {0x31, 5}, + {0x31, 5}, {0x31, 5}, {0x31, 5}, {0x31, 5}, // 0b00001xxx ('1') + {0x32, 5}, {0x32, 5}, {0x32, 5}, {0x32, 5}, + {0x32, 5}, {0x32, 5}, {0x32, 5}, {0x32, 5}, // 0b00010xxx ('2') + {0x61, 5}, {0x61, 5}, {0x61, 5}, {0x61, 5}, + {0x61, 5}, {0x61, 5}, {0x61, 5}, {0x61, 5}, // 0b00011xxx ('a') + {0x63, 5}, {0x63, 5}, {0x63, 5}, {0x63, 5}, + {0x63, 5}, {0x63, 5}, {0x63, 5}, {0x63, 5}, // 0b00100xxx ('c') + {0x65, 5}, {0x65, 5}, {0x65, 5}, {0x65, 5}, + {0x65, 5}, {0x65, 5}, {0x65, 5}, {0x65, 5}, // 0b00101xxx ('e') + {0x69, 5}, {0x69, 5}, {0x69, 5}, {0x69, 5}, + {0x69, 5}, {0x69, 5}, {0x69, 5}, {0x69, 5}, // 0b00110xxx ('i') + {0x6f, 5}, {0x6f, 5}, {0x6f, 5}, {0x6f, 5}, + {0x6f, 5}, {0x6f, 5}, {0x6f, 5}, {0x6f, 5}, // 0b00111xxx ('o') + {0x73, 5}, {0x73, 5}, {0x73, 5}, {0x73, 5}, + {0x73, 5}, {0x73, 5}, {0x73, 5}, {0x73, 5}, // 0b01000xxx ('s') + {0x74, 5}, {0x74, 5}, {0x74, 5}, {0x74, 5}, + {0x74, 5}, {0x74, 5}, {0x74, 5}, {0x74, 5}, // 0b01001xxx ('t') + {0x20, 6}, {0x20, 6}, {0x20, 6}, {0x20, 6}, // 0b010100xx (' ') + {0x25, 6}, {0x25, 6}, {0x25, 6}, {0x25, 6}, // 0b010101xx ('%') + {0x2d, 6}, {0x2d, 6}, {0x2d, 6}, {0x2d, 6}, // 0b010110xx ('-') + {0x2e, 6}, {0x2e, 6}, {0x2e, 6}, {0x2e, 6}, // 0b010111xx ('.') + {0x2f, 6}, {0x2f, 6}, {0x2f, 6}, {0x2f, 6}, // 0b011000xx ('/') + {0x33, 6}, {0x33, 6}, {0x33, 6}, {0x33, 6}, // 0b011001xx ('3') + {0x34, 6}, {0x34, 6}, {0x34, 6}, {0x34, 6}, // 0b011010xx ('4') + {0x35, 6}, {0x35, 6}, {0x35, 6}, {0x35, 6}, // 0b011011xx ('5') + {0x36, 6}, {0x36, 6}, {0x36, 6}, {0x36, 6}, // 0b011100xx ('6') + {0x37, 6}, {0x37, 6}, {0x37, 6}, {0x37, 6}, // 0b011101xx ('7') + {0x38, 6}, {0x38, 6}, {0x38, 6}, {0x38, 6}, // 0b011110xx ('8') + {0x39, 6}, {0x39, 6}, {0x39, 6}, {0x39, 6}, // 0b011111xx ('9') + {0x3d, 6}, {0x3d, 6}, {0x3d, 6}, {0x3d, 6}, // 0b100000xx ('=') + {0x41, 6}, {0x41, 6}, {0x41, 6}, {0x41, 6}, // 0b100001xx ('A') + {0x5f, 6}, {0x5f, 6}, {0x5f, 6}, {0x5f, 6}, // 0b100010xx ('_') + {0x62, 6}, {0x62, 6}, {0x62, 6}, {0x62, 6}, // 0b100011xx ('b') + {0x64, 6}, {0x64, 6}, {0x64, 6}, {0x64, 6}, // 0b100100xx ('d') + {0x66, 6}, {0x66, 6}, {0x66, 6}, {0x66, 6}, // 0b100101xx ('f') + {0x67, 6}, {0x67, 6}, {0x67, 6}, {0x67, 6}, // 0b100110xx ('g') + {0x68, 6}, {0x68, 6}, {0x68, 6}, {0x68, 6}, // 0b100111xx ('h') + {0x6c, 6}, {0x6c, 6}, {0x6c, 6}, {0x6c, 6}, // 0b101000xx ('l') + {0x6d, 6}, {0x6d, 6}, {0x6d, 6}, {0x6d, 6}, // 0b101001xx ('m') + {0x6e, 6}, {0x6e, 6}, {0x6e, 6}, {0x6e, 6}, // 0b101010xx ('n') + {0x70, 6}, {0x70, 6}, {0x70, 6}, {0x70, 6}, // 0b101011xx ('p') + {0x72, 6}, {0x72, 6}, {0x72, 6}, {0x72, 6}, // 0b101100xx ('r') + {0x75, 6}, {0x75, 6}, {0x75, 6}, {0x75, 6}, // 0b101101xx ('u') + {0x3a, 7}, {0x3a, 7}, // 0b1011100x (':') + {0x42, 7}, {0x42, 7}, // 0b1011101x ('B') + {0x43, 7}, {0x43, 7}, // 0b1011110x ('C') + {0x44, 7}, {0x44, 7}, // 0b1011111x ('D') + {0x45, 7}, {0x45, 7}, // 0b1100000x ('E') + {0x46, 7}, {0x46, 7}, // 0b1100001x ('F') + {0x47, 7}, {0x47, 7}, // 0b1100010x ('G') + {0x48, 7}, {0x48, 7}, // 0b1100011x ('H') + {0x49, 7}, {0x49, 7}, // 0b1100100x ('I') + {0x4a, 7}, {0x4a, 7}, // 0b1100101x ('J') + {0x4b, 7}, {0x4b, 7}, // 0b1100110x ('K') + {0x4c, 7}, {0x4c, 7}, // 0b1100111x ('L') + {0x4d, 7}, {0x4d, 7}, // 0b1101000x ('M') + {0x4e, 7}, {0x4e, 7}, // 0b1101001x ('N') + {0x4f, 7}, {0x4f, 7}, // 0b1101010x ('O') + {0x50, 7}, {0x50, 7}, // 0b1101011x ('P') + {0x51, 7}, {0x51, 7}, // 0b1101100x ('Q') + {0x52, 7}, {0x52, 7}, // 0b1101101x ('R') + {0x53, 7}, {0x53, 7}, // 0b1101110x ('S') + {0x54, 7}, {0x54, 7}, // 0b1101111x ('T') + {0x55, 7}, {0x55, 7}, // 0b1110000x ('U') + {0x56, 7}, {0x56, 7}, // 0b1110001x ('V') + {0x57, 7}, {0x57, 7}, // 0b1110010x ('W') + {0x59, 7}, {0x59, 7}, // 0b1110011x ('Y') + {0x6a, 7}, {0x6a, 7}, // 0b1110100x ('j') + {0x6b, 7}, {0x6b, 7}, // 0b1110101x ('k') + {0x71, 7}, {0x71, 7}, // 0b1110110x ('q') + {0x76, 7}, {0x76, 7}, // 0b1110111x ('v') + {0x77, 7}, {0x77, 7}, // 0b1111000x ('w') + {0x78, 7}, {0x78, 7}, // 0b1111001x ('x') + {0x79, 7}, {0x79, 7}, // 0b1111010x ('y') + {0x7a, 7}, {0x7a, 7}, // 0b1111011x ('z') + {0x26, 8}, // 0b11111000 ('&') + {0x2a, 8}, // 0b11111001 ('*') + {0x2c, 8}, // 0b11111010 (',') + {0x3b, 8}, // 0b11111011 (';') + {0x58, 8}, // 0b11111100 ('X') + {0x5a, 8}, // 0b11111101 ('Z') +}; + +constexpr size_t kShortCodeTableOldSize = 124; +constexpr ShortCodeInfo kShortCodeTableOld[kShortCodeTableOldSize] = { {0x30, 5}, // Match: 0b0000000, Symbol: 0 {0x30, 5}, // Match: 0b0000001, Symbol: 0 {0x30, 5}, // Match: 0b0000010, Symbol: 0 @@ -409,7 +501,13 @@ return ss.str(); } -HpackHuffmanDecoder::HpackHuffmanDecoder() = default; +HpackHuffmanDecoder::HpackHuffmanDecoder() + : enable_optimizations_( + GetQuicheReloadableFlag(hpack_huffman_decoder_optimizations)) { + if (enable_optimizations_) { + QUICHE_RELOADABLE_FLAG_COUNT(hpack_huffman_decoder_optimizations); + } +} HpackHuffmanDecoder::~HpackHuffmanDecoder() = default; @@ -421,14 +519,27 @@ while (true) { QUICHE_DVLOG(3) << "Enter Decode Loop, bit_buffer_: " << bit_buffer_; - if (bit_buffer_.count() >= 7) { + if (enable_optimizations_ && bit_buffer_.count() >= 8) { + // Get high 8 bits of the bit buffer, see if that contains a complete + // code of 5, 6, 7, or 8 bits. + uint8_t short_code = + bit_buffer_.value() >> (kHuffmanAccumulatorBitCount - 8); + if (short_code < kShortCodeTableSize) { + ShortCodeInfo info = kShortCodeTable[short_code]; + bit_buffer_.ConsumeBits(info.length); + output->push_back(static_cast<char>(info.symbol)); + continue; + } + // The code is more than 8 bits long. Use PrefixToInfo, etc. to decode + // longer codes. + } else if (!enable_optimizations_ && bit_buffer_.count() >= 7) { // Get high 7 bits of the bit buffer, see if that contains a complete // code of 5, 6 or 7 bits. uint8_t short_code = bit_buffer_.value() >> (kHuffmanAccumulatorBitCount - 7); QUICHE_DCHECK_LT(short_code, 128); - if (short_code < kShortCodeTableSize) { - ShortCodeInfo info = kShortCodeTable[short_code]; + if (short_code < kShortCodeTableOldSize) { + ShortCodeInfo info = kShortCodeTableOld[short_code]; bit_buffer_.ConsumeBits(info.length); output->push_back(static_cast<char>(info.symbol)); continue;
diff --git a/quiche/http2/hpack/huffman/hpack_huffman_decoder.h b/quiche/http2/hpack/huffman/hpack_huffman_decoder.h index 910aba5..2148845 100644 --- a/quiche/http2/hpack/huffman/hpack_huffman_decoder.h +++ b/quiche/http2/hpack/huffman/hpack_huffman_decoder.h
@@ -122,6 +122,7 @@ private: HuffmanBitBuffer bit_buffer_; + const bool enable_optimizations_; }; inline std::ostream& operator<<(std::ostream& out,
diff --git a/quiche/http2/hpack/huffman/hpack_huffman_decoder_test.cc b/quiche/http2/hpack/huffman/hpack_huffman_decoder_test.cc index 260415d..06d0e90 100644 --- a/quiche/http2/hpack/huffman/hpack_huffman_decoder_test.cc +++ b/quiche/http2/hpack/huffman/hpack_huffman_decoder_test.cc
@@ -16,6 +16,7 @@ #include "quiche/http2/decoder/decode_status.h" #include "quiche/http2/test_tools/random_decoder_test_base.h" #include "quiche/common/platform/api/quiche_expect_bug.h" +#include "quiche/common/platform/api/quiche_flags.h" #include "quiche/common/platform/api/quiche_test.h" namespace http2 { @@ -243,6 +244,24 @@ } } +TEST(HpackHuffmanDecoderStandaloneTest, ReloadableFlag8BitTable) { + std::string huffman_encoded; + ASSERT_TRUE( + absl::HexStringToBytes("f1e3c2e5f23a6ba0ab90f4ff", &huffman_encoded)); + std::string plain_string = "www.example.com"; + + for (bool flag_value : {false, true}) { + SetQuicheReloadableFlag(hpack_huffman_decoder_optimizations, flag_value); + HpackHuffmanDecoder decoder; + std::string buffer; + EXPECT_TRUE(decoder.Decode(huffman_encoded, &buffer)) + << "Failed when flag is " << flag_value; + EXPECT_TRUE(decoder.InputProperlyTerminated()) + << "Failed when flag is " << flag_value; + EXPECT_EQ(buffer, plain_string) << "Failed when flag is " << flag_value; + } +} + } // namespace } // namespace test } // namespace http2