📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: wwwyhx
跳转到指定楼层
上一主题 下一主题
收起左侧

google : 计算二进制1的个数

🔗
 楼主| wwwyhx 2011-5-2 01:22:50 | 只看该作者
全局:
回复  wwwyhx

关键是你要频繁做访存,你又不能保证你的查表的表一定在cache里,只要有一次访问它不在cache里,嘿嘿,访问内存需要的时钟周期可是比加加减减神马的多几个数量级的哦。
这东西必然要到实际机器上跑一跑测一测的,究竟哪个效率更好从体系结构到操作系统都关系很大的。

有的cpu里面有专门的指令用来算popcount的,感觉上那一定超级快吧?有人测试过,sometimes没有并行的算法快,虽然看上去指令数更多,但是消耗的时钟周期却更少。
Etrnls 发表于 2011-5-2 00:39


对cpu,体系结构啥的没啥研究,但是我的感觉(不确定)是~~
操作系统一般有提供以页面为单位,一定驻留内存的机制。

就算偶尔失配(没有其他太耗内存因素的干扰下几乎不可能),
也赶不上每个数多算那么几次*n的开销

我感觉那个操作花费的时钟周期啥的不会比直接读个内存取个数啥的少。

为啥popcount函数没用map方式可能是因为它觉得对于计算一个数来说,不值得分配一个256k内存再释放,这样内存分配释放的过程比较耗,但是如果需要计算很多数,就值得了。

同意因该测试得出结论,不过... 这里也没太大必要.. 大家发表一下意见就行了
回复

使用道具 举报

🔗
Etrnls 2011-5-2 09:57:42 | 只看该作者
全局:
回复 11# wwwyhx

你说的操作系统管理的东西是virtual memory,那个分页的东西是管理某个页面是否有对应的物理内存和它映射。

我说的是只要你访问内存,就灰常慢,你要保证要访问的内存在cpu的cache里面才行,所以至少在操作系统这一层相应的页面肯定不能miss的,要想访存的速度赶上加加减减的速度,必须访存指令一路没有任何障碍(页面木有映射、cache miss等等)。

其实这个算法有不需要乘法的版本的,只是现在大多数cpu乘法已经和加法速度差不多了(消耗的时钟周期木有数量级的差别),现在真正慢的是除法指令,所以我就贴了这个版本。
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-2 10:31:56 | 只看该作者
全局:
回复  wwwyhx

你说的操作系统管理的东西是virtual memory,那个分页的东西是管理某个页面是否有对应的物理内存和它映射。

我说的是只要你访问内存,就灰常慢,你要保证要访问的内存在cpu的cache里面才行,所以至少在操作系统这一层相应的页面肯定不能miss的,要想访存的速度赶上加加减减的速度,必须访存指令一路没有任何障碍(页面木有映射、cache miss等等)。

其实这个算法有不需要乘法的版本的,只是现在大多数cpu乘法已经和加法速度差不多了(消耗的时钟周期木有数量级的差别),现在真正慢的是除法指令,所以我就贴了这个 ...
Etrnls 发表于 2011-5-2 09:57


是的,我昨天又想了想,你指的这个失配主要是cpu一级缓存的失配,不是指内存的失配,就算是高速缓存也比寄存器慢,因为运算的临时结果还是存在寄存器里的,你说的没错,非常感谢

那个并行算法的思想就是计算每两位1的个数,存在对应的两位里
然后计算每4位1的个数(上次结果的每两位相加)
然后每8位。。。。。

的确很巧妙
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表