C:更快地访问查找表？

Question

我有一段代码,一次跟踪4个正弦值.

我的原始代码是每帧大约12000个sin()函数调用,运行速度为30 fps.

我尝试通过生成查找表来优化它.我最终得到了16个不同的查找表.我声明并将它们加载到程序顶部的单独头文件中.每个表都声明如下:

static const float d4_lookup[800] {...};

现在,使用这种新方法我实际上丢失了fps？!我现在以20 fps而不是30运行.每帧现在只需要执行8次sin/cos调用和19200次查询调用与12000次sin()调用.我使用带有-O3标志的gcc编译.目前,查找表包含在顶部,是程序全局范围的一部分.

我假设我没有将它们加载到正确的内存或其他类似的东西.如何加快查找时间？

**编辑1**

根据要求,这是使用查找调用的函数,每帧调用一次:

void
update_sines(void)
{
    static float c1_sin, c1_cos;
    static float c2_sin, c2_cos;
    static float c3_sin, c3_cos;
    static float c4_sin, c4_cos;

    clock_gettime(CLOCK_MONOTONIC, &spec);
    s = spec.tv_sec;
    ms = spec.tv_nsec * 0.0000001;
    etime = concatenate((long)s, ms);

    c1_sin = sinf(etime * 0.00525);
    c1_cos = cosf(etime * 0.00525);
    c2_sin = sinf(etime * 0.007326);
    c2_cos = cosf(etime * 0.007326);
    c3_sin = sinf(etime * 0.0046);
    c3_cos = cosf(etime * 0.0046);
    c4_sin = sinf(etime * 0.007992);
    c4_cos = cosf(etime * 0.007992);

    int k;
    for (k = 0; k < 800; ++k)
    {       
        sine1[k] = a1_lookup[k] * ((bx1_sin_lookup[k] * c1_cos) + (c1_sin * bx1_cos_lookup[k])) + d1_lookup[k];
        sine2[k] = a2_lookup[k] * ((bx2_sin_lookup[k] * c2_cos) + (c2_sin * bx2_cos_lookup[k])) + d2_lookup[k] + 50;
        sine3[k] = a3_lookup[k] * ((bx3_sin_lookup[k] * c3_cos) + (c3_sin * bx3_cos_lookup[k])) + d3_lookup[k];
        sine4[k] = a4_lookup[k] * ((bx4_sin_lookup[k] * c4_cos) + (c4_sin * bx4_cos_lookup[k])) + d4_lookup[k] + 50;
    }

}

**更新**

对于读这个帖子的人,我放弃了这个问题.我尝试使用OpenCL内核,结构,SIMD指令以及此处显示的所有解决方案.最后,每帧计算sinf()12800的原始代码比查找表工作得更快,因为查找表不适合缓存.然而它仍然只做30 fps.它只是为了跟上我的60fps期望而进行了太多的努力.我决定采取不同的方向.感谢所有为此主题做出贡献的人.大多数这些解决方案可能会有一些不错的速度改进,但没有像我需要的200%加速,以使查找表按我想要的方式工作.

Answer 1

有时很难知道什么会减慢你的速度,但是你可能会破坏你的缓存命中,你可以尝试查找结构

typedef struct 
{
  float bx1_sin;
  float bx2_sin;
  float bx3_sin;
  float bx4_sin;
  float bx1_cos;
 etc etc
 including  sine1,2,3,4 as well

} lookup_table

然后

lookup_table  lookup[800]

现在,第k次查找的所有内容都将位于同一小块内存中.

另外,如果你使用一个以k作为参数来做的宏来做循环的内容,那就说SINE_CALC(k)或内联函数......

你可以做

for (k = 0; k < 800; ++k)
{
  SINE_CALC(k); k++;
  SINE_CALC(k); k++;
  SINE_CALC(k); k++;
  SINE_CALC(k); k++;
  SINE_CALC(k); k++;
}

如果你做一个宏,请确保k ++在宏调用之外,如图所示

Answer 2

尝试展开你的循环,如下所示:

for (k = 0; k < 800; ++k)
{       
    sine1[k] = a1_lookup[k];
    sine2[k] = a2_lookup[k];
    sine3[k] = a3_lookup[k];
    sine4[k] = a4_lookup[k];
}
for (k = 0; k < 800; ++k)
{       
    sine1[k] *= ((bx1_sin_lookup[k] * c1_cos) + (c1_sin * bx1_cos_lookup[k]));
    sine2[k] *= ((bx2_sin_lookup[k] * c2_cos) + (c2_sin * bx2_cos_lookup[k]));
    sine3[k] *= ((bx3_sin_lookup[k] * c3_cos) + (c3_sin * bx3_cos_lookup[k]));
    sine4[k] *= ((bx4_sin_lookup[k] * c4_cos) + (c4_sin * bx4_cos_lookup[k]));
}
for (k = 0; k < 800; ++k)
{       
    sine1[k] += d1_lookup[k];
    sine2[k] += d2_lookup[k] + 50;
    sine3[k] += d3_lookup[k];
    sine4[k] += d4_lookup[k] + 50;
}

通过在每个循环中访问较少的查找表,您应该能够保留在缓存中.中间循环也可以拆分,但是您需要为其中一个子表达式创建一个中间表.