Skip to content

[chttp2] Improve huffman decode efficiency#30479

Merged
ctiller merged 137 commits intogrpc:masterfrom
ctiller:awesome-goats
Sep 13, 2022
Merged

[chttp2] Improve huffman decode efficiency#30479
ctiller merged 137 commits intogrpc:masterfrom
ctiller:awesome-goats

Conversation

@ctiller
Copy link
Copy Markdown
Member

@ctiller ctiller commented Aug 3, 2022 •
edited
Loading

This change introduces a configurable huffman decoding compilation engine, and uses it to generate a reasonably good decoder.

My original hope was to eliminate any lookup tables at all on this path, but I don't have any great ideas on how to do that and still have reasonable build times, so we'll stick to code generation for now.

This version is within a few kb of size of the previous version, and a little over twenty times faster:

-----------------------------------------------------------------
Benchmark                       Time             CPU   Iterations
-----------------------------------------------------------------
BM_Decode                  602870 ns       602753 ns         6939
BM_Decode                  607488 ns       607308 ns         6939
BM_Decode                  604599 ns       604457 ns         6939
BM_Decode                  603142 ns       602974 ns         6939
BM_Decode                  599810 ns       599652 ns         6939
BM_Decode                  600134 ns       599987 ns         6939
BM_Decode                  599574 ns       599461 ns         6939
BM_Decode                  599030 ns       598904 ns         6939
BM_Decode                  597569 ns       597436 ns         6939
BM_Decode                  597589 ns       597441 ns         6939
BM_Decode_mean             601180 ns       601037 ns           10
BM_Decode_median           599972 ns       599820 ns           10
BM_Decode_stddev             3237 ns         3226 ns           10
BM_Decode_cv                 0.54 %          0.54 %            10
BM_LegacyDecode          12332575 ns     12329242 ns          342
BM_LegacyDecode          12211321 ns     12208651 ns          342
BM_LegacyDecode          12174838 ns     12171827 ns          342
BM_LegacyDecode          12177283 ns     12174420 ns          342
BM_LegacyDecode          12161660 ns     12158573 ns          342
BM_LegacyDecode          12182466 ns     12179459 ns          342
BM_LegacyDecode          12207460 ns     12204790 ns          342
BM_LegacyDecode          12212739 ns     12209375 ns          342
BM_LegacyDecode          12192951 ns     12190298 ns          342
BM_LegacyDecode          12185965 ns     12183158 ns          342
BM_LegacyDecode_mean     12203926 ns     12200979 ns           10
BM_LegacyDecode_median   12189458 ns     12186728 ns           10
BM_LegacyDecode_stddev      48237 ns        48124 ns           10
BM_LegacyDecode_cv           0.40 %          0.39 %            10

Future work will be to tune the generation parameters and generate the absolute optimal arguments for data center and for mobile.

(note: the commits on this change are pretty meaningless - they were more storing intermediate steps during my research as I toyed with how to represent the tables and the tradeoffs in table size versus code size)

@grpc-checks grpc-checks bot added bloat/low and removed bloat/high labels Aug 5, 2022
ctiller and others added 18 commits September 10, 2022 09:03
@ctiller
fix
8fe1381
@ctiller
fix
a15eb6f
@ctiller
Automated change: Fix sanity tests
bdbea7c
@ctiller
Merge pull request #863 from ctiller/create-pull-request/patch-a15eb6f
ea55206 
Automated fix for refs/heads/awesome-goats
@ctiller
fix
b71c5ff
@ctiller
Merge branch 'awesome-goats' of github.com:ctiller/grpc into awesome-…
230ac35 
…goats
@ctiller
fix
8e8e511
@ctiller
Automated change: Fix sanity tests
6fe06e5
@ctiller
Merge pull request #864 from ctiller/create-pull-request/patch-8e8e511
ccba562 
Automated fix for refs/heads/awesome-goats
@ctiller
fix
9b5d3bd
@ctiller
Merge branch 'awesome-goats' of github.com:ctiller/grpc into awesome-…
f3dad6b 
…goats
@ctiller
add encode/decode fuzzer
99bc6fd
@ctiller
Automated change: Fix sanity tests
ea2cc67
@ctiller
Merge pull request #865 from ctiller/create-pull-request/patch-99bc6fd
3ce14b5 
Automated fix for refs/heads/awesome-goats
@ctiller
fix
2cfe766
@ctiller
Merge branch 'awesome-goats' of github.com:ctiller/grpc into awesome-…
dbcbf4c 
…goats
@ctiller
fix
07379e6
@ctiller
fix
bcd1bbf
yashykt
yashykt reviewed Sep 12, 2022
View reviewed changes
bazel/experiments.bzl
},
"off": {
"core_end2end_tests": [
"new_hpack_huffman_decoder",
Copy link
Copy Markdown
Member

@yashykt yashykt Sep 12, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

are tests also experiments?

Copy link
Copy Markdown
Member Author

@ctiller ctiller Sep 12, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

tests get enabled by experiments: we automatically run some subset of the test suite with each experiment in both states (on and off)

src/core/ext/transport/chttp2/transport/decode_huff.h Outdated
bool done_ = false;
};
} // namespace grpc_core
#endif // GRPC_CORE_EXT_TRANSPORT_CHTTP2_TRANSPORT_DECODE_HUFF_H No newline at end of file
Copy link
Copy Markdown
Member

@yashykt yashykt Sep 12, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

please fix the no new line at end of file

Copy link
Copy Markdown
Member Author

@ctiller ctiller Sep 12, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

done

src/core/ext/transport/chttp2/transport/hpack_parser.cc Outdated
} else {
assert(emit == 256);
if (IsNewHpackHuffmanDecoderEnabled()) {
// If there's insufficient bytes remaining, return now.
Copy link
Copy Markdown
Member

@yashykt yashykt Sep 12, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks like this this if -if (input->remaining() < length)... is the same in the bottom else part. We should be able to bring it out

Copy link
Copy Markdown
Member Author

@ctiller ctiller Sep 12, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

done

@ctiller ctiller merged commit 6c7f921 into grpc:master Sep 13, 2022
@ctiller ctiller deleted the awesome-goats branch September 13, 2022 18:24
ctiller added a commit that referenced this pull request Sep 13, 2022
@ctiller
Revert "[chttp2] Improve huffman decode efficiency (#30479)"
6b82022 
This reverts commit 6c7f921.
@ctiller ctiller mentioned this pull request Sep 13, 2022
Merged
ctiller added a commit that referenced this pull request Sep 13, 2022
@ctiller
Revert "[chttp2] Improve huffman decode efficiency (#30479)" (#30961)
bfea470 
This reverts commit 6c7f921.
ctiller added a commit that referenced this pull request Sep 13, 2022
@ctiller
Revert "Revert "[chttp2] Improve huffman decode efficiency (#30479)" (#…
dcf7a22 
…30961)"

This reverts commit bfea470.
ctiller added a commit that referenced this pull request Sep 13, 2022
@ctiller
Revert "Revert "[chttp2] Improve huffman decode efficiency (#30479)" (#…
92f58c1 
…30961)" (#30962)

This reverts commit bfea470.
@copybara-service copybara-service bot added the imported Specifies if the PR has been imported to the internal repository label Sep 14, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@yashykt yashykt yashykt approved these changes

@veblush veblush Awaiting requested review from veblush

@jtattermusch jtattermusch Awaiting requested review from jtattermusch

@gnossen gnossen Awaiting requested review from gnossen

Assignees

No one assigned

Labels

bloat/medium imported Specifies if the PR has been imported to the internal repository lang/c++ lang/core per-call-memory/neutral per-channel-memory/neutral release notes: no Indicates if PR should not be in release notes

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@ctiller @yashykt @grpc-kokoro