使用表查找的Alpha混合没有预期的那么快。

Question

我认为内存访问将比使用alpha混合完成的乘法和除法(尽管编译器优化)更快。但它没有预期的那么快。

在这种情况下，表中使用的16兆字节并不是问题。但是，如果表查找速度可能比执行所有CPU计算要慢的话，这将是一个问题。

有人能向我解释一下为什么和发生了什么吗？表查找会以较慢的CPU完成吗？

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

#define COLOR_MAX UCHAR_MAX

typedef unsigned char color;

color (*blending_table)[COLOR_MAX + 1][COLOR_MAX + 1];

static color blend(unsigned int destination, unsigned int source, unsigned int a) {
    return (source * a + destination * (COLOR_MAX - a)) / COLOR_MAX;
}

void initialize_blending_table(void) {
    int destination, source, a;

    blending_table = malloc((COLOR_MAX + 1) * sizeof *blending_table);
    for (destination = 0; destination <= COLOR_MAX; ++destination) {
        for (source = 0; source <= COLOR_MAX; ++source) {
            for (a = 0; a <= COLOR_MAX; ++a) {
                blending_table[destination][source][a] = blend(destination, source, a);
            }
        }
    }
}

struct timer {
    double start;
    double end;
};

void timer_start(struct timer *self) {
    self->start = clock();
}

void timer_end(struct timer *self) {
    self->end = clock();
}

double timer_measure_in_seconds(struct timer *self) {
    return (self->end - self->start) / CLOCKS_PER_SEC;
}

#define n 300

int main(void) {
    struct timer timer;
    volatile int i, j, k, l, m;

    timer_start(&timer);
    initialize_blending_table();
    timer_end(&timer);
    printf("init %f\n", timer_measure_in_seconds(&timer));

    timer_start(&timer);
    for (i = 0; i <= n; ++i) {
        for (j = 0; j <= COLOR_MAX; ++j) {
            for (k = 0; k <= COLOR_MAX; ++k) {
                for (l = 0; l <= COLOR_MAX; ++l) {
                    m = blending_table[j][k][l];
                }
            }
        }
    }
    timer_end(&timer);
    printf("table %f\n", timer_measure_in_seconds(&timer));

    timer_start(&timer);
    for (i = 0; i <= n; ++i) {
        for (j = 0; j <= COLOR_MAX; ++j) {
            for (k = 0; k <= COLOR_MAX; ++k) {
                for (l = 0; l <= COLOR_MAX; ++l) {
                    m = blend(j, k, l);
                }
            }
        }
    }
    timer_end(&timer);
    printf("function %f\n", timer_measure_in_seconds(&timer));

    return EXIT_SUCCESS;
}

结果

$ gcc test.c -O3
$ ./a.out
init 0.034328
table 14.176643
function 14.183924

Answer 1

查表不是万灵药。当桌子足够小的时候，它会有所帮助，但在你的例子中，它是非常大的。你写

在这种情况下，用于表的16兆字节不是一个问题。

我认为这是非常错误的，而且可能是你所经历的问题的根源。16兆字节对于L1缓存来说太大了，因此从表中的随机索引中读取数据将涉及较慢的缓存(L2、L3等)。缓存丢失的代价通常很大；如果希望LUT解决方案更快，则混合算法必须非常复杂。

阅读维基百科文章获得更多信息。

Answer 2

你的基准是无可救药的坏了，它使LUT看起来比实际要好得多，因为它按顺序读取表。

如果您的性能结果显示LUT比直接计算差，那么当您从实际的随机访问模式开始，缓存丢失时，LUT就会更糟。

集中精力改进计算，并启用矢量化。这可能比基于表格的方法有更好的回报。

(source * a + destination * (COLOR_MAX - a)) / COLOR_MAX

随着重排变得

(source * a + destination * COLOR_MAX - destination * a) / COLOR_MAX

它简化为

destination + (source - destination) * a / COLOR_MAX

它有一个乘和一个除以一个常数，两者都是非常有效的。而且很容易被矢量化。

您还应该将您的助手函数标记为inline，尽管一个很好的优化编译器可能会将其内联。