misskey
misskey copied to clipboard
misskey-dev
refactor: faster for loop
What
コードのリファクタリング (特にfor文) 毎回配列の長さを参照及び、計算していたのを最初に計算し、キャッシュするように変更した。
Why
毎回配列の長さを参照するのにも、計算するにもコストがかかるから。
Additional info (optional)
Checklist
- [x] Read the contribution guide
- [x] Test working in a local environment
Codecov Report
Attention: 15 lines in your changes are missing coverage. Please review.
Comparison is base (
b62d9f3) 64.21% compared to head (2b2475c) 65.72%.
Additional details and impacted files
@@ Coverage Diff @@
## develop #13104 +/- ##
===========================================
+ Coverage 64.21% 65.72% +1.51%
===========================================
Files 976 981 +5
Lines 108707 113568 +4861
Branches 5581 5642 +61
===========================================
+ Hits 69808 74648 +4840
- Misses 38899 38920 +21
:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.
![codecov[bot] avatar](https://avatars.githubusercontent.com/in/254?v=4 "Published by a pub.dev verified publisher"){kind=small}
![github-actions[bot] avatar](https://avatars.githubusercontent.com/in/15368?v=4 "Published by a pub.dev verified publisher"){kind=small}
naruhodo
- https://stackoverflow.com/questions/5752906/is-reading-the-length-property-of-an-array-really-that-expensive-an-operation
- https://dev.to/akashkava/javascript-does-not-cache-array-length-2n65
naruhodo
https://zenn.dev/rabee/articles/javascript-huge-array-for-each-is-very-slow
常に最新の状態を維持したいので、あえて生成日時を入れてコンフリするようにしていました。 差分を見る限り、今回の対応はループ回数の取得方法変更だけです。コンフリクトが起こることがおかしいのではなく、autogen配下がコミットされていることがおかしいと思われます。
V8エンジンは配列の要素数をキャッシュするのでバックエンドは変更しなくていいかも
- https://chromium.googlesource.com/v8/v8.git/+/refs/heads/main/src/objects/js-array-inl.h
- https://chromium.googlesource.com/v8/v8.git/+/refs/heads/main/src/objects/elements.cc
常に最新の状態を維持したいので、あえて生成日時を入れてコンフリするようにしていました。 差分を見る限り、今回の対応はループ回数の取得方法変更だけです。コンフリクトが起こることがおかしいのではなく、autogen配下がコミットされていることがおかしいと思われます。
CIが引っかかったので再生成したものと思われる そしてCIがおかしくなるのはbetaリリースの際にmisskey-jsのpackage.jsonのバージョンを更新していないから（のはず）
まあMisskeyがV8使わなくなる可能性は十分にあるわね
（V8から移行するかは置いておいても）確実にキャッシュされる方法があるならそのように変更する分には全く問題ない気がする
Bunが使用しているJavascriptCore.Frameworkも配列の要素数をキャッシュしてるっぽいのでやはりバックエンドを変更する必要はないかも
- https://github.com/WebKit/WebKit/blob/main/Source/JavaScriptCore/runtime/JSObject.h#L196-L201
- https://github.com/WebKit/WebKit/blob/main/Source/JavaScriptCore/runtime/JSArray.cpp#L641C10-L720
firefoxで試す感じfirefoxもlengthのキャッシュの速度の差があまりない(誤差レベル)だったのですが実際にこの２つで大きな差があるフロント側の実装が何なのかが気になりました
https://hg.mozilla.org/mozilla-central/file/2cac2f68bfdcfc9012c537044bc475f076bda7b0/js/src/builtin/Array.cpp#l185 https://hg.mozilla.org/mozilla-central/file/2cac2f68bfdcfc9012c537044bc475f076bda7b0/js/src/vm/ArrayObject.h#l30 https://hg.mozilla.org/mozilla-central/file/2cac2f68bfdcfc9012c537044bc475f076bda7b0/js/src/vm/NativeObject.h#l380
横槍を入れるようで申し訳ないのですが、そもそものindexをインクリメントしつつlengthを参照するようなループを極力しないようにするという方向性でのリファクタリングは求められていないものなのでしょうか？
ざっと見た感じでも、例えばこちらの処理はArray.prototype.reduceを使うほうがよさそうですし、こちらやこちらは簡単にfor...ofに置き換えることができるはずです。そもそものループや配列の処理方法を工夫したほうがより可読性も高まり、極端な場面を除き^1パフォーマンスも低下はしないはずです。
また、少し話はそれますが、インデックスを用いた配列などへのアクセスでは、手に入る値はundefinedとのunionとなります。（正確には、TSConfigでnoUncheckedIndexedAccessをtrueに設定することで、undefinedとのunionとして推論されるようになります。現在のMisskeyではそのようには設定されていません。そのため、型では問題がないにも関わらず実行時にエラーになってしまう危険性がある状況です。）
どのように推論されるにしても、そもそものインデックスを用いたアクセス自体を極力取り除く方向でのリファクタリングのほうがよいように感じます。（だからといってこのPRが全面的にだめというわけではないですが……。）
パフォーマンス向上を目指すのはよいことだと思います。しかし、実際にこの変更でパフォーマンスがどの程度向上するのかは不透明です。となると、可読性や型安全性が高まるようなリファクタリングができそうな場面では、そのようなリファクタリングをするほうがよいと思います。
ざっと見た感じでも、例えばこちらの処理は
Array.prototype.reduceを使うほうがよさそうですし、こちらやこちらは簡単にfor...ofに置き換えることができるはずです。そもそものループや配列の処理方法を工夫したほうがより可読性も高まり、極端な場面を除きパフォーマンスも低下はしないはずです。
手元でベンチマークを測った結果、速い順に
- Google Chrome 123.0.6312.86 (Official Build) では:
for (let i = 0; i < data.length; i++)、Array.prototype.reduce、for (const value of data) { - Safari バージョン17.4.1 (19618.1.15.11.14) では:
for (let i = 0; i < data.length; i++)、for (const value of data) {、Array.prototype.reduce - Node.js v21.5.0では:
for (let i = 0; i < data.length; i++)、Array.prototype.reduce、for (const value of data) {
となり現在の実装の方が全てのケースで速くなりました。さらにChromeで要素数が一万の配列に対して実行したところArray.prototype.reduceはJSArray::kMaxFastArrayLengthを超えてないのにも関わらず八倍程度for (let i = 0; i < data.length; i++)より遅くなりました。noUncheckedIndexedAccessの件でfor ... ofなどを使うように書き換えるのは同意しますが、パフォーマンスがあまり良くないので今は書き換えるのは控えたほうが無難だと思います。
これV8エンジンの最新版ではfor (let i = 0; i < data.length; i++)よりfor ... ofの方が速くなっているらしい(直そうと思ってV8の開発シェルでベンチマーク測ったら気づいた)