JavaScriptの便利な構文に潜む罠

この記事は kubell Advent Calendar 2024 12/23の記事です。

こんにちは、2024年4月に新卒でkubellに入社した石田です。

6月にフロントエンド開発部に配属されてから約半年が経ちました。

今回は半年間の業務の中で一番印象に残っている、フロントエンドのパフォーマンスチューニングについて書こうと思います。

ちなみに私は学生時代に競技プログラミングをやっていたこともあり、パフォーマンスチューニングが大好きです :D

誰に向けた記事なのか

普段 JavaScript（TypeScript）を使用して開発していて、あまり計算量を意識したことのない人に届くと嬉しいなと思いながら執筆しました。

問題のコード

配属されてから一ヶ月ほど経ち、業務のコードにも慣れてきた頃、以下のようなコードを見つけました。よくある API からのレスポンスを整形している処理です。

const rooms = Object.entries(response.room_dat).reduce(
  (acc, [roomId, room]) => {
    // 処理
    return { ...acc, [roomId]: hoge };
  },
  {},
);

一見すると問題なさそうなコードですが、実は場合によっては処理がものすごく遅くなる可能性があります。

なぜ遅いのかを理解するために、JavaScript の「スプレッド構文」と呼ばれるものについて少し解説します。

スプレッド構文とは？

JavaScriptの構文の一つで、配列やオブジェクトを展開することができる構文です。Object.assign() や Array.prototype.concat() 相当のものを簡潔に記述することができます。

詳しくはMDNを参照してください。

const obj = { a: 'foo' };
const newObj = { ...obj, b: 'bar' };

console.log(newObj); // { a: "foo", b: "bar" }

const arr = [1, 2, 3];
const newArr = [...arr, 4, 5];

console.log(newArr); // [1, 2, 3, 4, 5]

どんな罠があるのか

さて、このスプレッド構文ですが、このように一段階のシャローコピーを生成します。

const obj = { a: 'foo', b: { c: 'bar' } };
const newObj = { ...obj };
newObj.a = 123;
newObj.b.c = 456;
console.log(obj.a); // foo
console.log(obj.b.c); // 456

ネストしたオブジェクトを書き換えなければ、新しいオブジェクトをどんなにいじっても元のオブジェクトに影響を及ぼさないため便利なのですが、ここに罠があります。

コピーを生成するということは、当然コピーする要素数に応じた処理が必要になります。つまり、スプレッド構文は展開するオブジェクトや配列の要素数によって計算量が変わります。（今後これをＯ(N)と表記します*1）

問題のコード（再掲）

ここでもう一度先程のコードを見てみましょう。reduce の中で acc をスプレッド構文で展開しています。

const rooms = Object.entries(response.room_dat).reduce(
  (acc, [roomId, room]) => {
    // 処理
    return { ...acc, [roomId]: hoge };
  },
  {},
);

一度目の reduce では空のオブジェクトを展開し、二度目の reduce では要素数が一つのオブジェクトを、三度目は要素数が二つ、四度目は三つ ... といったように、reduce が進むにつれて展開されるオブジェクトが増えていき、最終的にN個のルーム情報を処理するには、(0 + 1 + 2 ... N-3 + N-2 + N-1) 個分のオブジェクトを展開します。

{};                                         // 1回目のreduceで展開されるacc
{ 1: 'foo' };                               // 2回目のreduceで展開されるacc
{ 1: 'foo', 2: 'bar' };                     // 3回目のreduceで展開されるacc
{ 1: 'foo', 2: 'bar', 3: 'buz' };           // 4回目のreduceで展開されるacc
{ 1: 'foo', 2: 'bar', 3: 'buz', 4: 'qux' }; // 5回目のreduceで展開されるacc

これはオーダー記法にするとＯ(N^2)*2と表されます。つまり、この処理は理論上ルーム数の二乗に比例する時間がかかります。

手元の環境では Ｏ(N^2) の場合、N が1万を超えたあたりから顕著に重くなり始め、10万を超えると分単位の時間がかかるようになりました。

チューニング編

我々のお客様の中には、非常に多くのグループチャットを運用してくださっている方もいます。フロントエンドエンジニアと言えども、黙って見過ごすわけにはいきません。修正しましょう。

さて、reduce 内で acc に破壊的な操作をした場合、影響を受けるのは第二引数で渡した初期値のみです。

今回の場合、初期値は空オブジェクトなので特に副作用は気にしなくてOKです。単純に acc に代入する処理に変えることで解決します。

基本的にどの言語も key-value 形式のデータ構造の操作は Ｏ(1) なので、Ｏ(N^2) から Ｏ(N) に改善することができました。これでグループチャットが100万個あっても安心です :D

const rooms = Object.entries(response.room_dat).reduce(
  (acc, [roomId, room]) => {
    // 処理
    acc[roomId] = hoge;
    return acc;
  },
  {},
);

終わりに

最後まで読んでいただきありがとうございました。

一般的にパフォーマンスと可読性はトレードオフの傾向にあると言われています。何でもかんでもパフォーマンスを追い求める必要は無いと思いますが、サイズが大きくなりうるデータを処理するときは、計算量のことを頭の片隅に入れながらコードを書くと良いと思います。

この記事を読んで計算量やアルゴリズムに興味を持った方は、ぜひ競技プログラミングをやってみましょう。楽しいですよ :)

*1:詳しくは「オーダー記法」で調べてみてください。

*2:正確には N*(N-1)/2 ≒ N^2/2 ですが、オーダー記法ではＯ(N) とＯ(N/2) を区別しません。

kubell Creator's Note

ビジネスチャット「Chatwork」のエンジニアのブログです。