C 三角函数查找 table 比 math.h 的函数慢？

Question

我正在写一个 raycaster，我试图通过查找 tables 来加快它的速度，这些函数是我最常调用的三角函数，即 sin、cos 和tan。第一个片段是我的 table 查找代码。为了避免为每个查找 table，我只查找一个 sin table，并将 cos(x) 定义为 sin(half_pi - x) 和 tan(x)作为 sin(x) / cos(x).

#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

const float two_pi = M_PI * 2, half_pi = M_PI / 2;

typedef struct {
    int fn_type, num_vals;
    double* vals, step;
} TrigTable;

static TrigTable sin_table;

TrigTable init_trig_table(const int fn_type, const int num_vals) {
    double (*trig_fn) (double), period;
    switch (fn_type) {
        case 0: trig_fn = sin, period = two_pi; break;
        case 1: trig_fn = cos, period = two_pi; break;
        case 2: trig_fn = tan, period = M_PI; break;
    }

    TrigTable table = {fn_type, num_vals,
        calloc(num_vals, sizeof(double)), period / num_vals};

    for (double x = 0; x < period; x += table.step)
        table.vals[(int) round(x / table.step)] = trig_fn(x);

    return table;
}

double _lookup(const TrigTable table, const double x) {
    return table.vals[(int) round(x / table.step)];
}

double lookup_sin(double x) {
    const double orig_x = x;
    if (x < 0) x = -x;
    if (x > two_pi) x = fmod(x, two_pi);

    const double result = _lookup(sin_table, x);
    return orig_x < 0 ? -result : result;
}

double lookup_cos(double x) {
    return lookup_sin(half_pi - x);
}

double lookup_tan(double x) {
    return lookup_sin(x) / lookup_cos(x);
}

以下是我如何对我的代码进行基准测试：我的当前时间（以毫秒为单位）的函数来自 here。问题出现在这里：当计时我的 lookup_sin 与 math.h 的 sin 时，我的变体需要大约三倍的时间：Table time vs default: 328 ms, 108 ms.

cos 的时间安排如下： Table time vs default: 332 ms, 109 ms

tan 的时间安排如下： Table time vs default: 715 ms, 153 ms

是什么让我的代码变慢了这么多？我认为预先计算 sin 值会大大加速我的代码。也许是 lookup_sin 函数中的 fmod ？请提供您的任何见解。我在没有启用优化的情况下使用 clang 进行编译，因此不会删除对每个触发函数的调用（我忽略了 return 值）。

const int64_t millis() {
    struct timespec now;
    timespec_get(&now, TIME_UTC);
    return ((int64_t) now.tv_sec) * 1000 + ((int64_t) now.tv_nsec) / 1000000;
}

const int64_t benchmark(double (*trig_fn) (double)) {
    const int64_t before = millis();

    for (double i = 0; i < 10000; i += 0.001)
        trig_fn(i);

    return millis() - before;
}

int main() {
    sin_table = init_trig_table(0, 15000);

    const int64_t table_time = benchmark(lookup_sin), default_time = benchmark(sin);
    printf("Table time vs default: %lld ms, %lld ms\n", table_time, default_time);

    free(sin_table.vals);
}

Answer 1

减少浮点运算。

OP 的代码在应该是缩放和查找的地方进行过多的 FP 数学运算。

将每个预先计算的因子的弧度缩放到索引中。

查找中的条目数 table 应该是 unsigned 的 2 次方，所以 mod 是一个简单的&.

首先，让我们简化并让 [0 ... 2*pi) 映射到索引 [0 ... number_of_entries) 来演示这个想法。

double lookup_sin_alt(double x) {
  long scaled_x = lround(x * scale_factor);  // This should be the _only_ line of FP code
  // All following code is integer code.
  scaled_x += number_of_entries/4 ; // If we are doing cosine
  unsigned index = scaled_x & (number_of_entries - 1);  // This & replaces fmod
  double result = table.vals[index];
  return result;
}

稍后我们可以使用四分之一大小 table [0 ... pi/2] 并使用整数操作引导 selection/reconstruction。

鉴于 OP's 低精度要求，请考虑在整个过程中使用 float 而不是 double，包括 float 函数，例如 lroundf().

C 三角函数查找 table 比 math.h 的函数慢？

C trigonometry lookup table slower than math.h's functions?

c

optimization

caching

trigonometry

lookup-tables