c++ - los - ¿Por qué DFS es más lento en un árbol y más rápido en el otro?

no me funcionan los hashtags en instagram 2018

Question

ACTUALIZACIÓN: Resulta que hubo un error en el analizador sintáctico que generó los árboles. Más en edición final.

Deje T ser un árbol binario tal que cada nodo interno tenga exactamente dos hijos. Para este árbol, queremos codificar una función que para cada nodo v en T encuentre la cantidad de nodos en el subárbol definido por v .

Ejemplo

Entrada

Salida deseada

Con rojo, indico los números que queremos calcular. Los nodos del árbol se almacenarán en una matriz, vamos a llamarlo TreeArray siguiendo el diseño de preorden.

Para el ejemplo anterior, TreeArray contendrá los siguientes objetos:

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

Un nodo del árbol se describe mediante la siguiente estructura:

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

};

La función para calcular todos los valores de size es la siguiente:

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;

}

Me gustaría entender por qué esta función es más rápida cuando T ve así (casi como una cadena de la izquierda):

y más lento cuando T ve así (casi como una cadena de derecha):

Los siguientes experimentos se realizaron en Intel (R) Core (TM) i5-3470 CPU @ 3.20GHz con 8 GB de RAM, caché L1 de 256 KB, caché L2 de 1 MB, caché L3 de 6 MB.

Cada punto en los gráficos es el resultado del siguiente ciclo for (los parámetros están definidos por el eje):

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

n corresponde al número total de nodos, y el tiempo se mide en segundos. Como podemos ver, está claro que a medida que n crece, la función es mucho más rápida cuando el árbol se ve como una cadena que se va, a pesar de que el número de nodos es exactamente el mismo en ambos casos.

Ahora tratemos de encontrar dónde está el cuello de botella. Usé la biblioteca PAPI para contar contadores de hardware interesantes.

El primer contador son las instrucciones, ¿cuántas instrucciones realmente gastamos? ¿Hay alguna diferencia cuando los árboles se ven diferentes?

La diferencia no es significante. Parece que para grandes entradas, la cadena izquierda requiere menos instrucciones, pero la diferencia es muy pequeña, por lo que creo que es seguro asumir que ambas requieren el mismo número de instrucciones.

Al ver que hemos almacenado el árbol en un bonito diseño de orden previo dentro de treeArray , tiene sentido ver qué está sucediendo en la memoria caché. Desafortunadamente para la memoria caché L1 mi computadora no proporciona ningún contador, pero tengo para L2 y L3.

Veamos los accesos a la memoria caché L2. Los accesos a la memoria caché L2 se producen cuando obtenemos una falla en la caché L1, por lo que es un contador indirecto para la falla L1 también.

Como podemos ver, el árbol correcto requiere menos errores L1, por lo que parece que usa el caché de manera eficiente.

Lo mismo para L2 falla, el árbol correcto parece ser más eficiente. Todavía no hay nada que indique por qué los árboles correctos son más lentos. Miremos a L3.

En L3, las cosas explotan para los árboles correctos. Entonces el problema parece estar en la memoria caché L3. Desafortunadamente no pude explicar la razón detrás de este comportamiento. ¿Por qué las cosas se arruinan en caché L3 para los árboles correctos?

Aquí está el código completo junto con el experimento:

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

Para compilar, escriba g++ -O3 -std=c++11 file.cpp Ejecute escribiendo ./executable tree.txt . En tree.txt almacenamos el árbol en el formato newick .

Here hay un árbol izquierdo con 10 ^ 5 hojas

Here hay un árbol correcto con 10 ^ 5 hojas

Los tiempos de carrera que obtengo son: ~ 0.07 segundos para los árboles que quedan, ~ 0.12 segundos para los árboles correctos

Me disculpo por la publicación larga, pero dado lo limitado que parece ser el problema, no pude encontrar una mejor manera de describirlo.

¡Gracias de antemano!

EDITAR:

Esta es una edición de seguimiento después de la respuesta de MrSmith42. Entiendo que la localidad juega un papel muy importante, pero no estoy seguro de entender que este es el caso aquí.

Para los dos árboles de ejemplo anteriores, veamos cómo accedemos a la memoria a lo largo del tiempo.

Para el árbol que se va:

Para el árbol correcto:

Para mí, parece que en ambos casos tenemos patrones de acceso local.

EDITAR:

Aquí hay un argumento sobre el número de ramas condicionales:

Aquí hay una trama sobre el número de errores de predicción de ramas:

Here hay un árbol que se va con 10 ^ 6 hojas

Here hay un árbol correcto con 10 ^ 6 hojas

EDICION FINAL:

Me gustaría disculparme por desperdiciar el tiempo de todos, el analizador que estaba usando tenía un parámetro sobre cómo me gustaría "izquierda" o "derecha" hacer que mi árbol se pareciera. Ese era un número flotante, tenía que estar cerca de 0 para que se dejara ir y cerca de 1 para hacerlo funcionar correctamente. Sin embargo, para que se vea como una cadena, tenía que ser muy pequeña, como 0.000000001 o 0.999999999 . Para entradas pequeñas, el árbol parecía una cadena incluso para valores como 0.0001 . Pensé que este número era lo suficientemente pequeño y que también daría una cadena para árboles más grandes, sin embargo, como mostraré, no es el caso. Si usa números como 0.000000001 el analizador deja de funcionar debido a problemas de coma flotante.

La respuesta de vadikrobot mostró que tenemos problemas de localidad. Inspirado por su experimento, decidí generalizar el diagrama del patrón de acceso anterior para ver cómo se comporta no solo en los árboles de ejemplo, sino en cualquier árbol.

Modifiqué el código de vadikrobot para que se vea así:

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

Patrones de acceso generados por el analizador incorrecto

Miremos un árbol izquierdo con 10 hojas.

Se ve muy bien, como se predijo en los diagramas anteriores (solo olvidé en los diagramas anteriores el hecho de que cuando encontramos el tamaño de un nodo, también accedemos al parámetro de tamaño de ese nodo, cur en el código fuente anterior).

Miremos un árbol izquierdo con 100 hojas.

Se ve como se esperaba ¿Qué hay de las 1000 hojas?

Esto definitivamente no es esperado. Hay un pequeño triángulo en la esquina superior derecha. Y la razón es que el árbol no se ve como una cadena de la izquierda, hay un pequeño subárbol colgando en algún lugar al final. El problema se agrava cuando las hojas son 10 ^ 4.

Miremos lo que sucede con los árboles correctos. Cuando las hojas son 10:

Se ve bien, ¿qué hay de 100 hojas?

Se ve bien también. Es por eso que cuestioné la localidad de los árboles correctos, para mí ambos parecían al menos teoría local. Ahora, si intentas aumentar el tamaño, sucede algo interesante:

Para 1000 hojas:

Para 10 ^ 4 hojas las cosas se vuelven aún más desordenadas:

Patrones de acceso generados por el analizador correcto

En lugar de usar ese analizador general, creé uno para esta pregunta específica:

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

Ahora los patrones de acceso se ven como se esperaba.

Para árboles abandonados con 10 ^ 4 hojas:

en la parte negra pasamos de un lugar bajo a un lugar alto, pero la distancia entre el bajo anterior y el mínimo actual es pequeña, igual para el alto anterior y el alto actual. Por lo tanto, la memoria caché debe ser lo suficientemente inteligente como para contener dos bloques, uno para los lugares bajos y otro para los lugares altos, dando una pequeña cantidad de errores de caché.

Para árboles correctos con 10 ^ 4 hojas:

Los experimentos originales otra vez . Esta vez solo pude probar hasta 10 ^ 5 hojas, porque como Mysticial notó, obtendremos un desbordamiento de la pila debido a la altura de los árboles, que no era el caso en los experimentos anteriores ya que la altura era más pequeña que la esperado.

En cuanto al tiempo, parecen realizar lo mismo, sin embargo, el caché y la rama no. Los árboles correctos golpean los árboles de la izquierda en las predicciones de ramas, los árboles de la izquierda golpean los árboles correctos en la memoria caché.

Tal vez mi uso de PAPI ha sido incorrecto, resultado de perf:

árboles abandonados:

árboles correctos:

Podría haber arruinado algo de nuevo, y me disculpo por esto. Incluí mi intento aquí por si acaso alguien quiere continuar investigando.

Answer 1

ACTUALIZAR:

Tracé el número de elementos accedidos en el arreglo en el tiempo

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

como resultado tramo el elemento 999990 del archivo de texto resultante:

Puede ver que para el árbol de la izquierda se accede localmente a todos los elementos, pero para el derecho existe falta de uniformidad en el acceso.

ANTIGUO:

Traté de calcular el número de lecturas de memoria usando valgrind. para la derecha

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

y para el izquierdo

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

Como puede ver, la cantidad de memoria es "rd" en el caso "más grande" que en el izquierdo

Answer 2

Los fallos de caché son diferentes debido a la ubicación de los nodos en nuestra memoria. Si accede a los nodos en el orden en que se encuentran en la memoria, es probable que la memoria caché ya los haya cargado desde el ram en la memoria caché (porque las páginas de memoria caché de carga (probablemente más grande que uno de sus nodos)).

Si accede a los nodos en orden aleatorio (en perspectiva a la posición en la RAM) o en orden inverso, es más probable que la memoria caché aún no los haya cargado desde la RAM.

Entonces, la diferencia no se debe a la estructura de su árbol, sino a la posición de los nodos de árbol en su RAM en comparación con el orden en que desea acceder a ellos.

EDITAR: (después de agregar el patrón de acceso a la pregunta):

Como puede ver en su gráfico de patrón de acceso:
En el "árbol izquierdo", el acceso salta de índices bajos a altos después de aproximadamente la mitad de los accesos. Entonces, la segunda mitad probablemente siempre dará lugar a errores de caché a medida que la distancia crece y crece.
En el "árbol correcto", la segunda mitad tiene al menos 2 nodos cerca uno del otro (en orden de acceso) y también los dos siguientes tienen algo de suerte en la misma página del caché.