Pytanie Dlaczego DFS wolniej w jednym drzewie, a szybciej w drugim?


AKTUALIZACJA: Okazało się, że w parserze generującym drzewa wystąpił błąd. Więcej w Ostatecznej edycji. 

Pozwolić T być drzewem binarnym, tak aby każdy węzeł wewnętrzny miał dokładnie dwoje dzieci. W przypadku tego drzewa chcemy zakodować funkcję dla każdego węzła v w T wyszukuje liczbę węzłów w poddrzewie zdefiniowanym przez v.

Przykład

Wkład

enter image description here

Pożądane wyjście

enter image description here

Z czerwonym wskazuję liczby, które chcemy obliczyć. Węzły drzewa będą przechowywane w tablicy, nazwijmy to TreeArray postępując zgodnie z układem przedsprzedaży.

Dla powyższego przykładu, TreeArray będzie zawierał następujące obiekty:

10, 11, 0, 12, 13, 2, 7, 3, 14, 1, 15, 16, 4, 8, 17, 18, 5, 9, 6

Węzeł drzewa jest opisany przez następującą strukturę:

struct tree_node{

    long long 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,
    // what we want to compute

    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;
        size = 1;
        pos = lpos = rpos = -1;
        numChildren = 0;
    }

};

Funkcja do obliczenia wszystkich size wartości są następujące:

void testCache(int cur){

    if(treeArray[cur].numChildren == 0){
        treeArray[cur].size = 1;
        return;
    }

    testCache(treeArray[cur].lpos);
    testCache(treeArray[cur].rpos);

    treeArray[cur].size = treeArray[treeArray[cur].lpos].size + 
    treeArray[treeArray[cur].rpos].size + 1;

}

Chciałbym zrozumieć, dlaczego ta funkcja jest szybciej gdy T wygląda tak (prawie jak łańcuch w lewo):

enter image description here

i wolniej, kiedy T wygląda tak (prawie jak prawy łańcuch):

enter image description here

Poniższe eksperymenty zostały przeprowadzone na procesorze Intel® Core i5-3470 @ 3.20GHz z 8 GB pamięci RAM, pamięci podręcznej L1 256 KB, pamięci podręcznej L2 1 MB, pamięci podręcznej L3 6 MB.

Każda kropka na wykresach jest wynikiem następującej pętli for (parametry są definiowane przez oś):

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

enter image description here

n odpowiada całkowitej liczbie węzłów, a czas jest mierzony w sekundach. Jak widać, jest jasne, że jak n rośnie funkcja jest znacznie szybsza, gdy drzewo wygląda jak łańcuch w lewo, mimo że liczba węzłów jest dokładnie taka sama w obu przypadkach.

Teraz spróbujmy znaleźć, gdzie jest wąskie gardło. Użyłem Biblioteka PAPI zliczyć interesujące liczniki sprzętu.

Pierwszy licznik to instrukcje, ile faktycznie wydamy instrukcji? Czy jest różnica, kiedy drzewa wyglądają inaczej?

enter image description here

Różnica nie jest znacząca. Wygląda na to, że dla dużych wejść lewy łańcuch wymaga mniej instrukcji, ale różnica jest tak mała, więc myślę, że można bezpiecznie założyć, że obie wymagają takiej samej liczby instrukcji.

Widząc, że zapisaliśmy drzewo w ładnym układzie przed zamówieniem wewnątrz treeArray warto zobaczyć, co dzieje się w pamięci podręcznej. Niestety dla pamięci podręcznej L1 mój komputer nie udostępnia żadnych liczników, ale mam dla L2 i L3.

Spójrzmy na dostęp do pamięci podręcznej L2. Dostęp do pamięci podręcznej L2 ma miejsce, gdy brakuje pamięci podręcznej L1, więc jest to również pośredni licznik błędów L1.

enter image description here

Jak widzimy, prawo do poruszania się w drzewie wymaga mniejszej liczby błędów L1, więc wydaje się, że efektywnie korzysta z pamięci podręcznej.

enter image description here

To samo, co w przypadku L2, a prawe drzewo wydaje się bardziej wydajne. Wciąż nic nie wskazuje na to, że właściwe drzewa są tak powolne. Spójrzmy na L3.

enter image description here

W L3 rzeczy eksplodują dla prawych idących drzew. Tak więc problem wydaje się być w pamięci podręcznej L3. Niestety nie mogłem wyjaśnić przyczyny tego zachowania. Dlaczego w pamięci podręcznej L3 rzeczy są pomieszane w poszukiwaniu prawych drzew?

Oto cały kod wraz z eksperymentem:

#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{

    long long 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{

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

}

/*
 *
 *
 * DOT FORMAT OUTPUT --- BEGIN
 *
 *
 */

void treeBstPrintDotAux(tree_node* node, ofstream& treeFout) {

    if(node->numChildren == 0) return;

    treeFout<<"    "<<node->id<<" -> "<<treeArrayReferences[node->lpos]->id<<";\n";
    treeBstPrintDotAux(treeArrayReferences[node->lpos], treeFout);

    treeFout<<"    "<<node->id<<" -> "<<treeArrayReferences[node->rpos]->id<<";\n";
    treeBstPrintDotAux(treeArrayReferences[node->rpos], treeFout);

}

void treePrintDotHelper(tree_node* cur, ofstream& treeFout){
    treeFout<<"digraph BST {\n";
    treeFout<<"    node [fontname=\"Arial\"];\n";

    if(cur == nullptr){
        treeFout<<"\n";
    }
    else if(cur->numChildren == 0){
        treeFout<<"    "<<cur->id<<";\n";
    }
    else{
        treeBstPrintDotAux(cur, treeFout);
    }

    treeFout<<"}\n";
}

void treePrintDot(string& file, tree_node* root){

    ofstream treeFout;
    treeFout.open(file, ios_base::out);
    treePrintDotHelper(root, treeFout);
    treeFout.close();

}

/*
 *
 *
 * DOT FORMAT OUTPUT --- END
 *
 *
 */

/*
 * experiments
 *
 */

tree_node* T;
int n;

void testCache(int cur){

    if(treeArray[cur].numChildren == 0){
        treeArray[cur].size = 1;
        return;
    }

    testCache(treeArray[cur].lpos);
    testCache(treeArray[cur].rpos);

    treeArray[cur].size = treeArray[treeArray[cur].lpos].size + treeArray[treeArray[cur].rpos].size + 1;

}


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

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

    n = T->size;
    double tt;

    startTimer();
    for (int i = 0; i < 100; i++) {
        testCache(0);
    }

    tt = endTimer();
    cout << tt / BILLION << '\t' << T->size;
    cout<<endl;

    return 0;
}

Skompiluj, pisząc g++ -O3 -std=c++11 file.cpp Uruchom, pisząc ./executable tree.txt. W tree.txt przechowujemy drzewo w format newick.

Tutaj to lewe drzewo z 10 ^ 5 listkami

Tutaj to prawo idące drzewo z 10 ^ 5 listkami

Czas działania: ~ 0,07 sekund dla lewych drzew ~ 0,12 sekundy dla prawych, idących drzew

Przepraszam za długi post, ale biorąc pod uwagę, jak wąski jest ten problem, nie mogłem znaleźć lepszego sposobu na jego opisanie.

Z góry dziękuję!

EDYTOWAĆ:

To jest kolejna edycja po odpowiedzi MrSmith42. Rozumiem, że lokalność odgrywa bardzo ważną rolę, ale nie jestem pewien, czy rozumiem, że tak jest w tym przypadku.

Dla dwóch przykładowych drzew powyżej zobaczymy, w jaki sposób uzyskujemy dostęp do pamięci w czasie.

Dla drzewa po lewej:

enter image description here

Dla właściwego drzewa:

enter image description here

Wydaje mi się, że w obu przypadkach mamy lokalne wzorce dostępu.

EDYTOWAĆ:

Oto fabuła o liczbie rozgałęzień warunkowych:

enter image description here

Oto spisek dotyczący liczby błędów w oddziale:

enter image description here

Tutaj to lewe drzewo z 10 ^ 6 listkami

Tutaj to prawo idące drzewo z 10 ^ 6 listkami

EDYCJA KOŃCOWA:

Chciałbym przeprosić za marnowanie czasu wszystkich, parser, którego używałem, miał parametr określający, jak "lewy" lub "prawy" będzie chciał sprawić, aby moje drzewo wyglądało. To była liczba zmiennoprzecinkowa, musiała być bliska 0, aby ją opuścić i zbliżyć się do 1, aby zrobić to dobrze. Jednak aby wyglądał jak łańcuch, musiał być bardzo mały 0.000000001 lub 0.999999999. W przypadku małych nakładów drzewo wyglądało jak łańcuch, nawet dla wartości takich jak 0.0001. Myślałem, że ta liczba jest wystarczająco mała i że dałaby również łańcuch dla większych drzew, jednak jak pokażę, nie jest tak. Jeśli używasz numerów takich jak 0.000000001 parser przestaje działać z powodu problemów z zmiennoprzecinkowymi.

Odpowiedź vadikrobota pokazała, że ​​mamy problemy z lokalnością. Zainspirowany jego eksperymentem postanowiłem uogólnić powyższy schemat schematu dostępu, aby zobaczyć, jak zachowuje się on nie tylko w przykładowych drzewach, ale w dowolnych drzewach.

Zmodyfikowałem kod vadikrobota, aby wyglądał tak:

void testCache(int cur, FILE *f) {

    if(treeArray[cur].numChildren == 0){
        fprintf(f, "%d\t", tim++);
        fprintf (f, "%d\n", cur);
        treeArray[cur].size = 1;
        return;
    }

    fprintf(f, "%d\t", tim++);
    fprintf (f, "%d\n", cur);
    testCache(treeArray[cur].lpos, f);
    fprintf(f, "%d\t", tim++);
    fprintf (f, "%d\n", cur);
    testCache(treeArray[cur].rpos, f);
    fprintf(f, "%d\t", tim++);
    fprintf (f, "%d\n", cur);
    fprintf(f, "%d\t", tim++);
    fprintf (f, "%d\n", treeArray[cur].lpos);
    fprintf(f, "%d\t", tim++);
    fprintf (f, "%d\n", treeArray[cur].rpos);
    treeArray[cur].size = treeArray[treeArray[cur].lpos].size + 
    treeArray[treeArray[cur].rpos].size + 1;
}

Wzorce dostępu generowane przez niewłaściwy analizator składni

Spójrzmy na lewe drzewo z 10 listkami.

enter image description here

Wygląda bardzo ładnie, jak można było przewidzieć na powyższych wykresach (na powyższych wykresach zapomniałem tylko o tym, że gdy znajdujemy rozmiar węzła, uzyskujemy również parametr wielkości tego węzła, cur w powyższym kodzie źródłowym).

Spójrzmy na lewe drzewo ze 100 listkami.

enter image description here

Wygląda zgodnie z oczekiwaniami. A co z 1000 listkami?

enter image description here

Z pewnością nie jest to oczekiwane. W prawym górnym rogu znajduje się mały trójkąt. Powodem tego jest fakt, że drzewo nie wygląda jak lewy łańcuch, na końcu znajduje się mały poddrzewo. Problem staje się jeszcze większy, gdy liście mają rozmiar 10 ^ 4.

enter image description here

Spójrzmy, co dzieje się z prawymi drzewami. Gdy liście mają 10:

enter image description here

Wygląda ładnie, a co ze 100 listkami?

enter image description here

Wygląda też dobrze. Właśnie dlatego zakwestionowałem lokalizację właściwych drzew, dla mnie obie wydawały się przynajmniej teorią lokalną. Teraz, jeśli spróbujesz zwiększyć rozmiar, wydarzy się coś ciekawego:

Dla 1000 liści:

enter image description here

Dla 10 ^ 4 listów rzeczy stają się jeszcze bardziej nieprzyjemne:

enter image description here

Wzorce dostępu generowane przez poprawny analizator składni

Zamiast tego ogólnego parsera utworzyłem jeden dla tego konkretnego pytania:

#include <iostream>
#include <fstream>

using namespace std;

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

    if(argc!=4){
        cout<<"type ./executable n{number of leafs} type{l:left going, r:right going} outputFile"<<endl;
        return 0;
    }

    int i;

    int n = atoi(argv[1]);

    if(n <= 2){cout<<"leafs must be at least 3"<<endl; return 0;}

    char c = argv[2][0];

    ofstream fout;
    fout.open(argv[3], ios_base::out);

    if(c == 'r'){

        for(i=0;i<n-1;i++){

            fout<<"("<<i<<",";

        }
        fout<<i;
        for(i=0;i<n;i++){
            fout<<")";
        }
        fout<<";"<<endl;

    }
    else{

        for(i=0;i<n-1;i++){
            fout<<"(";
        }

        fout<<1<<","<<n<<")";

        for(i=n-1;i>1;i--){
            fout<<","<<i<<")";
        }
        fout<<";"<<endl;

    }

    fout.close();


return 0;
}

Teraz wzorce dostępu wyglądają zgodnie z oczekiwaniami.

Dla drzew po lewej stronie z 10 ^ 4 listkami:

enter image description here

w czarnej części przechodzimy z niskiego miejsca na wysokie, ale odległość między poprzednim niskim a bieżącym niskim jest niewielka, taka sama jak poprzednia wysoka i aktualna wysoka. W związku z tym pamięć podręczna musi być wystarczająco inteligentna, aby pomieścić dwa bloki, jeden na niskie miejsca i jeden na wysokie miejsca, co daje niewielką liczbę pomyłek w pamięci podręcznej.

Dla prawych drzew z 10 ^ 4 listkami:

enter image description here

Oryginalne eksperymenty ponownie. Tym razem mogłem wypróbować tylko do 10 ^ 5 liści, ponieważ jak zauważono, otrzymamy przelew z powodu wysokości drzew, co nie miało miejsca w poprzednich eksperymentach, ponieważ wysokość była mniejsza niż ta spodziewany.

Jeśli chodzi o czas, wydaje się, że wykonują to samo, jednak pamięć podręczna i gałąź nie są mądre. Prawe drzewa biją lewe drzewa w przepowiedniach gałęzi, lewe drzewa biją odpowiednie drzewa w pamięci podręcznej.

Może moje użycie PAPI było błędne, wyjście z perf:

pozostawione drzewa:

enter image description here

prawe drzewa:

enter image description here

Mogłem znowu coś zepsuć i przepraszam za to. Uwzględniłem moją próbę tutaj, na wypadek, gdyby ktoś chciał kontynuować dochodzenie.


30
2017-09-12 13:10


pochodzenie


nie dzwonisz startTimer() gdziekolwiek - m.s.
te wykresy są generowane przez PAPI? - Abhinav Gauniyal
Przykro mi podczas edycji zapomniałem wstawić startTimer() przed pętlą for. Czas pracy zmienia się teraz ~0.7s dla l.txt i ~0.12s dla r.txt. Wygenerowałem wykresy za pomocą dot funkcje i en.wikipedia.org/wiki/DOT_(graph_description_language) - jsguy
Co się stanie, gdy zmienisz kolejność rekursji? IOW, przeszukaj prawą stronę przed lewą stroną? - Mysticial
Ponadto, jeśli twoje rozmiary testowe sięgają 2 milionów węzłów, spodziewałbym się, że benchmark do stackoverflow na lewym i prawym drzewku. - Mysticial


Odpowiedzi:


AKTUALIZACJA:

Wykreślam numer dostępnego elementu w tablicy w czasie

void testCache(int cur, FILE *f) {
   if(treeArray[cur].numChildren == 0){
       fprintf (f, "%d\n", cur);
       treeArray[cur].size = 1;
       return;
   }

   fprintf (f, "%d\n", cur);
   testCache(treeArray[cur].lpos, f);
   fprintf (f, "%d\n", cur);
   testCache(treeArray[cur].rpos, f);

   fprintf (f, "%d\n", treeArray[cur].lpos);
   fprintf (f, "%d\n", treeArray[cur].rpos);
   treeArray[cur].size = treeArray[treeArray[cur].lpos].size + treeArray[treeArray[cur].rpos].size + 1;
}

w wyniku tego wykreślam 999990 element wynikowego pliku tekstowego: enter image description here

Widać, że dla lewego drzewa wszystkie elementy są dostępne lokalnie, ale dla prawego istnieje niejednolitość dostępu.

STARY:

Próbowałem obliczyć liczbę odczytów pamięci za pomocą valgrind. na prawą

valgrind --tool=callgrind --cache-sim ./a.out right
==11493== I   refs:      427,444,674
==11493== I1  misses:          2,288
==11493== LLi misses:          2,068
==11493== I1  miss rate:        0.00%
==11493== LLi miss rate:        0.00%
==11493== 
==11493== D   refs:      213,159,341  (144,095,416 rd + 69,063,925 wr)
==11493== D1  misses:     15,401,346  ( 12,737,497 rd +  2,663,849 wr)
==11493== LLd misses:        329,337  (      7,935 rd +    321,402 wr)
==11493== D1  miss rate:         7.2% (        8.8%   +        3.9%  )
==11493== LLd miss rate:         0.2% (        0.0%   +        0.5%  )
==11493== 
==11493== LL refs:        15,403,634  ( 12,739,785 rd +  2,663,849 wr)
==11493== LL misses:         331,405  (     10,003 rd +    321,402 wr)
==11493== LL miss rate:          0.1% (        0.0%   +        0.5%  )

i dla lewej

valgrind --tool=callgrind --cache-sim=yes ./a.out left

==11496== I   refs:      418,204,722
==11496== I1  misses:          2,327
==11496== LLi misses:          2,099
==11496== I1  miss rate:        0.00%
==11496== LLi miss rate:        0.00%
==11496== 
==11496== D   refs:      204,114,971  (135,076,947 rd + 69,038,024 wr)
==11496== D1  misses:     19,470,268  ( 12,661,123 rd +  6,809,145 wr)
==11496== LLd misses:        306,948  (      7,935 rd +    299,013 wr)
==11496== D1  miss rate:         9.5% (        9.4%   +        9.9%  )
==11496== LLd miss rate:         0.2% (        0.0%   +        0.4%  )
==11496== 
==11496== LL refs:        19,472,595  ( 12,663,450 rd +  6,809,145 wr)
==11496== LL misses:         309,047  (     10,034 rd +    299,013 wr)
==11496== LL miss rate:          0.0% (        0.0%   +        0.4%  )

Jak widać ilość pamięci odczytać "rd" w "prawym" przypadku większe niż po lewej


2
2017-09-12 14:49



Ale on już to wie, pytanie brzmi: dlaczego ... - Jaa-c
masz rację i niestety to doprowadziło do uświadomienia sobie, że mylę parametr parsera, aby utworzyć te drzewa. Zasadniczo wszystkie eksperymenty, które prowadzę powyżej, nie były naprawdę uruchamiane na drzewach, które twierdziłem, że działają ... co za bałagan, jest mi naprawdę przykro (zaktualizuję mój wpis bardziej szczegółowo) - jsguy


Pomyłki pamięci podręcznej różnią się ze względu na lokalizację węzłów w naszej pamięci. Jeśli uzyskasz dostęp do węzłów w kolejności, w jakiej znajdują się one w pamięci, jest prawdopodobne, że pamięć podręczna już je załadowała z pamięci RAM w pamięci podręcznej (ponieważ strony pamięci podręcznej ładowania (najprawdopodobniej są większe niż jeden z twoich węzłów)).

Jeśli uzyskasz dostęp do węzłów w losowej kolejności (w perspektywie do pozycji w pamięci RAM) lub w odwrotnej kolejności, jest bardziej prawdopodobne, że pamięć podręczna jeszcze nie załadowała ich z pamięci RAM.

Różnica nie wynika więc ze struktury twojego drzewa, ale z pozycji drzewiastych węzłów w twojej pamięci RAM w porównaniu do kolejności, do której chcesz uzyskać do nich dostęp.


EDYCJA: (po dodaniu wzorca dostępu do pytania):

Jak widać na wykresie wzoru dostępu:
Na "pozostawione drzewo" skoki dostępu z niskich do wysokich indeksów po około połowie dostępów. Druga połowa najprawdopodobniej zawsze będzie prowadziła do chybień w pamięci podręcznej, gdy odległość wzrasta i rośnie.
Na "Prawe drzewo" druga połowa ma co najmniej dwa węzły blisko siebie (w kolejności dostępu), a kolejne dwa mają trochę szczęścia, czasami na tej samej stronie pamięci podręcznej.


3
2017-09-12 13:42



Dziękuję za odpowiedź, dodałem edycję jako kontynuację. Nie jestem pewien, czy nie robimy lokalnych dostępów dla właściwych drzew. Chyba że źle zrozumiałem jak testCache() sprawia, że ​​pamięć uzyskuje dostęp. - jsguy
Generalnie przechodzenie do sąsiednich węzłów w pamięci na wyższe adresy RAM jest szybsze, ponieważ menedżer pamięci podręcznej w CPU jest zoptymalizowany pod kątem tego kierunku. Na przykład. polecenia programu są w tej kolejności w pamięci RAM, a jeśli nie ma skoku lub pętli, jest to kolejność, w jakiej są wykonywane, tak samo jest w przypadku danych. Na przykład. wideo, obraz itp. są przechowywane w tej kolejności. - MrSmith42
Jeśli chodzi o lewe drzewo, jeśli mamy dostęp A[i] i wtedy A[j], gdzie i jest niski i j jest wysoka, następna para dostępów będzie A[i-1] i A[j+1]. Chociaż widzę, dlaczego może to prowadzić do pomyłek w pamięci podręcznej, czy nie jest tak, że pamięć podręczna będzie przechowywać zarówno blok pobliskich A[i] i A[j], co powoduje brak chybienia pamięci podręcznej z powodu tego skoku? O prawych drzewach idą wzorce dostępu A[j], A[j+1], A[j-2], A[j-1], A[j-4], A[j-3] itp. Nie jestem pewien, dlaczego pamięć podręczna nie byłaby w stanie pobrać wystarczająco dużego bloku, aby skutecznie je odczytać. - jsguy
@jsguy: Jeśli masz szczęście, oba bloki znajdują się w pamięci podręcznej. Ale przynajmniej dla lewej strony, cofamy się w adresach RAM, które są złe w większości przypadków. - MrSmith42