在某些情况下,人们在编译时知道特定的算法数据是什么样的,因此可能希望将此信息传达给编译器.这个问题是关于如何最好地实现这一点.
举例来说,考虑以下稀疏矩阵乘法的例子,其中矩阵是常数并且在编译时是已知的:
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]
在这种情况下,可以编写完全无分支的实现来实现任意输入向量的矩阵向量乘法:
#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]);
}
}
它打印矩阵向量乘法(81799, 9321, 0, 29089, 6435)的正确结果.
可以设想进一步的优化,其建立在关于参考的存储器局部性的数据特定知识上.
现在,显然这是一种可以使用的方法,但是当数据大小变大(在我的情况下大约为100MB)时它开始变得难以处理,并且在任何现实世界情况下都将依赖于元编程来生成相关联数据依赖知识.
烘焙数据特定知识的一般策略在优化方面是否具有里程数？如果是这样,这样做的最佳方法是什么？
在给出的示例中,在一个级别上,整个事情要简化为ARRAY_SIZE在运行时设置的数组的知识.这使我想到的办法是有限的(并且是一个真正的数据结构问题),但我非常有兴趣知道,如果得到的编译时的优化数据的一般的方法是在任何情况下非常有用.
小智 2
我认为这不是这个问题的一个很好的答案，但无论如何我都会尝试提供它。这也更多地是对相同基本答案的搜索。
我从事 3D VFX 工作，包括光线追踪，在这种情况下，采用在一秒钟内构建的数据结构进行相当适度的输入，然后进行大量处理，以至于用户可能需要等待数小时才能获得高质量的生产渲染，这种情况并不罕见在困难的照明情况下。
至少从理论上来说，如果我们能够进行这些“特定于数据的优化”，那么速度会快得多。变量可以变成文字常量，需要的分支明显减少，已知总是具有 45 个元素上限的数据可以分配在堆栈上而不是堆上，或者使用提前预分配的另一种形式的内存，引用的局部性可以比以往任何时候都得到更多的利用，矢量化可以更容易地应用，实现线程安全和效率可以更容易，等等。
这让我感到尴尬的是，这需要有关用户输入的信息，而这些信息只能在通常的“编译时”概念之后提供。因此，我的很多兴趣都与应用程序运行时的代码生成技术有关。
现在，显然这是一种可以使用的方法，但是当数据大小变大时（在我的例子中大约为 100MB），并且在任何现实情况下都将依赖于元编程来生成关联的数据，它开始变得笨拙。数据依赖型知识。
我认为除此之外，如果数据大小变得过大，那么我们通常需要大量的分支和变量，以避免生成太多代码，导致我们开始因 icache 未命中而成为瓶颈。
然而，即使能够将十几个经常访问的变量转换为编译时常量，并允许少数数据结构利用对指定输入的更多了解（并借助积极的优化器），也可能会产生很大的效果，特别是考虑到如何如果优化器提前提供了必要的信息，那么他们就会这样做。
其中一些问题通常可以通过日益复杂和通用的代码、元编程技术等来解决，但我们能走多远有一个峰值：优化器只能优化预先获得的信息。这里的困难在于以实用的方式提供该信息。而且，正如您已经猜到的那样，这很快就会变得笨拙、难以维护，并且生产力开始变得与效率一样重要（如果不是更重要）。
因此，对我来说最有前途的技术是针对特定问题域而不是针对特定输入而调整的代码生成技术（针对特定输入进行优化将更多地依赖于优化器，代码生成的存在使我们可以提供更多优化器所需的信息更容易/适当）。开放着色语言（Open Shading Language）就是一个已经做了类似事情的简单例子，它使用 JIT 编译，在一定程度上利用了这个想法：
OSL 使用 LLVM 编译器框架将着色器网络即时转换为机器代码（即时或“JIT”），并在此过程中大力优化着色器和网络，充分了解着色器参数和其他运行时值，而这些值是无法实现的。当着色器从源代码编译时就已经知道了。因此，我们发现我们的 OSL 着色网络的执行速度比用 C 手工制作的同等着色器快 25%！（这就是我们的旧着色器在渲染器中的工作方式。）
虽然与手写代码相比 25% 的改进是适度的，但这对于生产渲染器来说仍然是一个大问题，而且看起来我们可以远远超出这个范围。
使用节点作为可视化编程语言还提供了一个更具限制性的环境，有助于减少人为错误，允许在更高级别表达解决方案，查看动态更改的结果（即时周转）等 - 所以它不仅提高了效率，还提高了我们需要避免在此类优化中迷失的生产力。维护和构建代码生成器可能有点复杂，但它只需要所需的最少量代码，并且复杂性不会随着使用它生成的代码量而增加。
所以抱歉——这并不完全是对你问题的评论的答案，但我认为我们正在寻找类似的东西。