Почему DFS медленнее в одном дереве и быстрее в другом?

ОБНОВЛЕНИЕ: Оказывается, в парсере произошла ошибка, которая генерировала деревья. Подробнее в Final edit.

Пусть T - двоичное дерево, так что каждый внутренний node имеет ровно два ребенка. Для этого дерева мы хотим закодировать функцию, которая для каждого node v в T находит количество узлов в поддереве, определяемом v.

Пример

Ввод

Требуемый вывод

С красным я указываю числа, которые мы хотим вычислить. Узлы дерева будут храниться в массиве, назовем его TreeArray, выполнив макет предзаказа.

В приведенном выше примере TreeArray будет содержать следующие объекты:

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

A node дерева описывается следующей структурой:

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

};

Функция для вычисления всех значений size такова:

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;

}

Я хотел бы понять, почему эта функция быстрее, когда T выглядит так (почти как левая цепочка):

и медленнее, когда T выглядит так (почти как правая цепочка):

Следующие эксперименты проводились на процессоре Intel (R) Core (TM) i5-3470 с частотой 3,0 ГГц с 8 ГБ оперативной памяти, кеш-память L1 256 КБ, кеш второго уровня 1 МБ, кеш-память L3 6 МБ.

Каждая точка в графах является результатом следующего для цикла (параметры определяются осью):

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

n соответствует общему числу узлов, а время измеряется в секундах. Как видно, ясно, что при возрастании n функция намного быстрее, когда дерево выглядит как целая цепь слева, хотя число узлов в обоих случаях одинаково.

Теперь попробуем найти, где узкое место. Я использовал PAPI library для подсчета интересных счетчиков оборудования.

Первый счетчик - это инструкции, сколько инструкций мы фактически тратим? Есть ли разница, когда деревья выглядят иначе?

Разница незначительна. Похоже, что для больших входов левая цепочка требует меньше инструкций, но разница настолько мала, поэтому я думаю, что можно с уверенностью предположить, что оба они требуют одинакового количества инструкций.

Увидев, что мы сохранили дерево в хорошем предваритетном макете внутри TreeArray, имеет смысл увидеть, что происходит в кеше. К сожалению для кеша L1 мой компьютер не предоставляет никаких счетчиков, но у меня есть для L2 и L3.

Посмотрим на доступ к кешу L2. Доступ к кешу L2 происходит, когда мы получаем пропущенную кеш-память L1, так что это косвенный счетчик для пропусков L1.

Как мы видим, правильное дерево требует меньше промахов L1, поэтому кажется, что он эффективно использует кеш.

То же самое для пропусков L2, правильное дерево кажется более эффективным. Все еще ничего не говорит о том, почему правильные деревья растут так медленно. Посмотрите на L3.

В L3 вещи взрываются для правильных деревьев. Таким образом, проблема, похоже, в кэше L3. К сожалению, я не мог объяснить причину такого поведения. Почему в кэше L3 что-то происходит для правильных деревьев?

Вот весь код вместе с экспериментом:

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

Скомпилируйте, набрав g++ -O3 -std=c++11 file.cpp Запустите, набрав ./executable tree.txt. В tree.txt мы сохраняем дерево в новом формате.

Здесь - левое дерево с 10 ^ 5 листьями

Здесь - это правое дерево с листьями 10 ^ 5

Время выполнения: ~ 0.07 секунд для левых деревьев ~ 0.12 секунды для правильных деревьев

Я прошу прощения за длинный пост, но, учитывая, насколько сужен, кажется, проблема, я не мог найти лучшего способа описать это.

Заранее благодарю вас!

EDIT:

Это последующее редактирование после ответа MrSmith42. Я понимаю, что местность играет очень большую роль, но я не уверен, что понимаю, что это так.

Для двух приведенных выше деревьев рассмотрим, как мы получаем доступ к памяти с течением времени.

Для дерева слева:

Для правильного дерева:

Мне кажется, что в обоих случаях мы имеем локальные шаблоны доступа.

EDIT:

Вот сюжет о числе условных ветвей:

Вот сюжет о количестве неверных предсказаний ветки:

Здесь - левое дерево с листьями 10 ^ 6

Здесь - это правое дерево с листьями 10 ^ 6

ЗАВЕРШЕНИЕ:

Я хотел бы извиниться за то, что тратил все время, у синтаксического анализатора, который я использовал, был параметр для того, как "осталось" или "право", я хотел бы, чтобы мое дерево выглядело. Это было плавающее число, оно должно было быть близко к 0, чтобы оно оставалось и приближалось к 1, чтобы сделать это правильно. Однако, чтобы сделать его похожим на цепочку, он должен быть очень маленьким, например 0.000000001 или 0.999999999. Для небольших входов дерево выглядело как цепочка даже для значений типа 0.0001. Я думал, что это число было достаточно маленьким и что оно также даст цепь для больших деревьев, однако, как я покажу, это не так. Если вы используете числа типа 0.000000001, синтаксический анализатор перестает работать из-за проблем с плавающей запятой.

Ответ vadikrobot показал, что у нас есть проблемы с локальностью. Вдохновленный его экспериментом, я решил обобщить диаграмму диаграммы доступа выше, чтобы увидеть, как она ведет себя не только в деревьях примера, но и в любых деревьях.

Я изменил код vadikrobot, чтобы выглядеть так:

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

Шаблоны доступа, созданные неправильным парсером

Посмотрите на левое дерево с 10 листьями.

Выглядит очень красиво, как было предсказано на диаграммах выше (я только забыл на приведенных выше диаграммах тот факт, что, когда мы находим размер node, мы также получаем доступ к параметру размера этого node, cur в исходном коде выше).

Посмотрите на левое дерево с 100 листьями.

Выглядит так, как ожидалось. Что насчет 1000 листьев?

Это определенно не ожидается. В верхнем правом углу есть небольшой треугольник. И причина в том, что дерево не похоже на левую цепочку, в конце концов, где-то в конце висит небольшое поддерево. Проблема становится еще больше, когда листья 10 ^ 4.

Посмотрим, что происходит с правильными деревьями. Когда листья составляют 10:

Выглядит неплохо, около 100 листьев?

Выглядит хорошо. Вот почему я поставил под сомнение местность правильных деревьев, для меня оба казались, по крайней мере, теорией локальными. Теперь, если вы попытаетесь увеличить размер, произойдет что-то интересное:

Для 1000 листов:

Для 10 ^ 4 листьев вещи становятся еще более грязными:

Шаблоны доступа, созданные правильным парсером

Вместо использования этого общего анализатора я создал один для этого конкретного вопроса:

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

Теперь шаблоны доступа выглядят так, как ожидалось.

Для левых деревьев с 10 ^ 4 листьями:

в черной части мы переходим от низкого места к высокому месту, но расстояние между предыдущим низким и текущим низким невелико, то же самое для предыдущего максимума и текущего максимума. Следовательно, кеш должен быть достаточно умным, чтобы удерживать два блока: один для низких мест и один для высоких мест, что дает небольшое количество промахов в кеше.

Для правых деревьев с листьями 10 ^ 4:

Оригинальные эксперименты снова. На этот раз я мог только попробовать до 10 ^ 5 листьев, потому что, как заметил Mystical, мы получим переполнение стека из-за высоты деревьев, чего не было в предыдущих экспериментах, так как высота была меньше той, ожидается.

Разумеется, они кажутся одинаковыми, однако кеш и ветвь не нужны. Правые деревья били левые деревья в предсказаниях ветвей, левые деревья били правильные деревья в кеше.

Возможно, мое использование PAPI было неправильным, выход из perf:

левые деревья:

правые деревья:

Возможно, я снова что-то испортил, и я прошу прощения за это. Я включил свою попытку здесь на случай, если кто-то захочет продолжить расследование.

Ответы

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

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%  )

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%  )