关于一个运算优化的问题

shshsh_0510

原帖由 litaoye 于 2009-3-28 00:38 发表


是0.031，呵呵其实是大家的成绩，又优化了好几次，一直都是这个成绩，反正我到此算是才尽了
0.015就看各位了！

  快就是快，不用谦虚。

对这个我还有一点不太明白，为什么sort一下就会变快

无心人

我估计是Cache数据到二级缓存造成的

litaoye

试了一下,出了一个编译错误!

这部分也确实属于调用次数较多的,不知道会比原来的快多少,原来的方法也就是几次位运算,似乎速度也还可以。

不过咱现在对汇编是一点不懂了，不知道这两种方法转化为汇编会差多少？

原帖由 无心人 于 2009-3-28 14:02 发表
bool bitbool(UINT128 *Item,int index)
{
DWORD * cItem = (DWORD *)Item;
int bit = index >> 5;
int current = index & 0x1F;
return (*(cItem + bit) >> current) & 1;
}

这个可以改成：
_declspec(na ...

无心人

少些了一个_
是__declspec(naked)

不好意思啊

litaoye

其实相比给出程序,给我讲一下这两者转化为汇编,效率差距有多大?会更有意义!

原帖由 无心人 于 2009-3-29 08:53 发表
少些了一个_
是__declspec(naked)

不好意思啊

无心人

50%左右吧

无心人

bool bitbool(UINT128 *Item,int index)
{
DWORD * cItem = (DWORD *)Item;
int bit = index >> 5;
int current = index & 0x1F;
return (*(cItem + bit) >> current) & 1;
}

这个最优化的汇编是
假设采取__fastcall调用方式
__declspec(naked)
bool  bitbool(UINT128 *Item,int index)
{
/*
DWORD * cItem = (DWORD *)Item;
int bit = index >> 5;
int current = index & 0x1F;
return (*(cItem + bit) >> current) & 1;
*/
  __asm
  {
  mov eax, index
  mov ecx, eax
  shr eax, 5
  and ecx, 31
  mov eax, dword ptr Item[4 * eax]
  shr eax, cl
  and eax, 1
  ret
  }
}

8条
如果利用SSE2
可更短
但在某种意义上不如利用BT指令了
如果你的C/C++翻译成汇编，可能存在冗余指令
即更多指令了

另外，我那个版本
如果仅用0代表对应位是0，非零代表是1
则不需neg eax一条
即仅3条

liangbch

我的0.062秒的源代码，提交ID: 2516093， 见 http://acm.timus.ru/rating.aspx?space=1&num=1318

游客，本帖隐藏的内容需要积分高于 1000 才可浏览，您当前积分为 0

无心人

呵呵
还有可能改进么?

liangbch

用我自己的算法，性能应该到头了。使用楼主的代码，将关键部分用汇编优化，或许有提速的可能