C：如何更快地访问查找表？

Question

我有一段代码，每次追踪4条正弦曲线。

我的原始代码在每帧大约调用了12000个sin()函数，并以30fps的速度运行。

我尝试通过生成查找表进行优化。最终我得到了16个不同的查找表。我在程序顶部声明并加载它们，存放在一个单独的头文件中。每个表的声明方式如下：

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

现在，使用这种新的方法我实际上失去了fps吗？现在我的帧率只有20而不是30.每个帧现在只需要进行8次sin / cos调用和19200次查找调用，而不是12000次sin()调用。

我使用gcc编译，并带有-O3标志。目前，查找表被包含在顶部，并且是程序的全局范围的一部分。

我认为我没有以正确的内存方式加载它们或类似的原因。如何加快查找时间？

**编辑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指令以及所有在这里展示的解决方案。最终，计算每帧12800个sinf()函数原始代码比查找表更快，因为查找表无法适应缓存。但它仍然只能达到30fps。它有太多要做的事情，无法满足我想要的60fps期望。我决定采取不同的方向。感谢每个为此帖子做出贡献的人。大多数这些解决方案可能会有一些像我想要的200%速度提升，但是没有什么可以让查找表像我想要的那样工作。

- ReX357

---

为什么你有19200个查找调用而不是12000个sin()调用？ - rohit89

你如何访问查找表，以及如何计算索引？ - Martin Perry

如果你希望我们找出你的错误，那就展示你的代码。 - Barmar

@MartinPerry 只需在需要该值的地方调用表格，如 a1_lookup[i]。 - ReX357

你的查找范围为0..799，这是为什么？对于一个3.14周期函数来说，这似乎很奇怪。如果精度可以接受，也许可以制作157或314大小的查找表？此外，为什么不为sine本身和仅为sine创建单个查找函数？减少内存吞吐量（不加载所有16个查找表...）。还要记住，sin a = cos (a-PI/2)。它是周期性的，因此一个单独的查找表和参数修改就足够了。 - Dariusz

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++在宏调用之外，就像所示的那样。

- Keith Nicholas

---

这是一个有趣的概念。所以我基本上会创建这个结构体，并在其中放置一个函数，该函数将返回每个表的第k个位置作为16值数组？但是，查找调用最终仍然只是在程序的不同部分进行，对吗？很抱歉，我不太熟悉C语言在低级别上管理内存的方式，对我来说它看起来只是多了一个调用和一个额外的数组保存在内存中。 - ReX357

我认为你应该去维基百科上查看关于L1和L2缓存的页面，并在谷歌上搜索它们。你会发现很多大学讲义介绍内存缓存层次结构的工作原理。 - Barmar

@Barmar 栈、堆和数据段的访问速度都相同吗？ - ReX357

很难预测实际会发生什么。根据我的经验，展开循环（消除分支）通常可以获得最大的收益。 - Keith Nicholas

此外，结构体应包含结果（正弦值）、a、bx_sin、bx_cos 和 d，共 4 个单独的表格。使用两个嵌套循环，其中 1-4（或 0-3）循环在外层，0-799 循环在内层。 - Jim Balter

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;
}

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

- Barmar

---

不幸的是，我从中没有得到任何改进。我想知道是否可以在使用它们的for循环范围内包含所需的表，而不是一次性在顶部加载所有16个表？ - ReX357

我不认为那会有帮助。栈内存访问速度并不比静态数据更快，而且每次都需要将表复制到栈中。 - Barmar

我认为你可能需要使用一些低级诊断工具来查看代码中缓存的效果。 - Barmar

我能否为我的程序分配更多的缓存空间？ - ReX357

缓存是硬件，内置于CPU中。 - Barmar

Answer 3

英特尔处理器可以预测正向和反向遍历的4个数组的串行访问（并执行预取）。至少在Core 2 Duo时代是这样的。将for循环分割成：

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];
for (k = 0; k < 800; ++k)
    sine2[k] = a2_lookup[k] * ((bx2_sin_lookup[k] * c2_cos) + (c2_sin * bx2_cos_lookup[k])) + d2_lookup[k] + 50;
for (k = 0; k < 800; ++k)
    sine3[k] = a3_lookup[k] * ((bx3_sin_lookup[k] * c3_cos) + (c3_sin * bx3_cos_lookup[k])) + d3_lookup[k];
for (k = 0; k < 800; ++k)
    sine4[k] = a4_lookup[k] * ((bx4_sin_lookup[k] * c4_cos) + (c4_sin * bx4_cos_lookup[k])) + d4_lookup[k] + 50;

我猜你在其他答案中有比基准测试更多的缓存加载，所以这很重要。我建议你不要展开循环，编译器会处理得很好。

- Aleksandr Pakhomov

Answer 4

在我的Linux机器上（虚拟机，gcc，64位），使用简单的sin查找表可以提高>20%的速度。有趣的是，查找表的大小（在合理的<L1缓存大小值内）并不影响执行速度。

使用快速实现的sinsimple从这里，我获得了>45%的改进。

代码：

#include <math.h>
#include <stdio.h>
#include <stdint.h>
#include <sys/time.h>
#include <time.h>

#define LOOKUP_SIZE 628


uint64_t currentTimestampUs( void )
{
  struct timeval tv;
  time_t localTimeRet;
  uint64_t timestamp = 0;
  //time_t tzDiff = 0;
  struct tm when;
  int64_t localeOffset = 0;

  {
    localTimeRet = time(NULL);
    localtime_r ( &localTimeRet, &when );
    localeOffset = when.tm_gmtoff * 1000000ll;
  }

  gettimeofday ( &tv, NULL );
  timestamp = ((uint64_t)((tv.tv_sec) * 1000000ll) ) + ( (uint64_t)(tv.tv_usec) );
  timestamp+=localeOffset;

  return timestamp;
}


const double PI   = 3.141592653589793238462;
const double PI2  = 3.141592653589793238462 * 2;

static float sinarr[LOOKUP_SIZE];

void initSinArr() {
  int a =0;
  for (a=0; a<LOOKUP_SIZE; a++) {
    double arg = (1.0*a/LOOKUP_SIZE)*((double)PI * 0.5);
    float sinval_f = sin(arg); // double computation earlier to avoid losing precision on value
    sinarr[a] = sinval_f;
  }
}

float sinlookup(float val) {
  float normval = val;
  while (normval < 0) {
    normval += PI2;
  }
  while (normval > PI2) {
    normval -= PI2;
  }
  int index = LOOKUP_SIZE*(2*normval/PI);

  if (index > 3*LOOKUP_SIZE) {
    index = -index + 4*LOOKUP_SIZE;//LOOKUP_SIZE - (index-3*LOOKUP_SIZE);
    return -sinarr[index];
  } else if (index > 2*LOOKUP_SIZE) {
    index = index - 2*LOOKUP_SIZE;
    return -sinarr[index];
  } else if (index > LOOKUP_SIZE) {
    index = 2*LOOKUP_SIZE - index;
    return sinarr[index];
  } else {
    return sinarr[index];
  }
}


float sin_fast(float x) {
  while (x < -PI)
      x += PI2;

  while (x >  PI)
      x -= PI2;

  //compute sine
  if (x < 0)
      return 1.27323954 * x + .405284735 * x * x;
  else
      return 1.27323954 * x - 0.405284735 * x * x;

}

int main(void) {
  initSinArr();
  int a = 0;
  float val = 0;
  const int num_tries = 100000;

  uint64_t startLookup = currentTimestampUs();

  for (a=0; a<num_tries; a++) {
    for (val=0; val<PI2; val+=0.01) {
      float compval = sinlookup(val);
      (void)compval;
    }
  }

  uint64_t startSin = currentTimestampUs();

  for (a=0; a<num_tries; a++) {
    for (val=0; val<PI2; val+=0.01) {
      float compval = sin(val);
      (void)compval;
    }
  }

  uint64_t startFastSin = currentTimestampUs();

  for (a=0; a<num_tries; a++) {
    for (val=0; val<PI2; val+=0.01) {
      float compval = sin_fast(val);
      (void)compval;
    }
  }
  uint64_t end = currentTimestampUs();

  int64_t lookupMs = (startSin - startLookup)/1000;
  int64_t sinMs = (startFastSin - startSin)/1000;
  int64_t fastSinMs = (end - startFastSin)/1000;
  printf(" lookup: %lld ms\n", lookupMs );
  printf("    sin: %lld ms\n", sinMs );
  printf("   diff: %lld ms\n", sinMs-lookupMs);
  printf("  diff%: %lld %\n", 100*(sinMs-lookupMs)/sinMs);

  printf("fastsin: %lld ms\n", fastSinMs );
  printf("    sin: %lld ms\n", sinMs );
  printf("   diff: %lld ms\n", sinMs-fastSinMs);
  printf("  diff%: %lld %\n", 100*(sinMs-fastSinMs)/sinMs);
}

样例结果：

 lookup: 2276 ms
    sin: 3004 ms
   diff: 728 ms
  diff%: 24 %
fastsin: 1500 ms
    sin: 3004 ms
   diff: 1504 ms
  diff%: 50 %

- Dariusz

---

我刚试着实现了这个，但速度仍然没有提升。这种实现方式导致帧率有所下降。 - ReX357

@ReX357 查找或 fast_sin？无论哪种方式，相对于您的原始实现，它都应该更快。 - Dariusz

实现了快速正弦函数。将其放在for循环范围内。保持完全相同的帧率。 - ReX357