为什么这个递归C ++函数有这么糟糕的缓存行为？
设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);
}
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的输出中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] = ' ';
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中花费testCache1并且在testCache4什么也不testCache4 ？ 在这两种情况下函数调用的数量应该是相同的...
我想这个问题是对什么是缓存引用实际计数的误解。
如本答案中所述，英特尔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次而不是1次，但是tree_node每个数据成员位于同一缓存行上，所以在4次未命中中只有一次。
对于testCache4您可以看到，如果sizeof(tree_node) == 16并且高速缓存行是64字节，那么L1d加载缺失率实际上接近25％，这是您所期望的。
此外，编译器（至少gcc和-O2）将tail递归优化应用于这两个函数，从而消除了testCache4的递归，同时使testCache1单向递归。 因此， testCache1有许多额外的缓存引用，这些引用是testCache4没有的堆栈帧。
你也可以通过使用valgrind来获得没有预取的结果，这在输出中可能也更可靠。 它不会模拟CPU缓存的所有属性。
关于你的编辑：正如我所说的，gcc使用了尾递归优化，所以在testCache4中没有任何调用，当然，递归和testCache1额外的内存加载相对于testCache4留下的简单加载/添加循环具有显着的指令开销。
上一篇: Why does this recursive C++ function have such a bad cache behavior?
下一篇: R function for position of sun giving unexpected results