これは、とても面白いテーマです。
Python版が200万桁を1分未満なのに、JavaScript版は5万桁で704秒ということは、単純計算すると約4万～6万倍以上の性能差があります。
普通はPythonよりJavaScriptの方が遅くても数倍～数十倍程度なので、この差は「言語」よりもアルゴリズム・実装方法の違いによるものがほとんどです。
一番大きな原因
結論から言うと、
Python版は、高速な多倍長整数ライブラリや効率的なアルゴリズムを使っている可能性が非常に高い
ということです。
例えば
- Python標準の整数(int)
- MPIR
- GMP
- MPFR
- gmpy2
などを利用すると、内部ではC言語で何十年も最適化されたコードが動いています。
つまり
Python
↓
gmpy2
↓
MPFR
↓
GMP
↓
CPU実際には「Python」が計算しているのではなく、
C言語製ライブラリ
がほぼ全部やっています。
Pythonはその司令塔です。
JavaScriptでは？
一方、
JavaScript Webアプリは
BigIntや
decimal.js
big.jsなどで実装しているケースが多いです。
これらは多くが
JavaScriptだけ
で書かれています。
つまり
JavaScript
↓
JavaScript
↓
JavaScriptになります。
JavaScriptは実は速い
意外ですが、
JavaScriptのエンジン
- V8（Chrome）
- SpiderMonkey（Firefox）
- JavaScriptCore（Safari）
は非常に高速です。
実際、
Googleは毎年数百人規模でV8を最適化しています。
なので
普通の整数演算なら
Pythonより速いこともあります。
しかし
多倍長演算になると事情が変わります。
多倍長整数は別世界
例えば
123456789012345678901234567890くらいなら問題ありません。
しかし
2,000,000桁になると、
一回の加算ですら
2,000,000回近い計算になります。
掛け算はもっと大変です。
掛け算もアルゴリズムが違う
学校で習う
1234
×5678の掛け算は
O(n²)
です。
しかしGMPは
桁数に応じて
- Karatsuba
- Toom-Cook
- FFT multiplication
- Schönhage–Strassen
- NTT系
などを切り替えます。
例えば
100万桁になると
FFT乗算になります。
これは
O(n log n)
です。
この差は天文学的です。
SIN計算はさらに複雑
SINは
普通
sin(x)
=
x
-
x^3/3!
+
x^5/5!
...では計算しません。
この方法は非常に遅いです。
高速ライブラリは
例えば
- 引数縮小
- Binary Splitting
- AGM
- 高速除算
- 高速平方根
- 高速乗算
などを組み合わせます。
つまり
SINの中身は
数十種類以上のアルゴリズムで構成されています。
JavaScriptで一番時間がかかる部分
よくある実装では
for (...)
足す
for (...)
掛ける
for (...)
割るを何十万回も繰り返しています。
さらに
BigNumber.plus()BigNumber.times()BigNumber.div()のたびに
新しいオブジェクト
を生成します。
これが非常に重いです。
ガベージコレクション
JavaScriptには
GC（Garbage Collection）
があります。
例えば
a.plus(b)すると
新しいBigNumberが作られます。
100万回呼ぶと
100万個できます。
GCが始まると
数秒止まることもあります。
PythonでもGCはありますが、
GMP内部では
巨大メモリをかなり効率よく管理しています。
Webブラウザという制約
ブラウザでは
UI
JavaScript
DOM
描画
イベント
全部が同じ環境です。
だから
CPUを100%使い続けると
画面まで止まります。
Pythonは
コンソールなら
CPUをほぼ100%使えます。
CPU命令の違い
GMPは
CPUごとに
例えば
AVX2
AVX512
BMI2
MULX
ADCXなどを利用します。
つまり
IntelならIntel専用
AMDならAMD専用
ARMならARM専用
のコードがあります。
JavaScriptでは
これらを直接使えません。
キャッシュ最適化
GMPは
CPUキャッシュ
L1
L2
L3
まで考えて
データ配置を変えます。
これは職人芸です。
世界中の数学ライブラリ開発者が
20年以上かけて改良しています。
JavaScriptへ応用する方法
ここからが重要です。
① WebAssemblyを使う
一番おすすめです。
JavaScript
↓
WebAssembly
↓
GMPあるいは
MPFRをWebAssembly化します。
すると
数十倍〜数百倍高速になることがあります。
② Web Worker
計算を
Workerへ移します。
UIが固まりません。
体感速度が大きく改善します。
③ Binary Splitting
SINの級数計算なら
Binary Splitting
が有効です。
これはπ計算でもよく使われます。
④ FFT乗算
50,000桁を超えるなら
FFT乗算を使うだけでも
大幅に改善する可能性があります。
⑤ 引数縮小
SINなら
69.9456°をそのまま計算するのではなく
周期性を利用して
0～π/4くらいまで縮小してから級数計算すると、
必要な項数が減り、計算量を抑えられます。
⑥ メモリ再利用
毎回
new BigNumber()せず、
使い回せる領域は再利用します。
GC負荷がかなり減ります。
業界話
実は世界最高速クラスの多倍長ライブラリを書いている人たちは、それほど多くありません。
代表格のGMPは1990年代から改良が続けられており、CPUアーキテクチャごとのアセンブリコードまで含めて膨大な最適化が積み重ねられています。多倍長演算ライブラリは、暗号・数論・数値解析・計算機代数など幅広い分野で使われるため、「一度ライブラリを徹底的に速くし、多くのソフトウェアがそれを利用する」という文化が根付いています。
一方、Web開発では「速度より保守性や移植性」を重視することが多く、JavaScript製の多倍長ライブラリは、ブラウザでどこでも動くことを優先した設計になっている場合が少なくありません。そのため、純粋な演算速度では専用ライブラリとの差が大きくなります。
あなたのケースで特に注目した点
「5万桁で704秒」という数字は、ブラウザで純粋なJavaScriptによる高精度三角関数計算としては十分に起こり得る範囲ですが、「200万桁を1分未満」というPython版は、単なるPythonコードでは説明しにくい速度です。内部で高度に最適化された多倍長演算ライブラリやアルゴリズムを利用している可能性が高いでしょう。
もしJavaScript版でも「数十万桁〜数百万桁」を現実的な時間で目指すのであれば、純粋なJavaScriptの改良だけでなく、WebAssembly化したGMP/MPFRの利用、Web Workerによる並列化、Binary SplittingやFFT乗算などのアルゴリズム改善を組み合わせることが、最も大きな性能向上につながる可能性があります。
0 件のコメント:
コメントを投稿