函数的优化

求一个函数的优化
发在这个区说明算法层面上的优化我已经想不出来了，只能追求常数上的优化了。瓶颈就一个函数，我想问一下能有什么优化。
先给代码：

typedef unsigned long long uint64;
uint64 dp[33][19];
int n;
uint64 StateToIndex(uint64 state, int blackpos)
{
uint64 result = 0;
int prev = 1;
for(int i=n-1;i>=0;i--)
switch((state >> (2*i)) & 0x3)
{
case 2:
result += dp[i][prev+1] + dp[i][prev];
if(--prev < 0)
return -1; //invalid state
break;
case 1:
result += dp[i][prev];
++prev;
default:
break;
}
return result;
}

以下是几点说明。
1. 代码里n的范围大概在24~28左右，并且可以看成常数，也就是说单个进程里n的值不会改变。dp数组是运行时计算，但是和输入无关，所以也能看成常数。uint64类型是必须的，uint32不够大。
2. 程序逻辑保证数据都合法，prev不会越界。for loop结束以后prev保证==0。
3. 那个if期望是一般不进入if。
4. 目前dp是运行期生成，n是全局变量。dp直接写编译期常数没有问题。n写成template int也没有问题，不过我不知道n做成const对这里有没有好处。坏处目前倒有一个，编译时间会从12秒增加到若干分钟（因为组合爆炸，代码里已经有很多的template了）。
5. 试过预计算dp[i][prev+1] + dp[i][prev]，但是效果不明显。试过if(unlikely())，效果也不明显。
6. 最终平台linux 3.2 x64，gcc 4.7.2，开-O3。CPU是i7 3930K。目标是做到几倍的优化（我知道这有可能非常困难，但是做不到几倍的话我这程序就要跑一整年了）。


最后给个dp数组的计算代码：

dp[0][0] = 1;
for(int i=1;i<=32;i++)
for(int j=0;j<=16;j++)
{
if(j <= i-1)
dp[i][j] += dp[i-1][j]; // current value 0
if(j+1 <= i-1)
dp[i][j] += dp[i-1][j+1]; // current value 1
if(j > 0)
dp[i][j] += dp[i-1][j-1]; // current value 2
}

[解决办法]
提供两点拙见：
1、64位整型应直接用__int64_t类型，编译器极有可能针对64位运算作相应的优化；
2、switch语句应该放到for的外面，这样for循环的时候会少执行一些指令。
[解决办法]
仅从楼主给的信息来看，不明白楼主到底要做什么
一般说来空间可以换时间

for(int i=n-1;i>=0;i--)
        switch((state >> (2*i)) & 0x3)
        {
        case 2:
            result += dp[i][prev+1] + dp[i][prev];
            if(--prev < 0)
                return -1; //invalid state
            break;
        case 1:
            result += dp[i][prev];
            ++prev;
        default:
            break;
        }

你的目标是求result
而result和三个东西有关, state某几位，i,prev
你如果可以把这些东西做成一张表，速度应该可以提高一些
比如state的4位一起算，这样有16个状态(实际上只有4个)
i有64/4=16种状态，prev最大可能到32，也有32种状态
这样你需要一张 16*16*32 = 8K的表来算result
result += tab[i][prev][state>>i&0xf];
还有就是prev会更改，也需要一张这样的8K表
prev = prev_tab[i][prev][state>>i&0xf]

16K的表把计算化成16次查表，表需要预先计算出来

[解决办法]
这代码再优化一些是没问题，优化几倍肯定要完全改思路了
[解决办法]

引用:

结果发现主要是内存io瓶颈……那为什么性能还能随线程数线性增长呢……

此处存取的数据位置集中，非常合CPU缓存的胃口，也许其作用超过了大家的直观感觉吧。
[解决办法]
貌似没有写好。 

typedef unsigned long long uint64;
uint64 dp[33][19];
int n;
uint64 StateToIndex(uint64 state, int blackpos)
{
    uint64 result = 0;
    int prev = 1;
    for(int i=n-1;i>=0;i--)
        switch((state >> (2*i)) & 0x3)
        {
        case 2:
            result += dp[i][prev+1] + dp[i][prev];
            if(--prev < 0)
                return -1; //invalid state
            break;
        case 1:
            result += dp[i][prev];
            ++prev;
        default:
            break;
        }
    return result;
}


uint64 StateToIndex_24(uint64 state, int blackpos)
{
    uint64 result = 0;
    int prev = 1;
    static uint64 masks[3][24] = {
      {
        (uint64)0x3<<0,  (uint64)0x3<<2,  (uint64)0x3<<4,  (uint64)0x3<<6,  (uint64)0x3<<8,  (uint64)0x3<<10,(uint64)0x3<<12,
        (uint64)0x3<<14,(uint64)0x3<<16,(uint64)0x3<<18,(uint64)0x3<<20,(uint64)0x3<<22,(uint64)0x3<<24,(uint64)0x3<<26,
        (uint64)0x3<<28,(uint64)0x3<<30,(uint64)0x3<<32,(uint64)0x3<<34,(uint64)0x3<<36,(uint64)0x3<<38,(uint64)0x3<<40,
        (uint64)0x3<<42,(uint64)0x3<<44,(uint64)0x3<<46
      },
      
      {
        (uint64)0x2<<0,  (uint64)0x2<<2,  (uint64)0x2<<4,(uint64)0x2<<6,    (uint64)0x2<<8,(uint64)0x2<<10,  (uint64)0x2<<12,
        (uint64)0x2<<14,(uint64)0x2<<16,(uint64)0x2<<18,(uint64)0x2<<20,(uint64)0x2<<22,(uint64)0x2<<24,(uint64)0x2<<26,
        (uint64)0x2<<28,(uint64)0x2<<30,(uint64)0x2<<32,(uint64)0x2<<34,(uint64)0x2<<36,(uint64)0x2<<38,(uint64)0x2<<40, 
 
        (uint64)0x2<<42,(uint64)0x2<<44,(uint64)0x2<<46
      },
      
      {
        (uint64)0x1<<0,  (uint64)0x1<<2,  (uint64)0x1<<4,  (uint64)0x1<<6,  (uint64)0x1<<8,(uint64)0x1<<10,  (uint64)0x1<<12,
        (uint64)0x1<<14,(uint64)0x1<<16,(uint64)0x1<<18,(uint64)0x1<<20,(uint64)0x1<<22,(uint64)0x1<<24,(uint64)0x1<<26,
        (uint64)0x1<<28,(uint64)0x1<<30,(uint64)0x1<<32,(uint64)0x1<<34,(uint64)0x1<<36,(uint64)0x1<<38,(uint64)0x1<<40,
        (uint64)0x1<<42,(uint64)0x1<<44,(uint64)0x1<<46
      }
      
    };
    uint64 v;
#define _It_(i) \
    v = state & masks[0][i];\
    if(masks[1][i] == v)\
    {\
      result += dp[i][prev+1] + dp[i][prev];\
       if(--prev < 0)\
        return -1; \
    }\
    else if(masks[2][i] == v)\
    {\
      result += dp[i][prev];\
      ++prev;\
    }
  _It_(23);
  _It_(22);
  _It_(21);
  _It_(20);
  _It_(19);
  _It_(18);
  _It_(17);
  _It_(16);
  _It_(15);
  _It_(14);
  _It_(13);
  _It_(12);
  _It_(11);
  _It_(10);
  _It_(9);
  _It_(8);
  _It_(7);
  _It_(6);
  _It_(5);
  _It_(4);
  _It_(3);
  _It_(2);
  _It_(1);
  _It_(0);   
  return result;
}

查看更多 下一篇