実装したいものを思い描いていたところ、その過程で「整数の1が立ったビットを数える」ということが必要となりました。ところが、Rubyで実装するとかなり遅いことに気づいたので、C言語などで実装してみることにしました（jkr2255/bit_counter）。

先行事例

最近はPOPCNTというCPU命令になるぐらいだし（後述）、だれか実装しているだろうと思ったら、意外とBignumについてはほぼ手付かずだということに気づきました。

「ないんだったら、自分で作ればいいのよ！」

負の数について

Rubyの場合、整数が無限桁を（概念上）許容して、しかも負の数は２の補数表現ということもあって、符号ビットの1が無限に続くこととなっています。さすがにこの状態で1の数を数えても「無限大」となって意味がないので、負の数の時は「0の数を数えて、さらにそれをマイナスにして返す」という実装にしました¹。

JRuby版…Javaに実装済み

C言語で拡張を作ると、JRubyは非対応となってしまします。ところが、今回の場合は、Long.bitCount()やBigInteger#bitCount()という、目的ぴったりなメソッドがJava側にあったので、これを呼び出すだけでほぼ片付きました。

とはいえ、JRubyでC拡張のビルドが始まってしまうとエラーになるので、RakefileやgemspecでJRubyかどうかの条件分岐を入れて、さらにJRuby用Gemを別個で生成してRubyGemsにプッシュする必要がありました。

C拡張の作成

Rubyの整数はFixnumとBignumに分かれていますが、Fixnumは簡単にC言語の整数にできるので、やるべきことは

C言語レベルで高速にビットを数える
Bignumをビット配列に変換する

この2つです。

C言語レベルでのビットカウント

まず、SSE 4.2で導入されたPOPCNT命令が使えるかCPUIDでチェックして、有効ならPOPCNTで数えます²。なかった場合はGCC組み込みの__builtin_popcountl()を使って、それもないときは手で書いたバージョンのカウント関数を使います。

`Bignum`の値を配列に変換

Bignumで演算を続ければそのたびにオブジェクトを生成してしまって、スピードは全く出ません。ということで、いったんBignumから数値配列に変換しますが、Rubyのバージョンによってrb_big_packとrb_integer_packという2つの関数があって、どっちが有効かが違ったりします。あと、変換用のバッファーも容量が小さい場合にはALLOCではなくALLOCAでスタックにとってオーバーヘッドを避けています（実際、小さな数ではこれだけで3割高速化しました）。

配列に入ればあとはカウントですが、Windows x64環境ではlongが32ビット幅なので、ポインタを読み替えて64ビットのPOPCNT命令を使えるようにしています。

ベンチマーク

よく使われるnum.to_s(2).count('1')と比較してみたところ、（POPCNT命令のあるマシンで）5倍から20倍ほど高速化していました。

残る課題

いちおうRubiniusでも動くことは動くのですが、あまり速くならないので、なんとかならないものか検討中です。

JavaのBigInteger#bitCount()は、「符号ビットと異なる」ビットの数を返す、となっています。つまり、負数についても正の値を返します。 ↩
AVXなどを使って気合を入れればもう少し速くなるようですが、そこまではやっていません。 ↩