c++ - sistemas - Rendimiento de algoritmo extraño

sistema de recomendacion tesis

Question

Para el contexto, escribí este algoritmo para obtener el número de subcadenas únicas de cualquier cadena. Crea el árbol de sufijos para la cadena que cuenta los nodos que contiene y lo devuelve como la respuesta. El problema que quería resolver requería un algoritmo O (n) , por lo que esta pregunta es solo sobre cómo se comporta este código y no sobre qué tan malo es en lo que hace.

struct node{
    char value = '' '';
    vector<node*> children;
    ~node()
    {
        for (node* child: children)
        {
            delete child;
        }
    }
};

int numberOfUniqueSubstrings(string aString, node*& root)
{
    root = new node();
    int substrings = 0;
    for (int i = 0; i < aString.size(); ++i)
    {
        string tmp = aString.substr(i, aString.size());
        node* currentNode = root;
        char indexToNext = 0;
        for (int j = 0; j < currentNode->children.size(); ++j)
        {
            if (currentNode->children[j]->value == tmp[indexToNext])
            {
                currentNode = currentNode->children[j];
                j = -1;
                indexToNext++;
            }
        }
        for (int j = indexToNext; j < tmp.size(); ++j)
        {
            node* theNewNode = new node;
            theNewNode->value = tmp[j];
            currentNode->children.push_back(theNewNode);
            currentNode = theNewNode;
            substrings++;
        }
    }
    return substrings;
}

Decidí hacer una prueba comparativa de este algoritmo para el que simplemente pasé sobre una cadena grande tomando una subcadena más grande en cada iteración, y numberOfUniqueSusbstrings a numberOfUniqueSusbstrings midiendo el tiempo que tardó en terminar.

Lo dibujé en octava y esto es lo que obtuve ( x es el tamaño de la cadena y y es el tiempo en microsegundos)

Primero pensé que el problema residía en la cadena de entrada, pero es solo una cadena alfanumérica que obtuve de un libro (cualquier otro texto se comporta de forma tan extraña).

También intenté promediar muchas llamadas a la función con el mismo parámetro y el resultado es prácticamente el mismo.

Esto se está compilando con g++ problem.cpp -std=c++14 -O3 pero parece hacer lo mismo en -O2 y -O0 .

Edición: Después de la respuesta de @interjay, he intentado hacer solo aquello que deja la función como:

int numberOfUniqueSubstrings(string aString, node*& root)
{
    root = new node();
    int substrings = 0;
    for (int i = 0; i < aString.size(); ++i)
    {
        node* currentNode = root;
        char indexToNext = i;
        for (int j = 0; j < currentNode->children.size(); ++j)
        {
            if (currentNode->children[j]->value == aString[indexToNext])
            {
                currentNode = currentNode->children[j];
                j = -1;
                indexToNext++;
            }
        }
        for (int j = indexToNext; j < aString.size(); ++j)
        {
            node* theNewNode = new node;
            theNewNode->value = aString[j];
            currentNode->children.push_back(theNewNode);
            currentNode = theNewNode;
            substrings++;
        }
    }
    return substrings;
}

Y de hecho lo hace un poco más rápido. Pero no menos extraño porque planifiqué esto:

Algo está sucediendo en x = 1000 y no tengo ni idea de lo que podría ser.

Otra parcela por si acaso:

Ahora he ejecutado gprof para una cadena de tamaño 999:

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
100.15      0.02     0.02      974    20.56    20.56  node::~node()
  0.00      0.02     0.00   498688     0.00     0.00  void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&)
  0.00      0.02     0.00        1     0.00     0.00  _GLOBAL__sub_I__Z7imprimePK4node
  0.00      0.02     0.00        1     0.00     0.00  numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&)
^L
            Call graph


granularity: each sample hit covers 2 byte(s) for 49.93% of 0.02 seconds

index % time    self  children    called     name
                               54285             node::~node() [1]
                0.02    0.00     974/974         test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
[1]    100.0    0.02    0.00     974+54285   node::~node() [1]
                               54285             node::~node() [1]
-----------------------------------------------
                                                 <spontaneous>
[2]    100.0    0.00    0.02                 test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
                0.02    0.00     974/974         node::~node() [1]
                0.00    0.00       1/1           numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
-----------------------------------------------
                0.00    0.00  498688/498688      numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
[10]     0.0    0.00    0.00  498688         void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&) [10]
-----------------------------------------------
                0.00    0.00       1/1           __libc_csu_init [21]
[11]     0.0    0.00    0.00       1         _GLOBAL__sub_I__Z7imprimePK4node [11]
-----------------------------------------------
                0.00    0.00       1/1           test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
[12]     0.0    0.00    0.00       1         numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
                0.00    0.00  498688/498688      void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&) [10]
-----------------------------------------------

Y para una cadena de tamaño 1001:

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
100.15      0.02     0.02      974    20.56    20.56  node::~node()
  0.00      0.02     0.00   498688     0.00     0.00  void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&)
  0.00      0.02     0.00        1     0.00     0.00  _GLOBAL__sub_I__Z7imprimePK4node
  0.00      0.02     0.00        1     0.00     0.00  numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&)


            Call graph


granularity: each sample hit covers 2 byte(s) for 49.93% of 0.02 seconds

index % time    self  children    called     name
                               54285             node::~node() [1]
                0.02    0.00     974/974         test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
[1]    100.0    0.02    0.00     974+54285   node::~node() [1]
                               54285             node::~node() [1]
-----------------------------------------------
                                                 <spontaneous>
[2]    100.0    0.00    0.02                 test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
                0.02    0.00     974/974         node::~node() [1]
                0.00    0.00       1/1           numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
-----------------------------------------------
                0.00    0.00  498688/498688      numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
[10]     0.0    0.00    0.00  498688         void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&) [10]
-----------------------------------------------
                0.00    0.00       1/1           __libc_csu_init [21]
[11]     0.0    0.00    0.00       1         _GLOBAL__sub_I__Z7imprimePK4node [11]
-----------------------------------------------
                0.00    0.00       1/1           test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
[12]     0.0    0.00    0.00       1         numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
                0.00    0.00  498688/498688      void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&) [10]
-----------------------------------------------


Index by function name

  [11] _GLOBAL__sub_I__Z7imprimePK4node [1] node::~node()
  [12] numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [10] void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&)

Sin embargo, parece que la ejecución del generador de perfiles elimina el efecto y los tiempos son prácticamente iguales en ambos casos.

Answer 1

La hipótesis de trabajo de la mayoría de las personas parece ser que hay algún tipo de número mágico codificado en las bibliotecas que resulta en una transición de fase en el rendimiento alrededor de 999-1000 (a excepción de LSerni, quien hace la observación de que puede haber múltiples números mágicos).

Intentaré explorar sistemáticamente esta y otras hipótesis a continuación (el código fuente está disponible al final de esta respuesta).

Luego ejecuté mi código para ver si podía duplicar sus resultados en mi CPU Intel (R) Core (TM) i5 M480, Linux 4.8.0-34-genérico, usando G ++ 6.2.0-5ubuntu2 como mi compilador con -O3 optimizaciones

Efectivamente, hay una gota mágica de 999-1000 (y otra cerca de 1600):

Tenga en cuenta que mi conjunto de datos Trans-1000 no es tan limpio como el suyo: esto puede deberse a que estoy jugando con algunas otras cosas en segundo plano en mi máquina, mientras que tenía un entorno de prueba más silencioso.

Mi siguiente pregunta fue: ¿es este número 1000 mágico estable entre entornos?

Así que intenté ejecutar el código en una máquina Intel (R) Xeon (R) CPU E5-2680 v3, Linux 2.6.32-642.6.1.el6.x86_64, utilizando G ++ 4.9.2. Y, como era de esperar, el número mágico era diferente, ocurriendo en 975-976:

Esto nos dice que, si había un número mágico, se cambia entre versiones. Esto disminuye mi confianza en la teoría del número mágico por varias razones. (a) Cambia. (b) 1000 + 24 bytes de sobrecarga es un buen candidato para la magia. 975 + 49 bytes lo es menos. (c) El primer entorno tiene mejor software en un procesador más lento, pero el primer entorno muestra lo que consideraría un peor desempeño: esperar hasta 1000 para acelerar las cosas. Esto parece una regresión.

Probé una prueba diferente: ejecutar el programa con diferentes datos de entrada aleatorios. Eso da este resultado:

El punto saliente en el gráfico anterior es que la caída de 999-1000 no es tan especial. Se parece a muchas de las gotas anteriores: una lenta disminución de la velocidad seguida por una mejora brusca. También vale la pena señalar que muchas de las caídas anteriores no se alinean.

Esto me sugirió que este es un comportamiento dependiente de la entrada y que existe una correlación entre las ejecuciones. Por lo tanto, me pregunté qué pasaría si redujera la correlación entre ejecuciones aleatorizando su orden. Esto dio:

Algo sigue sucediendo alrededor del 999-1000:

Vamos a ampliar aún más :

Ejecutar esto en la computadora más rápida con el software anterior da un resultado similar:

Zoom:

Dado que la asignación aleatoria del orden en el que se consideran cadenas de diferentes longitudes elimina esencialmente la lenta acumulación entre ejecuciones (la correlación mencionada anteriormente), esto sugiere que el fenómeno que se está viendo requiere algún tipo de estado global. Por lo tanto, C ++ cadena / vector no puede ser una explicación. Por lo tanto, malloc, "el sistema operativo" o restricciones arquitectónicas deben ser la explicación.

Tenga en cuenta que cuando el orden de longitudes es aleatorio, hay un punto en el que el código se ejecuta más lento en lugar de más rápido. En mi opinión, esto es consistente con la superación de algún tipo de tamaño de caché, pero el ruido en la señal junto con el primer gráfico en este post también sugiere una posible fragmentación de la memoria. Por lo tanto, decidí reiniciar el programa antes de cada ejecución para asegurar un nuevo montón. Eso resultó en lo siguiente:

Y ahora vemos que no hay más roturas ni saltos. Esto sugiere que el tamaño del caché no era el problema, sino que el comportamiento observado tiene algo que ver con el uso de memoria general del programa.

Otro argumento contra un efecto de caché es el siguiente. Ambas máquinas tienen cachés L1 y L2 de 32 kB y 256 kB, por lo que su rendimiento de caché debería ser similar. Mi máquina lenta tiene un caché L3 de 3.072kB. Si asume una página de 4kB por asignación, 1000 nodos otorga 4,000kB asignados, lo cual está cerca del tamaño del caché. Sin embargo, la máquina rápida tiene una memoria caché L3 de 30,720 kB y muestra una ruptura en 975. Si el fenómeno fuera un efecto de caché, se esperaría que la ruptura, en todo caso, se produzca más tarde. Por lo tanto, estoy bastante seguro de que el almacenamiento en caché no funciona aquí.

El único culpable que queda es malloc.

¿Por qué está pasando esto? No estoy seguro. Pero, como programador, no me importa, como sigue.

Probablemente haya una explicación para esto, pero está en un nivel que es demasiado profundo para cambiarlo o realmente preocuparse. Podría hacer algo exótico para arreglarlo, pero eso requeriría pensar en lo que está pasando en algún lugar en su bajo vientre oscuro. Usamos lenguajes de nivel superior como C ++ específicamente para evitar meternos con ese tipo de detalles a menos que realmente tengamos que hacerlo.

Y mis resultados dicen que no tenemos que hacerlo en este caso. (a) El último gráfico nos dice que es probable que cualquier ejecución independiente del código muestre un comportamiento casi óptimo, (b) la ejecución aleatoria secuencial puede nivelar el rendimiento, y (c) la pérdida de eficiencia es del orden de una centésima parte de un segundo, que es totalmente aceptable a menos que esté procesando grandes cantidades de datos.

El código fuente sigue. Tenga en cuenta que el código cambia el char indexToNext de char indexToNext su versión a char indexToNext a int indexToNext , solucionando posibles problemas de desbordamiento de enteros. Probar la sugerencia de interjay de que evitamos hacer copias de la cadena en realidad resultó en un peor desempeño.

#include <string>
#include <chrono>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <time.h>
#include <algorithm>

struct profiler
{
  std::string name;
  std::chrono::high_resolution_clock::time_point p;
  profiler(std::string const &n) :
      name(n), p(std::chrono::high_resolution_clock::now()) { }
  ~profiler()
  {
      using dura = std::chrono::duration<double>;
      auto d = std::chrono::high_resolution_clock::now() - p;
      std::cout //<< name << ": "
          << std::chrono::duration_cast<dura>(d).count()
          << std::endl;
  }
};

#define PROFILE_BLOCK(pbn) profiler _pfinstance(pbn)

struct node {
  char value = '' '';
  std::vector<node*> children;
  ~node(){
    for (node* child: children)
      delete child;
  }
};

int numberOfUniqueSubstrings(const std::string aString, node*& root)
{
    root = new node();
    int substrings = 0;
    for (int i = 0; i < aString.size(); ++i)
    {
        node* currentNode = root;
        int indexToNext = i;
        for (int j = 0; j < currentNode->children.size(); ++j)
        {
            if (currentNode->children[j]->value == aString[indexToNext])
            {
                currentNode = currentNode->children[j];
                j = -1;
                indexToNext++;
            }
        }
        for (int j = indexToNext; j < aString.size(); ++j)
        {
            node* theNewNode  = new node;
            theNewNode->value = aString[j];
            currentNode->children.push_back(theNewNode);
            currentNode = theNewNode;
            substrings++;
        }
    }
    return substrings;
}


int main(int argc, char **argv){
  const int MAX_LEN = 1300;

  if(argc==1){
    std::cerr<<"Syntax: "<<argv[0]<<"<SEED> [LENGTH]"<<std::endl;
    std::cerr<<"Seed of -1 implies all lengths should be explore and input randomized from time."<<std::endl;
    std::cerr<<"Positive seed sets the seed and explores a single input of LENGTH"<<std::endl;
    return -1;
  }

  int seed = std::stoi(argv[1]);

  if(seed==-1)
    srand(time(NULL));
  else
    srand(seed);

  //Generate a random string of the appropriate length
  std::string a;
  for(int fill=0;fill<MAX_LEN;fill++)
      a.push_back(''a''+rand()%26);

  //Generate a list of lengths of strings to experiment with
  std::vector<int> lengths_to_try;
  if(seed==-1){
    for(int i=1;i<MAX_LEN;i++)
      lengths_to_try.push_back(i);
  } else {  
    lengths_to_try.push_back(std::stoi(argv[2]));
  }

  //Enable this line to randomly sort the strings
  std::random_shuffle(lengths_to_try.begin(),lengths_to_try.end());

  for(auto len: lengths_to_try){
    std::string test(a.begin(),a.begin()+len);

    std::cout<<len<<" ";
    {
      PROFILE_BLOCK("Some time");
      node *n;
      int c = numberOfUniqueSubstrings(test,n);
      delete n;
    }
  }
}

substr es una "constante"

El código original de OP incluía lo siguiente:

for (int i = 0; i < aString.size(); ++i)
{
  string tmp = aString.substr(i, aString.size());

La operación de substr aquí toma tiempo O(n) en la longitud de la cadena. En una respuesta a continuación , se argumenta que esta operación O(n) da como resultado el bajo rendimiento del código original de OP.

No estoy de acuerdo con esta evaluación. Debido al almacenamiento en caché y las operaciones SIMD, las CPU pueden leer y copiar datos en bloques de hasta 64 bytes (¡o más!). Debido a esto, los costos de asignación de memoria pueden dominar el costo de copiar la cadena. Por lo tanto, para los tamaños de entrada de OP, la operación substr actúa más como una constante costosa que un bucle adicional.

Esto se puede demostrar mediante pruebas compilando el código con, por ejemplo, g++ temp.cpp -O3 --std=c++14 -g y perfilando con, por ejemplo, sudo operf ./a.out -1 . El perfil de uso del tiempo resultante se ve así:

25.24%  a.out    a.out                [.] _ZN4nodeD2Ev        #Node destruction                                                                           
24.77%  a.out    libc-2.24.so         [.] _int_malloc                                                                                    
13.93%  a.out    libc-2.24.so         [.] malloc_consolidate                                                                            
11.06%  a.out    libc-2.24.so         [.] _int_free                                                                                      
 7.39%  a.out    libc-2.24.so         [.] malloc                                                                                        
 5.62%  a.out    libc-2.24.so         [.] free                                                                                          
 3.92%  a.out    a.out                [.] _ZNSt6vectorIP4nodeSaIS1_EE19_M_emplace_back_auxIJRKS1_EEEvDpOT_                              
 2.68%  a.out    a.out                [.]
 8.07%  OTHER STUFF

De lo cual es evidente que la administración de memoria domina el tiempo de ejecución.

Answer 2

Yo sospecharía de malloc más que de string o vector . Es completamente posible que trate <1000 bytes y> 1000 bytes de manera diferente. La coalescencia de bloques liberados puede ser costosa. Puede abstenerse de tratar de unir los bloques más grandes (es decir, manteniéndolos en grupos). Pero esto es realmente sólo una conjetura. ¿Por qué no pruebas un perfilador y obtienes datos reales? gprof es fácil de usar.

Este artículo tiene algunos detalles interesantes sobre glibc malloc . Si eso es lo que está bajo el capó de su programa, las diferencias entre los tipos de contenedores descritos allí podrían estar en el trabajo. De hecho, los trozos se liberan a un "contenedor sin clasificar" que ocasionalmente se reorganiza. Es posible que las puntas sean estas reorganizaciones para evitar el crecimiento del montón. Si esa teoría es correcta, entonces el suavizado podría ser el resultado del crecimiento de la arena del montón a un tamaño donde la reorganización no es tan costosa.

Pero, de nuevo, esta es toda una conjetura que se puede resolver ejecutando el generador de perfiles para ver a dónde va el tiempo en <1000 vs> 1000.

Answer 3

for (int i = 0; i < aString.size(); ++i)
{
    string tmp = aString.substr(i, aString.size());

Esto ya hace que su algoritmo O (n ^ 2) o peor. La llamada a substr crea una subcadena de tamaño n/2 en promedio, por lo que toma O (n) y se llama n veces.

Parece que en realidad no necesitas la cadena tmp ya que solo lees de ella. En su lugar, lea de la cadena original pero cambie su indexación en consecuencia.

El bucle for (int j = indexToNext; j < tmp.size(); ++j) probablemente también le dará a su algoritmo O (n ^ 2) tiempo total (digo "probablemente" porque depende del valor calculado de indexToNext , pero a partir de las pruebas con cadenas aleatorias parece ser cierto). Se ejecuta O (n) veces, y cada vez llevará hasta O (n) iteraciones.