JSでのslice文字列生成コストについて

Question

前提・実現したいこと

ブラウザ(Chrome,FF)上でJavaScriptの<文字列>.slice()を動かしたときのコストについて、同一文字列同一引数だった場合に2度目以降が高速であることについて疑問を解消したいです。

発生している問題・エラーメッセージ

同一の文字列に対して同一の引数でslice()を実行すると、2度目以降が高速になります。
これがなぜなのかを知りたいです。
1度メモリ上に展開した文字列リテラルを再参照できる仕組みがあるのだろうか？と考えていますが、それが同一条件で実行するFunctionをキャッシュしているのか、生成されるべき文字列リテラルと今持っている文字列リテラルマップ（なんてあるのか・・・？）を照合しているのか、JavaScript言語の仕様なのか・・・

### Chrome
time: 5.348876953125ms
time: 0.005126953125ms
time: 0.001708984375ms
time: 0.002197265625ms
time: 0.001953125ms
time: 0.002197265625ms
time: 0.0009765625ms
time: 0.001708984375ms
time: 0.003173828125ms
time: 0.002197265625ms
### Firefox
time: 10ms
time: 0ms * 2回
time: 2ms
time: 0ms * 4回
time: 2ms
time: 0ms

該当のソースコード

文字列を生成して、同じ文字列に対して同じsliceを10回繰り返します。2回目以降早くなります。

// str準備
let str = ""
for (let i = 0; i < 1000000; i++) {
	str += i % 10;
}

//本題
for (let i = 0; i < 10; i++) {
	console.time("time")
	const slc = str.slice(0, str.length / 10);
	console.timeEnd("time")
}

試したこと

• strを再生成して実行すると、同様に1度目は低速、2度目以降高速になります。
• 実行後、以下を実行してもやはり高速でした

console.time("wow")
str.slice(0, 10000*10)
console.timeEnd("wow")

補足情報（FW/ツールのバージョンなど）

• ブラウザ

-- Chrome 65.0.3325.181（Official Build） （64 ビット）
-- Firefox 59.0.2 (64-bit)

• OS

-- Windows 10 Home

• CPU

-- Core i5

• Memory

-- 8GB

Answer 1

まあ、私は開発者でもないし、JavaScriptでは環境がいろいろあるため、あくまで予想にしかなりませんが。

GCCなんかのコンパイラの世界では、コード解釈の段階で、同じ文字列が生成されると確定するときは、生成するのは一回にして、あとはそれをコピーして使い回す、といういわゆる最適化が行われます。

それと同じことが、そこでおこなわれてるんじゃないでしょうか。

---

追記
JavaScriptのことはよーわからんですが、提示されたソースには
const が書かれてますが、これは定数の意味じゃないんでしょうか。
そうだとすれば、もともと生成されるのは最初の一回だけだと思われます。

Comments

[退会済みユーザー]

ご回答ありがとうございます。
各ブラウザのJavaScriptエンジンが、JavaScriptロード後のコードコンパイル時に「このfor文内では同じことをしているから、最初の一度は実行してキャッシュして、後はキャッシュを使うように予め紐づけておこう」とやっている、という説だと解釈しました。
そういった可能性もありそうな気がしました。ありがとうございます。

[退会済みユーザー]

追記ありがとうございます。
constは再代入不可ですが、forブロック内で完結して再生成を繰り返しているので、ここでは再生成がないようにはならないです。
例えば```slc```の右辺をランダムに生成するようにすると、```slc```は毎回変わりますが、特に問題ないです。

[defghi1977]

JavaScriptのJITコンパイラの進化は目覚ましく, ありとあらゆる手を使って高速化しているのでぶっちゃけ「ようわからん」です.

[maisumakun]

「ループ内で変化しない処理をループ実行前の1度で済ませる」という最適化は、「ループ不変式の追い出し」と名前が付く程度に普及しています。

> y_waiwaiさんへ

JavaScriptのconstはブロックスコープなので、ループ1回ごとにスコープが違ってきます（何も最適化せずに行うなら、毎回sliceが必要です）。

[退会済みユーザー]

defghi1977さん
＃teratail初心者のため、返信流儀が間違っていたらごめんなさい
ご回答ありがとうございます。
神秘の可能性もありますね。高速化は、美しいアーキテクチャ改変よりも膨大なケーススタディの積み上げであることも多いので、そのまま神秘化していって、このケースも「なんか早い」の可能性もありますね。

[退会済みユーザー]

maisumakunさん
＃teratail初心者のため、返信流儀が間違っていたらごめんなさい
ご回答ありがとうございます。
なるほど、「ループ不変式の追い出し」という概念があるんですね。ありがとうございます。

神秘性を現実世界まで引き寄せていただいたmaisumakunさんの回答意図と少しずれてしまい恐縮ですが、上記コードを走らせた後に以下を実行すると、これまた高速でした。
console.time("wow")
str.slice(0, 10000*10)
console.timeEnd("wow")
これはfor文とは結果が等価で、かつ「追い出し」されていないと思うのですが、結果は0.05msと高速パターンでした。
これも「追い出し」対象になるように設計されているのか、別の神秘が効いているのか、、、進めば進むほど迷うプログラムの世界。

[defghi1977]

個人的にはJavaScriptのそのものの動作速度に拘るのは無意味に思いますが.
それよりDOM操作の効率について調べたほうが実用的(やり方1つで数桁レベルでの差異が出てくる).

[HayatoKamono]

for文を使わない場合も同様に２回目以降は処理速度があがることを確認しました。

const str = 'string';
let i;

console.time('str1');
i = str.slice();
console.timeEnd('str1');

console.time('str2');
i = str.slice();
console.timeEnd('str2');

console.time('str3');
i = str.slice();
console.timeEnd('str3');

// str1: 0.367ms
// str2: 0.057ms
// str3: 0.006ms

[y_waiwai]

まあ、その関数がCPUのキャッシュに入ってしまえばなにもしなくても２回目以降の実行は早くなりますしね、
実行時間だけではなにが効いているのかわかりにくいですねー

[退会済みユーザー]

defghi1977さん
ご回答ありがとうございます。
確かに、DOM構成やデータ取得用のネットワークレイテンシがより性能のボトルネックになるのは確かですね。
実サービスを構築するときには、そういった「コスパの良いところ」に原価を使っていくようにしたいです。

[退会済みユーザー]

HayatoKamonoさん
検証ありがとうございます。
やはり関数キャッシュ説もありそうですね。

[maisumakun]

現実問題としては、「プロダクトの成否に関わるほど速度がクリティカルになる場面」、あるいは「特定のシチュエーションで使うに耐えないほど遅くなる場合」を除けば、通信やDOM操作でない純粋なJavaScriptの速度まで考慮しないといけない場面は多くないと思います。

[退会済みユーザー]

y_waiwaiさん
ご回答ありがとうございます。
関数事態がキャッシュされている可能性もありそうですね。JavaScriptは関数もオブジェクトですし。
ただ、for文のソースコードをfunctionに切り出した上で実行し、strを変更して再度同じfunctionを実行すると、これまた1度目は低速、2度目は高速でした。また、strを変更しない場合はそのまま高速でした。
つまり、関数自体のキャッシュが性能につながっているのではなく、やはり結果としての文字列リテラルをキャッシュしてどうにか参照しているような気がしてきました。

[defghi1977]

> 文字列リテラルをキャッシュしてどうにか参照している
それで正しいと思いますよ. 言語系を問わず大抵その実装となるはず.

[退会済みユーザー]

maisumakunさん
ご回答ありがとうございます。
その通りですね。レンダリングを秒単位でブロックするレベルでなければ、他を優先するのがコスパよさそうです。
＃この疑問が「言語的に常識」なものであることを期待したのですが、実はそうでもなさそうなので、解析者としては辛いですが、人間としては少しホッとしました。

[退会済みユーザー]

defghi1977さん
ご回答ありがとうございます。
仮説に同意していただける方がいてよかったです。この動作は頭の片隅に入れておくことにします。

[defghi1977]

いや，仮説じゃなくてJavaの内部実装

[退会済みユーザー]

defghi1977さん
失礼しました、JavaScriptとしては確認が取れていないので、「仮説」としていました。
言葉足らずで申し訳ありません。

[defghi1977]

個人的にはベストプラクティスがあれば大抵横展開しているはずなので, どこも大体おなじじゃろうなと思っています

[退会済みユーザー]

defghi1977さん
そうですね、本件も駆動系の共通知となっているかもしれません。

Answer 2

結論

ブラウザ(Chrome)上でJavaScriptの<文字列>.slice()を動かしたときのコストについて、同一文字列同一引数だった場合に2度目以降が高速である理由は、事実と推察より以下の仮定をここでの結論とする。(V8の内部までは追わない)

• 「同一文字列オブジェクト」に対する「同等引数でのslice」を実施される場合、1度目の実行でブラウザ側が結果をアクセス可能な形でキャッシュし、2度目以降はsliceメソッドが呼ばずに高速にreturnしているため

結論を導いた事実

ChromeにてF12で開いたコンソールに以下のコードを実行し、生成された「slice!」ボタンを押下したときのパフォーマンスログを確認する。

// str準備
let str = ""
let str2 = "";
let str3 = "";
function init() {
    for (let i = 0; i < 1000000; i++) {
        str += i % 10;
        str2 += i % 10;
        if (i < 100000) {
            str3 += 1000;
        }
    }
}

//本題
function slicetest() {
    for (let i = 0; i < 10; i++) {
        console.time("time1")
        const slc = str.slice(0, 100);
        console.timeEnd("time1")
    }
    for (let i = 0; i < 10; i++) {
        console.time("time2")
        const slc = str2.slice(0, 100);
        console.timeEnd("time2")
    }
    for (let i = 0; i < 10; i++) {
        console.time("time3")
        const slc = str3.slice(0, 100);
        console.timeEnd("time3")
    }
}

// イベント発火用ボタンを作成。本質でないのでワンライナーで書く。気にしなくていい。
document.body.insertBefore((() => {let b = document.createElement("button");b.onclick=slicetest;b.innerHTML="slice!";;return b;})(), document.body.firstChild);
document.body.insertBefore((() => {let b = document.createElement("button");b.onclick=init;b.innerHTML="init str";return b;})(), document.body.firstChild);

// とりあえず一回init
init();

実行した結果のパフォーマンスが以下

ここから分かる事実は、

1. 図中(A)を見ると、文字列オブジェクトstrに対する最初の1回はsliceが呼ばれ、コストをかけて(10ms)結果が返っている
2. 図中(B)を見ると、文字列オブジェクトstrに対する2回目以降はsliceが呼ばれることなく、コストなし(1ms未満)で結果が返っている
3. 図中(C)を見ると、同じ内容の文字列で異なるオブジェクトstr2に対しては、最初の1回はsliceが呼ばれ、コストをかけて(10ms)結果が返っている。

である。

つまり、ある文字列オブジェクトに対して、2度目以降のsliceでは、何某かがsliceを呼び出すことなくコストなしでその結果をリターンしている

※なお参考として、Firefoxでも同様に2度目以降sliceそのものが呼ばれていないことは確認したことを記載しておく。

結論を導く推察

上記、何某はブラウザのJSエンジン(この場合はV8)と考えられる。このエンジンが、同一オブジェクトに対する関数結果を実行時にキャッシュし、それを返却していると推察した。他言語のコンパイラ等でもこういった最適化実装が存在するため、同様な実装があるという推察は妥当であると判断した。

その他の仮説と否定

「同等文字列」に対する「同等slice」であれば、高速になる

異なるオブジェクトであっても「同じ結果になる」つまり「結果が同じリテラルを参照しても良い」ためコンパイラのインテリジェンスによっては不可能ではないと仮説されたが、前図の(A)と(C)により、これは否定された。(今後の進化によりどうなるかは不明)

関数自体のキャッシュにより、高速になる

逆に言うと、関数オブジェクト生成のコストが1度目のネックになるという仮説だが、前図の(A)(C)の差がほぼない(実際は(C)の方が0.2ms遅い、関数オブジェクトがキャッシュされることが性能に効くなら(A)より(C)が明確に早い必要がある)ことから、これは否定された。(関数のキャッシュが存在しない、というのではなく、関数のキャッシュが今回の疑問点の回答にはならない、ということ)

Answer 3

回答ではないです。

Node.jsでやってみました。エンジンはChromeのV8エンジンと近い作りだと思います。自分はこの結果を見て「sliceが同じ条件で実行したとき2回目から早くなる」という単純な因果関係があるとは思えませんでした。

const N = 3
let str = ""

for (let i = 0; i < 100000; i++) {
  str += "0123456789"
}

console.log('string slice - A')
{
  const slc = str.slice(0, str.length / 10);
}
for (let i = 0; i < N; i++) {
  run(slice_test)
  run(slice_test2)
}

console.log('string slice - B')
slice_test(); // ここで一回sliceを実行
for (let i = 0; i < N; i++) {
  run(slice_test);
  run(slice_test2)
  str = ("a" + str).substring(1)
}

function slice_test() {
  const slc = str.slice(0, str.length / 10);
}

function slice_test2() {
  const slc = str.slice(0, str.length / 10);
}

function run(f) {
  console.time("time")
  f();
  console.timeEnd("time")
}

結果
string slice - A
time: 0.213ms <=既に1度sliceを実行しているが遅い
time: 0.039ms <=既に1度sliceを実行しているが遅い
time: 0.006ms
time: 0.006ms
time: 0.005ms
time: 0.004ms
string slice - B
time: 0.006ms
time: 0.004ms
time: 0.027ms
time: 0.009ms
time: 0.012ms
time: 0.006ms

正確な理由はわかりませんが、直感的にはv8のコンパイラーがコードを最適化しているためではないかと思えました。例えば上のコードでslice_testやslice_test2関数はsliceの計算結果をどこでも使っていません。v8エンジンのオプティマイザー(っていうんでしょうか)が関数単位に最適化を施すとするなら(消し忘れの文章が残ってたので削除)

• コンパイルはいつ行われるのだろう？

V8エンジンではコードを読み込んだ時点でコンパイルされるんでしょうか？それとも関数が最初に実行されたときでしょうか？なんとなく後者であるような気がしますが、そうだとするとslice_testやslice_test2関数が初めて実行された時点でコンパイルされるためコンパイル時間がかかっているのではないかと思えます。

• コンパイルした後に最適化しているかも知れない

slice_testやslice_test2ではsliceを計算してはいますが結果を使ってません。よって最初のコンパイル時点あるいは最適化の時点でslice自体まったく呼び出さないような最適化が行われるかも知れません。

追記：実際にslice_testの方だけ結果を用いるようにしてみたところ測定結果にほとんど違いがみられませんでした。sliceを呼び出さない最適化をしているのか、本ケースの程度ではsliceが早すぎて違いが見えないのかどちらかわかりませんでした。

---

以上は単なる想像です。v8エンジンの動作について情報は以下の記事を参考にしました。

https://postd.cc/how-javascript-works-inside-the-v8-engine-5-tips-on-how-to-write-optimized-code/

複数のスレッドで並行して最適化してるんですね・・・
こんな頭のいいエンジンですと、単純なコードを実行して性能測定してみてもなぜそういう結果になるか予測が難しそうに思いました。

FirefoxのJSエンジンの特性については特に調べてませんが、調べてみるとどんな具合に動くのか何か情報が得られるのではないでしょうか？詳細な動作はわからないにしても「どんな特徴をもったエンジンか」についての情報から、設計の際の参考にできる場合もあるんじゃないかと思いました。

Comments

[退会済みユーザー]

ご回答ありがとうございます。

いただいたコードで、最初にsliceしている箇所とBのslice部分についてもconsole.timeを入れ込みブラウザ上で実施したところ、以下のようになりました。

string slice - A
addlogA: 1.3271484375ms
time: 0.051025390625ms ★
time: 0.029052734375ms ★
time: 0.0078125ms
time: 0.005859375ms
time: 0.01220703125ms
time: 0.009033203125ms
string slice - B
addlogB: 0.00390625ms
time: 0.0029296875ms
time: 0.002197265625ms
time: 0.009033203125ms
time: 0.0048828125ms
time: 0.0029296875ms
time: 0.001708984375ms

addlogAのみ明らかに遅くなっているため、この時点でやはりなにがしか文字列のキャッシュしている可能性は高いかと思います。

また、★の部分は他よりも一桁くらい遅いですが、これは当該関数の初めての呼び出しで、関数自体のキャッシュがないことによる遅延だと予想されます。

そのため、今のところこれまでの議論の内容をむしろ強化してくれている結果(非ブラウザによるJavaScript実行)であるかも、と考えています。
実検証やアドバイスをいただき、誠にありがとうございます。

[KSwordOfHaste]

本文にはコンパイルしている時間と書きましたが事前にコンパイルされていたとしても初めての実行で遅くなるといった可能性はいろいろありそうですね。キャッシュヒット/ミスといった話もその一部かと思います。

[退会済みユーザー]

ご回答ありがとうございます。
そうですね。挙動から察するにここでは前述のキャッシュが優位に働いてそうな気がしますが、真実を見たわけではないので、有力な可能性の一つとしてとらえておきます。

[KSwordOfHaste]

いずれにせよ、アプリケーションプログラマーにとって大事なのは「関数を始めて実行したときや、特定の場所にラムダ式が書かれていてそこを始めて通過した場合に多少遅くなる」という事実の方であろうと思います。またループ内のどこに何が書いてあるかにも影響があるように見えます。
forループの中を
run(slice_test)
run(slice_test2)
run(() => { const slc = str.slice(0, str.length / 10); });
とかいたときと
run(() => { const slc = str.slice(0, str.length / 10); });
run(slice_test)
run(slice_test2)
と書いたときの結果を見ると面白かったです。どちらもラムダ式か関数呼び出しかとはあまり関係なくループの先頭付近にある関数呼び出しがだいたい遅くなることがわかります。ループをしながら最適化が進んでるのかもしれませんね。