速さは正義。どうも、かわしんです。
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
でした。
環境
- Macbook Pro (13-inch, 2018, Four Thunderbolt 3 Ports)
- Processor: 2.7 GHz Quad-Core Intel Core i7
- Memory: 16 GB 2133 MHz LPDDR3
$ 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" と調べて出てきたものを片っぱしからベンチマークに突っ込みます。
いくつかのクレートは以下の理由でベンチマークが取れませんでした。
- https://crates.io/crates/safe_http_parser
- なぜかダウンロードできない。
- https://crates.io/crates/simple_http_parser
- インターフェースが
std::net::TCPStream
しか受け付けないため比較できず。全然 simple じゃない。
- インターフェースが
- https://crates.io/crates/http_request_parser
- simple_http_parser と同じ理由
- https://crates.io/crates/li-async-h1
- パーサは httparse を使っていた
- https://crates.io/crates/async-h1
- li-async-h1 と同じ理由
- https://crates.io/crates/http_headers
- 空の
it_works()
しかないライブラリ・・・。名前の予約だけしたのかな・・・。
- 空の
- https://crates.io/crates/pico
- 期待していたが crate が壊れていてコンパイルできなかった。
その結果が最初に貼り付けたログです。
なぜ速いのか
Pure Rust なもので特に早かったクレートは thhp
、httparse
、uhttp_request
の 3 つでした。これらのどれも picohttpparser
と同じようにステートレスにパースしています。
uhttp_request
は改行で split した後にさらに空白で split するなどやや無駄があるように思いました。また、各文字が正しい値になっているかの validation をしていません。そのためあまり参考にはならないかもしれないです。
httparse
はダウンロード数の多いクレートなので Rust の中のデファクトのライブラリだと思われます。
thhp
は Totemo-Hayai (とても速い) HTTP Parser の略だそうです。作者の方の Twitter を見る限り、picohttpparser
を意識して書かれているようです。
最近書いてる http parser が SSE 使わない picohttpparser 程度には早くなった。
— いじゅういん (@kei10in) 2018年4月4日
httparse
と thhp
のコードを読むとそれぞれ違いがあります。ただ、どこが有意な差を生み出しているのかはさらに調査が必要そうです。
- method の評価
httparse
: 先頭 4 バイトを match 構文で比較thhp
: 1 文字ずつTCHAR_MAP
で検証picohttpparser
: SIMD とtoken_char_map
で検証
- path の評価
- version の評価
httparse
: 先頭 8 バイトを match 構文で比較thhp
: 先頭 8 バイトを 1 文字ずつ評価picohttpparser
: 先頭 8 バイトを 1 文字ずつ評価
- field name の評価
httparse
:parse_headers_iter_uninit
でやっているがなんか長い。HEADER_NAME_MAP
で1文字ずつ評価しているthhp
: 1 文字ずつTCHAR_MAP
で検証picohttpparser
: SIMD とtoken_char_map
で検証
- filed value の評価
結論
thhp
がすでにあるので picohttpparser
の Rust への移植は諦めました。。。thhp
は filed value 以外でも SIMD を使うようにすればもっと速くなりそう。