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

Question

我认为内存访问会比使用 alpha 混合完成的乘法和除法（尽管编译器优化）更快。但是并没有想象中那么快

用于 table 的 16 兆字节在这种情况下不是问题。但是，如果 table 查找甚至比执行所有 CPU 计算还慢，这就是一个问题。

任何人都可以向我解释为什么以及发生了什么事吗？ table 查找会被较慢的 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

Table查找不是万能的。当 table 足够小时它会有所帮助，但在您的情况下 table 非常大。你写

16 megabytes used for the table is not an issue in this case

我认为这是非常错误的，并且可能是您遇到问题的根源。 16 兆字节对于 L1 缓存来说太大了，因此从 table 中的随机索引读取数据将涉及较慢的缓存（L2、L3 等）。缓存未命中的代价通常很大；如果您希望 LUT 解决方案更快，您的混合算法必须非常复杂。

阅读 Wikipedia article 了解更多信息。

Answer 2

您的基准测试无可救药地被破坏了，它使 LUT 看起来比实际情况好很多，因为它按顺序读取 table。

如果您的性能结果显示 LUT 比直接计算差，那么当您从真实世界的随机访问模式和缓存未命中开始时，LUT 会更差。

专注于改进计算，并启用矢量化。它的回报可能比基于 table 的方法好得多。

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

重新排列后变为

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

简化为

destination + (source - destination) * a / COLOR_MAX

其中有一个乘法和一个除法，两者都非常有效。而且它很容易矢量化。

你也应该将你的辅助函数标记为 inline，尽管一个好的优化编译器可能无论如何都会内联它。

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

Alpha blending using table lookup is not as fast as expected

c

performance

optimization

alphablending

lookup-tables