C++:循环优化和循环展开(循环或不循环)

Question

更新:

这个讨论比我预期的要进一步,所以当我将这个问题突然出现在脑海中的时候,我正在用我正在处理的代码更新这个.这是一个8到16行代码之间的决定,以确定谁是我的c ++课程入门的井字游戏的赢家.

注意:这是为了与课程在同一水平,

注2:标记是字符x或o或'')

这是一个优化问题.如果这是一个重复,我道歉但我找不到其他地方的答案.

基本上,它归结为以下代码是否会更好地循环:

    char CheckForWinner() {

    //returns the token of the player that satisfies one of the winning requirements
    if (Square[0][0] == Square[0][1] && Square[0][0] == Square[0][2] ) { //If all three tokens in the first row are the same
        return Square[0][0]; //Return the token
    } else if (Square[1][0] == Square[1][1] && Square[1][0] == Square[1][2] ) { //Check the next row
        return Square[1][0]; //Return the token
    } else if (Square[2][0] == Square[2][1] && Square[2][0] == Square[2][2] ) {
        return Square[2][0];
    } else if (Square[0][0] == Square[1][0] && Square[0][0] == Square[2][0] ) { //If no rows satisfy conditions, check columns
        return Square[0][0]; //Return the token
    } else if (Square[0][1] == Square[1][1] && Square[0][1] == Square[2][1] ) { 
        return Square[0][1];
    } else if (Square[0][2] == Square[1][2] && Square[0][2] == Square[2][2] ) { 
        return Square[0][2];
    } else if (Square[0][0] == Square[1][1] && Square[0][0] == Square[2][2] ) { //finally, check diagonals
        return Square[0][0];
    } else if (Square[0][2] == Square[1][1] && Square[0][2] == Square[2][0] ) {
        return Square[0][2];
    }

    return ' ';
}

这对他们只是输入100个cout线的系统或多或少有点负担吗？

我很好奇,因为它似乎像我们不仅进行100条COUT线,但我们也分配一个新的变量来存储,并强制计算机处理100个数学方程式以及输出数据.

我可以理解编译器可能提供某种程度的优化,但我有兴趣在更一般的层面上知道.首先,我使用VisualStudio 2012或MingGW(g ++)进行编译.

Answer 1

关于展开循环的所有100次迭代是否有效,没有单一的答案.

对于没有代码缓存的"较小"系统,展开所有100次迭代的机会非常好,至少在执行速度方面是这样.另一方面,足够小以至于其CPU没有高速缓存的系统通常会在其他资源中受到足够的限制,这样做是非常不可取的.

如果系统确实有一个缓存,那么展开循环的所有100次迭代往往会导致执行速度变慢的可能性非常大.循环本身的开销几乎肯定比重新获取100次基本相同的代码花费更少的时间.

在典型情况下,循环展开在循环的几次迭代展开时最有效(但通常少于100次迭代).在典型情况下,您会看到大约4到16次迭代的广泛平台被展开.

然而,正如许多人首先尝试优化的典型情况一样,我猜你真的在寻找完全错误的方向.如果你想优化那个循环,很可能(到目前为止)最大的收益来自于你在循环中做的微小改变.我愿意打赌,从展开循环中获得的任何改进都会太小而无法可靠地测量,更不用说实际注意了(即使你将迭代次数从100增加到几百万).

另一方面,如果你重写循环以消除每次迭代不必要的缓冲区刷新:

for ( int i = 1; i <= 100; i++ ) 
    cout << i << "\n";

[如果你没有意识到:std::endl在流中插入一个新行并刷新流.在大多数情况下(可能包括这个),缓冲区刷新是不必要的,可能是不可取的.去除它可以提高速度的很多由8:1的因素--improvement:1或10:1是相当常见]

有可能根本不需要太多来衡量速度的差异.有一个非常公平的机会,你可以在100次迭代中测量它,如果你尝试更多的迭代,差异很可能变得非常痛苦.

当你处理一个不受I/O限制的循环,并且没有像这样明显的大规模改进时,循环展开可能会成为一个更有吸引力的选择.在这种情况下,您首先需要注意大多数编译器可以自动循环展开,因此尝试在源代码中执行此操作不太可能有很大帮助,除非这为其他优化提供了机会(例如,如果您有循环这甚至在迭代上做了一件事而在奇数迭代上做了另一件事,展开那两个迭代可以消除条件和跳跃等等,所以手工做可以提供有意义的改进,因为编译器可能没有"注意到"奇数/甚至模式,消除条件,跳跃等

还要注意,现代CPU可以(通常会)并行执行代码,并以推测方式执行代码,这可以消除循环的大部分开销.由于循环的分支几乎总是被占用(即,除了最后一次迭代之外的所有循环),CPU的分支预测器会将其预测为已采用,因此CPU可能同时"在飞行中"有几次迭代值的指令,即使你不要展开循环.循环本身的大多数代码(例如,递增i)可以与循环中的至少一些其他代码并行执行,因此循环的开销可能非常小.

编辑2:看看手头的具体问题,我认为我的工作方式有所不同.我没有将TTT板存储为2D阵列,而是将其存储为一对位图,一个用于X,另一个用于O. 这使您可以在单个操作中测试整个获胜组合,而不是三个单独的比较.由于每行是3位,因此对于常量使用八进制可能最容易:

static const std::array<short, 8> winners = {
    /* rows */      0007, 0070, 0700, 
    /* columns */   0111, 0222, 0444, 
    /* diagonals */ 0124, 0421
};

在这种情况下,我几乎肯定会使用循环:

char CheckForWinner(short X, short O) { 
    // `winners` definition from above goes here.

    for (int i=0; i<winners.size(); i++) {
        if (X & winners[i] == winners[i])
            return 'X';
        if (O & winners[i] == winners[i])
            return 'O';
    }
    return ' ';
}

这里最大的问题是你是否真的想要单独传递X和O板,或者是否更有意义传递两个短路阵列.使用阵列的明显优势是更容易进入对方板.例如,要测试是否允许在一个板中移动,您需要检查该位是否在另一个板中设置.将电路板存储在一个阵列中,您可以通过n指示您要移动的电路板,并使用1-n另一个电路板,在那里您将检查该位是否已设置.