JSのbenchmarkの比較(vitest, deno, mitata)

2024/12/06に公開

これは 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(5005000): 変更なし
warmupTime(1005000): 4.33x → 5.35x
warmupIterations(51000): 変更なし

まとめ

vitestはすでに使っていたら気になるコードは気軽に bench を使って良さそうです。picosecond粒度や、GCの影響があるものであればmitata/denoで良さそうです。

株式会社エスマット

Discussion