c++ - 为什么这个递归 C++ 函数有如此糟糕的缓存行为？

Question

设 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;
            numChildren = 0;
       }

};

现在假设我们需要一个函数来返回树中所有 ID 的总和。听起来很简单，您所要做的就是使用 for 循环遍历 TreeArray 并累积所有找到的 ID。但是，我有兴趣了解以下实现的缓存行为:

void testCache1(int cur){

     //find the positions of the left and right children
     int lpos = TreeArray[cur].lpos;
     int rpos = TreeArray[cur].rpos;

     //if there are no children we are at a leaf so update r and return

     if(TreeArray[cur].numChildren == 0){
        r += TreeArray[cur].id;
        return;
     }

     //otherwise we are in an internal node, so update r and recurse
     //first to the left subtree and then to the right subtree

     r += TreeArray[cur].id;

     testCache1(lpos);
     testCache1(rpos);

}

为了测试缓存行为，我做了以下实验:

r = 0; //r is a global variable
int main(int argc, char* argv[]){

    for(int i=0;i<100;i++) {
        r = 0;
        testCache1(0);
    }

    cout<<r<<endl;
    return 0;
}

对于具有 500 万个叶子的随机树，perf stat -B -e cache-misses,cache-references,instructions ./run_tests 111.txt 打印以下内容:

 Performance counter stats for './run_tests 111.txt':

   469,511,047      cache-misses              #   89.379 % of all cache refs    
   525,301,814      cache-references                                            
20,715,360,185      instructions             

  11.214075268 seconds time elapsed

一开始我想可能是因为我生成树的方式，我将其排除在我的问题中，但是当我运行 sudo perf record -e cache-misses ./run_tests 111.txt 我收到了以下输出:

正如我们所见，大部分缓存未命中都来自此函数。但是我不明白为什么会这样。 cur 的值将是连续的，我将首先访问 TreeArray 的位置 0，然后是位置 1，2, 3 等

为了增加我对正在发生的事情的理解，我有以下函数可以找到相同的总和:

void testCache4(int index){

     if(index == TreeArray.size) return;

     r += TreeArray[index].id;

     testCache4(index+1);

}

testCache4 以相同的方式访问 TreeArray 的元素，但缓存行为要好得多。

perf stat -B -e cache-misses,cache-references,instructions ./run_tests 11.txt 的输出:

 Performance counter stats for './run_tests 111.txt':

   396,941,872      cache-misses              #   54.293 % of all cache refs    
   731,109,661      cache-references                                            
11,547,097,924      instructions             

   4.306576556 seconds time elapsed

在 sudo perf record -e cache-misses ./run_tests 111.txt 的输出中，该函数甚至不存在:

我为这篇冗长的帖子道歉，但我感到完全迷失了。先感谢您。

编辑:

这是完整的测试文件，连同解析器和所需的一切。假定树在作为参数给出的文本文件中可用。输入 g++ -O3 -std=c++11 file.cpp 编译，输入 ./executable tree.txt 运行。我正在使用的树可以找到here (不要打开，点击保存我们)。

#include <iostream>
#include <fstream>
#define BILLION  1000000000LL

using namespace std;

/*
 *
 * Timing functions
 *
 */

timespec startT, endT;

void startTimer(){
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &startT);
}

double endTimer(){
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &endT);
    return endT.tv_sec * BILLION + endT.tv_nsec - (startT.tv_sec * BILLION + startT.tv_nsec);
}

/*
 *
 * tree node
 *
 */

//this struct is used for creating the first tree after reading it from the external file, for this we need left and child pointers

struct tree_node_temp{

    int id; //id of the node, randomly generated
    int numChildren; //number of children, it is 2 but for the leafs it's 0
    int size; //size of the subtree rooted at the current node
    tree_node_temp *leftChild;
    tree_node_temp *rightChild;

    tree_node_temp(){
        id = -1;
        size = 1;
        leftChild = nullptr;
        rightChild = nullptr;
        numChildren = 0;
    }

};

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 size; //size of the subtree rooted at the current node

    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;
        numChildren = 0;
    }

};

/*
 *
 * Tree parser. The input is a file containing the tree in the newick format.
 *
 */

string treeNewickStr; //string storing the newick format of a tree that we read from a file
int treeCurSTRindex; //index to the current position we are in while reading the newick string
int treeNumLeafs; //number of leafs in current tree
tree_node ** treeArrayReferences; //stack of references to free node objects
tree_node *treeArray; //array of node objects
int treeStackReferencesTop; //the top index to the references stack
int curpos; //used to find pos,lpos and rpos when creating the pre order layout tree


//helper function for readNewick
tree_node_temp* readNewickHelper() {

    int i;
    if(treeCurSTRindex == treeNewickStr.size())
        return nullptr;

    tree_node_temp * leftChild;
    tree_node_temp * rightChild;

    if(treeNewickStr[treeCurSTRindex] == '('){
        //create a left child
        treeCurSTRindex++;
        leftChild = readNewickHelper();
    }

    if(treeNewickStr[treeCurSTRindex] == ','){
        //create a right child
        treeCurSTRindex++;
        rightChild = readNewickHelper();
    }

    if(treeNewickStr[treeCurSTRindex] == ')' || treeNewickStr[treeCurSTRindex] == ';'){
        treeCurSTRindex++;
        tree_node_temp * cur = new tree_node_temp();
        cur->numChildren = 2;
        cur->leftChild = leftChild;
        cur->rightChild = rightChild;
        cur->size = 1 + leftChild->size + rightChild->size;
        return cur;
    }

    //we are about to read a label, keep reading until we read a "," ")" or "(" (we assume that the newick string has the right format)
    i = 0;
    char treeLabel[20]; //buffer used for the label
    while(treeNewickStr[treeCurSTRindex]!=',' && treeNewickStr[treeCurSTRindex]!='(' && treeNewickStr[treeCurSTRindex]!=')'){
        treeLabel[i] = treeNewickStr[treeCurSTRindex];
        treeCurSTRindex++;
        i++;
    }

    treeLabel[i] = '\0';
    tree_node_temp * cur = new tree_node_temp();
    cur->numChildren = 0;
    cur->id = atoi(treeLabel)-1;
    treeNumLeafs++;

    return cur;
}

//create the pre order tree, curRoot in the first call points to the root of the first tree that was given to us by the parser
void treeInit(tree_node_temp * curRoot){

    tree_node * curFinalRoot = treeArrayReferences[curpos];

    curFinalRoot->pos = curpos;

    if(curRoot->numChildren == 0) {
        curFinalRoot->id = curRoot->id;
        return;
    }

    //add left child
    tree_node * cnode = treeArrayReferences[treeStackReferencesTop];
    curFinalRoot->lpos = curpos + 1;
    curpos = curpos + 1;
    treeStackReferencesTop++;
    cnode->id = curRoot->leftChild->id;
    treeInit(curRoot->leftChild);

    //add right child
    curFinalRoot->rpos = curpos + 1;
    curpos = curpos + 1;
    cnode = treeArrayReferences[treeStackReferencesTop];
    treeStackReferencesTop++;
    cnode->id = curRoot->rightChild->id;
    treeInit(curRoot->rightChild);

    curFinalRoot->id = curRoot->id;
    curFinalRoot->numChildren = 2;
    curFinalRoot->size = curRoot->size;

}

//the ids of the leafs are deteremined by the newick file, for the internal nodes we just incrementally give the id determined by the dfs traversal
void updateInternalNodeIDs(int cur){

    tree_node* curNode = treeArrayReferences[cur];

    if(curNode->numChildren == 0){
        return;
    }
    curNode->id = treeNumLeafs++;
    updateInternalNodeIDs(curNode->lpos);
    updateInternalNodeIDs(curNode->rpos);

}

//frees the memory of the first tree generated by the parser
void treeFreeMemory(tree_node_temp* cur){

    if(cur->numChildren == 0){
        delete cur;
        return;
    }
    treeFreeMemory(cur->leftChild);
    treeFreeMemory(cur->rightChild);

    delete cur;

}

//reads the tree stored in "file" under the newick format and creates it in the main memory. The output (what the function returns) is a pointer to the root of the tree.
//this tree is scattered anywhere in the memory.

tree_node* readNewick(string& file){

    treeCurSTRindex = -1;
    treeNewickStr = "";
    treeNumLeafs = 0;

    ifstream treeFin;

    treeFin.open(file, ios_base::in);
    //read the newick format of the tree and store it in a string
    treeFin>>treeNewickStr;
    //initialize index for reading the string
    treeCurSTRindex = 0;
    //create the tree in main memory
    tree_node_temp* root = readNewickHelper();

    //store the tree in an array following the pre order layout
    treeArray = new tree_node[root->size];
    treeArrayReferences = new tree_node*[root->size];
    int i;
    for(i=0;i<root->size;i++)
        treeArrayReferences[i] = &treeArray[i];
    treeStackReferencesTop = 0;

    tree_node* finalRoot = treeArrayReferences[treeStackReferencesTop];
    curpos = treeStackReferencesTop;
    treeStackReferencesTop++;
    finalRoot->id = root->id;
    treeInit(root);

    //update the internal node ids (the leaf ids are defined by the ids stored in the newick string)
    updateInternalNodeIDs(0);
    //close the file
    treeFin.close();

    //free the memory of initial tree
    treeFreeMemory(root);
    //return the pre order tree
    return finalRoot;

}

/*
 * experiments
 *
 */

int r;
tree_node* T;

void testCache1(int cur){

    int lpos = treeArray[cur].lpos;
    int rpos = treeArray[cur].rpos;

    if(treeArray[cur].numChildren == 0){
        r += treeArray[cur].id;
        return;
    }

    r += treeArray[cur].id;

    testCache1(lpos);
    testCache1(rpos);

}


void testCache4(int index){

    if(index == T->size) return;

    r += treeArray[index].id;

    testCache4(index+1);

}


int main(int argc, char* argv[]){

    string Tnewick = argv[1];
    T = readNewick(Tnewick);
    double tt;

    startTimer();
    for(int i=0;i<100;i++) {
        r = 0;
        testCache4(0);
    }
    tt = endTimer();
    cout<<r<<endl;
    cout<<tt/BILLION<<endl;

    startTimer();
    for(int i=0;i<100;i++) {
        r = 0;
        testCache1(0);
    }
    tt = endTimer();
    cout<<r<<endl;
    cout<<tt/BILLION<<endl;

    delete[] treeArray;
    delete[] treeArrayReferences;

    return 0;
}

编辑 2:

我用 valgrind 运行一些分析测试。这些说明实际上可能是这里的开销，但我不明白为什么。例如，即使在上面的 perf 实验中，一个版本也给出了大约 200 亿条指令，而另一个版本给出了 110 亿条。这是 90 亿的差异。

启用 -O3 我得到以下信息:

所以函数调用在 testCache1 中是昂贵的，而在 testCache4 中没有成本？两种情况下的函数调用量应该是一样的……

Answer 1

我想这个问题是对缓存引用实际计数的误解。

如 this answer 中所述Intel CPU 上的缓存引用实际上是对末级缓存的引用数。因此，由 L1 缓存提供的内存引用不计算在内。Intel 64 and IA-32 Architectures Developer's Manual指出来自 L1 预取器的加载被计算在内。

如果您实际比较缓存未命中的绝对数量，您会发现这两个函数的数量大致相等。我在测试中使用了一个完全平衡的树，删除了 pos 以获得 16 的大小，非常适合缓存行并得到以下数字:

testCache4:

843.628.131      L1-dcache-loads                                               (56,83%)
193.006.858      L1-dcache-load-misses     #   22,73% of all L1-dcache hits    (57,31%)
326.698.621      cache-references                                              (57,07%)
188.435.203      cache-misses              #   57,679 % of all cache refs      (56,76%)

testCache1:

3.519.968.253    L1-dcache-loads                                               (57,17%)
193.664.806      L1-dcache-load-misses     #    5,50% of all L1-dcache hits    (57,24%)
256.638.490      cache-references                                              (57,12%)
188.007.927      cache-misses              #   73,258 % of all cache refs      (57,23%)

如果我手动禁用所有硬件预取器:

testCache4:

846.124.474      L1-dcache-loads                                               (57,22%)
192.495.450      L1-dcache-load-misses     #   22,75% of all L1-dcache hits    (57,31%)
193.699.811      cache-references                                              (57,03%)
185.445.753      cache-misses              #   95,739 % of all cache refs      (57,17%)

testCache1:

3.534.308.118    L1-dcache-loads                                               (57,16%)
193.595.962      L1-dcache-load-misses     #    5,48% of all L1-dcache hits    (57,18%)
193.639.498      cache-references                                              (57,12%)
185.120.733      cache-misses              #   95,601 % of all cache refs      (57,15%)

如您所见，差异现在已经消失。由于预取器和实际引用被计算了两次，所以只有额外的缓存引用事件。

实际上，如果计算所有内存引用，testCache1 的总缓存未命中率较低，因为每个 tree_node 被引用了 4 次，而不是 1 次，但是tree_node 位于同一缓存行，因此只有四分之一未命中。

对于 testCache4，您可以看到 L1d 加载未命中率实际上接近 25%，如果 sizeof(tree_node) == 16 并且缓存行是64 字节。

此外，编译器(至少是带 -O2 的 gcc)对两个函数应用尾递归优化，消除了 testCache4 的递归，同时使 testCache1 成为单向递归。因此 testCache1 有许多对栈帧的额外缓存引用，而 testCache4 没有。

您也可以使用 valgrind 在没有预取器的情况下获得结果，它的输出可能也更可靠。不过，它不会模拟 CPU 缓存的所有属性。

关于您的编辑:正如我提到的 gcc 应用尾递归优化，因此 testCache4 中没有剩余调用，当然 testCache1 中的递归和额外内存负载具有重要意义与 testCache4 中留下的简单加载/添加循环相比的指令开销。