找回密码
 欢迎注册
楼主: gxqcn

[讨论] 一个快速得到bit位索引的算法

[复制链接]
发表于 2008-3-12 10:53:12 | 显示全部楼层
考虑做连续0的消除
没想好指令如何操作
最好别引入多指令

考虑移位和测试指令两种情况
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-12 11:02:50 | 显示全部楼层
刚查了
shl能检测两个位
shl eax, 1
此时CF, OF标志组合代表了前两位的位情况
CF = 0 OF = 0  表00
CF = 0 OF = 1 表01
CF= 1  OF =  0 表11
CF = 1 OF = 1 表10
看能利用么
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-12 11:14:06 | 显示全部楼层
版本find_by_yaos_7

void find_by_yaos_7(DWORD a, DWORD index[33])
{
  __asm
  {
  mov eax, dword ptr [a]
  mov edi, dword ptr [index]
  mov ecx, 31
loop1:
  shl eax, 1
  jc  loop3
  js loop2
// CF = 0; SF = 0; 00
  shl eax, 1
  sub ecx, 2
  jnc loop1
  jmp exit1
loop2:
//CF = 0; SF = 1; 01
  sub ecx, 1
  mov [edi], ecx
  add edi, 4
  shl eax, 1
  sub ecx, 1
  jnc loop1
  jmp exit1
loop3:
//CF = 1; SF = 0; 10
  js  loop4
  mov [edi], ecx
  add edi, 4
  shl eax, 1
  sub ecx, 2
  jnc loop1
  jmp exit1
loop4:
  //CF = 1; SF = 1;  11
  mov [edi], ecx
  sub ecx, 1
  mov [edi+4], ecx
  add edi, 8
  shl eax, 1
  sub ecx, 1
  jnc loop1
  jmp exit1
exit1:
  mov [edi], -1
  }
}

仅在bit=1很少时弱于版本find_by_yaos_4
比其他版本均优化
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-12 11:22:20 | 显示全部楼层
可能弄复杂了
检测SF就可以
CF:SF就是位组合的前两位
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-15 20:43:04 | 显示全部楼层
今天想到一个更好的写法
星期一去测试
先写下来
cmovc是如果CF=1则mov

DWORD find_by_yaos_8(DWORD a, DWORD index[33])
{
  __asm
  {
  mov edx, dword ptr [a]
  mov ebx, dword ptr [index]
  xor eax, eax
  mov ecx, 31
loop1:
  shl edx, 1
  cmovc dword ptr [ebx + 4 * eax],  ecx
  adc eax, 0
  sub ecx, 1
  jnc loop1
  mov dword ptr [ebx + 4 * eax], -1
  }
}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-15 21:13:51 | 显示全部楼层
现代编译器中的CMOV指令
指令在逆向常见的由编译器生成的程序时基本上见不到,这可能是因为在早期的IA-32处理器中没有CMOV指令,而最早提供CMOV指令的是 Pentium Pro处理器。因此,大多数编译器为了避免卷入向后兼容性的问题中,都不愿意使用CMOV指令。有意思的是,即使这些编译器被专门设置成是为更晚推出的处理器生成代码,编译器仍然不喜欢使用CMOV指令。实际使用CMOV指令的C/C++编译器只有两个——Intel公司的C++编译器和GCC编译器(GNU的C编译器)。当前最新版本的Microsoft C/C++ Optimizing编译器(版本为13.10.3077)即使在目标处理器已经显式定义为新一代的处理器的情况下,也不会使用CMOV指令。


关于条件传送指令(CMOVcc)CMOV,我以前也考虑过。
但查了一下指令周期表,在P4上几乎是3倍于MOV指令,所以是否划算,还得对比测试后才知道。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-15 21:46:17 | 显示全部楼层
关键是那几个指令几乎不相关
所以先CMOVC是否能保证在循环结束能执行完, 可以考虑
整个循环比前面算法消掉一个跳转
而且循环段指令几乎是完全不同类型的指令,并行度很高, 关联度也不高
在我改进的一系列算法里只有这个是单跳转的
其他少的2个多的7-8个
一切等测试再说 :)
希望能获得优势
===============================
这么多测试和函数不同的写法
发现了一个问题, 跳转不可怕
指令慢, 长度长, 指令阻塞才是阻碍速度根源
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-15 21:53:42 | 显示全部楼层
http://www.intel.com/cd/ids/deve ... /204504.htm?page=13

《移植到 64 位平台》第 3 部分:移植您的应用
频繁的分支误预测
提高分支的可预测性能够对代码的性能产生显著的影响。分支误预测对性能的影响在基于英特尔® 64 位扩展技术的处理器上运行的 32位与 64位版应用之间变化不大。但是比较一下基于英特尔® 64 位扩展技术的处理器上运行的 32 位版应用与英特尔® 安腾® 处理器上运行的 64 位应用,就会看到两者之间存在着很大的差距(英特尔® 安腾® 架构很少放过分支误预测)。

建议:


使用英特尔® 编译器,通过 Profile Guided Basic-block Optimization 选项(/Qprof 选项)减少分支。
考虑使用英特尔编译器选项 /Qxi,以 cmov 和 fcmov 指令替换分支指令。
设计您的代码,提高分支的可预测性。
确保每一个 CALL 函数都有与之匹配的返回值。
避免数据与指令混合。
打开非常短的循环。
当分支基于随机预测的数据时,考虑对代码进行修改,使用条件 MOV 指令或者 SIMD 流指令扩展指令集(SSE)或 MMX™ 技术指令,以避免分支。例如,修改下面的代码:
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-15 21:55:57 | 显示全部楼层
我想入手64位CPU书
好几本选择的
  64位微处理器应用编程
  64位微处理器及其编程
  64位微处理器系统编程
都不太满意
也不知道安腾的东西到底值得学否
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-16 09:29:27 | 显示全部楼层
使用CMOV在这里应该有明显的好处,毕竟分支预测错误的代价是很高的。3 倍MOV指令周期同分支预测失败代价相比太小了。
通过条件指令代替跳转语句这种优化技术叫If conversion,在安腾的编译器里面属于非常重要的优化技术。
如果仅仅为了学习计算机体系结构,看看安腾还是挺有用的,里面使用了很多非常创新的东西。不过这个架构
在实际应用中基本上不会被采用了,所以实际应用意义不大。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 22:42 , Processed in 0.055326 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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