関数の戻り値をキャッシュするためのタプルキー付きコレクションの高性能な実装（JavaScript）

要約

背景

重い計算をする関数の戻り値を、引数をキーとしてキャッシュしたい。

キャッシュされるべき関数は、オブジェクト（配列も含む）を引数に取ることもある。そのためキャッシュキーとしてオブジェクトの一部を扱えるようにしたい。

コードによる説明

code:ts

// このようなシグネチャを持つ、キャッシュされた戻り値を返す高階関数が欲しい。

const cachedFunctionFrom = <A extends unknown[], R>(

func: (...args: A[]) => R,

): ((...args: A[]) => R) => {

// ...

};

// とても重い計算をする関数

const heavyFunction(a: number[][], b: number[][]): number => {

return doSomeHeavyProcess();

}

// このループはとても時間がかかるが、

for (let i = 0; i < 10; i++)

const cachedHeavyFunction = cachedFunctionFrom(heavyFunction);

// 高階関数を使うこのループでは、実際に重い計算をするのが最初の1回だけで、

// 残りの9回はキャッシュされた戻り値を利用するので、10分の1の時間で終わる。

for (let i = 0; i < 10; i++)

JavaScriptの配列はオブジェクトである。オブジェクトは、各プロパティが同じ値を保持していても、別々に初期化されているのであれば別のオブジェクトである。

「タプルキーの第1要素を根にぶら下げ、第2要素を第1要素にぶら下げ、……、最後の要素を葉として、葉に値を持たせる」という方法で木を作る。

保持された値を読み書きするときは、タプルキーを舐めながら、ツリーを葉に向かって探索していく。探索中に要素同士の深い比較はしない。

この方法であれば、タプルキーの要素数がどんなに多かったとしても、あるいは要素の中身がどんなに複雑なオブジェクトであったとしても、

最良ケースで、タプルキーの要素数に線形に比例する時間（線形時間）でキャッシュの読み書きができる。

実際の実装

性能比較

性能比較を行った環境

マシン: MacBook Air (M4, 2024)

CPU: Apple M4 8コアCPU, 10コアGPU

RAM: 16GB

JavaScriptの実行環境: Node.js v24.13.1

性能比較用のプログラム

Mapを読み書きするのにかかった時間と、Mapのために確保されたヒープメモリの消費量を計測する。

読み書きはランダムに行われるものとする。

時間はテストデータの準備が完了してから読み書きが完了するまでを計測対象とする。

ヒープメモリの消費量は、読み書きが完了したときの消費量から、テストデータの準備が完了したときの消費量を引くことで算出する。

code:ts

import { memoryUsage } from "node:process";

const COUNT = 100000;

const MAX_TUPLE_LENGTH = 10;

const MAX_INNER_OBJ_SIZE = 10;

// テスト用のデータ。

const entries: [number[][], number][] = [];

for (let i = 0; i < COUNT; i++) {

const key = Array.from(

{ length: Math.floor(Math.random() * MAX_TUPLE_LENGTH) },

() =>

Array.from(

{ length: Math.floor(Math.random() * MAX_INNER_OBJ_SIZE) },

() => Math.floor(Math.random() * 2 ** 53),

),

);

}

const ops = Array(COUNT)

.fill(0)

.map(() => Math.random());

const heapTotalOnReady = memoryUsage().heapTotal;

// この関数に、上記で拵えたデータとテスト対象のMapを渡して呼び出してテストする。

const runMapPerformanceTest = (

map: Map<number[][], number>,

entries: [number[][], number][],

ops: number[],

): { time: number; heapTotal: number } => {

const startedAt = globalThis.performance.now();

let heapTotal: number = 0;

for (let i = 0; i < ops.length; i++) {

if (op < 0.4) map.set(key, value);

else if (op < 0.8) map.get(key);

else map.delete(key);

if (i === ops.length - 1)

heapTotal = memoryUsage().heapTotal - heapTotalOnReady;

}

const endedAt = globalThis.performance.now();

return { time: endedAt - startedAt, heapTotal };

};

実験1（100,000操作、タプルキー最大要素数10、各要素の配列の最大長さ10、5回の平均）

table:結果1

実装 op/s op/s 比較 Heap (bytes) Heap 比較

StringifiedTupleKeyedMap 386,301 1 8,257,536 1

TreeTupleKeyedMap 2,710,569 7.02 11,147,674 1.35

タプルキーの要素数が最大10、各要素の配列の長さが最大10というのは、一般的な関数のキャッシュキーとしてあり得る状況である。

実験2（100,000操作、タプルキー最大要素数10、各要素の配列の最大長さ100、5回の平均）

table:結果2

実装 op/s op/s 比較 Heap (bytes) Heap 比較

StringifiedTupleKeyedMap 39,583 1 143,720,448 1

TreeTupleKeyedMap 3,049,163 77.0 14,974,976 0.104

実験1における条件のうち、キーの要素の大きさを10倍にしたものである。引数の数は変わらないが、一つひとつの引数が巨大なオブジェクトである場合を想定したケースである。

実験3（100,000操作、タプルキー最大要素数100、各要素の配列の最大長さ10、5回の平均）

table:結果3

実装 op/s op/s 比較 Heap (bytes) Heap 比較

StringifiedTupleKeyedMap 37,812 1 150,863,872 1

TreeTupleKeyedMap 195,891 5.18 454,754,304 3.01

実験2ではキーの中身の要素を増やしたが、これはキー自体を長くしたケースである。引数が100個もある関数は珍しいと思うので、このユースケースで使われることはあまり考えられない。

似た目的を持つ既存の実装

関数の値をキャッシュすることに特化している。