当用文字替换变量用法时，程序速度减慢了很多，为什么

Question

我试图优化我的解决方案以应对这一挑战。在注意到其他解决方案之一使用了一个很好的技巧——将size更改为编译时模板参数之后，我想检查一下它如何加快代码的速度。

我是从MSVC2013用Release配置编译的。这是原始代码：

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
using std::cout;
using std::endl;
typedef std::vector<char*> Board;
int size;
void rotate(char *str){
    char temp = str[0];
    str[0] = str[1];
    str[1] = str[2];
    str[2] = str[3];
    str[3] = temp;
}
inline char fastToLower(char c){    //actually it's toUpper but whatever
    return (c - 65) % 32;
}
bool checkLeftEdge(Board::iterator begin, Board::iterator right){
    if ((right - begin) % size == 0)
        return true;
    auto left = right - 1;
    char c1 = (*right)[3], c2 = (*left)[1];
    return fastToLower(c1) == fastToLower(c2) && c1 != c2;
}
bool checkTopEdge(Board::iterator begin, Board::iterator bottom){
    auto top = bottom - size;
    if (top < begin)
        return true;
    char c1 = (*bottom)[0], c2 = (*top)[2];
    return fastToLower(c1) == fastToLower(c2) && c1 != c2;
}
bool isLastElementValid(Board::iterator begin, Board::iterator last){
    return
        checkTopEdge(begin, last) &&
        checkLeftEdge(begin, last);
}
bool recurse(Board::iterator begin, Board::iterator end, Board::iterator len){
    if (len == end)
        return true;
    for (auto it = len; it != end; ++it){
        std::swap(*len, *it);
        for (int j = 0; j < 4; ++j){
            if (isLastElementValid(begin, len)){
                bool ret = recurse(begin, end, len + 1);
                if (ret == true)
                    return ret;
            }
            rotate(*len);
        }
        std::swap(*len, *it);
    }
    return false;
}
void draw(const Board &board){
    for (int y = 0; y < size; ++y){
        cout << std::string(size * 4 + 1, '-') << endl;
        for (int x = 0; x < size; ++x)
            cout << "| " << board[to_index(x, y)][0] << " ";
        cout << "|" << endl;
        for (int x = 0; x < size; ++x)
            cout << "|" << board[to_index(x, y)][3] << " " << board[to_index(x, y)][1];
        cout << "|" << endl;
        for (int x = 0; x < size; ++x)
            cout << "| " << board[to_index(x, y)][2] << " ";
        cout << "|" << endl;
    }
    cout << std::string(size * 4 + 1, '-') << endl;
    cout << endl;
}
int main(){
    std::ifstream in ("in.txt");
    if (!in)
        return 1;
    in >> size;
    Board board(size * size);
    for (auto& ptr : board){
        ptr = new char[4];
        in.ignore();
        in.read(ptr, 4);
    }   
    auto success = recurse(board.begin(), board.end(), board.begin());
    if (success)
        draw(board);
    for (auto& ptr : board)
        delete []ptr;
    std::cin.ignore();
    std::cin.get();
}

使用这组样本数据：

5
ckck
yYcc
YcCK
kKCM
CMKc
cKYC
kYcm
KYyY
Mccm
yKcm
mykK
MMCm
ckYC
ycmm
MmKM
kymc
KMMK
KcyM
kYck
YCKM
myYm
kYyY
CMKM
yYCM
YKyk

该程序运行了11.5秒。

当我更换时

bool checkTopEdge(Board::iterator begin, Board::iterator bottom){
    auto top = bottom - size;

带有

    auto top = bottom - 5;

这个程序运行了不到10秒。

但当我更换时：

bool checkLeftEdge(Board::iterator begin, Board::iterator right){
    if ((right - begin) % size == 0)

带有

    if ((right - begin) % 5 == 0)

时间增加到了16秒！

我看了一眼反汇编，注意到isLastElementValid函数不再内联，尽管checkLeftEdge和checkTopEdge仍然内联。

代码的修改部分似乎没有太大变化：

0138136C  mov         eax,ecx  
0138136E  sub         eax,esi  
01381370  sar         eax,2  
01381373  cdq  
01381374  idiv        eax,ebx  
01381376  test        edx,edx  
01381378  je          recurse+0E2h (013813B2h) 

具有5个文字：

00B4133D  mov         eax,ecx  
00B4133F  mov         esi,5  
00B41344  sub         eax,edx  
00B41346  sar         eax,2  
00B41349  cdq  
00B4134A  idiv        eax,esi  
00B4134C  test        edx,edx  
00B4134E  je          isLastElementValid+0CAh (0B4139Ah)  

所以我的问题是：我不明白我所做的更改是如何导致程序变慢的。即使MSVC出于任何原因决定不再内联其中一个函数，我也不敢相信这一点会导致运行时间增加50%。

Answer 1

这实际上是由linining引起的。我已经通过将__declspec(noinline)添加到isLastElementValid中进行了检查，这确实造成了50%的损失。

强制使用__forceinline内联解决了我的问题。