c - 同时找到最小值和最大值 : algorithm should be faster but isn't

Question

我正在尝试实现一种算法来查找文件中一组 long 的最小值和最大值。我的测试文件包含 10 亿个 long。

该算法按预期工作，但执行速度并不比原始版本快。它应该明显更快，因为原始版本执行大约 2n 次比较，而这个版本执行 3n/2 次比较。

$ time ./findminmax_naive somelongs 
count: 1000000000
min: 0
max: 2147483647

real    0m24.156s
user    0m4.956s
sys     0m3.896s

$ time ./findminmax_faster somelongs 
count: 1000000000
min: 0
max: 2147483647

real    0m25.048s
user    0m6.948s
sys     0m3.980s

这是“天真的”版本:

#include <alloca.h>
#include <stdio.h>
#include <stdlib.h>

int
main(int ac, char *av[])
{
        FILE *f;
        long count, readcount, i, min, max;
        size_t rlen;
        long *n;

        if (ac != 2 && ac != 3) {
                fprintf(stderr, "Usage: %s <file> [readcount]\n", av[0]);
                exit(1);
        }

        f = fopen(av[1], "r");
        if (f == NULL)
            perror("fopen");
        readcount = 1024;
        if (ac == 3)
            readcount = atol(av[2]);
        n = alloca(sizeof (long) * readcount);
        rlen = fread(n, sizeof (*n), 1, f);
        min = max = n[0];
        count = 1;
        while (1) {
                rlen = fread(n, sizeof (*n), readcount, f);
                for (i = 0; i < (long)rlen; i++) {
                        count++;
                        if (n[i] < min)
                            min = n[i];
                        if (n[i] > max)
                            max = n[i];
                }
                if (feof(f))
                        break;
        }
        printf("count: %ld\n", count);
        printf("min: %ld\n", min);
        printf("max: %ld\n", max);
        exit(0);
}

这是(应该)“更快”版本的代码:

#include <alloca.h>
#include <stdio.h>
#include <stdlib.h>

int
main(int ac, char *av[])
{
        FILE *f;
        long count, readcount, i, min, max;
        size_t rlen;
        long *n;

        if (ac != 2 && ac != 3) {
                fprintf(stderr, "Usage: %s <file> [readcount]\n", av[0]);
                exit(1);
        }

        f = fopen(av[1], "r");
        if (f == NULL)
                perror("fopen");
        readcount = 1024;
        if (ac == 3)
                readcount = atol(av[2]);
        readcount = (readcount + 1) & (-1 << 1);
        n = alloca(sizeof (long) * readcount);
        rlen = fread(n, sizeof (*n), 1, f);
        min = max = n[0];
        count = 1;
        while (1) {
                rlen = fread(n, sizeof (*n), readcount, f);
                for (i = 0; i < (long)rlen; i += 2) {
                        count += 2;
                        if (n[i] < n[i + 1]) {
                                if (n[i] < min)
                                        min = n[i];
                                if (n[i + 1] > max)
                                        max = n[i + 1];
                        } else {
                                if (n[i + 1] < min)
                                        min = n[i + 1];
                                if (n[i] > max)
                                        max = n[i];
                        }
                }
                if (feof(f))
                        break;
        }
        if (rlen % 2) {
                if (n[rlen - 1] < min)
                        min = n[rlen - 1];
                if (n[rlen - 1] > max)
                        max = n[rlen - 1];
                count++;
        }
        printf("count: %ld\n", count);
        printf("min: %ld\n", min);
        printf("max: %ld\n", max);
        exit(0);
}

你知道我错过了什么吗？

感谢您的帮助。

-- 杰瑞米

Answer 1

关键是分支预测。除非文件以病态的最坏情况顺序排序，否则原始版本将执行几乎每次都正确预测的 2n 个分支。您的“聪明”版本执行几乎从未被正确预测的 n/2 个分支，以及可能被正确预测的额外 n 个比较。

错误预测分支的成本在很大程度上取决于 cpu 架构，甚至是特定的 cpu 型号，但至少我预计错误预测分支的成本是正确预测分支的几倍。在极端情况下，正确预测的分支可能具有零周期的有效成本。

作为一个有趣的例子，我最近尝试优化 strlen，并发现在孤立的情况下，一个非常简单的展开 strlen - 一次比较和分支一个字节 -比聪明的矢量化方法更快。这几乎可以肯定是因为 strlen 具有特殊属性，即 every 分支直到最后一个分支将始终被正确预测。

顺便说一下，为了检验我的假设，试试这个输入模式:

999999999, 1000000001, 999999998, 1000000002, 999999997, 1000000003, ...

它将为朴素算法给出最坏情况的分支预测，并为聪明版本的外部条件给出最佳情况。