JSのbenchmarkの比較(vitest, deno, mitata)
これは SMat Advent Calendar 2024 の12/6分の記事です。
弊社では「SmartMat Cloud」というIoT重量計 x SaaSでモノの流れを可視化するサービスを提供しております。最近オンボーディング改善のためスマホのweb appを作っております。
はじめに
先日、あいまい検索の機能をプロトタイプ作ってみました。手法は深く考えずに「レーベンシュタイン距離」のベースで作ったが、npm パッケージ(fastest-levenshtein)にもありましたので差し替えしました。しかし、「fastest」ってどれぐらいか気になり、benchmarkのツールを試しずつ、調べてみました。
JSのbenchmarkは現実の現状は何?
Deno 2のリリースノートにはbench
コマンドがあり、mitata 1.0のリリースノートにはオンラインで良い議論が始まっていたので、深く調べる必要はあまりなかったです。UI/BFFの単体テストはvitestを使っていて、bench
コマンドもあるから気軽に試せます。これでJSにおける最新のベンチマークをカバーできるでしょう。素朴な実装を見て、fastest-levenshtein
と比較してみよう!
Naive implementation
曖昧検索のプロトタイプのため、下記のコードは商品名・商品コードなどの比較計算が十分でした。
// naiveLevenshtein.ts
export function levenshteinDistance(s1: string, s2: string): number {
// Convert strings to arrays to handle surrogate pairs
const arr1 = Array.from(s1)
const arr2 = Array.from(s2)
const costs: number[] = new Array()
for (let i = 0; i <= arr1.length; i++) {
let lastValue = i
for (let j = 0; j <= arr2.length; j++) {
if (i === 0) costs[j] = j
else if (j > 0) {
let newValue = costs[j - 1]
if (arr1[i - 1] !== arr2[j - 1])
newValue = Math.min(Math.min(newValue, lastValue), costs[j]) + 1
costs[j - 1] = lastValue
lastValue = newValue
}
}
if (i > 0) costs[arr2.length] = lastValue
}
return costs[arr2.length]
}
levenshteinDistance
は、s1とs2を同じにするために必要な変更の数を計算する:
import { levenshteinDistance } from './naiveLevenshtein'
const corpus = 'CIショウヒン'
const query = 'ショウヒン'
const distance = levenshteinDistance(corpus, query) // queryは「CI」がないため、distanceは2になる。
次はbenchmarkのはしてみましょう!
Let's bench!
デモコードはこちら。deno 2, vitest, mitataで用意して、試してみました。
Deno 2
Deno/mitata/vitestは .bench.ts
のネーミングルールなど似ているところが多いけど、denoはグローバルの Deno
から bench
が参照されます。
// deno/levenshtein.bench.ts
import { distance as fastestLevenshtein } from 'npm:fastest-levenshtein';
import { levenshteinDistance } from '../naiveLevenshtein.ts';
const corpus = 'CIショウヒン'
const query = 'ショウヒン'
Deno.bench('fastest-levenshtein', { group: 'fastest-levenshtein' }, () => {
fastestLevenshtein(corpus, query)
})
Deno.bench('naiveLevenshtein', { group: 'fastest-levenshtein' }, () => {
levenshteinDistance(corpus, query)
})
コマンドを実行しましたら:
❯ pnpm run benchmark:deno
> benchmarking@0.0.0 benchmark:deno /Users/rjames/experiment/benching
> deno bench deno/*
Check file:///Users/rjames/experiment/benching/deno/levenshtein.bench.ts
CPU | Apple M2
Runtime | Deno 2.0.0 (aarch64-apple-darwin)
file:///Users/rjames/experiment/benching/deno/levenshtein.bench.ts
benchmark time/iter (avg) iter/s (min … max) p75 p99 p995
--------------------- ----------------------------- --------------------- --------------------------
group fastest-levenshtein
fastest-levenshtein 27.6 ns 36,200,000 ( 25.2 ns … 63.1 ns) 28.0 ns 35.9 ns 36.9 ns
naivelevenshtein 312.7 ns 3,198,000 (296.5 ns … 357.7 ns) 317.8 ns 348.5 ns 357.7 ns
summary
fastest-levenshtein
11.32x faster than naivelevenshtein
fastest-levenshtein
はめっちゃ早いです!他のツールはどうでしょう?
Vitest
denoと異なるシンタックスはglobal objectではなくて、importの参照先でできます。
// vitest/levenshtein.bench.ts
import { bench } from 'vitest'
import { distance as fastestLevenshtein } from 'fastest-levenshtein';
import { levenshteinDistance } from '../naiveLevenshtein.ts';
const corpus = 'CIショウヒン'
const query = 'ショウヒン'
bench('fastest-levenshtein', () => {
fastestLevenshtein(corpus, query)
})
bench('naiveLevenshtein', () => {
levenshteinDistance(corpus, query)
})
TUIの見た目は少し違うけど、 fastest-levenshtein
は4倍早いだけ?あとで調べましょう。
❯ pnpm run benchmark:vitest
> benchmarking@0.0.0 benchmark:vitest /Users/rjames/experiment/benching
> vitest bench vitest/*
Benchmarking is an experimental feature.
Breaking changes might not follow SemVer, please pin Vitest's version when using it.
DEV v2.1.3 /Users/rjames/experiment/benching
✓ vitest/levenshtein.bench.ts (2) 3704ms
name hz min max mean p75 p99 p995 p999 rme samples
· fastest-levenshtein 13,862,856.14 0.0000 0.0792 0.0001 0.0001 0.0001 0.0001 0.0002 ±0.07% 6931429 fastest
· naiveLevenshtein 2,935,640.66 0.0002 0.1726 0.0003 0.0003 0.0005 0.0005 0.0006 ±0.35% 1467821
BENCH Summary
fastest-levenshtein - vitest/levenshtein.bench.ts
4.72x faster than naiveLevenshtein
PASS Waiting for file changes...
press h to show help, press q to quit
Mitata
Hackernews で mitata の1.0のリリースを見つけ、試してみたくなりました。シンタックスが少し違うので、await run()
が必要です。
// mitata/levenshtein.bench.ts
import { bench, run } from 'mitata'
import { distance as fastestLevenshtein } from 'fastest-levenshtein';
import { levenshteinDistance } from '../naiveLevenshtein.mjs';
const corpus = 'CIショウヒン'
const query = 'ショウヒン'
bench('fastest-levenshtein', () => {
fastestLevenshtein(corpus, query)
})
bench('naiveLevenshtein', () => {
levenshteinDistance(corpus, query)
})
await run()
❯ pnpm run benchmark:mitata
> benchmarking@0.0.0 benchmark:mitata /Users/rjames/experiment/benching
> node mitata/levenshtein.bench.mjs
clk: ~2.97 GHz
cpu: Apple M2
runtime: node 22.9.0 (arm64-darwin)
benchmark avg (min … max) p75 p99 (min … top 1%)
-------------------------------------- -------------------------------
fastest-levenshtein 25.95 ns/iter 25.69 ns █
(24.60 ns … 111.99 ns) 34.46 ns ▂▂█▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁
naiveLevenshtein 310.02 ns/iter 311.39 ns █
(290.90 ns … 372.94 ns) 334.38 ns ▁▁▁▁▂▁▃█▃▂▂▂▁▁▁▄▂▁▁▁▁
こちらも fastest-levenshtein
11倍ぐらい早いです!
なぜ vitest だけ違いますかね?
実施の違いの調査
どうやら deno の bench
は mitata を使っているようなので mitata vs tinybench になります。マイクロベンチマークにおける vitest(tinybench)のコンフィギュレーション/ランタイムの原因でしょうかね。
tinybench に影響ありそうなオプションを下記のように試してみたが、 mitata のような変動はあんまりなかったです。
time
(500
→ 5000
): 変更なし
warmupTime
(100
→ 5000
): 4.33x → 5.35x
warmupIterations
(5
→ 1000
): 変更なし
まとめ
vitestはすでに使っていたら気になるコードは気軽に bench
を使って良さそうです。picosecond粒度や、GCの影響があるものであればmitata/denoで良さそうです。
Discussion