かずの心の贅肉 bitを数える

かずの心の贅肉

コンピュータ将棋など…。

[142] [141] [140] [139] [138] [137] [136] [135] [134] [133] [132]

[PR]

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

【2024/11/22 21:55 】

CATEGORY[]

bitを数える

セットされているbitを数える関数を作ってみました。
ダウンロード(popcnt.zip)

popcnt_a はループによる数え上げ、popcnt_bはbitシフトと論理積(AND)と加算による数え上げ。
Athlon64X2 4600+ではpopcnt_bは一定の時間で終了するんだけど、セットされているbitの数だけループを回るpopcnt_aは思わぬ結果が？！

popcnt_aではセットされたbitの数が 1 が最速で以下、0、2、・・・と続きました。
Core2Duoでは確か 0 が一番でしたけど…??

以下の結果では Athlon64X2 ではpopcnt_a(1)＜popcnt_b()＜popcnt_a(0)＜popcnt_a(2)＜・・・＜popcnt_a(32)なので、
常にpopcnt_b()を使うのがいいのかなぁ～。

結果：
popcnt_a:00000000000000000000000000000000: 2.3590 sec
popcnt_b:00000000000000000000000000000000: 1.9370 sec
popcnt_a:00000000000000000000000000000001: 0.7970 sec
popcnt_b:00000000000000000000000000000001: 1.9370 sec
popcnt_a:00000000000000000000000000010001: 5.9070 sec
popcnt_b:00000000000000000000000000010001: 1.9370 sec
popcnt_a:00000000000000000001000100010001: 6.5470 sec
popcnt_b:00000000000000000001000100010001: 1.9380 sec
popcnt_a:00010001000100010001000100010001: 7.8280 sec
popcnt_b:00010001000100010001000100010001: 1.9380 sec
popcnt_a:01010101010101010101010101010101: 9.9840 sec
popcnt_b:01010101010101010101010101010101: 1.9380 sec
popcnt_a:11111111111111111111111111111111:13.5150 sec
popcnt_b:11111111111111111111111111111111: 1.9380 sec

【2009/09/12 14:23 】

CATEGORY[開発]

Trackback[]

COMMENT[6]

ソース読んでみたんですが

ひょっとしてpopcnt_aって最上位（左端）ビットだけが1だと遅くなりません？
なんにせよ、一定時間で終わるpopcnt_bの方が使い勝手はよさそうですが。

＃もしくは、Phenomかってハードウェア実行とかw

【2009/09/12 16:39】 NAME[森岡＠GA将!!!!] WEBLINK[] EDIT[

]

Re:ソース読んでみたんですが

64bit環境ではpopcnt_aのほうが速いようです。

x...x10...0 : u
x...x01...1 : u-1
x...x00...0 : u & (u-1)

ただし
x...x : don't care
1...1 : All 1
0...0 : All 0

なので、どこの位置が1でもセットされているbit数が同じなら演算時間に差は出ないかと。

PhenomII はありますが、スキル(or ツール?)の関係でpopcntを使えません orz

【2009/09/14 05:06】

無題

64bit OSで64bit幅のpopcntと、SSE4.2のPOPCNTも計測おながい(´ω｀)人

【2009/09/12 16:39】 NAME[やねうらお] WEBLINK[] EDIT[

]

64bit環境

やね巨匠なら自前で出来るのではないでしょうか?
とりあえず64bit OSでもやってみました。

【2009/09/14 05:07】

無題

昔、似たような比較を
http://d.hatena.ne.jp/mkomiya/20070906/p4

>SSE4.2のPOPCNT
　これが知りたいです

【2009/09/12 18:37】 NAME[komiya] WEBLINK[] EDIT[

]

SSE4.2

スキル(or ツール?)の関係でダメでした。
昔の記事は実行前に確認しています。

【2009/09/14 05:09】

無題

popcnt_bだと時間が一定？
生成されたアセンブラはどうなんですか？

【2009/09/12 18:39】 NAME[komiya] WEBLINK[] EDIT[

]

Re:無題

シフトと論理積と加算なので実行時間の変動要素はないんじゃないかと。
とはいえ、微妙に変動していますね…。なんででしょう??
とりあえず、新しい日記のほうのアーカイブに生成されたアセンブラを付けました。

【2009/09/14 05:30】

無題

> PhenomII はありますが、スキル(or ツール?)の関係でpopcntを使えません orz

普通にbyte配列にアセンブルしたコードを突っ込んで、VirtualAllocでPAGE_EXECUTE_READWRITEで実行可能にして、そこを実行すればいいのでは。

【2009/09/14 07:00】 NAME[やねうらお] WEBLINK[] EDIT[

]

ハンドアセンブル

AMD64のマニュアルにPOPCNTを見つけましたが、バイトコードがわかりません。
POPCNT reg16, reg/mem16 F3 0F B8 /r Count the 1s in reg/mem16.
POPCNT reg32, reg/mem32 F3 0F B8 /r Count the 1s in reg/mem32.
POPCNT reg64, reg/mem64 F3 0F B8 /r Count the 1s in reg/mem64.

【2009/09/15 02:57】

無題

> AMD64のマニュアルにPOPCNTを見つけましたが、バイトコードがわかりません。

ええと、バイトコードは、まさにその「F3 0F B8 /r」です。

/rの部分は、レジスタなのかメモリなのかを表わすコードが来ます。

AMDの↓のマニュアルでは
http://support.amd.com/us/Processor_TechDocs/24594.pdf
これのPP.364-372です。

この/rは、他の命令で/rと書いてあるのと同じなので、面倒なことを考えたくなければ、試しにいまお手持ちのVCで何かインラインアセンブラで書いてみて、それがどうバイナリに変わったのか混合モードで見れば、何を書けばいいかわかると思います。

【2009/09/15 08:41】 NAME[やねうらお] WEBLINK[] EDIT[

]

バイトコード

>まさにその「F3 0F B8 /r」です。

えーと、POPCNT EAX,ECX なら「F3 0F B8 C8」でしょうか??
とりあえず、gcc と objdump の出力からの推測です。
REX は難しくてわかりませんが、POPCNT RAX,RCX だと 48？で「48 F3 0F B8 C8」でしょうか??

とりあえず、バイトコードはわかったけど、それを実行するところはパスで。
VS2008なら簡単かな??

【2009/09/16 01:33】