低级别的C/C++性能？

Question

更新: 我刚刚成功打破了我的32行代码记录:

void test(char *file_char, unsigned int size)
{
    char* file_ = file_char;
    char* size_x = file_char+size;
    char to_find = 0;

    for(unsigned int i = 0; i < 10000; i++)
    {
        file_char = file_;

        while(*file_char++ != to_find);//skip all characters till we find a 0

        if(*file_char)//some if in order to avoid compiler removing our test code
            cout << "found";
    }
}

以上代码要求数组中至少出现一次0，否则会出现错误，但比if代码更快，而且更加紧凑。

有没有办法让上述代码更快？（使用一个字符数组并尝试查找字符出现的位置）

我写了一些代码，我真的很困惑。

初始化：

int main()
{
    FILE *file;
    file = fopen("C:\\data.txt", "rb");

    static const int size = 60000;

    char *file_char = (char*)malloc(size);

    unsigned int i = 0;
    while(i < size)
        fread(&file_char[i++], 1, 1, file);

    clock_t clock_ = clock();
    test(file_char, size);
    std::cout << ((double)clock()-clock_)/1000;
    return 0;
}

下面的代码执行需要3.5秒钟：

void test(char *file_char, unsigned int size)
{
    for(unsigned int i = 0; i < 100000; i++)
    {
        unsigned int pos = 0;
        char to_find = 0;
        while(pos < size)
            if(file_char[pos++] == to_find)
                std::cout << "found";
    }
}

但下面的代码只需要1.8秒，时间减少了一半！

void test(char *file_char, unsigned int size)
{
    for(unsigned int i = 0; i < 100000; i++)
    {
        unsigned int pos = 0;
        char to_find = 0;
        while(pos < size)
        {
            if(file_char[pos] == to_find)
                std::cout << "found";
            else if(file_char[pos+1] == to_find)
                std::cout << "found";
            else if(file_char[pos+2] == to_find)
                std::cout << "found";
            else if(file_char[pos+3] == to_find)
                std::cout << "found";
            else if(file_char[pos+4] == to_find)
                std::cout << "found";
            else if(file_char[pos+5] == to_find)
                std::cout << "found";
            else if(file_char[pos+6] == to_find)
                std::cout << "found";
            else if(file_char[pos+7] == to_find)
                std::cout << "found";
            else if(file_char[pos+8] == to_find)
                std::cout << "found";
            else if(file_char[pos+9] == to_find)
                std::cout << "found";
            else if(file_char[pos+10] == to_find)
                std::cout << "found";
            else if(file_char[pos+11] == to_find)
                std::cout << "found";
            else if(file_char[pos+12] == to_find)
                std::cout << "found";
            else if(file_char[pos+13] == to_find)
                std::cout << "found";
            else if(file_char[pos+14] == to_find)
                std::cout << "found";
            else if(file_char[pos+15] == to_find)
                std::cout << "found";
            else if(file_char[pos+16] == to_find)
                std::cout << "found";
            else if(file_char[pos+17] == to_find)
                std::cout << "found";
            else if(file_char[pos+18] == to_find)
                std::cout << "found";
            else if(file_char[pos+19] == to_find)
                std::cout << "found";
            else if(file_char[pos+20] == to_find)
                std::cout << "found";
            else if(file_char[pos+21] == to_find)
                std::cout << "found";
            else if(file_char[pos+22] == to_find)
                std::cout << "found";
            else if(file_char[pos+23] == to_find)
                std::cout << "found";
            else if(file_char[pos+24] == to_find)
                std::cout << "found";
            else if(file_char[pos+25] == to_find)
                std::cout << "found";
            else if(file_char[pos+26] == to_find)
                std::cout << "found";
            else if(file_char[pos+27] == to_find)
                std::cout << "found";
            else if(file_char[pos+28] == to_find)
                std::cout << "found";
            else if(file_char[pos+29] == to_find)
                std::cout << "found";
            else if(file_char[pos+30] == to_find)
                std::cout << "found";
            else if(file_char[pos+31] == to_find)
                std::cout << "found";

            pos+=32;
        }
    }
}

我使用的是Visual Studio 2012 x64，程序从未输出任何内容，因为没有char为0。这是如何解释的？如何在不使用32个if语句的情况下实现相同的性能？

编辑1：如果我创建64个if语句，与32个if语句版本相比，速度没有增加。

编辑2：如果我删除else并保留if语句，程序需要4秒钟才能完成。

那么，如何解释上述不合理的结果？

- Luka

---

首先，你的第二个函数不正确 - 它可能会访问数组范围外的内存。 - Code Painters

因为 +=32 的原因是什么？是的，该数组的输入大小始终为32的倍数。 - Luka

但是你意识到这两个程序并不等价吗？假设 file_char[0] == to_find，那么它将打印“found”并跳过接下来的32个。你应该用 if 替换所有的 else if。 - Jabberwocky

那么没有 else 的版本的执行时间是多少呢？我敢打赌它更接近于3.5秒而不是1.8秒。 - Jabberwocky

你是对的，这需要4秒钟。这怎么可能呢？ - Luka

Answer 1

你的循环基本上由两个比较组成：pos < size 和 file_char[pos] == to_find。通过展开循环，你可以将比较次数从2 * size减少到(size + size / 32)。

- Zebra North

---

这个有道理，请解释一下：如果我使用64个if语句，与32个if语句相比，速度没有增加。为什么？ - Luka

@Luka 你确定吗？展开到64个if应该比展开到32个if快大约1/65（1.5％）。在你的情况下，大约是0.03秒。 - Klas Lindbäck

1.5％太少了，无法可靠地测量。但现在我明白了。 - Luka

Answer 2

我认为这两个代码是不同的。

在第一个代码中，您每次都要检查“if”比较。

在第二个代码中，如果第一个条件成立，您将跳过所有后续条件！ （因为有else） 因此，您可以节省大量比较（但会缺少检查）。

为了使代码相同，您需要删除所有“else”。

- Irisciences

---

如果您在问题的代码下面阅读文本，您会发现该代码永远不会使用那个快捷方式。 - Klas Lindbäck

Answer 3

我进行了一些测试以确保结果。在Linux和Windows下使用g++时，我得到了与您在Visual Studio中得到的相同结果： 版本1（未显式展开循环） g++ -O3 7.5秒 版本2（显式展开循环） g++ -O3 2.1秒

但是，如果打开-funroll-loops选项（通常此优化默认情况下未启用，因为它可能会使运行速度变快或变慢）： 版本1（未显式展开循环） g++ -O3 -funroll-loops 2.2秒 版本2（显式展开循环） g++ -O3 -funroll-loops 2.2秒

所以这与循环展开有关。

编辑

您可以将最后一个示例更改为显式插入哨兵，例如：

int main()
{
  static const int size = 60000;

  char *file_char = (char*)malloc(size+1);  // The last element is the sentry

  // ...Fill file_char[]...

  file_char[size] = 0;  // the sentry

  // ...
}

因此，test函数不会失败（当然你必须检查你是否找到了哨兵或“好”的零值，但这只是一个if语句）。

第三版（哨兵）

g++ -O3 0.68秒

g++ -O3 -funroll-loops 0.72秒

- manlio

Answer 4

在您的第二个例子中，一旦找到匹配项，它就会跳过余下的比较...如果您可以保证每32个索引只有一个to_find，则该方法可行...但您也可以重新编写代码（可能会出现1个错误）：

void test(char *file_char, unsigned int size)
{
    for(unsigned int i = 0; i < 100000; i++)
    {
        unsigned int pos = 0;
        char to_find = 0;
        int skip = 32;
        while(pos < size)
        {
            if(file_char[pos++] == to_find)
            {
                std::cout << "found";
                pos+=skip;
            }
            skip--;
            if (!skip)
            {skip = 32;}
        }
    }
}

- Grady Player

Answer 5

这是一种优化技术，通常由某些优化编译器应用，称为循环展开优化。在第一段代码中，for循环必须运行10,000次迭代，而在第二段代码中，迭代次数减少到floor(10,000/32)。在许多迭代过程中，for循环的结尾被编译成一个跳转指令到循环的开始处（无条件跳转在机器代码中相当昂贵，因为它可能导致CPU中的指令缓冲区刷新），因此循环测试和循环计数器更新指令执行的频率要低得多。在相当数量的迭代中，这代表了执行时间的显着改进。此外，尽管循环内else测试的数量大大增加，但它们将编译成类似于以下内容的跳转表：

if( condition1 ) goto found

if( condition2 ) goto found

...

发现：

它可以提供显著更好的性能。

- jester