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

Question

我目前正在开发一个项目,我希望通过调用C来优化Python中的一些数值计算.

简而言之,我需要计算y[i] = f(x[i])一个巨大数组中每个元素的值x(通常有10^9条目或更多).这里,x[i]是一个介于-10和10之间的整数,是一个f获取x[i]并返回double的函数.我的问题是,f但需要很长时间才能以数值稳定的方式进行评估.

为了加快速度,我想将所有2*10 + 1可能的值硬编码f(x[i])到常量数组中,例如:

double table_of_values[] = {f(-10), ...., f(10)};

然后f使用"查找表"方法进行评估,如下所示:

for (i = 0; i < N; i++) {
    y[i] = table_of_values[x[i] + 11]; //instead of y[i] = f(x[i])
}

由于我不是很精通用C 编写优化代码,我想知道:

1. 具体来说 - 因为x真的很大 - 我想知道在评估循环时是否值得进行二度优化(例如通过x预先排序,或者通过找到一种处理负指数的智能方法(除了刚做[x[i] + 10 + 1])？

2. 说x[i]不是介于-10和10之间,而是介于-20和20之间.在这种情况下,我仍然可以使用相同的方法,但需要手动硬编码查找表.有没有办法在代码中动态生成查找表,以便我使用相同的方法并允许x[i]属于变量范围？

Answer 1

生成具有动态范围值的表格相当容易.

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

#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 lo,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可能/应该是inline速度的函数.请注意,一旦表计算一次,fcached(x[i])就会非常快.您提到的[由"偏差"解决]的索引偏移问题在计算时间上非常小.

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

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

访问模式x是独立的.如果x以线性方式访问(例如for (i = 0; i < 999999999; ++i) x[i]),您将获得最佳性能.如果以半随机方式访问它,它将对H/W缓存逻辑产生压力,并且能够保持所需/所需x值"缓存热"

即使是线性访问,因为它x是如此之大,当你到达终点时,第一个元素将被从H/W缓存中逐出(例如,大多数CPU缓存大约为几兆字节)

然而,如果x只在一个有限的范围具有值,改变从类型int x[...]到short x[...]或甚至char x[...]切割尺寸由2×[或4x]的一个因素.而且,这可以在性能上有可衡量的改进.

更新:我添加了一个fripper函数来显示[我知道]以x循环方式访问表和数组的最快方式.我还添加了一个typedef命名,xval_t以允许x数组占用更少的空间(即具有更好的H/W缓存性能).

更新#2:

根据你的意见......

fcached[主要]被编码以说明简单/单一访问.但是,它没有在最后的例子中使用.

内联的确切要求多年来有所不同(例如,外部内联).现在最好用:static inline.但是,如果使用c++,它可能会再次不同.有专门讨论这个问题的整个页面.原因是由于在不同.c文件中进行编译,优化开启或关闭时会发生什么.另外,请考虑使用gcc扩展名.所以,要一直强制内联:

__attribute__((__always_inline__)) static inline

fripper是最快的,因为它避免了重写全局变量table_of_values和table_bias每次循环迭代.在fripper中,编译器优化器将确保它们保留在寄存器中.请参阅我的回答:是否更快地访问静态或动态分配的内存？至于为什么.

但是,我编写了一个fripper使用的变体,fcached并且反汇编的代码是相同的[并且是最优的 ].所以,我们可以忽视......或者,我们可以吗？有时,反汇编代码是一个很好的交叉检查,也是唯一可以确定的方法.创建完全优化的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 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
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,10);
    x = malloc(sizeof(xval_t) * XLEN);
    dummyptr = malloc(sizeof(double) * XLEN);
    fripper(x);
    fripper_fcached(x);

    return 0;
}