kawasin73のブログ

技術記事とかいろんなことをかくブログです

The fastest HTTP parser of Rust

Rust 調査

速さは正義。どうも、かわしんです。

Rust で一番速い HTTP パーサーは C で書かれた picohttpparser の Rust バインディング、picohttpparser-sys です。ガハハ。

$ RUSTFLAGS="-C target-feature=+sse4.2" cargo +nightly bench
    Finished bench [optimized] target(s) in 0.28s
warning: the following packages contain code that will be rejected by a future version of Rust: traitobject v0.1.0
note: to see what the problems were, use the option `--future-incompat-report`, or run `cargo report future-incompatibilities --id 78`
     Running unittests src/main.rs (target/release/deps/rust_http_parser_bench-63366b14855362d6)

running 16 tests
test tests::bench_dumb_http_parser   ... bench:       2,085 ns/iter (+/- 537) = 337 MB/s
test tests::bench_http_box           ... bench:         592 ns/iter (+/- 43) = 1187 MB/s
test tests::bench_http_bytes         ... bench:       2,347 ns/iter (+/- 341) = 299 MB/s
test tests::bench_http_muncher       ... bench:         795 ns/iter (+/- 141) = 884 MB/s
test tests::bench_http_parser        ... bench:       3,791 ns/iter (+/- 594) = 185 MB/s
test tests::bench_http_pull_parser   ... bench:       6,990 ns/iter (+/- 658) = 100 MB/s
test tests::bench_http_tiny          ... bench:      12,675 ns/iter (+/- 1,219) = 55 MB/s
test tests::bench_httparse           ... bench:         276 ns/iter (+/- 11) = 2547 MB/s
test tests::bench_milstian_http      ... bench:      23,279 ns/iter (+/- 2,616) = 30 MB/s
test tests::bench_picohttpparser_sys ... bench:         135 ns/iter (+/- 24) = 5207 MB/s
test tests::bench_rhymuweb           ... bench:       6,868 ns/iter (+/- 631) = 102 MB/s
test tests::bench_rocket_http_hyper  ... bench:       4,119 ns/iter (+/- 420) = 170 MB/s
test tests::bench_saf_httparser      ... bench:       5,870 ns/iter (+/- 528) = 119 MB/s
test tests::bench_stream_httparse    ... bench:       1,781 ns/iter (+/- 202) = 394 MB/s
test tests::bench_thhp               ... bench:         177 ns/iter (+/- 14) = 3971 MB/s
test tests::bench_uhttp_request      ... bench:         261 ns/iter (+/- 24) = 2693 MB/s

test result: ok. 0 passed; 0 failed; 0 ignored; 16 measured; 0 filtered out; finished in 19.03s

Pure Rust な HTTP パーサーで一番速いのは thhp でした。

github.com

環境

$ cargo -V
cargo 1.68.0-nightly (8c460b223 2023-01-04)

背景

仕事で Rust を使うようになり何か Rust を使って自分で作りたいと思ったのが発端です。

1から作るのは大変なので何か有名なプロダクトを Rust に移植しようかなと思っていて、もともと興味のあった HTTP サーバかデータベースを色々調べていました。

そこで、h2o の作者の Kazuho Oku さんのスライドを見つけて感銘を受けます。2014 年の発表資料ですが今でも感動できる資料です。特に 21 ページの "characteristics of a fast program" はとても良かったです。

  • characteristics of a fast program
    • executes less instructions
      • speed is a result of simplicity, not complexity
    • causes less pipeline hazards
      • minimum number of conditional branches / indirect calls
      • use branch-predictor-friendly logic

www.slideshare.net

このスライドでは最速の HTTP パーサーとして picohttpparser が紹介されていました。そこで、picohttpparser を Rust に移植することにしました。

が、すでに Rust で picohttpparser より速い HTTP パーサが実装されていたら新規性が薄れるので Rust の HTTP パーサのベンチマークを取ることにしました。

調査

Rust の HTTP パーサは crates.io で "http parser" と調べて出てきたものを片っぱしからベンチマークに突っ込みます。

github.com

いくつかのクレートは以下の理由でベンチマークが取れませんでした。

その結果が最初に貼り付けたログです。

なぜ速いのか

Pure Rust なもので特に早かったクレートは thhp、httparse、uhttp_request の 3 つでした。これらのどれも picohttpparser と同じようにステートレスにパースしています。

github.com

uhttp_request は改行で split した後にさらに空白で split するなどやや無駄があるように思いました。また、各文字が正しい値になっているかの validation をしていません。そのためあまり参考にはならないかもしれないです。

github.com

httparse はダウンロード数の多いクレートなので Rust の中のデファクトのライブラリだと思われます。

github.com

thhp は Totemo-Hayai (とても速い) HTTP Parser の略だそうです。作者の方の Twitter を見る限り、picohttpparser を意識して書かれているようです。

httparse と thhp のコードを読むとそれぞれ違いがあります。ただ、どこが有意な差を生み出しているのかはさらに調査が必要そうです。

  • method の評価
    • httparse: 先頭 4 バイトを match 構文で比較
    • thhp: 1 文字ずつ TCHAR_MAP で検証
    • picohttpparser: SIMD と token_char_map で検証
  • path の評価
    • httparse: SIMD と URI_MAP で評価
    • thhp: 1 文字ずつ 0x20 < c && c < 0x7F で評価
    • picohttpparser: SIMD と IS_PRINTABLE_ASCII(c) ((unsigned char)(c)-040u < 0137u) で評価
  • version の評価
    • httparse: 先頭 8 バイトを match 構文で比較
    • thhp: 先頭 8 バイトを 1 文字ずつ評価
    • picohttpparser: 先頭 8 バイトを 1 文字ずつ評価
  • field name の評価
    • httparse: parse_headers_iter_uninit でやっているがなんか長い。HEADER_NAME_MAP で１文字ずつ評価している
    • thhp: 1 文字ずつ TCHAR_MAP で検証
    • picohttpparser: SIMD と token_char_map で検証
  • filed value の評価
    • httparse: parse_headers_iter_uninit でやっている。SIMD と HEADER_VALUE_MAP
    • thhp: SIMD と FIELD_VALUE_CHAR_MAP で評価
    • picohttpparser: SIMD と IS_PRINTABLE_ASCIIで評価。さらに追加の検証も入っている。

結論

thhp がすでにあるので picohttpparser の Rust への移植は諦めました。。。thhp は filed value 以外でも SIMD を使うようにすればもっと速くなりそう。