はじめに
先日Node学園 30時限目に参加して、Node v10で新しく入ったBigIntについて話してきました。
本記事では発表内容の補足というか、時間の都合上「おまけスライド」にしたbig-integerパッケージとの比較について説明します。
スライドどれよ
この記事を読む前に、軽く目を通しても通さなくてもどっちでもいいです。
基礎知識
まずは、NumberとBigIntとbig-integerについて簡単に説明します。
Number
- 現在のJavaScriptの数値型
- 64bit
- ただし整数部は53bit
- 表せるのは
9007199254740991（Number.MAX_SAFE_INTEGER）まで
- 表せるのは
- 詳しくはMDN参照
BigInt
-
TC39でプロポーザルに挙がっている新しい数値型
- 現在はStage3
- 採用確定ではない（Stage4になるまでは却下される可能性あり）
-
任意精度の整数
- ハードウェアがサポートしているのではなく、各処理系がソフトウェア的に実装する
- 数値リテラルに
nをつけるか、BigInt()関数で生成する-
256n,0x100n -
BigInt(256),BigInt("256"),BigInt("0x100")
-
- Node v10で実験的サポート
-
--harmony-bigintオプションが必要
-
big-integer
- 任意精度の整数を扱えるNPMのパッケージ
- ビルトインの型でもオブジェクトでもないよ！
- Node v0.6以降で動作
- 最新バージョンにアップグレードしなくても使える
性能を比較してみる
ベンチマークその1
演算を1億回ひたすら繰り返す雑なベンチマークで速度検証してみます。
let i, j, k, val;
for(i = 1n; i <= 100n; i++) {
for(j = 1n; j <= 100n; j++) {
for(k = 1n; k <= 100n; k++) {
for(l = 1n; l <= 100n; l++) {
val = i;
val += j;
val *= k;
val %= l;
}
}
}
}
const BigInteger = require("big-integer");
let i, j, k, val;
for(i = 1; i <= 100; i++) {
for(j = 1; j <= 100; j++) {
for(k = 1; k <= 100; k++) {
for(l = 1; l <= 100; l++) {
val = BigInteger(i);
val = val.plus(j);
val = val.multiply(k);
val = val.mod(l);
}
}
}
}
最後が除算ではなく剰余算なのは、（スライドを見てもらえばわかるとおもいますが）もともとNumberとBigIntの性能比較につかったベンチマークだったので、どちらでも結果が変わらない剰余算を使ったのが理由です。
（除算だと1 / 2 === 0.5に対し、1n / 2n === 0nと結果が変わる）
予想
そりゃBigIntのほうが速いでしょう。
big-integerはJavaScript上で実装しているのに対し、BigIntはJavaScriptの言語仕様に含まれている（オーバーヘッドが少ない）上にC++で実装しているんだもの。
結果
$ time node --harmony-bigint benchmark-bigint.js
real 0m22.087s
user 0m24.116s
sys 0m0.355s
$ time node --harmony-bigint benchmark-big-integer.js
real 0m7.587s
user 0m8.001s
sys 0m0.362s
ファッ？big-integerのほうが3倍も高速だと！？
解説
なんとも意外な結果ですが、実はbig-integerはNumber型で収まる範囲の演算についてはNumber型でそのまま演算するので、常にソフトウェアで演算するBigIntよりも速いのです。
ベンチマークその2
というわけで、今度はNumber型の範囲外の整数に対してベンチマークを走らせてみます。
let i, j, k, val;
for(i = 1n; i <= 100n; i++) {
for(j = 1n; j <= 100n; j++) {
for(k = 1n; k <= 100n; k++) {
for(l = 1n; l <= 100n; l++) {
val = BigInt(Number.MAX_SAFE_INTEGER) + i;
val += j;
val *= k;
val %= l;
}
}
}
}
const BigInteger = require("big-integer");
let i, j, k, val;
for(i = 1; i <= 100; i++) {
for(j = 1; j <= 100; j++) {
for(k = 1; k <= 100; k++) {
for(l = 1; l <= 100; l++) {
val = BigInteger(Number.MAX_SAFE_INTEGER).plus(i);
val = val.plus(j);
val = val.multiply(k);
val = val.mod(l);
}
}
}
}
結果
$ time node --harmony-bigint benchmark-bigint-2.js
real 0m30.764s
user 0m33.004s
sys 0m0.343s
$ time node --harmony-bigint benchmark-big-integer-2.js
real 0m41.659s
user 0m42.663s
sys 0m0.932s
今度はBigIntがbig-integerより1.3倍高速という結果が出ました。
その他の違い
BigIntとbig-integerの実装には、パックの単位の違いもあります。
BigIntは4バイト単位でパックしているのに対し、big-integerは10000000単位でパックしています。
たとえば123456789012345678901234567890（0x18ee90ff6c373e0ee4e3f0ad2）という数値は
- BigIntの場合
- 下から4バイト単位に切る;
1,8ee90ff6,c373e0ee,4e3f0ad2 - little-endianで配列に入れる;
[0x4e3f0ad2, 0xc373e0ee, 0x0x8ee90ff6, 0x00000001]
- 下から4バイト単位に切る;
- big-integerの場合
- 下から10000000単位に切る;
12,3456789,0123456,7890123,4567890 - little-endianで配列に入れる;
[4567890, 7890123, 123456, 3456789, 12]
- 下から10000000単位に切る;
このことから、次のようにも言えます。
- 2進表現で高速に計算できるものはBigIntが有利
- 2の累乗、4の累乗、ビットシフト等
- 2進文字列、16進文字列等への変換
- 10進表現で高速に計算できるものはbig-integerが有利
- 10の累乗等
- 10進文字列への変換
- 1パックあたりに詰め込める値はBigIntのほうが大きいため、桁数が多くなるとBigIntが有利
ただし、「BigIntは4バイト単位でパックしている」というのはあくまでV8のBigIntの実装なので、JavaScriptエンジンごとに変わる可能性があります。
結論
どっちも得意分野と不得意分野があるので、条件によってBigIntが速いときもbig-integerが速いときもあります。
結局どっちを使えばいいの？という人のための目安を挙げておきます。
-
BigIntを使えない環境ならbig-integer一択
- 古いNodeでも動かしたい
- LTSを使いたい
-
--harmonyオプションを使いたくない - Webブラウザでも動かしたい
- Number型の範囲に収まる可能性があるならbig-integerも検討の余地あり
- ビットシフトや16進文字列への変換等、2進表現で高速に計算できる演算が多いならBigIntが有利
- 10倍、100倍や10進文字列への変換等、10進表現で高速に計算できる演算が多いならbig-integerが有利
- 桁数が何百、何千と多くなるとBigIntが有利
2018年11月2日追記
10月30日にNode v10のLTSがリリースされました。
https://nodejs.org/ja/
LTSで、 --harmony-bigint なしで BigInt を使えるようになりました！
$ node
> process.versions.node
'10.13.0'
> typeof 0n
'bigint'
> 2**100
1.2676506002282294e+30
> 2n**100n
1267650600228229401496703205376n