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

Question

我正在编写一个 raycaster，我试图通过为我最常用的三角函数(即 sin)制作查找表来加快它的速度。 , cos , 和 tan .第一个片段是我的表查找代码。为了避免每一个都做一个查找表，我只做了一个sin表，并定义 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 values 会大大加速我的代码。也许是 fmod在 lookup_sin功能？请提供您所拥有的任何见解。我正在编译 clang未启用优化，因此不会删除对每个触发函数的调用(我忽略了返回值)。

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 数学运算。
将每个预先计算的因子的弧度缩放为一个索引。
查找表中的条目数应为 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;
}

稍后我们可以使用四分之一大小的表 [0 ... pi/2] 并使用整数运算来引导选择/重建。
给定 OP's精度要求低，考虑使用 float而不是 double整个包括 float函数如 lroundf() .