相关疑难解决方法(0)

这是一段看似非常特殊的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)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c) …

在我的生活中,我不能记住那天老师说的话,我希望你可能知道.

该模块是"数据结构和算法",他告诉我们的一些事情:

该if声明是最昂贵的[东西.[东西]注册[东西].

是的,我确实有一个可怕的记忆,我真的很抱歉,但我一直在谷歌搜索几个小时,没有任何事情发生.有任何想法吗？

问题:

我试图找出如何编写代码(C preffered,ASM仅在没有其他解决方案的情况下),这将使分支预测在50%的情况下失败.

所以它必须是一段代码"对于与分支相关的编译器优化"是"imune",而且所有HW分支预测都不应该超过50%(抛硬币).即使是更大的挑战,也能够在多个CPU架构上运行代码并获得相同的50%未命中率.

我设法编写了一个在x86平台上达到47%分支未命中率的代码.我怀疑失踪可能有3%来自:

• 程序启动开销已经分支(尽管很小)
• Profiler开销 - 基本上对于每个计数器读取都会引发中断,因此可能会添加其他可预测的分支.
• 在后台运行的系统调用包含循环和可预测的分支

我编写了自己的随机数生成器,以避免调用rand,它的实现可能隐藏了可预测的分支.当可用时它也可以使用rdrand.延迟对我来说无关紧要.

问题:

1. 我能比我的代码版做得更好吗？更好的意思是为所有CPU架构获得更高的分支错误预测和相同的结果.
2. 这段代码可以预测吗？那是什么意思？

代码:

#include <stdio.h>
#include <time.h>

#define RDRAND
#define LCG_A   1103515245
#define LCG_C   22345
#define LCG_M   2147483648
#define ULL64   unsigned long long

ULL64 generated;

ULL64 rand_lcg(ULL64 seed)
{
#ifdef RDRAND
    ULL64 result = 0;
    asm volatile ("rdrand %0;" : "=r" (result));
    return result;
#else
    return (LCG_A * seed + LCG_C) % LCG_M;
#endif
}

ULL64 rand_rec1()
{ …

我发现这个主题为什么处理排序数组比未排序数组更快？.并尝试运行此代码.而且我发现了奇怪的行为.如果我使用-O3优化标志编译此代码,则需要2.98605 sec运行.如果我用-O2它编译1.98093 sec.我尝试在同一环境中的同一台机器上运行此代码几次(5或6),我关闭所有其他软件(chrome,skype等).

gcc --version
gcc (Ubuntu 4.9.2-0ubuntu1~14.04) 4.9.2
Copyright (C) 2014 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

那么请你能解释一下为什么会这样吗？我阅读gcc手册,我看到-O3包括-O2.谢谢你的帮助.

PS添加代码

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

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

    for (unsigned …