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

# はじめに
先日[Node学園 30時限目](https://nodejs.connpass.com/event/83639/)に参加して、Node v10で新しく入った`BigInt`について話してきました。

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

# スライドどれよ

[BigInt あれこれ](https://shimataro.github.io/slides/20180427-tng-30.html)

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

# 基礎知識
まずは、`Number`と`BigInt`と`big-integer`について簡単に説明します。

## Number
* **現在のJavaScriptの数値型**
* 64bit
* ただし**整数部は53bit**
    * 表せるのは`9007199254740991`（[`Number.MAX_SAFE_INTEGER`](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER)）まで
* 詳しくは[MDN](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Number)参照

## BigInt
* [TC39](https://tc39.github.io/proposal-bigint/)でプロポーザルに挙がっている**新しい数値型**
    * 現在はStage3
    * 採用確定ではない（Stage4になるまでは却下される可能性あり）
* **任意精度**の整数
    * ハードウェアがサポートしているのではなく、各処理系がソフトウェア的に実装する
* 数値リテラルに`n`をつけるか、`BigInt()`関数で生成する
    * `256n`, `0x100n`
    * `BigInt(256)`, `BigInt("256")`, `BigInt("0x100")`
* Node v10で実験的サポート
    * `--harmony-bigint`オプションが必要

## big-integer
* 任意精度の整数を扱える[**NPMのパッケージ**](https://www.npmjs.com/package/big-integer)
    * ビルトインの型でもオブジェクトでもないよ！
* Node v0.6以降で動作
    * 最新バージョンにアップグレードしなくても使える

# 性能を比較してみる
## ベンチマークその1
演算を1億回ひたすら繰り返す雑なベンチマークで速度検証してみます。

```javascript: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;
            }
        }
    }
}
```

```javascript: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++で実装しているんだもの。

### 結果
```bash
$ time node --harmony-bigint benchmark-bigint.js

real    0m22.087s
user    0m24.116s
sys     0m0.355s
```

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

```javascript: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;
            }
        }
    }
}
```

```javascript: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);
            }
        }
    }
}
```

### 結果
```bash
$ time node --harmony-bigint benchmark-bigint-2.js

real    0m30.764s
user    0m33.004s
sys     0m0.343s
```

```bash
$ 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の場合
    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` を使えるようになりました！

```bash
$ node
> process.versions.node
'10.13.0'
> typeof 0n
'bigint'
> 2**100
1.2676506002282294e+30
> 2n**100n
1267650600228229401496703205376n
```