为什么这个递归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将是连续的,我将第一接入位置0的TreeArray,那么位置1,2,3等.

为了增加对我对正在发生的事情的理解的疑问,我有以下函数找到相同的求和:

void testCache4(int index){

     if(index == TreeArray.size) return;

     r += TreeArray[index].id;

     testCache4(index+1);

}

testCache4TreeArray以相同的方式访问元素,但缓存行为要好得多.

输出来自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.我正在使用的树可以在这里找到(不要打开,点击保存我们).

#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;
}

EDIT2:

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

随着-O3启用我得到如下:

所以函数调用很昂贵testCache1而且成本不高testCache4？两种情况下的函数调用量应该相同......

Answer 1

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

正如这个答案中所解释的，Intel CPU 上的缓存引用实际上是对最后一级缓存的引用数量。因此，由 L1 高速缓存提供服务的内存引用不计算在内。Intel 64 和 IA-32 架构开发人员手册指出，来自 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 次，而不是一次，但 a 的每个数据成员都tree_node位于同一缓存行上，因此只有 4 次未命中中有 1 次。

您可以看到，如果缓存行为 64 字节，testCache4则 L1d 负载未命中率实际上接近 25% 。sizeof(tree_node) == 16

此外，编译器（至少带有 -O2 的 gcc）对两个函数应用尾递归优化，消除了 的递归testCache4，同时进行testCache1单向递归。因此，testCache1有许多对堆栈帧的附加缓存引用，而这testCache4是没有的。

您也可以使用 valgrind 获得无需预取器的结果，它的输出可能也更可靠。但它并没有模拟 CPU 缓存的所有属性。

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