実装したいものを思い描いていたところ、その過程で「整数の1が立ったビットを数える」ということが必要となりました。ところが、Rubyで実装するとかなり遅いことに気づいたので、C言語などで実装してみることにしました（jkr2255/bit_counter）。
先行事例
最近はPOPCNTというCPU命令になるぐらいだし（後述）、だれか実装しているだろうと思ったら、意外とBignumについてはほぼ手付かずだということに気づきました。
「ないんだったら、自分で作ればいいのよ！」
負の数について
Rubyの場合、整数が無限桁を（概念上）許容して、しかも負の数は２の補数表現ということもあって、符号ビットの1が無限に続くこととなっています。さすがにこの状態で1の数を数えても「無限大」となって意味がないので、負の数の時は「0の数を数えて、さらにそれをマイナスにして返す」という実装にしました1。
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で数えます2。なかった場合は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でも動くことは動くのですが、あまり速くならないので、なんとかならないものか検討中です。