编译时数据特定的优化

Question

在某些情况下，人们在编译时就知道一段特定的算法数据是什么样的，因此可能希望将此信息传达给编译器。这个问题是关于如何最好地实现这一目标。

例如，考虑以下稀疏矩阵乘法示例，其中矩阵是常量并且在编译时已知:

matrix = [  0, 210,   0, 248, 137]
         [  0,   0,   0,   0, 239]
         [  0,   0,   0,   0,   0]
         [116, 112,   0,   0,   7]
         [  0,   0,   0,   0, 165]

在这种情况下，可以编写一个完全无分支的实现来实现任意输入 vector 的矩阵 vector 乘法:

#include <stdio.h>

#define ARRAY_SIZE 8
static const int matrix[ARRAY_SIZE] = {210, 248, 137, 239, 116, 112, 7, 165};
static const int input_indices[ARRAY_SIZE] = {1, 3, 4, 4, 0, 1, 4, 4};
static const int output_indices[ARRAY_SIZE] = {0, 0, 0, 1, 3, 3, 3, 4};

static void matrix_multiply(int *input_array, int *output_array)
{
    for (int i=0; i<ARRAY_SIZE; ++i){
        output_array[output_indices[i]] += (
                matrix[i] * input_array[input_indices[i]]);
    }
}

int main()
{
    int test_input[5] = {36, 220, 212, 122,  39};
    int output[5] = {0};

    matrix_multiply(test_input, output);

    for (int i=0; i<5; ++i){
        printf("%d\n", output[i]);
    }

}

打印矩阵 vector 乘法的正确结果(81799、9321、0、29089、6435)。

可以设想进一步的优化，建立在关于引用的内存位置的数据特定知识的基础上。

现在，显然这是一种可以使用的方法，但是当数据量变大时(比如我的情况下大约 100MB)，它开始变得笨拙，并且在任何现实世界的情况下都依赖于元编程来生成相关的数据依赖知识。

在数据特定知识中烘焙的一般策略在优化方面是否具有里程数？如果是这样，执行此操作的最佳方法是什么？

在给定的例子中，在一个层面上，整个事情比在运行时设置的数组减少到关于 ARRAY_SIZE 的知识。这让我认为这种方法是有限的(并且实际上是一个数据结构问题)，但我很想知道数据派生编译时优化的一般方法是否在任何情况下都有用。

Answer 1

我不认为这是对这个问题的一个很好的答案，但我还是会尝试提供它。它也更像是对相同基本答案的搜索。

我从事 3D VFX 工作，包括光线追踪，在这种情况下，使用不到一秒的数据结构进行相当适度的输入，然后进行大量处理，以至于用户可能需要等待数小时在困难的照明条件下进行高质量的制作渲染。

至少在理论上，如果我们能够进行这些“特定于数据的优化”，这可能会进行得更快。变量可以变成文字常量，可能需要明显更少的分支，已知总是有 45 个元素上限的数据可以分配在堆栈上而不是堆上，或者使用另一种预先分配的内存形式，引用的局部性可以被比以往任何时候都更广泛地利用，矢量化可以更容易地应用，同时实现线程安全和效率可能会容易得多，等等。

这让我感到尴尬的是，这需要有关用户输入的信息，这些信息只能在通常的“编译时”概念之后提供。因此，我的很多兴趣都与应用程序运行时的代码生成技术有关。

Now, clearly this is an approach which can be used, but it starts getting unwieldy when the size of the data gets big (say ~100MB in my case) and also in any real world situation would depend on meta-programming to generate the associated data dependent knowledge.

我认为除此之外，如果数据量过大，那么我们确实经常需要大量的分支和变量，只是为了避免生成过多的代码，以至于我们开始因 icache 未命中而成为瓶颈。

然而，即使能够将十几个经常访问的变量转换为编译时常量，并允许少数数据结构利用对指定输入的更多知识(并借助积极的优化器)，也可能在这里产生巨大的影响，特别是考虑到优化器在提前提供必要信息的情况下的表现如何。

其中一些问题通常可以通过越来越复杂和通用的代码、元编程技术等来解决，但我们能达到的程度有一个峰值:优化器只能优化预先可用的信息。这里的困难在于以实用的方式提供该信息。而且，正如您已经猜到的那样，这很快就会变得笨拙、难以维护，并且生产力开始变得与效率一样重要(如果不是更重要的话)。

所以对我来说最有前途的技术围绕针对特定问题域而不是针对特定输入进行调整的代码生成技术(针对特定输入的优化将更多地依赖于优化器，代码生成就在那里，因此我们可以更容易/适本地提供优化器所需的更多信息)。 Open Shading Language 是一个已经做了类似事情的简单示例，它使用 JIT 编译在适度的水平上利用了这个想法:

OSL uses the LLVM compiler framework to translate shader networks into machine code on the fly (just in time, or "JIT"), and in the process heavily optimizes shaders and networks with full knowledge of the shader parameters and other runtime values that could not have been known when the shaders were compiled from source code. As a result, we are seeing our OSL shading networks execute 25% faster than the equivalent shaders hand-crafted in C! (That's how our old shaders worked in our renderer.)

虽然比手写代码有 25% 的改进并不多，但这在生产渲染器中仍然是一个大问题，而且我们似乎可以做得更多。

使用节点作为可视化编程语言还提供了一个更严格的环境，有助于减少人为错误，允许在更高级别表达解决方案，查看动态更改的结果(即时周转)等。- - 因此它不仅提高了效率，而且提高了我们需要避免在此类优化中迷失的生产力。维护和构建代码生成器可能有点复杂，但它只需要具有所需的最少代码量，并且不会随着使用它生成的代码量的增加而增加复杂性。

很抱歉 - 这并不是作为评论对您的问题的准确回答，但我认为我们正在寻找类似的东西。