GoでHTTPルータを作ってみた

はじめに

パトリシア木を使ってHTTPルーティングすると早いって聞いたので、
こんな感じかなと思ってGoで実装してみました

要件

まず、下記のようなパスのパターンをルーティングするとします

GET /users
GET /users/:name
GET /users/taro/man
GET /users/hanako/woman
GET /users/akira/:sex
GET /users/:name/:sex
GET /users/:name/woman

パスのパターンとして二種類あって、パラム付きは : と * の二種類をメタ文字として扱います
まあよくあるやつです

• 静的パターン /users/taro/man
• パラム付きパターン /users/:name/woman

優先度は 静的 → : → * とします

実装

で、考えた結果こんな感じの木になりました
オレンジは終端ノードです

ルックアップの処理として、まず根の下にメソッドがあってそれを進みます
次にフルパスが静的パスかどうかを判定します
先頭に / があるものが静的のフルパスになります
判定に失敗したらパラム付きパスと判断して、ディレクトリ単位で木を辿っていきます
ディレクトリの静的判定に失敗したときに、兄弟にパラム付きの物があればそっちに進みます
文字列が最後まで進んだとき、ノードに http.HandlerFunc が入っていたらそれを返します

詳しくは下記に実装してみたので見てみてください
https://github.com/ngc224/mux/

ベンチマーク

で、せっかく作ったので早いと言われている他のルーターとくらべてみました
BenchmarkMy が今回作ったやつです
ミドルウェアなどの機能がないからかもしれませんが、まあそこそこの速度は出ているようです

BenchmarkMy_GithubAll                    10000         229581 ns/op        53444 B/op          501 allocs/op
BenchmarkBeego_GithubAll                  3000         438911 ns/op        74709 B/op          812 allocs/op
BenchmarkChi_GithubAll                   10000         295937 ns/op        61716 B/op          406 allocs/op
BenchmarkDenco_GithubAll                 20000          96656 ns/op        20224 B/op          167 allocs/op
BenchmarkGin_GithubAll                   50000          44018 ns/op            0 B/op            0 allocs/op
BenchmarkHttpRouter_GithubAll            20000          65990 ns/op        13792 B/op          167 allocs/op
BenchmarkLARS_GithubAll                  50000          33338 ns/op            0 B/op            0 allocs/op
BenchmarkPossum_GithubAll                 3000         385266 ns/op        84454 B/op          609 allocs/op
BenchmarkRivet_GithubAll                 10000         119507 ns/op        16272 B/op          167 allocs/op
BenchmarkTango_GithubAll                  3000         441718 ns/op        63845 B/op         1618 allocs/op
BenchmarkVulcan_GithubAll                10000         263241 ns/op        19894 B/op          609 allocs/op

何故か静的パスが早いです

BenchmarkMy_StaticAll                   200000           9118 ns/op            0 B/op            0 allocs/op
BenchmarkBeego_StaticAll                  5000         356464 ns/op        57780 B/op          628 allocs/op
BenchmarkChi_StaticAll                   10000         201796 ns/op        47731 B/op          314 allocs/op
BenchmarkDenco_StaticAll                200000           9202 ns/op            0 B/op            0 allocs/op
BenchmarkGin_StaticAll                  100000          20539 ns/op            0 B/op            0 allocs/op
BenchmarkHttpRouter_StaticAll           100000          12728 ns/op            0 B/op            0 allocs/op
BenchmarkHttpTreeMux_StaticAll          100000          12333 ns/op            0 B/op            0 allocs/op
BenchmarkLARS_StaticAll                  50000          20841 ns/op            0 B/op            0 allocs/op
BenchmarkPossum_StaticAll                 5000         282806 ns/op        65316 B/op          471 allocs/op
BenchmarkRivet_StaticAll                 50000          29397 ns/op            0 B/op            0 allocs/op
BenchmarkTango_StaticAll                  5000         321933 ns/op        39235 B/op         1256 allocs/op
BenchmarkVulcan_StaticAll                10000         177711 ns/op        15386 B/op          471 allocs/op

総評

ていうか分岐していない節を一つにまとめたものをパトリシア木っていうらしいですが、
これ違いますね...
他のルータの実装見て研究していきたいです