unordered_map - unordered_set c++

Plantilla de código hinchado con unordered_map

Question

Me pregunté si unordered_map se implementa usando el borrado de tipo, ya que un unordered_map<Key, A*> y unordered_map<Key, B*> pueden usar exactamente el mismo código (aparte de casting, que no es una opción en el código de máquina). Es decir, la implementación de ambos podría basarse en unordered_map<Key, void*> para guardar el tamaño del código.

Actualización: esta técnica se conoce comúnmente como el modismo de la plantilla delgada (gracias a los comentaristas a continuación por señalarlo).

Actualización 2: Me interesaría especialmente la opinión de Howard Hinnant . Esperemos que lea esto.

Así que escribí esta pequeña prueba:

#include <iostream>

#if BOOST
# include <boost/unordered_map.hpp>
  using boost::unordered_map;
#else
# include <unordered_map>
  using std::unordered_map;
#endif

struct A { A(int x) : x(x) {} int x; };
struct B { B(int x) : x(x) {} int x; };

int main()
{
#if SMALL
    unordered_map<std::string, void*> ma, mb;
#else
    unordered_map<std::string, A*> ma;
    unordered_map<std::string, B*> mb;
#endif

    ma["foo"] = new A(1);
    mb["bar"] = new B(2);

    std::cout << ((A*) ma["foo"])->x << std::endl;
    std::cout << ((B*) mb["bar"])->x << std::endl;

    // yes, it leaks.
}

Y determinó el tamaño de la salida compilada con varias configuraciones:

#!/bin/sh

for BOOST in 0 1 ; do
    for OPT in 2 3 s ; do
        for SMALL in 0 1 ; do
            clang++ -stdlib=libc++ -O${OPT} -DSMALL=${SMALL} -DBOOST=${BOOST} map_test.cpp -o map_test
            strip map_test
            SIZE=$(echo "scale=1;$(stat -f "%z" map_test)/1024" | bc)
            echo boost=$BOOST opt=$OPT small=$SMALL size=${SIZE}K
        done
    done
done

Resulta que, con todas las configuraciones que probé, parece que se instancia una gran cantidad de código interno de unordered_map :

With Clang and libc++:
          |   -O2   |   -O3   |   -Os
-DSMALL=0 |  24.7K  |  23.5K  |  28.2K
-DSMALL=1 |  17.9K  |  17.2K  |  19.8K


With Clang and Boost:
          |   -O2   |   -O3   |   -Os
-DSMALL=0 |  23.9K  |  23.9K  |  32.5K
-DSMALL=1 |  17.4K  |  17.4K  |  22.3K


With GCC and Boost:
          |   -O2   |   -O3   |   -Os
-DSMALL=0 |  21.8K  |  21.8K  |  35.5K
-DSMALL=1 |  16.4K  |  16.4K  |  26.2K

(Con los compiladores de Xcode de Apple)

Ahora a la pregunta: ¿Existe alguna razón técnica convincente por la cual los implementadores hayan optado por omitir esta simple optimización?

Además: ¿por qué diablos es el efecto de -Os exactamente lo contrario de lo que se anuncia?

Actualización 3 :

Según lo sugerido por Nicol Bolas, he repetido las mediciones con shared_ptr<void/A/B> lugar de punteros desnudos (creados con make_shared y emitidos con static_pointer_cast ). La tendencia en los resultados es la misma:

With Clang and libc++:
          |   -O2   |   -O3   |   -Os
-DSMALL=0 |  27.9K  |  26.7K  |  30.9K
-DSMALL=1 |  25.0K  |  20.3K  |  26.8K


With Clang and Boost:
          |   -O2   |   -O3   |   -Os
-DSMALL=0 |  35.3K  |  34.3K  |  43.1K
-DSMALL=1 |  27.8K  |  26.8K  |  32.6K

Answer 1

Cuando tiene un parámetro void * no hay verificación de tipo en tiempo de compilación.

Mapas como los que usted propone serían una falla en un programa, ya que aceptarían elementos de valor de tipo A *, B *, e incluso tipos de fantasía más inimaginables que no tendrían nada que hacer en ese mapa. (por ejemplo, int *, float *; std :: string *, CString *, CWnd * ... imagina el desorden en tu mapa ...)

Su optimización es prematura. Y la optimización prematura es la raíz de todo mal.

Answer 2

Ya que se me ha pedido específicamente que comente, lo haré, aunque no estoy seguro de que tenga mucho más para agregar de lo que ya se ha dicho. (lo siento, me tomó 8 días para llegar aquí)

He implementado el lenguaje de plantilla delgada antes, para algunos contenedores, a saber, vector, deque y list. Actualmente no lo tengo implementado para ningún contenedor en libc ++. Y nunca lo he implementado para los contenedores desordenados.

Se guarda en el tamaño del código. También agrega complejidad, mucho más que lo que implica el enlace de wikibooks referenciado. También se puede hacer para algo más que punteros. Puedes hacerlo para todos los escalares que tengan el mismo tamaño. Por ejemplo, ¿por qué tienen diferentes instancias para int y unsigned ? Incluso ptrdiff_t puede almacenarse en la misma instanciación que T* . Después de todo, todo es sólo una bolsa de bits en la parte inferior. Pero es extremadamente difícil obtener las plantillas de miembros que toman un rango de iteradores correctos al jugar estos trucos.

Sin embargo, hay desventajas (además de la dificultad de implementación). No funciona tan bien con el depurador. Como mínimo, hace que sea mucho más difícil para el depurador mostrar las entrañas del contenedor. Y si bien el ahorro en el tamaño del código puede ser significativo, me quedaría corto al considerar que el ahorro en el tamaño del código es dramático. Especialmente en comparación con la memoria requerida para almacenar fotografías, animaciones, clips de audio, mapas de calles, años de correo electrónico con todos los archivos adjuntos de sus mejores amigos y familiares, etc. Es importante optimizar el tamaño del código. Pero debe tener en cuenta que en muchas aplicaciones de hoy (incluso en dispositivos integrados), si reduce el tamaño de su código a la mitad, puede reducir el tamaño de su aplicación en un 5% (las estadísticas son ciertamente extraídas del aire).

Mi posición actual es que esta optimización en particular es mejor pagada e implementada en el enlazador en lugar de en el contenedor de plantillas. Aunque sé que esto no es fácil de implementar en el enlazador, he oído hablar de implementaciones exitosas.

Dicho esto, todavía trato de hacer optimizaciones de tamaño de código en plantillas. Por ejemplo, en las estructuras de ayuda de libc ++, como __hash_map_node_destructor tienen la menor cantidad de parámetros posible, por lo que si cualquiera de sus códigos se describe, es más probable que una instanciación de la ayuda pueda servir para más de una instancia de unordered_map . Esta técnica es amigable con el depurador, y no es tan difícil hacerlo bien. E incluso puede tener algunos efectos secundarios positivos para el cliente cuando se aplica a los iteradores ( N2980 ).

En resumen, no lo compararía con el código para ir más allá e implementar esta optimización. Pero tampoco lo clasificaría como una prioridad tan alta como lo hice hace una década, ya que la tecnología del enlazador ha progresado y la proporción entre el tamaño del código y el tamaño de la aplicación ha tendido a disminuir drásticamente.