C：使用查找表评估有限的小整数值函数的最快方法？

这是一个简单的单表方法：

#include <malloc.h>

#define VARIABLE_USED(_sym) 
    do { 
        if (1) 
            break; 
        if (!! _sym) 
            break; 
    } while (0)

double *table_of_values;
int table_bias;

// use the smallest of these that can contain the values the x array may have
#if 0
typedef int xval_t;
#endif
#if 0
typedef short xval_t;
#endif
#if 1
typedef char xval_t;
#endif

#define XLEN        (1 << 9)
xval_t *x;

// fslow -- your original function
double
fslow(int i)
{
    return 1;  // whatever
}

// ftablegen -- generate variable table
void
ftablegen(double (*f)(int),int lo,int hi)
{
    int len;

    table_bias = -lo;

    len = hi - lo;
    len += 1;

    // NOTE: you can do free(table_of_values) when no longer needed
    table_of_values = malloc(sizeof(double) * len);

    for (int i = lo;  i <= hi;  ++i)
        table_of_values[i + table_bias] = f(i);
}

// fcached -- retrieve cached table data
double
fcached(int i)
{
    return table_of_values[i + table_bias];
}

// fripper -- access x and table arrays
void
fripper(xval_t *x)
{
    double *tptr;
    int bias;
    double val;

    // ensure these go into registers to prevent needless extra memory fetches
    tptr = table_of_values;
    bias = table_bias;

    for (int i = 0;  i < XLEN;  ++i) {
        val = tptr[x[i] + bias];

        // do stuff with val
        VARIABLE_USED(val);
    }
}

int
main(void)
{

    ftablegen(fslow,-10,10);
    x = malloc(sizeof(xval_t) * XLEN);
    fripper(x);

    return 0;
}

这是一种稍微复杂的方式,允许生成许多类似的表：

#include <malloc.h>

#define VARIABLE_USED(_sym) 
    do { 
        if (1) 
            break; 
        if (!! _sym) 
            break; 
    } while (0)

// use the smallest of these that can contain the values the x array may have
#if 0
typedef int xval_t;
#endif
#if 1
typedef short xval_t;
#endif
#if 0
typedef char xval_t;
#endif

#define XLEN        (1 << 9)
xval_t *x;

struct table {
    int tbl_lo;                         // lowest index
    int tbl_hi;                         // highest index
    int tbl_bias;                       // bias for index
    double *tbl_data;                   // cached data
};

struct table ftable1;
struct table ftable2;

double
fslow(int i)
{
    return 1;  // whatever
}

double
f2(int i)
{
    return 2;  // whatever
}

// ftablegen -- generate variable table
void
ftablegen(double (*f)(int),int hi,struct table *tbl)
{
    int len;

    tbl->tbl_bias = -lo;

    len = hi - lo;
    len += 1;

    // NOTE: you can do free tbl_data when no longer needed
    tbl->tbl_data = malloc(sizeof(double) * len);

    for (int i = lo;  i <= hi;  ++i)
        tbl->tbl_data[i + tbl->tbl_bias] = fslow(i);
}

// fcached -- retrieve cached table data
double
fcached(struct table *tbl,int i)
{
    return tbl->tbl_data[i + tbl->tbl_bias];
}

// fripper -- access x and table arrays
void
fripper(xval_t *x,struct table *tbl)
{
    double *tptr;
    int bias;
    double val;

    // ensure these go into registers to prevent needless extra memory fetches
    tptr = tbl->tbl_data;
    bias = tbl->tbl_bias;

    for (int i = 0;  i < XLEN;  ++i) {
        val = tptr[x[i] + bias];

        // do stuff with val
        VARIABLE_USED(val);
    }
}

int
main(void)
{

    x = malloc(sizeof(xval_t) * XLEN);

    // NOTE: we could use 'char' for xval_t ...
    ftablegen(fslow,-37,62,&ftable1);
    fripper(x,&ftable1);

    // ... but,this forces us to use a 'short' for xval_t
    ftablegen(f2,-99,307,&ftable2);

    return 0;
}

笔记：

fcached可以/应该是速度的内联函数.请注意,一旦表计算一次,fcached(x [i])就会非常快.您提到的[由“偏差”解决]的索引偏移问题在计算时间上非常小.

虽然x可能是一个大数组,但f()值的缓存数组相当小(例如-10到10).即使它是(例如)-100到100,这仍然是大约200个元素.这个小的缓存数组[可能]会留在硬件内存缓存中,因此访问速度会非常快.

因此,排序x以优化查找表的H / W高速缓存性能将几乎没有[可测量的]效果.

x的访问模式是独立的.如果以线性方式访问x,则会获得最佳性能(例如,对于(i = 0; i <999999999; i)x [i]).如果以半随机方式访问它,它将对H / W缓存逻辑造成压力,并且能够保持所需/所需x值“缓存热” 即使使用线性访问,由于x非常大,到达最后时,第一个元素将从H / W缓存中逐出(例如,大多数CPU缓存大约为几兆字节) 但是,如果x只有有限范围内的值,则将类型从int x […]更改为short x […]或甚至char x […]将大小减小2倍[或者4倍.而且,这可以在性能上有可衡量的改进. 更新：我添加了一个fripper函数来显示[我知道]以最快的方式访问循环中的表和x数组.我还添加了一个名为xval_t的typedef,以允许x数组占用更少的空间(即具有更好的H / W缓存性能). 更新#2： 根据你的意见…… fcached [主要]被编码以说明简单/单一访问.但是,它没有在最后的例子中使用. 内联的确切要求多年来有所不同(例如,外部内联).现在最好用：静态内联.但是,如果使用c,它可能会再次不同.有专门讨论这个问题的整个页面.原因是因为在不同的.c文件中进行编译,当打开或关闭优化时会发生什么.另外,请考虑使用gcc扩展名.所以,要一直强制内联：

__attribute__((__always_inline__)) static inline

fripper是最快的,因为它避免了在每次循环迭代时重写全局table_of_values和table_bias.在fripper中,编译器优化器将确保它们保留在寄存器中.看到我的回答：Is accessing statically or dynamically allocated memory faster?为什么.

但是,我编写了一个使用fcached的fripper变体,并且反汇编的代码是相同的[并且是最优的].所以,我们可以忽视……或者,我们可以吗？有时,反汇编代码是一个很好的交叉检查,也是唯一可以确定的方法.创建完全优化的C代码时只需一个额外的项目.编译器可以为代码生成提供许多选项,因此有时它只是反复试验.

因为基准测试非常重要,所以我把我的例程用于时间戳(FYI,[AFAIK],底层的clock_gettime调用是python的time.clock())的基础.

那么,这是更新版本：

#include <malloc.h>
#include <time.h>

typedef long long s64;

#define SUPER_INLINE 
    __attribute__((__always_inline__)) static inline

#define VARIABLE_USED(_sym) 
    do { 
        if (1) 
            break; 
        if (!! _sym) 
            break; 
    } while (0)

#define TVSEC           1000000000LL    // nanoseconds in a second
#define TVSECF          1e9             // nanoseconds in a second

// tvget -- get high resolution time of day
// RETURNS: absolute nanoseconds
s64
tvget(void)
{
    struct timespec ts;
    s64 nsec;

    clock_gettime(CLOCK_REALTIME,&ts);

    nsec = ts.tv_sec;
    nsec *= TVSEC;
    nsec += ts.tv_nsec;

    return nsec;
)

// tvgetf -- get high resolution time of day
// RETURNS: fractional seconds
double
tvgetf(void)
{
    struct timespec ts;
    double sec;

    clock_gettime(CLOCK_REALTIME,&ts);

    sec = ts.tv_nsec;
    sec /= TVSECF;
    sec += ts.tv_sec;

    return sec;
)

double *table_of_values;
int table_bias;

double *dummyptr;

// use the smallest of these that can contain the values the x array may have
#if 0
typedef int xval_t;
#endif
#if 0
typedef short xval_t;
#endif
#if 1
typedef char xval_t;
#endif

#define XLEN        (1 << 9)
xval_t *x;

// fslow -- your original function
double
fslow(int i)
{
    return 1;  // whatever
}

// ftablegen -- generate variable table
void
ftablegen(double (*f)(int),int hi)
{
    int len;

    table_bias = -lo;

    len = hi - lo;
    len += 1;

    // NOTE: you can do free(table_of_values) when no longer needed
    table_of_values = malloc(sizeof(double) * len);

    for (int i = lo;  i <= hi;  ++i)
        table_of_values[i + table_bias] = f(i);
}

// fcached -- retrieve cached table data
SUPER_INLINE double
fcached(int i)
{
    return table_of_values[i + table_bias];
}

// fripper_fcached -- access x and table arrays
void
fripper_fcached(xval_t *x)
{
    double val;
    double *dptr;

    dptr = dummyptr;

    for (int i = 0;  i < XLEN;  ++i) {
        val = fcached(x[i]);

        // do stuff with val
        dptr[i] = val;
    }
}

// fripper -- access x and table arrays
void
fripper(xval_t *x)
{
    double *tptr;
    int bias;
    double val;
    double *dptr;

    // ensure these go into registers to prevent needless extra memory fetches
    tptr = table_of_values;
    bias = table_bias;
    dptr = dummyptr;

    for (int i = 0;  i < XLEN;  ++i) {
        val = tptr[x[i] + bias];

        // do stuff with val
        dptr[i] = val;
    }
}

int
main(void)
{

    ftablegen(fslow,10);
    x = malloc(sizeof(xval_t) * XLEN);
    dummyptr = malloc(sizeof(double) * XLEN);
    fripper(x);
    fripper_fcached(x);

    return 0;
}