Edited at

JavaScriptの任意精度整数: BigInt vs big-integer (2018年11月2日追記)


はじめに

先日Node学園 30時限目に参加して、Node v10で新しく入ったBigIntについて話してきました。

本記事では発表内容の補足というか、時間の都合上「おまけスライド」にしたbig-integerパッケージとの比較について説明します。


スライドどれよ

BigInt あれこれ

この記事を読む前に、軽く目を通しても通さなくてもどっちでもいいです。


基礎知識

まずは、NumberBigIntbig-integerについて簡単に説明します。


Number


  • 現在のJavaScriptの数値型

  • 64bit

  • ただし整数部は53bit



  • 詳しくは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億回ひたすら繰り返す雑なベンチマークで速度検証してみます。


benchmark-bigint.js

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;
}
}
}
}


benchmark-big-integer.js

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型の範囲外の整数に対してベンチマークを走らせてみます。


benchmark-bigint-2.js

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;
}
}
}
}


benchmark-big-integer-2.js

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単位でパックしています。

たとえば1234567890123456789012345678900x18ee90ff6c373e0ee4e3f0ad2)という数値は


  • BigIntの場合


    1. 下から4バイト単位に切る; 1, 8ee90ff6, c373e0ee, 4e3f0ad2

    2. little-endianで配列に入れる; [0x4e3f0ad2, 0xc373e0ee, 0x0x8ee90ff6, 0x00000001]



  • big-integerの場合


    1. 下から10000000単位に切る; 12, 3456789, 0123456, 7890123, 4567890

    2. little-endianで配列に入れる; [4567890, 7890123, 123456, 3456789, 12]



このことから、次のようにも言えます。


  • 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