c++ - सी++ प्रोग्राम्स



इस पुनरावर्ती सी++ फ़ंक्शन में ऐसा एक बुरा कैश व्यवहार क्यों होता है? (1)

आज्ञा देना एक मूल द्विआधारी पेड़ ऐसा होना चाहिए कि हर आंतरिक नोड में दो बच्चे हैं। पेड़ के नोड्स को एक सरणी में संग्रहीत किया जाएगा, हम इसे TreeArray को 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;
       }

};

अब मान लीजिए कि हमें ऐसा फ़ंक्शन चाहिए जो पेड़ में सभी आईडी का योग देता है। बहुत तुच्छ लगता है, आपको बस ऐसा करना है जो कि TreeArray ऊपर लूप के लिए उपयोग करता है और सभी पाया गया TreeArray इकट्ठा करता है हालांकि, मुझे निम्न कार्यान्वयन के कैश व्यवहार को समझने में दिलचस्पी है:

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

5 लाख पत्तों के साथ एक यादृच्छिक पेड़ के लिए, 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 हूं sudo perf record -e cache-misses ./run_tests 111.txt मुझे निम्नलिखित आउटपुट प्राप्त हुआ:

जैसा कि हम देख सकते हैं कि कैशिंग के अधिकांश कैश इस फ़ंक्शन से आते हैं। हालांकि मैं समझ नहीं पा रहा हूं कि यह मामला क्यों है। cur मूल्य अनुक्रमिक होंगे, मैं पहले TreeArray की स्थिति 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 से आउटपुट 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 टाइप करके और टाइप करके ./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 के साथ कुछ प्रोफाइल परीक्षण चला रहा हूँ निर्देश वास्तव में ऊपरी हो सकते हैं, लेकिन मुझे समझ में नहीं आता कि क्यों उदाहरण के लिए, पेर्फ के ऊपर के प्रयोगों में भी, एक संस्करण में लगभग 20 बिलियन निर्देश और 11 अरब अन्य हैं। यह 9 बिलियन अंतर है

-O3 सक्षम होने के साथ मुझे निम्न प्राप्त हुआ:

तो फ़ंक्शन कॉल्स testCache1 में महंगा है और testCache1 लागत कुछ भी नहीं है? दोनों मामलों में फ़ंक्शन कॉल्स की मात्रा समान होनी चाहिए ...


मुझे लगता है कि समस्या कैश-संदर्भों में वास्तव में गिनती की गलतफहमी है I

जैसा कि इस जवाब में बताया गया है कि इंटेल CPU पर कैश-संदर्भ वास्तव में अंतिम-स्तरीय कैश के संदर्भ की संख्या हैं। इसलिए स्मृति संदर्भ जो एल 1 कैशे द्वारा परोसा गया था, गिना नहीं गया है। इंटेल 64 और आईए -32 आर्किटेक्चर डेवलपर के मैनुअल में बताया गया है कि एल 1 प्रीफैचर से लोड की गणना की जाती है।

यदि आप वास्तव में कैश-मिसेज़ की पूर्ण संख्या की तुलना करते हैं, तो आप देखेंगे कि वे दोनों कार्यों के लिए मोटे तौर पर बराबर हैं। मैंने परीक्षण के लिए एक पूरी तरह से संतुलित पेड़ का इस्तेमाल किया, कैश लाइनों में 16 फिटिंग का आकार पाने के लिए pos को हटा दिया और निम्नलिखित नंबर मिला:

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 बार बजाय संदर्भित किया जाता है, लेकिन एक tree_node प्रत्येक डाटा सदस्य एक ही कैश लाइन पर है और इसलिए केवल 4 में से कोई एक ।

testCache4 आप देख सकते हैं कि एल 1 डी लोड मिस रेशियो वास्तव में करीब 25% है जो आपको उम्मीद होगी कि sizeof(tree_node) == 16 और कैश लाइन 64 बाइट्स हैं।

साथ ही कंपाइलर (कम से कम जीसीसी- testCache1 testCache4 के पुनरावर्तन को समाप्त करते हुए दोनों कार्यों के लिए पूंछ testCache4 अनुकूलन लागू करता है, जबकि testCache1 1 एक- testCache1 रिकर्सिव बनाते हैं। इसलिए testCache1 में स्टैक फ़्रेम के कई अतिरिक्त कैश संदर्भ होते हैं जो testCache4 पास नहीं है।

आप वाल्ग्रिंड का इस्तेमाल करके पूर्व-फीचर के बिना भी परिणाम प्राप्त कर सकते हैं, जो संभवत: इसके आउटपुट में भी अधिक विश्वसनीय है। यह हालांकि CPU कैश के सभी गुणों का अनुकरण नहीं करता है।

आपके संपादनों के बारे में: जैसा कि मैंने जीसीसी से पलता पुनर्क्रयन ऑप्टिमाइज़ेशन को पूरा किया है, इसलिए testCache4 में कोई कॉल नहीं छोड़ी गई है और निश्चित रूप से पुनरावर्ती और testCache1 में अतिरिक्त मेमोरी लोड हैं, testCache1 कि testCache1 में testCache1 गए सरल लोड / जोड़ लूप की तुलना में महत्वपूर्ण निर्देश ओवरहेड है।





tree