这是C++代码的一块 显示一些非常特殊的行为

出于某种原因,对数据进行分类(之前奇迹般地使主环速度快近六倍:

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;
    for (unsigned i = 0; i < 100000; ++i)
    {
        for (unsigned c = 0; c < arraySize; ++c)
        {   // Primary loop.
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << '\n';
    std::cout << "sum = " << sum << '\n';
}
  • 不无std::sort(data, data + arraySize);代码在11.54秒内运行
  • 根据分类数据 代码在1.93秒内运行

(分类本身需要的时间比这个通过数组的时间要长, 所以如果我们需要计算未知数组, 它实际上不值得做 。)


起初,我以为这只是一种语言或编译器异常, 所以我尝试了爪哇:

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < 100000; ++i)
        {
            for (int c = 0; c < arraySize; ++c)
            {   // Primary loop.
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

其结果类似,但不太极端。


我第一种想法是 分类能把数据带进缓存缓存,但那是愚蠢的 因为阵列是刚刚产生的。

  • 这是怎么回事?
  • 为什么处理一个分类阵列的速度要快于处理一个未排序阵列的速度?

守则正在总结一些独立的术语,因此命令不应重要。


相关/后续行动不同/以后的编译者和选项的相同效果:


当前回答

分流收益!

重要的是要理解分支错误控制不会减慢程序。 错误预测的成本就好像不存在分支预测,而你等待着对表达方式的评价来决定运行的代码(下段有进一步的解释 ) 。

if (expression)
{
    // Run 1
} else {
    // Run 2
}

每当有if-else \ switch语句中,必须评价表达式,以决定应执行哪个区块。在编译器生成的组装代码中,有条件分支分支分支插入说明。

分支指令可导致计算机开始执行不同的指令序列,从而偏离其按顺序执行指令的默认行为(即如果表达式为虚假,程序跳过代码)if(根据某些条件,即我们案件的表达方式评价)

尽管如此,汇编者试图在对结果进行实际评估之前预测结果。if如果表达式是真实的,那么就太好了!我们得到了评估它所需的时间,并在代码中取得了进展;如果不是,我们运行错误的代码,管道被冲洗,正确的模块被运行。

可视化:

假设你需要选择路线1或路线2, 等待你的伴侣检查地图, 你已经停留在 ##,等待, 或者你可以选择路线1, 如果你运气好(路线1是正确的路线), 那么伟大的你不必等待你的伴侣检查地图(你省下时间让他检查地图), 否则你就会转回去。

尽管冲水管道的速度超快,但如今赌博是值得的。 预测分类数据或缓慢变化的数据总是比预测快速变化容易,也好于预测快速变化。

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------

其他回答

这个问题已经回答过很多次了。我还是想提醒大家注意另一个有趣的分析。

最近,这个例子(稍作修改)也被用来演示如何在 Windows 上显示一个代码在程序本身中被剖析。 顺便提一下, 作者还展示了如何使用结果来确定代码的大部分时间用于分解和未排序的案例中。 最后, 文章还展示了如何使用HAL( Hardware Empaction Develople) 的一个鲜为人知的特征来确定未分类案例中的分支错误发生多少。

链接在此 :自我辩护示范

在分类的情况下,你可以做的比依靠成功的分支预测或任何无分支比较的把戏:完全删除分支。

事实上,阵阵列被分割在一个毗连区内,data < 128data >= 128。因此,您应该用 a 来找到分区点脑细胞细胞研究(使用Lg(arraySize) = 15比较),然后从该点做一个直线积累。

类似的东西( 未检查 )

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

或, 略微糊涂

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

一种既快又快的方法,约近分类或未排序的解决方案为 :sum= 3137536;(假设分布真正统一,预计价值为191.5的16384个样本):-)

其他答复的假设是,一个人需要对数据进行分类是不正确的。

以下代码不排序整个阵列,但只排序其中的200个元素部分,因此运行速度最快。

只对 K 元素部分进行排序,以线性时间完成预处理,O(n),而不是O(n.log(n))排序整个阵列需要时间 。

#include <algorithm>
#include <ctime>
#include <iostream>

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

    for (unsigned c = 0; c < l; ++c)
        data[c] = std::rand() % 256;

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i) {
        for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

这个“证明”也与任何算法问题无关, 比如排序顺序, 并且确实是分支预测。

由于一种被称为分支预测的现象,分类的阵列的处理速度要快于未排序的阵列。

分支预测器是一个数字电路(在计算机结构中),它试图预测一个分支会走哪条路,从而改善教学管道的流量。电路/计算机预测下一步并进行执行。

错误的预测导致回到前一步,执行另一个预测。 假设预测是正确的,代码将持续到下一步骤。 错误的预测导致重复同一步骤,直到出现正确的预测。

你问题的答案很简单

在未排列的阵列中,计算机进行多次预测,导致误差的可能性增加。而在分类的阵列中,计算机的预测减少,误差的可能性减少。 做更多的预测需要更多的时间。

排序的数组: 直路

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

未排列的队列: 曲线路

______   ________
|     |__|

部门预测: 猜测/预测哪条道路是直的,未检查就沿着这条道路走

___________________________________________ Straight road
 |_________________________________________|Longer road

虽然两条道路都到达同一目的地,但直路更短,另一条更长。如果你错误地选择另一条道路,就没有回头路,所以如果你选择更长的路,你就会浪费一些更多的时间。这与计算机中发生的事情相似,我希望这能帮助你更好地了解。


我还想列举:@Simon_ weaver评论中:

它不会减少预测数量 — — 它会减少不正确的预测。 它仍然必须通过循环预测每一次...

分流收益!

重要的是要理解分支错误控制不会减慢程序。 错误预测的成本就好像不存在分支预测,而你等待着对表达方式的评价来决定运行的代码(下段有进一步的解释 ) 。

if (expression)
{
    // Run 1
} else {
    // Run 2
}

每当有if-else \ switch语句中,必须评价表达式,以决定应执行哪个区块。在编译器生成的组装代码中,有条件分支分支分支插入说明。

分支指令可导致计算机开始执行不同的指令序列,从而偏离其按顺序执行指令的默认行为(即如果表达式为虚假,程序跳过代码)if(根据某些条件,即我们案件的表达方式评价)

尽管如此,汇编者试图在对结果进行实际评估之前预测结果。if如果表达式是真实的,那么就太好了!我们得到了评估它所需的时间,并在代码中取得了进展;如果不是,我们运行错误的代码,管道被冲洗,正确的模块被运行。

可视化:

假设你需要选择路线1或路线2, 等待你的伴侣检查地图, 你已经停留在 ##,等待, 或者你可以选择路线1, 如果你运气好(路线1是正确的路线), 那么伟大的你不必等待你的伴侣检查地图(你省下时间让他检查地图), 否则你就会转回去。

尽管冲水管道的速度超快,但如今赌博是值得的。 预测分类数据或缓慢变化的数据总是比预测快速变化容易,也好于预测快速变化。

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------