¿Existe alguna documentación que compare / contraste las implementaciones de la biblioteca estándar de C ++? [cerrado]

16

(Esta no es una programación de juegos per se, pero estoy seguro de que si preguntara esto en SO, me dirían que no optimice prematuramente, a pesar de que la historia nos dice que cada juego grande termina preocupándose por estas cosas).

¿Existe algún documento en alguna parte que resuma las diferencias en el rendimiento, y particularmente el uso de memoria, entre diferentes implementaciones de bibliotecas estándar de C ++? Los detalles de algunas implementaciones están protegidos por NDA, pero una comparación entre incluso STLport vs. libstdc ++ vs. libc ++ vs. MSVC / Dinkumware (vs. ¿EASTL?) Parece ser inmensamente útil.

En particular, estoy buscando respuestas a preguntas como:

  • ¿Cuánta sobrecarga de memoria se asocia con los contenedores estándar?
  • ¿Qué contenedores, si los hay, hacen asignaciones dinámicas simplemente por ser declarados?
  • ¿Std :: string hace copia en escritura? ¿Optimización de cadena corta? Cuerdas?
  • ¿Std :: deque utiliza un buffer de anillo o es basura?
c++ performance memory-efficiency
fuente
Tenía la impresión de que dequesiempre se implementaba en el STL con un vector.
Tetrad
@Tetrad: Hasta hace unas semanas, yo también lo estaba, pero luego leí que a menudo lo implementaba una estructura tipo cuerda, y eso parece ser lo que hay en STLport.
El STL tiene un borrador de trabajo abierto , que se puede utilizar para encontrar información sobre las diversas estructuras de datos (tanto secuenciales como asociativas), algoritmos y clases auxiliares implementadas. Sin embargo, parece ser que la sobrecarga de memoria es específica de la implementación, en lugar de la especificación definida.
Thomas Russell
3
@Duck: El desarrollo de juegos es el único lugar que conozco que utiliza regularmente funciones de C ++ de alto nivel, pero necesita rastrear meticulosamente las asignaciones de memoria porque se ejecuta en sistemas de poca memoria sin memoria virtual. Cada respuesta individual en SO sería "no optimices prematuramente, el STL está bien, ¡úsalo!" - El 50% de las respuestas aquí hasta ahora son eso, y sin embargo, la prueba de Maik muestra claramente una gran preocupación por los juegos que desean usar std :: map, y la confusión de Tetrad y la mía sobre las implementaciones comunes de std :: deque también.
2
@ Joe Wreschnig Realmente no quiero votar para cerrar porque estoy interesado en el resultado de esto. : p
El pato comunista

Respuestas:

6

En caso de que no encuentre dicho cuadro de comparación, la alternativa es inyectar un asignador propio a las clases STL en cuestión y agregar un poco de registro.

La implementación que probé (VC 8.0) no usa asignación de memoria simplemente declarando una cadena / vector / deque, pero para ello enumera y asigna. La cadena tiene una optimización de cadena corta, ya que agregar 3 caracteres no activó una asignación. La salida se agrega debajo del código.

// basic allocator implementation used from here
// http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4079

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <map>

template <class T> class my_allocator;

// specialize for void:
template <> 
class my_allocator<void> 
{
public:
    typedef void*       pointer;
    typedef const void* const_pointer;
    // reference to void members are impossible.
    typedef void value_type;
    template <class U> 
    struct rebind 
    { 
        typedef my_allocator<U> other; 
    };
};

#define LOG_ALLOC_SIZE(call, size)      std::cout << "  " << call << "  " << std::setw(2) << size << " byte" << std::endl

template <class T> 
class my_allocator 
{
public:
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;
    typedef T*        pointer;
    typedef const T*  const_pointer;
    typedef T&        reference;
    typedef const T&  const_reference;
    typedef T         value_type;
    template <class U> 
    struct rebind 
    { 
        typedef my_allocator<U> other; 
    };

    my_allocator() throw() : alloc() {}
    my_allocator(const my_allocator&b) throw() : alloc(b.alloc) {}

    template <class U> my_allocator(const my_allocator<U>&b) throw() : alloc(b.alloc) {}
    ~my_allocator() throw() {}

    pointer       address(reference x) const                    { return alloc.address(x); }
    const_pointer address(const_reference x) const              { return alloc.address(x); }

    pointer allocate(size_type s, 
               my_allocator<void>::const_pointer hint = 0)      { LOG_ALLOC_SIZE("my_allocator::allocate  ", s * sizeof(T)); return alloc.allocate(s, hint); }
    void deallocate(pointer p, size_type n)                     { LOG_ALLOC_SIZE("my_allocator::deallocate", n * sizeof(T)); alloc.deallocate(p, n); }

    size_type max_size() const throw()                          { return alloc.max_size(); }

    void construct(pointer p, const T& val)                     { alloc.construct(p, val); }
    void destroy(pointer p)                                     { alloc.destroy(p); }

    std::allocator<T> alloc;
};

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

    {
        typedef std::basic_string<char, std::char_traits<char>, my_allocator<char> > my_string;

        std::cout << "===============================================" << std::endl;
        std::cout << "my_string ctor start" << std::endl;
        my_string test;
        std::cout << "my_string ctor end" << std::endl;
        std::cout << "my_string add 3 chars" << std::endl;
        test = "abc";
        std::cout << "my_string add a huge number of chars chars" << std::endl;
        test += "d df uodfug ondusgp idugnösndögs ifdögsdoiug ösodifugnösdiuödofu odsugöodiu niu od unoudö n nodsu nosfdi un abc";
        std::cout << "my_string copy" << std::endl;
        my_string copy = test;
        std::cout << "my_string copy on write test" << std::endl;
        copy[3] = 'X';
        std::cout << "my_string dtors start" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "vector ctor start" << std::endl;
        std::vector<int, my_allocator<int> > v;
        std::cout << "vector ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            v.push_back(i);
        }
        std::cout << "vector dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "deque ctor start" << std::endl;
        std::deque<int, my_allocator<int> > d;
        std::cout << "deque ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "deque insert start" << std::endl;
            d.push_back(i);
            std::cout << "deque insert end" << std::endl;
        }
        std::cout << "deque dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "list ctor start" << std::endl;
        std::list<int, my_allocator<int> > l;
        std::cout << "list ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "list insert start" << std::endl;
            l.push_back(i);
            std::cout << "list insert end" << std::endl;
        }
        std::cout << "list dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "map ctor start" << std::endl;
        std::map<int, float, std::less<int>, my_allocator<std::pair<const int, float> > > m;
        std::cout << "map ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "map insert start" << std::endl;
            std::pair<int, float> a(i, (float)i);
            m.insert(a);
            std::cout << "map insert end" << std::endl;
        }
        std::cout << "map dtor starts" << std::endl;
    }

    return 0;
}

Hasta ahora VC8 y STLPort 5.2 probados, aquí está la comparación (incluida en la prueba: cadena, vector, deque, lista, mapa)

                    Allocation on declare   Overhead List Node      Overhead Map Node

VC8                 map, list               8 Byte                  16 Byte
STLPort 5.2 (VC8)   deque                   8 Byte                  16 Byte
Paulhodge's EASTL   (none)                  8 Byte                  16 Byte

Cadena de salida VC8 / vector / deque / list / map:

===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
my_string add a huge number of chars chars
  my_allocator::allocate    128 byte
my_string copy
  my_allocator::allocate    128 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  128 byte
  my_allocator::deallocate  128 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    12 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate  12 byte
  my_allocator::allocate    24 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  24 byte

===============================================
deque ctor start
deque ctor end
deque insert start
  my_allocator::allocate    32 byte
  my_allocator::allocate    16 byte
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
  my_allocator::allocate    16 byte
deque insert end
deque dtor starts
  my_allocator::deallocate  16 byte
  my_allocator::deallocate  16 byte
  my_allocator::deallocate  32 byte

===============================================
list ctor start
  my_allocator::allocate    12 byte
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
  my_allocator::allocate    24 byte
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte

STLPort 5.2. salida compilada con VC8

===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
my_string add a huge number of chars chars
  my_allocator::allocate    115 byte
my_string copy
  my_allocator::allocate    115 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  115 byte
  my_allocator::deallocate  115 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::deallocate   0 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    32 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  32 byte

===============================================
deque ctor start
  my_allocator::allocate    32 byte
  my_allocator::allocate    128 byte
deque ctor end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque dtor starts
  my_allocator::deallocate  128 byte
  my_allocator::deallocate  32 byte

===============================================
list ctor start
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte

Resultados EASTL , no hay deque disponible

===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
  my_allocator::allocate     9 byte
my_string add a huge number of chars chars
  my_allocator::allocate    115 byte
  my_allocator::deallocate   9 byte
my_string copy
  my_allocator::allocate    115 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  115 byte
  my_allocator::deallocate  115 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    32 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  32 byte

===============================================
list ctor start
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
Maik Semder
fuente
Esto es útil para obtener los detalles de las asignaciones subyacentes, pero desafortunadamente no nos dice nada sobre la sobrecarga y el rendimiento esperado de la caché.
@ Joe, es difícil responder a todas sus preguntas en una sola respuesta. No estoy seguro de qué quieres decir exactamente con "gastos generales" y, además, ¿en comparación con qué? Pensé que por gastos generales te refieres al consumo de memoria.
Maik Semder
Por "gastos generales" me refería más al tamaño de las instancias vacías de las estructuras y todos sus iteradores asociados, y cómo los más complicados manejan la asignación, por ejemplo, std :: list asigna internamente más de un nodo a la vez, o lo hago pagar el costo de asignación base para cada nodo, etc.
1
La pregunta no es tanto "Por favor haga esta comparación" como "dónde hay un recurso para esta comparación". No creo que SO sea un buen lugar para "mantenerla". Quizás deberías comenzar a lanzarlo en un sitio de Google o wiki o algo así.
1
@Joe bueno ahora está aquí: p No estoy muy interesado en moverlo a otro sitio, solo estaba interesado en los resultados.
Maik Semder
8

std::stringno hace copia en escritura. CoW solía ser una optimización, pero tan pronto como varios hilos ingresan a la imagen, está más allá de una pesimismo: puede ralentizar el código por factores masivos. Es tan malo que el estándar C ++ 0x lo prohíbe activamente como estrategia de implementación. No solo eso, sino que la permisividad de std::stringdistribuir iteradores mutables y referencias de caracteres significa que "escribir" std::stringimplica casi todas las operaciones.

La optimización de cadenas cortas es de aproximadamente 6 caracteres, creo, o algo así en esa región. Las cuerdas no están permitidas, std::stringdeben almacenar memoria contigua para la c_str()función. Técnicamente, podría mantener una cuerda contigua y una cuerda en la misma clase, pero nadie lo hizo. Además, por lo que sé de las cuerdas, hacerlas seguras para manipularlas sería increíblemente lento, tal vez tan malo o peor que CoW.

Ningún contenedor realiza la asignación de memoria al declararse en STL modernos. Los contenedores basados ​​en nodos como list y map solían hacerlo, pero ahora tienen una optimización final integrada y no la necesitan. Es común realizar una optimización llamada "swaptimization" donde intercambia con un contenedor vacío. Considerar:

std::vector<std::string> MahFunction();
int main() {
    std::vector<std::string> MahVariable;
    MahFunction().swap(MahVariable);
}

Por supuesto, en C ++ 0x esto es redundante, pero en C ++ 03, cuando esto se usaba comúnmente, si MahVariable asigna memoria en la declaración, entonces reduce la efectividad. Sé con vectorcerteza que esto se usó para reasignaciones más rápidas de contenedores como en el MSVC9 STL que eliminó la necesidad de copiar los elementos.

dequeutiliza algo que se conoce como una lista vinculada desenrollada. Básicamente es una lista de matrices, generalmente de tamaño fijo en el nodo. Como tal, para la mayoría de los usos, conserva los beneficios de ambas estructuras de datos: acceso contiguo y eliminación de O (1) amortizada, y puede agregar tanto a la anulación frontal como posterior y una mejor invalidación del iterador que vector. dequenunca se puede implementar por vector debido a su complejidad algorítmica y a las garantías de invalidación de iterador.

¿Cuánta sobrecarga de memoria está asociada? Bueno, sinceramente, es una pregunta un poco inútil. Los contenedores STL están diseñados para ser eficientes, y si replicaras su funcionalidad, terminarías con algo que funciona peor o en el mismo lugar nuevamente. Al conocer sus estructuras de datos subyacentes, puede conocer la sobrecarga de memoria que usan, dan o toman, y solo será más que eso por una buena razón, como la optimización de cadenas pequeñas.

DeadMG
fuente
"Es tan malo que el estándar C ++ 0x lo prohíbe activamente como estrategia de implementación". Y lo prohíben porque las implementaciones anteriores lo usaron o trataron de usarlo. Aparentemente, vives en un mundo donde todo el mundo usa el último STL implementado de manera óptima todo el tiempo. Esta respuesta no es de ninguna ayuda.
También tengo curiosidad por saber qué propiedades de std :: deque crees que impiden un almacenamiento subyacente contiguo: los iteradores solo son válidos después de las eliminaciones al inicio / final, no en el medio ni después de cualquier inserción, que se puede hacer fácilmente con un vector. Y el uso de un búfer circular parece cumplir con todas las garantías algorítmicas: O (1) amortiguado insertar y eliminar en los extremos, O (n) eliminar en el medio.
3
@ Joe: Creo que se ha observado que CoW es algo malo desde finales de los 90. Hay implementaciones de cadenas que lo usaron, especialmente CString, pero eso no significa que std::stringlo hicieran en ese momento. No tiene que estar utilizando las últimas y mejores implementaciones de STL para eso. msdn.microsoft.com/en-us/library/22a9t119.aspx dice "Si se inserta un elemento en la parte delantera, todas las referencias siguen siendo válidas". No estoy seguro de cómo piensa implementar eso con un búfer circular, ya que necesitará cambiar el tamaño cuando se llene.
DeadMG
gotw.ca/publications/optimizations.htm . Julio de 1999.
DeadMG
Ciertamente no voy a defender a COW como una técnica de implementación, pero tampoco soy ingenuo en cuanto a la frecuencia con la que el software continúa siendo implementado usando técnicas pobres mucho después de que se identifican como pobres. Por ejemplo, la prueba anterior de Maik revela un stdlib moderno que se asigna en la declaración. Gracias por el puntero sobre la validez de referencia de deque. (Para nitpick, un vector puede cumplir con todas las garantías sobre la invalidación del iterador y la complejidad algorítmica; ese requisito no es ninguno.) En todo caso, veo esto como una necesidad adicional de un documento como mi pregunta.
2

La pregunta no es tanto "Por favor haga esta comparación" como "dónde hay un recurso para esta comparación"

Si esa es realmente su pregunta (que seguramente no es lo que dijo en el texto de su pregunta real, que terminó en 4 preguntas, ninguna de las cuales preguntaba dónde podría encontrar un recurso), entonces la respuesta es simplemente:

No hay uno

La mayoría de los programadores de C ++ no tienen que preocuparse demasiado por la sobrecarga de las estructuras de la biblioteca estándar, el rendimiento de la caché de ellas (que de todos modos depende mucho del compilador) o ese tipo de cosas. Sin mencionar que, por lo general, no puede elegir la implementación de la biblioteca estándar; usa lo que viene con su compilador. Entonces, incluso si hace algunas cosas desagradables, las opciones de alternativas son limitadas.

Por supuesto, hay programadores que se preocupan por este tipo de cosas. Pero todos renunciaron a usar la biblioteca estándar hace mucho tiempo.

Entonces tienes un grupo de programadores a los que simplemente no les importa. Y otro grupo de programadores a los que les importaría si lo estuvieran usando, pero como no lo están usando, no les importa. Como a nadie le importa, no hay información real sobre este tipo de cosas. Hay parches informales de información aquí y allá (Effective C ++ tiene una sección sobre implementaciones std :: string y las grandes diferencias entre ellos), pero nada exhaustivo. Y ciertamente, nada se mantiene actualizado.

Nicol Bolas
fuente
Respuesta especulativa +1 para probablemente cierto, -1 para ninguna forma de probarlo.
deceleratedcaviar
He visto muchas comparaciones muy buenas y detalladas en el pasado, pero todas están desactualizadas. Cualquier cosa antes de la introducción del movimiento es prácticamente irrelevante hoy en día.
Peter - Unban Robert Harvey