0

我有一个内部带有开关的循环，看起来像这样（但要复杂得多）。

for(int i = 0; i < N; i += inc)
{
    v = 0.0;
    switch(ConstVal)
    {
    case 2: v += A[i];
    case 1: v += A[i+k];
    case 0: v += A[i+j];
    }
    // do some stuff with v
}

ConstVal 在编译时未知，但在初始化例程期间已修复。有没有办法在不编译 for 循环的多个变体的情况下删除 switch 语句？鉴于 x86 具有间接分支，应该有一种简单的方法来内联汇编以跳转到我想要的情况，而不是每次迭代都回到循环的顶部。你会怎么做（在 gcc 中）？最后，能否在不干扰编译器优化分析的情况下做到这一点。我已经在手动展开循环，但我确信还有很多我不想破坏的优化正在进行。

据我了解，Julia 元编程功能使您可以访问解析器和抽象语法树。结合 JIT，您可以解决此类问题。我认为即使没有间接分支的语义，C 中也会有一些合理的解决方法。请注意，Duff 的设备不是解决方案，因为我想在每次循环迭代时返回相同的 case 语句。这个问题经常出现。

编辑

我发现没有条件间接分支 x86 指令。此外，gcc 内联汇编只允许固定标签。然而，使用 gcc 扩展，这仍然可以完成。例如，参见https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html#Labels-as-Values。

就是这样。在我的代码中，很难确定是否存在任何性能差异，但在另一台机器上或使用更小更简单的循环时，它可能会有所不同。

void *forswitch;
switch(ConstVal)
{
case 2: forswitch = &&C; break;
case 1: forswitch = &&B; break;
case 0: forswitch = &&A; break;
}
void *_forswitch[] = {forswitch, &&END_FOR_SWITCH};


i = 0;
{
    v = 0.0;
    C: v += _A[i];
    B: v += _A[i+k];
    A: v += _A[i+j];

    // do some stuff with v

    i += inc;
    forswitch = _forswitch[i==N];
    //forswitch = (i<N)? forswitch: &&END_FOR_SWITCH;
    goto *forswitch;
}

END_FOR_SWITCH:
return;

我已经用我自己的基于 gcc 扩展的实现替换了 for 循环，它可以访问机器级间接分支。有几种方法可以做到这一点。第一个是索引一个数组，该数组根据循环索引跳转到循环的条件开始或循环结束。另一种方法（注释）是每次有条件地设置分支寄存器。编译器应使用条件移动 (CMOV) 替换任何分支。

此解决方案存在许多明显的问题。(1) 不便携。(2) 通过自己实现循环，不仅代码更难理解，而且可能会干扰编译器优化（例如自动循环展开）。(3) 即使没有中断，编译器也无法联合优化整个 switch 语句，因为它在编译时不知道哪些语句将实际执行。但是，它可能能够以类似于其他人在下面的一些回复中指出的方式巧妙地重新组织开关。通过自己手动实现开关（结合 for 循环），我使编译器更难以进行任何此类优化，因为通过删除开关语义，我的意图被优化所掩盖。

尽管如此，如果它显着提高了性能，我仍然认为这比拥有多个代码副本要好。使用宏，可以有条件地编译不可移植的扩展；这基本上可以看起来像一个正常的循环。

编辑 2

我找到了一个更好的解决方案，它更便携、更有效。当您遇到可能的运行时确定选项数量较少的情况时，您可以围绕优化函数进行包装，修复所有运行时常量，然后为每个常量副本内联函数。如果只有一个常量，您可以使用函数指针查找表，每个指针设置常量并内联函数。如果您有更复杂的情况，您将需要一些 if-elseif-else 控制结构。其中一个函数可以保留所有自由变量，因此不失一般性。我认为这是一种编译时闭包。编译器正在完成所有艰苦的工作，没有任何凌乱的宏或其他重复的代码需要维护。

在我的代码中，这导致已经显着优化的代码的性能提高了 10% 到 20%（由于对各种常量进行了硬编码，而与开关本身没有任何关系）。在我的玩具示例中，更改看起来像这样。

inline void __foo(const int ConstVal)
{
    for(int i = 0; i < N; i += inc)
    {
        v = 0.0;
        switch(ConstVal)
        {
        case 2: v += A[i];
        case 1: v += A[i+k];
        case 0: v += A[i+j];
        }
        // do some stuff with v
    }
}

void foo()
{
    // this could be done with a lookup table
    switch(ConstVal)
    {
    case2: __foo(2);  break;
    case1: __foo(1);  break;
    case0: __foo(0);  break;
    }
}

通过内联 __foo，编译器将消除开关以及您传递的任何其他常量。当然，你最终会得到更多的编译代码，但对于一个小的优化例程来说，这应该没什么大不了的。

4

3 回答 3

2

不，我看不到任何优化 switch 语句的方法。此外，它并没有那么贵。因为没有break声明，所以 switch 有“跌倒”的趋势。它转化为：

    switch(ConstVal)
    {
    case 2: v= A[i] + A[i+k] + A[i+j]; break;
    case 1: v=        A[i+k] + A[i+j]; break;
    case 0: v=                 A[i+j]; break;
    }
    // do some stuff with v

而且我看不到如何删除对ConstVal.

您可以在循环之前使用 3 个循环进行切换，每个循环对应一个，ConstVal但这肯定会看起来像丑陋的代码，具体取决于做什么do some stuff with v。

于 2016-11-04T21:58:31.920 回答
1

你什么时候知道ConstVal，它多久改变一次？如果您可以重新编译一个小例程并在更改时重新链接整个事物ConstVal，那将解决您的问题。

说了这么多，你知道这是个问题吗？这是否switch占执行时间的 10% 或更多？人们把注意力集中在非问题上是很常见的。他们知道他们应该“首先分析”，但他们实际上并没有这样做。（这是“准备射击”的情况：）

很多人依赖的一个方法就是这个。

于 2016-11-06T12:30:41.587 回答
0

有没有办法在不编译 for 循环的多个变体的情况下删除 switch 语句？

一般来说，最好是制作不同的变体或保持原样。但在这种情况下，也许我们可以发明一些技巧。这种

switch (constVal) {
case 2:
    A1 = A;
    B1 = A + k;
    C1 = A + j;
    break;
case 1:
    A1 = big_zero_array;
    B1 = A + k;
    C1 = A + j;
    break;
case 0:
    A1 = B1 = big_zero_array;
    C1 = A + j
    break;
}

for (int i = 0; i < N; i += inc) {
    v = A1[i] + B1[i] + C1[i];
    //....
}

这个东西仍然需要额外的内存，在某些情况下可能会更慢。

于 2016-11-06T12:38:46.323 回答