c - 如何设置重复数据，使大部分可以优化掉？

Question

我需要对 32 kbit 宽的数据执行按位与运算。这些值之一是固定位掩码。

我一次执行这个 AND 32 位。简化后，我的算法将如下所示:

_{(我正在从这个示例中删除内存管理、变量范围问题等)}

#include <stdint.h>

const uint32_t mask[1024] = {
            0b00110110100101100111001011000111,
            0b10001110100101111010010100100100,
            0b11101010010000110001101010010101,
            0b10001110100101111010010100100100,
            (...) // 1019 more lines!
            0b00110110100101100111001011000111};

uint32_t answer[1024] = {0};
uint32_t workingdata = 0;
uint16_t i = 0;

int main(void)
{
    for (i=0; i<1024; i++)
    {
        workingdata = getnextdatachunk();
        answer[i] = workingdata & mask[i];
    }

    do_something_with_answer();

    return 0;
}

事情是这样的:如果您查看示例位掩码，mask[1] == mask[3] 和 mask[0] == mask[1023]。

在我的实际位掩码中，大多数值都是重复的；整个 1024 值数组中只有 20 个不同的值。此外，在我的最终应用程序中，我有 16 个不同的位掩码，每个都有类似的内部重复。

我正在寻找一种好方法来避免存储和遍历这么多不必要的数据。

我考虑过的一种方法类似于查找表，其中我的数组只包含每个所需位掩码 block 的单个实例:

const uint32_t mask[20] = {
            0b00110110100101100111001011000111,
            0b10001110100101111010010100100100,
            (...) // only 17 more lines!
            0b11101010010000110001101010010101};

uint32_t answer[1024] = {0};
uint32_t workingdata = 0;
uint16_t i = 0;

int main(void)
{
    for (i=0; i<1024; i++)
    {
        workingdata = getnextdata();

        switch(i)
        {
            // the mask indexes are precalculated:

            case 0:
                answer[i] = workingdata & mask[5];
                break;
            case 1:
                answer[i] = workingdata & mask[2];
                break;
            case 2:
                answer[i] = workingdata & mask[2];
                break;
            case 3:
                answer[i] = workingdata & mask[0];
                break;
            case (...): // 1020 more cases!
                (...);
                break;
            default:
        }
    }

    do_something_with_answer();

    return 0;
}

或者，使用更紧凑的 switch 语句:

switch(i)
{
    // the mask indexes are precalculated:

    case 0,3,4,5,18,35,67,(...),1019:
        answer[i] = workingdata & mask[0];
        break;
    case 1,15,16,55,89,91,(...),1004:
        answer[i] = workingdata & mask[1];
        break;
    case (...): // Only 18 more cases!
        (...);
        break;
    default:
}

这两种解决方案都让人不清楚发生了什么，我真的很想避免这种情况。

理想情况下，我希望保留原始结构并让 gcc 的优化器删除所有不必要的数据。 如何保持我的代码编写良好并仍然高效？

Answer 1

让我们发明一个积分系统，假设从 L1 缓存中获取数据需要 4 分，从 L2 缓存中获取数据需要 8 分，而不可预测的分支需要 12 分。请注意，选择这些点是为了粗略地表示“平均但未知的 80x86 CPU 的周期”。

具有单个 1024 条目表的原始代码每次迭代的总成本为 4 点(假设其完成的次数足以影响性能，因此假设数据的使用频率足以位于 L1 缓存中)。

使用 switch 语句，编译器将(希望 - 如果分支是性能噩梦，则一系列)将其转换为跳转表并执行类似 goto table[i]; 的操作可能算作从表中获取数据(4 分)，然后是一个不可预测的分支(12 分)；或每次迭代总共 16 个点。

请注意，对于 64 位代码，编译器生成的跳转表将包含 1024 个条目，其中每个条目均为 64 位；并且该表将是第一个选项表的两倍大(这是 1024 个条目，每个条目为 32 位)。然而，许多 CPU 中的 L1 数据缓存是 64 KiB，因此 64 KiB 的跳转表意味着进入 L1 数据缓存的任何其他内容(源数据被 AND 运算，生成的“答案”数据，CPU 堆栈中的任何内容)导致(64 字节或 8 个条目)从缓存中逐出跳转表以腾出空间。这意味着有时您会为“L1 未命中，L2 命中”付出代价。假设这种情况发生的概率为 5%，那么每次迭代的实际成本最终为“(95 * (4+12) + 5 * (8+12) )/100 = 16.2”点。

鉴于您希望第一个选项的性能更好(“每次迭代 16.2 点”明显大于“每次迭代 4 点”)，并且您希望第一个选项的可执行文件大小更好选项(即使不考虑 switch 的每个 case 的任何代码，32 KiB 表的大小是 64 KiB 表的一半)，并且假设第一个选项具有更简单(更易于维护)的代码；我看不出您想要使用第二个选项的任何原因。

为了优化这段代码，我会尝试处理更大的部分。举个简单的例子，你能不能做这样的事情:

    uint64_t mask[512] = { ....

    uint64_t workingdata;
    uint64_t temp;

    for (i=0; i<512; i++)
    {
        workingdata = getnextdatachunk() << 32 | getnextdatachunk();
        temp = workingdata & mask[i];
        answer[i*2] = temp;
        answer[i*2+1] = temp >> 32;
    }

如果您可以做这样的事情，那么它可能(充其量)将性能提高一倍；但是，如果您可以“每次迭代 64 位，迭代次数减半”，您也可以使用 SIMD 内在函数来执行“每次迭代 128 位，迭代次数的四分之一”或“每次迭代 256 位，迭代次数的八分之一”迭代”，并可能使它快将近 8 倍。

当然，除此之外的步骤是缓冲足够多的源数据，以提高使用多线程(多 CPU)的效率(例如，同步成本可以有效分摊)。 4 个 CPU 并行处理每个迭代 256 位，您将获得(理论上最好的情况)加速“比原始 1024 次迭代快 32 倍，单 CPU 版本每次迭代 32 位”。