为什么多个 if 语句比执行 while 循环更快？

Question

我的程序输入的是一个大字符串，大约有 30,000 个字符。下面是我自己的 strlen 的代码：

size_t  strlen(const char *c)
{
    int i;

    i = 0;
    while (c[i] != '[=10=]')
        i++;
    return (i);
}

上面的 strlen 版本执行需要大约 2.1 秒。通过不同的版本，我能够达到 ~1.4 秒。

我的问题是，为什么多个 if 语句比执行 while 循环更快？

size_t  strlen(const char *str)
{
    const char  *start;

    start = str;
    while (1)
    {
        if (str[0] == '[=11=]')
            return (str - start);
        if (str[1] == '[=11=]')
            return (str - start + 1);
        if (str[2] == '[=11=]')
            return (str - start + 2);
        if (str[3] == '[=11=]')
            return (str - start + 3);
        if (str[4] == '[=11=]')
            return (str - start + 4);
        if (str[5] == '[=11=]')
            return (str - start + 5);
        if (str[6] == '[=11=]')
            return (str - start + 6);
        if (str[7] == '[=11=]')
            return (str - start + 7);
        if (str[8] == '[=11=]')
            return (str - start + 8);
        str += 9; // 
    }
}

我的问题是，为什么很多 if 语句比运行循环更快？

编辑：使用标准库，大约需要 1.25 秒。

Answer 1

您的问题很中肯，但您的基准测试不完整并且结果令人惊讶。

这是您的代码的修改和检测版本：

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <fcntl.h>
#include <unistd.h>

#define VERSION     3
#define TRIALS      100
#define ITERATIONS  100

#if VERSION == 1

size_t strlen1(const char *c) {
    size_t i;

    i = 0;
    while (c[i] != '[=10=]')
        i++;
    return (i);
}
#define strlen(s)  strlen1(s)

#elif VERSION == 2

size_t strlen2(const char *str) {
    const char  *start;

    start = str;
    while (1) {
        if (str[0] == '[=10=]')
            return (str - start);
        if (str[1] == '[=10=]')
            return (str - start + 1);
        if (str[2] == '[=10=]')
            return (str - start + 2);
        if (str[3] == '[=10=]')
            return (str - start + 3);
        if (str[4] == '[=10=]')
            return (str - start + 4);
        if (str[5] == '[=10=]')
            return (str - start + 5);
        if (str[6] == '[=10=]')
            return (str - start + 6);
        if (str[7] == '[=10=]')
            return (str - start + 7);
        if (str[8] == '[=10=]')
            return (str - start + 8);
        str += 9;
    }
}
#define strlen(s)  strlen2(s)

#elif VERSION == 3

size_t strlen3(const char *str) {
    const uint64_t *px, sub = 0x0101010101010101, mask = 0x8080808080808080;
    const char *p;

    for (p = str; (uintptr_t)p & 7; p++) {
        if (!*p)
            return p - str;
    }
    for (px = (const uint64_t *)(uintptr_t)p;;) {
        uint64_t x = *px++;
        if (((x - sub) & ~x) & mask)
            break;
    }
    for (p = (const char *)(px - 1); *p; p++)
        continue;
    return p - str;
}
#define strlen(s)  strlen3(s)

#endif

int get_next_line(int fd, char **pp) {
    char buf[32768];
    char *line = NULL, *new_line;
    char *p;
    ssize_t line_size = 0;
    ssize_t nread, chunk;

    while ((nread = read(fd, buf, sizeof buf)) > 0) {
        p = memchr(buf, '\n', nread);
        chunk = (p == NULL) ? nread : p - buf;
        new_line = realloc(line, line_size + chunk + 1);
        if (!new_line) {
            free(line);
            *pp = NULL;
            return 0;
        }
        line = new_line;
        memcpy(line + line_size, buf, chunk);
        line_size += chunk;
        line[line_size] = '[=10=]';
        if (p != NULL) {
            lseek(fd, chunk + 1 - nread, SEEK_CUR);
            break;
        }
    }
    *pp = line;
    return line != NULL;
}

int main() {
    char *line = NULL;
    int fd, fd2, count, trial;
    clock_t min_clock = 0;

    fd = open("one_big_fat_line.txt", O_RDONLY);
    if (fd < 0) {
        printf("cannot open one_big_fat_line.txt\n");
        return 1;
    }

    fd2 = open("output.txt", O_WRONLY | O_CREAT | O_TRUNC, S_IREAD | S_IWRITE);
    if (fd2 < 0) {
        printf("cannot open output.txt\n");
        return 1;
    }

    for (trial = 0; trial < TRIALS; trial++) {
        clock_t t = clock();
        for (count = 0; count < ITERATIONS; count++) {
            lseek(fd, 0L, SEEK_SET);
            lseek(fd2, 0L, SEEK_SET);
            while (get_next_line(fd, &line) == 1) {
                write(fd2, line, strlen(line));
                write(fd2, "\n", 1);
                free(line);
            }
        }
        t = clock() - t;
        if (min_clock == 0 || min_clock > t)
            min_clock = t;
    }
    close(fd);
    close(fd2);

    double time_taken = (double)min_clock / CLOCKS_PER_SEC;
    printf("Version %d time: %.3f microseconds\n", VERSION, time_taken * 1000000 / ITERATIONS);
    return 0;
}

该程序打开一个文件，使用使用 unix 系统调用的自定义函数 read_next_line() 和 malloc 到 return 任意大小的行从中读取行。然后它使用 unix 系统调用 write 写入这些行，并使用单独的系统调用附加一个换行符。

用你的测试文件（一个 30000 字节的文件，单行 ASCII 字符）对这个序列进行基准测试，显示出与你测量的非常不同的性能：取决于选择的 strlen 实现和编译优化设置，我的笔记本电脑上的时间范围从每次迭代 15 微秒到 82 微秒，远不及您观察到的 1 或 2 秒。

使用 C 库默认实现，无论是否进行优化，我每次迭代都得到 14.5 微秒。
使用您的 strlen1 天真的实现，我在禁用优化的情况下获得 82 微秒，在 -O3 优化的情况下获得 25 微秒。
使用您的 strlen2 展开实施，-O0 的速度提高到 30 微秒，-O3 的速度提高到 20 微秒。
最后，一次读取 8 个字节的更高级的 C 实现 strlen3 提供了进一步改进的性能，-O0 为 21 微秒，-O3 为 15.5 微秒.

请注意编译器优化对性能的影响远大于手动优化。

您的展开版本性能更好的原因是生成的代码每字节递增一次指针并且每字节执行一次无条件跳转，而展开版本将这些减少到每 9 个字节一次。但是请注意，C 编译器在 -O3 的原始代码上获得的性能几乎与您自己展开循环所获得的性能相同。

高级版本在性能上非常接近 C 库实现，它可能使用带有 SIMD 指令的汇编语言。它一次读取 8 个字节并执行算术技巧来检测这些字节中的任何一个在从其值中减去 1 时是否将其最高位从 0 更改为 1。需要额外的初始步骤来对齐指针以读取 64 位字，从而避免在某些体系结构上具有未定义行为的未对齐读取。它还假设内存保护在字节级别不可用。在现代 x86 系统上，内存保护具有 4K 或更大的粒度，但一些其他系统（例如 Windows 2.x 保护的粒度要细得多，完全阻止了这种优化。

但请注意，基准测试还测量从输入文件读取、定位换行符和写入输出文件的时间。 strlen 和 strlen3 的相对性能可能更重要。实际上，仅 strlen(line) 和 30000 字节行的单独基准显示 strlen3() 的时间为 2.2 微秒，strlen().

的时间为 0.85 微秒

结论：

基准测试是一个棘手的游戏。
编译器在被告知这样做时擅长优化，-O3 是一个很好的默认值。
重新定义库函数以尝试优化它们是徒劳且有风险的。

为什么多个 if 语句比执行 while 循环更快？

Why are multiple if statements faster than executing a while loop?

c

performance

for-loop

performance-testing