注意：このブログではGo言語のBigint(多倍長整数)について触れています
12/6 追記：殺せました

こんにちは。 ISUCON7本戦に「百万円ドリブン」の一員として参加しました。メンバーは僕と, @nakario, @aokabi の三人で,二人はサークルのメンバーです。集中のあまり美味しいお昼のクッキーと珈琲は逃してしまいました。

結果はタイトルの通りであり、競技時間内ではネックとなっていた Bigint を殺すことが出来ず、悔しかったのでBigint周りで試行錯誤をした結果について述べます。具体的には、Bigintと__float128について述べます。

今回のボトルネック

ボトルネックの測定と発見は @nakario が率先してやってくれました。僕の改善担当箇所はそれにより判明したボトルネックの一つ「Bigint の10進上位15桁の取得」でした。

初期実装

初期実装では、Bigintを一旦文字列に変換してから先頭から15文字をとるという実装になっていました。ベンチマークを回すと分かるのですが、このBigintは15万桁程度まで達する可能性があり、すなわち15万文字の最初の15文字のみしか使わないということが平気で起こり、遅いのも容易に理解できます。これは改善しなければなりませんね。

改善案

Go言語ではBigintはuint(符号なし64bit整数)の配列として表現されています。単純に思いつく改善方法は、上位15桁さえ分かればよいので、その配列の上位2つのuintからその数字を近似して計算する方法です。例えば、 45桁の整数 111112222233333444445555566666777778888899999
= 326529 × 2¹²⁸ + 8741109308212120013 × 2⁶⁴ + 7629705161560292767
となっているわけですが、これを上位2つのみを使用し、
326529 × 2¹²⁸ + 8741109308212120013 × 2⁶⁴
= 111112222233333444445555559037072617328607232
と近似します。計算すれば分かることですが、桁が増えても上位2つのみを用いればよいことに変わりはありません。上位2つを用いて近似することにより、桁数オーダーだった部分を改善することが出来ます。こうすれば BigIntを一つも使わなくてもよくなり、大幅な改善が見込めますね。

実装と精度の問題

上記の案をそのままuint64やfloat64で計算すると桁は容易に溢れるので、 log10 して計算し、最後に10の指数で戻せばよいです。楽勝ですね。
…
…
…
なーんてことは無かった…。そもそもfloat64は15.9桁までしか整数との1対1対応を保証してくれません。今回必要な桁は15桁、かなりギリギリです。 log10したり演算をすると、微妙に2桁程度合わないのです…。 ISUCON中ずっと「あと2桁!!あと2桁なんや…!!」って叫んでいました。本質的に精度が微妙に足りないのです。このあと僕は迷走してしまい、ISUCONは敗北を期しました。

こたえ

15桁全てを合わすことは到底不可能でも、それが何桁かどうかは精度の問題なしにすぐに計算できます。よって、桁数を計算しもとのBigIntからその10の桁数分で除算するという方法がとれます。
例えば 111112222233333444445555566666777778888899999 / 100000000000000000000000000000
を行い 111112222233333 にするような感じです。本質的にはBigIntをStringに変換する処理がBigInt除算の処理に変わります。実はこれだけでかなり高速になり、初期実装からこの部分のみを変更してベンチマークを走らせたところ、(ネックは他にもあるので一概には言えませんが) 7000点程度だったものから14000点まであがり、スコアが二倍になりました… ~~はいbigintゲーwwwwwwwwww~~

bigint許さん

しかしながらこんなにも僕を困らせてくれる bigint 、殺すしかありません。なんとしてでも bigintを実装から全て消し去り心の平穏を取り戻したいものです。さて、僕の最初に思いついた実装方法は、精度が足りなかっただけなわけですから、もっと精度の高いものを使えばbigintを使わなくても実装できるはずです。残念ながら Go言語には float64までしかありません。 float128くらいまであればよいのですが…
…
…
…
はい、というわけで GCC の __float128 を使ってみましょう。

__float128

__float128 の枠組みは、疑似四倍精度とも呼ばれ、ソフトウェア的に float64を複数用いることで擬似的に4倍精度を達成する枠組みです。 gccでコンパイルすれば簡単に使えるので、Go言語とC言語を繋ぐ cgo を用いれば上手くできそうです。 cgo では、C言語でコンパイルしたい関数を書いたC言語のコードを用意し、そのインターフェースとコンパイルフラグ等をgo言語でシュッと記述すると簡単に二つを繋ぐことができます。以下にCとGoのコードを載せます。

#include <math.h>
#include <quadmath.h>
typedef unsigned long long UINT64;
void myb2e(UINT64 w1,UINT64 w2,UINT64 bef,UINT64 *o_keta,UINT64 *o_res){
  __float128
    fw1 = w1,
    fw2 = w2,
    log10ed = (64 * bef) * M_LN2q / M_LN10q
              + log10q(18446744073709551616.0Q * fw1 + fw2),
    res = expq((log10ed - floorq(log10ed)) * M_LN10q) * 100000000000000.0Q;
  *o_keta = (UINT64)log10ed - 14;
  *o_res = res + 0.000000000000001Q;
}

package main
//#cgo LDFLAGS: -lquadmath
//#cgo CFLAGS: -O3
//#include <stdlib.h>
//typedef unsigned long long UINT64;
//extern void myb2e(UINT64 w1,UINT64 w2,UINT64 bef,UINT64* o_keta,UINT64* o_res);
import "C"
func B2E(w1, w2, bef uint64) (keta, res uint64) {
    var o_keta C.UINT64
    var o_res C.UINT64
    C.myb2e(C.UINT64(w1), C.UINT64(w2), C.UINT64(bef), &o_keta, &o_res)
    return uint64(o_keta), uint64(o_res)
}

はい。bigintを殺せました。勝利ですね。早速ベンチを回しましょう…。
…
…
…

6 0 0 0 点!!!

初期実装より遅い !!

イヤイヤイヤイヤ、オイオイオイオイ… cgoのオーバーヘッドが意外と大きいのか?と思って計測してみましたが、そういうわけでもなく、純粋に __float128 が遅いようです…。まじかぁ…

まとめ

BigIntを殺そうとしたが結局BigIntを完全に殺すことはできなかった。 BigIntくんも__float128くんよりは生かす価値があるようだ、命拾いしたな…

この記事を読んだ人はこんな記事も読んでいます

aokabit.hatenablog.com

nakario.hateblo.jp

全コード

github.com

12/6 追記 (実質Bigintを殺せた)

Bigint同士の除算は桁数オーダーの時間が掛かりますが、初期実装の段階では上記の改善のみでよさそうです。この後、更に高速化してもう一度この部分がネックになってきた場合には、除算を上位の3つのuintのみで行えばよいですね。この実装であれば実質BigIntを殺したといっても過言ではないのでかなり満足です。

// 桁数が増えても大丈夫
func customBigIntDiv(a *big.Int, b *big.Int) int64 {
    alen := len(a.Bits())
    if alen < 4 {
        return big.NewInt(0).Div(a, b).Int64() 
    }
    an := big.NewInt(0).SetBits(a.Bits()[alen-3:])
    bn := big.NewInt(0).SetBits(b.Bits()[alen-3:])
    return big.NewInt(0).Div(an, bn).Int64() 
}