相关疑难解决方法(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) …

我试图了解跳转表及其在switch case语句之间的关系.

我被告知跳转表是编译器生成的O(1)结构,它使得查找值基本上与您可以获得的速度一样快.但是在某些情况下,Hashtable/Dictionary可能会更快.我还被告知这只有在开关盒包含ordered数据值时才有效.

有人可以确认或否认这一点并解释跳转表是什么,它的重要性和时间复杂性与使用字典或散列表相比.谢谢.

一些参考：

_{这是对为什么处理排序数组比处理未排序数组更快？}

_{我发现在r标签中与分支预测有些相关的唯一帖子是为什么采样矩阵行很慢？}

问题说明：

我正在调查是否处理排序后的数组比处理一个未排序的一个（相同测试的问题更快Java和C-第一连杆），看看是否分支预测是影响R以相同的方式。

请参阅下面的基准示例：

set.seed(128)
#or making a vector with 1e7
myvec <- rnorm(1e8, 128, 128)  

myvecsorted <- sort(myvec)

mysumU = 0
mysumS = 0

SvU <- microbenchmark::microbenchmark(
  Unsorted = for (i in 1:length(myvec)) {
    
    if (myvec[i] > 128) {
      mysumU = mysumU + myvec[i]
    }
    
  } ,
  Sorted = for (i in 1:length(myvecsorted)) {
    
    if (myvecsorted[i] > 128) {
      mysumS = mysumS + myvecsorted[i]
    }
    
  } , …

我试图详细了解当分支预测错误时，skylake CPU管道的各个阶段中的指令会发生什么，以及从正确的分支目标开始执行指令的速度如何。

因此，让我们在这里将两个代码路径标记为红色（一个预测但未实际采用）和绿色（一个已预测但未预期）。所以问题是：1.在红色指令开始被丢弃之前，分支必须经过管道多远（以及在管道的哪个阶段被丢弃）？2.绿色指令（在分支到达的流水线阶段方面）多久可以开始执行？

我看过Agner Fogg的文档和许多讲义，但这些观点并不清楚。

我有一个相当重要的问题,我的计算图有周期和多个"计算路径".我没有做一个调度程序循环,每个顶点将被逐个调用,我有一个想法是将所有预先分配的"框架对象"放在堆中(代码+数据).
这有点类似于线程代码(甚至更好:CPS),只是在堆中跳转,执行代码.每个代码段与堆中自己的"帧指针"相关联,并使用与之相关的数据.帧始终保持分配状态.代码只在已知位置产生副作用,计算(如果需要)下一个goto值并跳转到那里.
我还没有尝试过(这将是一个重要的事情,使它正确,我完全意识到所有的困难)所以我想问x86机械专家:它能比调度程序循环更快吗？我知道在硬件中进行的调用/返回指令有几种优化.
访问相对于堆栈指针的数据或任何其他指针之间有区别吗？是否有预取间接跳转(跳转到存储在寄存器中的值？).
这个想法是否可行？

PS如果你已经读过这个并且仍然无法理解这个想法的意思(原谅我尝试解释事情的失败)想象这整个就像是一堆堆上的预先分配的协同程序,彼此相互影响.标准x86堆栈未在进程中使用,因为所有内容都在堆上.