当前在线人数20132
首页 - 分类讨论区 - 电脑网络 - 葵花宝典版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
Re: bit count discussion
[版面:葵花宝典][首篇作者:adven] , 2004年12月31日22:31:14 ,次阅读,次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
adven
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: adven (冒险者), 信区: Programming
标  题: Re: bit count discussion
发信站: Unknown Space - 未名空间 (Fri Dec 31 22:32:04 2004), 转信

OK. 半决赛名单。我都采纳!

#define bit1count(bitint)                                       \
(                                                               \
  regx=(bitint),                                                \
  regx=(regx&0x55555555)+((regx&0xaaaaaaaa)>>1),                \
  regx=(regx&0x33333333)+((regx&0xcccccccc)>>2),                \
  regx=(regx&0x0f0f0f0f)+((regx&0xf0f0f0f0)>>4),                \
  regx=(regx&0x00ff00ff)+((regx&0xff00ff00)>>8),                \
  regx=(regx&0x0000ffff)+((regx&0xffff0000)>>16)                \
)

#define bit1lookup(bitint)                                      \
(                                                               \
  regx=bit1count_tab[bitint&0x000007FF],                        \
  regx+=bit1count_tab[(bitint&0x003FF800)>>11],                 \
  regx+=bit1count_tab[(bitint&0xFFC00000)>>22]                  \
)

table size 2K. 一次load进一个cacheblock/cacheline.
if it's dense bits, 常访问的table部分更小。
if it's sparse bits, 也很小。
乱来,那就没辙了。换大cache机器:)

【 在 Ringer (NFS U2) 的大作中提到: 】
: 不管是不是向量机,极限性能最后决定于你cpu里有多少个ALU,ALU的宽度和L1大小
: 你那个算法仅在L1很小,ALU很宽,使用software pipelining的时候才有可能接近或
: 者稍微超出查表性能
: 【 在 adven (冒险者) 的大作中提到: 】
: : 跟你说了。我的是向量运算!你真以为就一个或者一串integer啊!


--

        理论联系实际

※ 修改:.adven 于 Dec 31 22:45:05 修改本文.[FROM: 199.74.]
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 199.74.]

 
Ringer
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: Ringer (NFS U2), 信区: Programming
标  题: Re: bit count discussion
发信站: Unknown Space - 未名空间 (Fri Dec 31 22:49:59 2004), 转信


【 在 adven (冒险者) 的大作中提到: 】
: OK. 半决赛名单。我都采纳!
: #define bit1count(bitint)                                       \
: (                                                               \
:   regx=(bitint),                                                \
:   regx=(regx&0x55555555)+((regx&0xaaaaaaaa)>>1),                \
:   regx=(regx&0x33333333)+((regx&0xcccccccc)>>2),                \
:   regx=(regx&0x0f0f0f0f)+((regx&0xf0f0f0f0)>>4),                \
:   regx=(regx&0x00ff00ff)+((regx&0xff00ff00)>>8),                \
:   regx=(regx&0x0000ffff)+((regx&0xffff0000)>>16)                \
: )
: #define bit1lookup(bitint)                                      \
: (                                                               \
:   regx=bit1count_tab[bitint&0x000007FF],                        \
:   regx+=bit1count_tab[(bitint&0x003FF800)>>11],                 \
:   regx+=bit1count_tab[(bitint&0xFFC00000)>>22]                  \

change it to

   regx=bit1count_tab[...]  +  ... + ...



: )
: table size 2K. 一次load进一个cacheblock/cacheline.
: if it's dense bits, 常访问的table部分更小。
: if it's sparse bits, 也很小。
: 乱来,那就没辙了。换大cache机器:)
: 【 在 Ringer (NFS U2) 的大作中提到: 】
: : 不管是不是向量机,极限性能最后决定于你cpu里有多少个ALU,ALU的宽度和L1大小
: : 你那个算法仅在L1很小,ALU很宽,使用software pipelining的时候才有可能接近或
: : 者稍微超出查表性能


--
qishiwoxiangshuodezhiyouyijuhua,zhejuhuashishenmene?
heihei,niyidinghenxiangzhidaoba!nawojiugaosunihaole.
kanwanleyihounikebuyaogaosubieren,burandehuawozaiye
buhenishuohuale!zhejuhuajiushi...feilebantianjinkan
zhejuhuaderenzhenkelian...xianzainizhongyuzhidaoleba

※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 158.130.]

 
adven
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: adven (冒险者), 信区: Programming
标  题: Re: bit count discussion
发信站: Unknown Space - 未名空间 (Fri Dec 31 22:51:03 2004), 站内信件

反正汇编也会reg的:)
改了心里踏实些也好。

#define bit1lookup(bitint)                                      \
(                                                               \
  bit1count_tab[bitint&0x000007FF] +                            \
  bit1count_tab[(bitint&0x003FF800)>>11] +                      \
  bit1count_tab[bitint>>22]                                     \
)

【 在 Ringer (NFS U2) 的大作中提到: 】
: 【 在 adven (冒险者) 的大作中提到: 】
: : OK. 半决赛名单。我都采纳!
: : #define bit1count(bitint)                                       \
: : (                                                               \
: :   regx=(bitint),                                                \
: :   regx=(regx&0x55555555)+((regx&0xaaaaaaaa)>>1),                \
: :   regx=(regx&0x33333333)+((regx&0xcccccccc)>>2),                \
: :   regx=(regx&0x0f0f0f0f)+((regx&0xf0f0f0f0)>>4),                \
: :   regx=(regx&0x00ff00ff)+((regx&0xff00ff00)>>8),                \
: :   regx=(regx&0x0000ffff)+((regx&0xffff0000)>>16)                \
: : )
: : #define bit1lookup(bitint)                                      \
: : (                                                               \
: :   regx=bit1count_tab[bitint&0x000007FF],                        \
: :   regx+=bit1count_tab[(bitint&0x003FF800)>>11],                 \
: :   regx+=bit1count_tab[(bitint&0xFFC00000)>>22]                  \
: change it to
:    regx=bit1count_tab[...]  +  ... + ...
: : )
: : table size 2K. 一次load进一个cacheblock/cacheline.
: : if it's dense bits, 常访问的table部分更小。
: : if it's sparse bits, 也很小。
: : 乱来,那就没辙了。换大cache机器:)


--

        理论联系实际

※ 修改:.adven 于 Dec 31 22:52:39 修改本文.[FROM: 199.74.]
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 199.74.]

[分页:1 ]
[快速返回] [ 进入葵花宝典讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996