相关疑难解决方法(0)

我试图弄清楚为什么修改后的C程序比未修改的计数器部分运行得更快(我添加了很少的代码行来执行一些额外的工作).在这种情况下,我怀疑" 缓存效应 "是主要的解释(指令缓存).因此,我到达perf(https://perf.wiki.kernel.org/index.php/Main_Page)分析工具,但遗憾的是我无法理解其有关缓存未命中的输出的含义.

提供了几个关于缓存的事件:

  cache-references                                   [Hardware event]
  cache-misses                                       [Hardware event]
  L1-dcache-loads                                    [Hardware cache event]
  L1-dcache-load-misses                              [Hardware cache event]
  L1-dcache-stores                                   [Hardware cache event]
  L1-dcache-store-misses                             [Hardware cache event]
  L1-dcache-prefetches                               [Hardware cache event]
  L1-dcache-prefetch-misses                          [Hardware cache event]
  L1-icache-loads                                    [Hardware cache event]
  L1-icache-load-misses                              [Hardware cache event]
  L1-icache-prefetches                               [Hardware cache event]
  L1-icache-prefetch-misses                          [Hardware cache event]
  LLC-loads                                          [Hardware cache event]
  LLC-load-misses                                    [Hardware cache event]
  LLC-stores                                         [Hardware cache event]
  LLC-store-misses                                   [Hardware cache event]
  LLC-prefetches                                     [Hardware cache event]
  LLC-prefetch-misses                                [Hardware cache event]
  dTLB-loads                                         [Hardware cache event] …

我们T是一个有根的二叉树,使得每一个内部节点正好有两个孩子.树的节点将存储在一个数组中,让我们TreeArray按照预先排序布局调用它.

例如,如果这是我们拥有的树:

然后TreeArray将包含以下节点对象:

7, 3, 1, 0, 2, 6, 12, 9, 8, 11, 13

此树中的节点是此类结构:

struct tree_node{

    int id; //id of the node, randomly generated
    int numChildren; //number of children, it is 2 but for the leafs it's 0

    int pos; //position in TreeArray where the node is stored
    int lpos; //position of the left child
    int rpos; //position of the right child

    tree_node(){
            id = -1;
            pos = lpos = rpos = -1; …