JSのウェブフレームワークで高速なルーターを実装する方法

https://nseg.connpass.com/event/251366/ での発表資料です。

Transcript

1. JS のウェブフレームワークで 高速なルーターを 実装する方法 天野卓@2022年6月25日 1 1
2. https://github.com/honojs/hono 2 2
3. https://github.com/honojs/hono/blob/master/README.md Hono - [炎] means flame in Japanese - is a small, simple, and ultrafast web framework for Cloudflare Workers or Service Worker based serverless such as Fastly Compute@Edge. 3 3
4. https://zenn.dev/yusukebe/articles/0c7fed0949e6f7 4 4
5. https://workers.cloudflare.com/ 5 5
6. Cloudflare Workers https://developers.cloudflare.com/workers/runtime- apis/web-standards/ Cloudflare Workers uses the V8 JavaScript engine from Google Chrome. The Workers runtime is updated at least once a week, to at least the version that is currently used by Chrome’s stable release. This means you can safely use the latest JavaScript features, with no need for transpilers. All of the standard built-in objects supported by the current Google Chrome stable release are supported, with a few notable exceptions: 6 6
7. https://yusukebe.com/posts/2022/cloudflare-workers- 7 7
8. 今日話すこと 8 8
9. https://github.com/honojs/hono 9 9
10. 注意事項 ベンチマークは node:18.4 のdocker imageで計測 ホストはEC2の c5.large エンジンはCloudflare Workersと同じV8なので、この環 境で最適化できれば概ねOK（？） (Compute@EdgeはSpiderMonkeyらしい) 環境やバージョンが異なると性能の傾向も異なるかも 10 10
11. さて 11 11
12. ルーターの仕事 12 12
13. const app = new Hono(); app.get("/", function a() {}); app.get("/users/:id", function b() {}); app.get("/users/:id/posts", function c() {}); GET / => a GET /users/1 => b GET /users/1/posts => c 13 13
14. 素朴な実装 14 14
15. const routes = [ [/^\/$/, a], [/^\/users\/[^/]+$/, b], [/^\/users\/[^/]+\/posts$/, c], ]; // ここまでを事前に用意しておく const path = request.url.replace(/https?:\/\/[^/]+/, ""); // 実行時にリクエストオブジェクトからパスを取り出す for (const [regexp, handler] of routes) { if (regexp.test(path)) { return handler; } } 15 15
16. 木構造を使う実装 16 16
17. / $ users :id $ posts $ 17 17
18. 木構造を使う実装 JS上での実装でも結構速度はでる :idの文字種を制限しない場合には、ノードでの文字列の一致 も省略することができ、実行時には1度も正規表現による一致 を行わずに同値の比較だけで高速に探索することができる コードもシンプルで直観的なものにしやすい 18 18
19. もっと速くしたい 19 19
20. 文字列の一致に特化した機能といえば 20 20
21. 正規表現 21 21
22. Perlでの先行事例 Router::Boom https://metacpan.org/dist/Router-Boom 22 22
23. Perlでできること use re 'eval'; my @routes = ($a, $b, $c); my @c = (); my $m = undef; $path =~ m{ \A/(?:\z(?{$m=0}) |users/([^/]+)(?:\z(?{$m=1;@c=($1)}) |/posts\z(?{$m=2;@c=($1)}))) }x; 23 23
24. JavaScriptでできること（抜粋） const re = /^\/(?:$()|users\/([^\/]+)(?:$()|\/posts$()))/; const matchResult = path.match(re); routeData[matchResult.indexOf("", 1)]; 24 24
25. JavaScriptでできること（全体） const routeData: [number, Array<[string, number]>][] = []; routeData[1] = [a, []]; routeData[3] = [b, [["id", 1]]]; routeData[4] = [c, [["id", 1]]]; const re = /^\/(?:$()|users\/([^\/]+)(?:$()|\/posts$()))/; // ここまでを事前に用意しておく const matchResult = path.match(re); if (matchResult) { const [handler, paramMap] = routeData[matchResult.indexOf("", 1)]; const pathParams = {} for (const [key, index] of paramMap) { pathParams[key] = matchResult[index]; } return [handler, pathParams]; } 25 25
26. 実行時の処理を以下の関数の 呼び出しのみで済むようにする String.prototype.match() Array.prototype.indexOf() 26 26
27. String.prototype.match() トライ木から正規表現を生成してRegExpオブジェクトを作 っておいて、それを適用する。 27 27
28. JSでわざわざトライ木でまとめる必要はあるの？ 28 28
29. const prefix = Array.from({ length: 1000 }, () => "prefix").join(""); const re = new RegExp(Array.from({ length: 26 }, (_, k) => `${prefix}${String.fromCharCode("a".charCodeAt(0) + k)}` ).join("|")); // `${prefix}a|${prefix}b|${prefix}c|...` suite .add("a", () => { re.test(`${prefix}a`); }) .add("z", () => { re.test(`${prefix}z`); }) .run(); a x 326,194 ops/sec ±0.61% (91 runs sampled) z x 334,725 ops/sec ±0.72% (92 runs sampled) 29 29
30. const prefix = Array.from({ length: 1000 }, () => "prefix").join(""); const re = new RegExp(Array.from({ length: 26 }, (_, k) => `with-(capture)${prefix}${String.fromCharCode("a".charCodeAt(0) + k)}` ).join("|")); // `with-(capture)${prefix}a|with-(capture)${prefix}b|...` suite .add("a", () => { re.test(`with-capture${prefix}a`); }) .add("z", () => { re.test(`with-capture${prefix}z`); }) .run(); a x 301,888 ops/sec ±0.54% (93 runs sampled) z x 272,048 ops/sec ±0.42% (96 runs sampled) 30 30
31. const prefix = Array.from({ length: 1000 }, () => "prefix").join(""); const re = new RegExp( `with-(capture)(?:${...})` ).join("|")); // `with-(capture)(?:${prefix}a|${prefix}b|${prefix}c|...` suite .add("a", () => { re.test(`with-capture${prefix}a`); }) .add("z", () => { re.test(`with-capture${prefix}z`); }) .run(); a x 310,702 ops/sec ±0.58% (93 runs sampled) z x 314,374 ops/sec ±0.92% (88 runs sampled) 31 31
32. Array.prototype.indexOf() indexOf() は計算量としては O(n) だけれども ウェブフレームワークのルーティングなので、nはそれほ ど大きくならない nが大きくなければ、JSで頑張るよりもindexOfを使った 方が速い 32 32
33. ここまでで、 探索については高速になりました 33 33
34. もうちょっとだけ続くんじゃ 34 34
35. 最初に出したルーティング定義の例 const app = new Hono(); app.get("/", function a() {}); app.get("/users/:id", function b() {}); app.get("/users/:id/posts", function c() {}); 35 35
36. ミドルウェアを適用する例 const app = new Hono(); app.all("*", logger); app.all("/api/*", cors); app.get("/api/users/:id", function handler() {}); app.all("/api/*", fallback); 36 36
37. const routes = [ [/^\//, logger], [/^\/api(?:$|\/)/, cors], [/^\/api\/users\/[^/]+$/, handler], [/^\/api(?:$|\/)/, fallback], ]; // ここまでを事前に用意しておく const path = request.url.replace(/https?:\/\/[^/]+/, ""); const handlers = []; for (const [regexp, handler] of routes) { if (regexp.test(path)) { handlers.push(handler); } } return handlers.reduceRight((prev, current) => { current(() => prev()) }, () => undefined) 37 37
38. 雰囲気としてはこんな感じ logger(() => { cors(() => { handler(() => { fallback(); }); }); }); 38 38
39. 39 39
40. 40 40
41. 41 41
42. Honoでは、ここまでがルーターの仕事 const routes = [ [/^\//, logger], [/^\/api(?:$|\/)/, cors], [/^\/api\/users\/[^/]+$/, handler], [/^\/api(?:$|\/)/, fallback], ]; // ここまでを事前に用意しておく const path = request.url.replace(/https?:\/\/[^/]+/, ""); const handlers = []; for (const [regexp, handler] of routes) { if (regexp.test(path)) { handlers.push(handler); } } return handlers 42 42
43. これ相当の処理は別の場所で行う return handlers.reduceRight((prev, current) => { current(() => prev()) }, () => undefined) 43 43
44. const app = new Hono(); app.all("*", logger); app.all("/api/*", cors); app.get("/api/users/:id", function handler() {}); app.all("/api/*", fallback); GET /api/users/1 => [logger, cors, handler, fallback] 44 44
45. 複数のミドルウェア/ハンドラを探して返すのは、 正規表現一発で探すのと相性が悪いのでは？ const re = /^\/(?:$()|users\/([^\/]+)(?:$()|\/posts$()))/; 45 45
46. 46 46
47. 殆どのユースケースで 以下のようになっているはず。 探すべきなのは1つのハンドラである ハンドラに適用されるミドルウェアは決まっている 47 47
48. const app = new Hono(); app.all("*", logger); app.all("/api/*", cors); app.get("/api/users/:id", function handler() {}); app.all("/api/*", fallback); つまりここで探し出したいのは handler であり、 かつ handler が見つかったときには、常に [logger, cors, handler, fallback] が返されるはず。 48 48
49. const routeData: [number, Array<[string, number]>][] = []; routeData[1] = [a, []]; routeData[3] = [b, [["id", 1]]]; routeData[4] = [c, [["id", 1]]]; const re = /^\/(?:$()|users\/([^\/]+)(?:$()|\/posts$()))/; // ここまでを事前に用意しておく const path = request.url.replace(/https?:\/\/[^/]+/, ""); const matchResult = path.match(re); if (matchResult) { const [handler, paramMap] = routeData[matchResult.indexOf("", 1)]; const pathParams = {} for (const [key, index] of paramMap) { pathParams[key] = matchResult[index]; } return [handler, pathParams]; } 49 49
50. const a = [ logger, cors, a ]; const b = [ logger, basicAuth, b ]; const c = [ logger, basicAuth, c ]; 50 50
51. const routeData: [number, Array<[string, number]>][] = []; routeData[1] = [ a, []]; routeData[3] = [ b, [["id", 1]]]; routeData[4] = [ c, [["id", 1]]]; const re = /^\/(?:$()|users\/([^\/]+)(?:$()|\/posts$()))/; // ここまでを事前に用意しておく const matchResult = url.match(re); if (matchResult) { const [handler, paramMap] = routeData[matchResult.indexOf("", 1)]; const pathParams = {} for (const [key, index] of paramMap) { pathParams[key] = matchResult[index]; } return [handler, pathParams]; } 51 51
52. の作り方 const app = new Hono(); app.all("*", logger); app.all("/api/*", cors); app.get("/api/users/:id", function handler() {}); app.all("/api/*", fallback); 52 52
53. 登録された状態 [ // [ パス, 登録順, ハンドラ] ["*", 0, logger], ["/api/*", 1, cors], ["/api/users/:id", 2, handler], ["/api/*", 3, fallback], ] 53 53
54. パスの抽象度の高い順に並べ替えを行い、 上のパスに含まれていれば同じ になると考える [ ["*", 0, logger], ["/api/*", 1, cors], ["/api/*", 3, fallback], ["/api/users/:id", 2, handler], ] 54 54
55. 登録順に並べ替えをし直す [ ["*", 0, logger], ["/api/*", 1, cors], ["/api/users/:id", 2, handler], ["/api/*", 3, fallback], ] 55 55
56. ハンドラだけ取り出す = [ logger, cors, handler, fallback, ] 56 56
57. 例外もある 57 57
58. 以下のケースではハンドラ b に適用されるミドルウェアは 決まっているいない const app = new Hono(); app.get("/", function a() {}); app.get("/:type/subtype/:action", function a() {}); app.get("/users/:id/posts", function b() {}); GET /users/1/posts => [b] GET /users/subtype/create => [a, b] 58 58
59. reg-exp-routerでも このような例外的なケースも一応対応している。 が、このケースではtrie-routerの方が速い。 59 59
60. まとめ 60 60
61. reg-exp-routerの速さのポイント 1つの正規表現にまとめて、1度の適用で探索 をたくさん用意しておいて、URLに一致する を探す 61 61
62. おまけ 62 62
63. どれが速い？ join / += indexOf / lastIndexOf split("/") / split(/\//) for / forEach / for-of (V8とSpiderMonkeyで違いがあります) 63 63
64. join / += const strings = Array.from({ length: 1000 }, () => "hello"); suite .add("join", () => { return strings.join(""); }) .add("+=", () => { let res = ""; strings.forEach((str) => (res += str)); return res; }) .add("reduce", () => { return strings.reduce((res, str) => res + str, ""); }) .run(); 64 64
65. join x 48,489 ops/sec ±2.26% (97 runs sampled) += x 105,353 ops/sec ±1.63% (97 runs sampled) reduce x 130,151 ops/sec ±3.11% (93 runs sampled) Fastest is join by reduce 65 65
66. indexOf / lastIndexOf const re = new RegExp([...Array(1000)].map((_, i) => `/${i}$()` ).join("|")); const m = "/500".match(re); suite .add("indexOf()", () => { return m.indexOf(""); }) .add("lastIndexOf()", () => { return m.lastIndexOf(""); }) .run(); 66 66
67. indexOf() x 340,204,824 ops/sec ±0.69% (88 runs sampled) lastIndexOf() x 545,046 ops/sec ±0.76% (94 runs sampled) Fastest is indexOf() indexOf()はC++ lastIndexOf()はTorque 67 67
68. split("/") / split(/\//) const string = process.argv[process.argv.length - 1] || "/"; suite .add(`"/"`, () => { return string.split("/"); }) .add("/\\//", () => { return string.split(/\//); }) .run(); 68 68
69. "/" x 4,386,136 ops/sec ±0.27% (98 runs sampled) /\// x 9,975,101 ops/sec ±0.24% (95 runs sampled) Fastest is /\// 69 69
70. 70 70
71. "/" /\// 10 1913225.672 2705181.449 100 308134.289 297026.579 1000 33429.193 27861.556 71 71
72. String.prototype.splitはC++ 72 72
73. https://developer.mozilla.org/ja/docs/Web/JavaScript/Ref 73 73
74. const splitter = {}; splitter[Symbol.split] = function (){ return ["42"]; } console.log("test".split(splitter)); // => ["42"] 74 74
75. V8のコメントの抜粋 // Redirect to splitter method if {separator[@@split]} is not undefined. RegExpの場合には（おそらく）ここで処理されて返る // String and integer conversions. // Shortcut for {limit} == 0. // If the separator string is empty then return the elements in the subject. ... 75 75
76. いっそindexOfを使った方が速いのでは 76 76
77. function splitByIndexOf(str: string, sep: string): string[] { const res: string[] = []; for (let i = 0, j = str.indexOf(sep); ; j = str.indexOf(sep, i)) { if (j === -1) { res.push(str.substring(i)); break; } else { res.push(str.substring(i, j)); i = j + 1; } } return res; } ※ limitには未対応 77 77
78. const string = process.argv[process.argv.length - 1] || "/"; suite .add(`"/"`, () => { return string.split("/"); }) .add("/\\//", () => { return string.split(/\//); }) .add("splitByIndexOf", () => { return splitByIndexOf(string, "/"); }) .run(); 78 78
79. 79 79
80. "/" /\// splitByIndexOf 10 1913225.672 2705181.449 2514207.636 100 308134.289 297026.579 267884.594 1000 33429.193 27861.556 25881.830 80 80
81. suite .add( `"/"`, () => string.split("/"), { onStart: () => delete String.prototype[Symbol.split], } ) .add( "prototype", () => string.split("/"), { onStart: () => String.prototype[Symbol.split] = splitByIndexOf, } ) 81 81
82. 82 82
83. for / forEach / for-of 83 83
84. 参照するべき記事 JavaScriptのループはどれが一番高速なのか forとwhileを使った高速な書き方 結局JavaScriptの配列ループはどれが一番速いのか forEachやfor-ofも含めてどのような傾向にあるのか？ 84 84
85. https://github.com/usualoma/ultrafast-js- router/blob/main/benchmark/for-sum.ts 85 85
86. while x 13,837,421 ops/sec ±0.31% (97 runs sampled) for x 13,904,145 ops/sec ±0.68% (92 runs sampled) for with len x 13,942,264 ops/sec ±1.15% (99 runs sampled) for with decrement x 7,646,750 ops/sec ±0.21% (96 runs sampled) forEach x 4,837,059 ops/sec ±0.08% (100 runs sampled) reduce x 7,477,822 ops/sec ±1.64% (98 runs sampled) for-of x 5,279,595 ops/sec ±0.20% (97 runs sampled) Fastest is for 86 86
87. https://github.com/usualoma/ultrafast-js- router/blob/main/benchmark/for-mul.ts 87 87
88. while x 5,340,699 ops/sec ±0.19% (98 runs sampled) for x 5,312,270 ops/sec ±0.58% (98 runs sampled) for with len x 6,251,252 ops/sec ±0.55% (94 runs sampled) for with decrement x 5,374,107 ops/sec ±0.21% (100 runs sampled) forEach x 5,178,295 ops/sec ±1.84% (98 runs sampled) for-of x 4,522,059 ops/sec ±0.10% (97 runs sampled) Fastest is for with len 88 88