5

char[]想象一下，您想计算给定包含多少个非 ASCII 字符。想象一下，性能真的很重要，所以我们可以跳过我们最喜欢的口号。

最简单的方法显然是

int simpleCount() {
    int result = 0;
    for (int i = 0; i < string.length; i++) {
        result += string[i] >= 128 ? 1 : 0;
    }
    return result;
}

然后你会认为许多输入都是纯 ASCII 的，单独处理它们可能是个好主意。为简单起见，假设您只写了这个

private int skip(int i) {
    for (; i < string.length; i++) {
        if (string[i] >= 128) break;
    }
    return i;
}

这种微不足道的方法可能对更复杂的处理有用，在这里它不会造成任何伤害，对吧？所以让我们继续

int smartCount() {
    int result = 0;
    for (int i = skip(0); i < string.length; i++) {
        result += string[i] >= 128 ? 1 : 0;
    }
    return result;
}

它与 相同simpleCount。我称其为“智能”，因为要完成的实际工作更加复杂，因此快速跳过 ASCII 是有意义的。如果没有或非常短的 ASCII 前缀，它可能会花费更多的周期，但仅此而已，对吗？

也许你想这样重写它，它是一样的，只是可能更可重用，对吧？

int smarterCount() {
    return finish(skip(0));
}

int finish(int i) {
    int result = 0;
    for (; i < string.length; i++) {
        result += string[i] >= 128 ? 1 : 0;
    }
    return result;
}

然后你在一些非常长的随机字符串 上运行基准测试并得到这个 参数确定 ASCII 与非 ASCII 的比率以及非 ASCII 序列的平均长度，但正如你所见，它们并不重要。尝试不同的种子，什么都无所谓。基准使用caliper ，因此通常的陷阱不适用。结果相当可重复，末尾的小黑条表示最小和最大时间。图像

有人知道这里发生了什么吗？任何人都可以复制它吗？

4

2 回答 2

3

我的初步猜测是，这是关于分支预测的。

这个循环：

for (int i = 0; i < string.length; i++) {
    result += string[i] >= 128 ? 1 : 0;
}

恰好包含一个分支，即循环的后向边缘，并且具有高度可预测性。现代处理器将能够准确地预测这一点，从而用指令填充其整个管道。加载顺序也是高度可预测的，因此它将能够预取流水线指令所需的所有内容。高性能结果。

这个循环：

for (; i < string.length - 1; i++) {
    if (string[i] >= 128) break;
}

中间有一个脏的、依赖数据的条件分支。这对于处理器来说更难准确预测。

现在，这并不完全有意义，因为 (a) 处理器肯定会很快了解到通常不会采用 break 分支，(b) 负载仍然是可预测的，因此就像可预取一样，并且 (c ) 在该循环退出后，代码进入一个循环，该循环与快速运行的循环相同。所以我不希望这会产生很大的不同。

于 2013-11-03T11:00:06.027 回答
3

知道了。

不同之处在于优化器/CPU 预测for. 如果它能够预先预测重复次数，它可以跳过对i < string.length. 因此，优化器需要预先知道 for 循环中的条件多久成功一次，因此它必须知道string.lengthand的值i。

我做了一个简单的测试，string.length用一个在方法中设置一次的局部变量替换setup。结果：smarterCount运行时间约为simpleCount. 在更改之前smarterCount大约需要 50% 的时间simpleCount。smartCount没有改变。

看起来优化器丢失了当调用另一个方法时它必须执行多少循环的信息。这就是为什么finish()使用常量集立即跑得更快的原因，但不是smartCount()，因为smartCount()不知道这一步i之后会发生什么。skip()所以我做了第二次测试，我将循环从复制skip()到smartCount().

瞧，这三种方法都在同一时间（800-900 毫秒）内返回。

不同的运行时

于 2013-11-04T14:34:09.240 回答