c++ - ¿Qué está pasando con la sobrecarga de memoria de std:: deque?

visual-c++ memory

Question

Estoy trabajando en un algoritmo de clasificación externo que usa std::queue y debe restringir cuidadosamente su uso de memoria. Me he dado cuenta de que durante la fase de fusión (que usa varias std::queue de longitud fija), el uso de mi memoria aumenta a aproximadamente 2,5 veces lo que esperaba. Como std::queue usa de manera predeterminada std::deque como su contenedor subyacente, realicé algunas pruebas en std::deque para determinar su sobrecarga de memoria. Estos son los resultados, que se ejecutan en VC ++ 9, en modo de lanzamiento, con un proceso de 64 bits:

Al agregar 100,000,000 de caracteres a std::deque , el uso de la memoria aumenta a 252,216K. Tenga en cuenta que 100M char s (1 byte) debe ocupar 97,656K, por lo que esta es una sobrecarga de 154,560K.

Repetí la prueba con double s (8 bytes) y vi crecer la memoria a 1,976,676K, mientras que 100M double s deberían ocupar 781,250K, ¡para una sobrecarga de 1,195,426K!

Ahora entiendo que std::deque normalmente se implementa como una lista vinculada de "fragmentos". Si esto es cierto, ¿por qué la sobrecarga es proporcional al tamaño del elemento (porque, por supuesto, el tamaño del puntero debe ser fijo a 8 bytes)? ¿Y por qué es tan grande?

¿Alguien puede arrojar algo de luz sobre por qué std::deque usa tanta memoria dañada? Estoy pensando en cambiar los contenedores subyacentes de std::queue a std::vector ya que no hay gastos generales (dado que se reserve tamaño adecuado). Estoy pensando que los beneficios de std::deque se niegan en gran medida por el hecho de que tiene una sobrecarga tan grande (que provoca fallas de caché, fallas de página, etc.), y que el costo de copiar elementos std::vector puede ser menos, dado que el uso general de la memoria es mucho menor. ¿Es solo una mala implementación de std::deque por parte de Microsoft?

Answer 1

¿Es posible que estés ejecutando binarios de Debug? 252MB para 100M caracteres parece mucho ...

Puede verificar la atribución de esto usando umdh a instantánea antes y después y luego comparar los dos; podría arrojar algo de luz sobre por qué es más grande de lo que esperaba.

EDIT: FYI - Cuando ejecuto esto fuera del depurador en VS2010 obtengo 181MB con char s.

deque<char> mydequeue;
for (size_t i = 0; i < 100 * 1024 * 1024; ++i)
{
  mydequeue.push_back(char(i));
}

EDITAR: Apoyando la otra respuesta de @Dialecticus, esto me da la misma huella que el double :

struct twoInt64s
{
public:
    twoInt64s(__int64 _a, __int64 _b) : a(_a), b(_b) {}

    __int64 a;
    __int64 b;
};

EDITAR: con _DEQUESIZ modificado como se muestra (128 caracteres por bloque), 100M caracteres ahora toma 113M de memoria.

Mi conclusión es que la sobrecarga restante que viste se debe a las estructuras de gestión para los bloques deque , que tienen 16 caracteres de datos, más información de control para deque y más información de control para heap manager.

#define _DEQUESIZ   (sizeof (value_type) <= 1 ? 128 /
    : sizeof (value_type) <= 2 ? 8 /
    : sizeof (value_type) <= 4 ? 4 /
    : sizeof (value_type) <= 8 ? 2 /
    : 1)    /* elements per block (a power of 2) */

Moraleja: si realmente desea optimizar esto para su propósito especial, prepárese para jugar con <deque> . Su comportamiento depende críticamente del tamaño de sus elementos, y más allá de eso en el patrón de uso esperado.

EDITAR: Dependiendo de su conocimiento del tamaño de las colas, es posible que pueda incluir boost :: circular_buffer como reemplazo del contenedor std :: queue. Apuesto a que esto funcionaría más como quisieras (y esperaras).

Answer 2

Mire el código para _DEQUESIZ (número de elementos por bloque):

#define _DEQUESIZ   (sizeof (_Ty) <= 1 ? 16 /
    : sizeof (_Ty) <= 2 ? 8 /
    : sizeof (_Ty) <= 4 ? 4 /
    : sizeof (_Ty) <= 8 ? 2 : 1)    /* elements per block (a power of 2) */

Se vuelve más pequeño si el elemento es más grande. Solo para elementos de más de 8 bytes obtendrá el comportamiento esperado (disminución porcentual de gastos generales con aumento del tamaño del elemento).

Answer 3

Sin mirar la implementación real de std :: queue está usando, creo que su asignación de memoria se ve así:

if (new element won''t fit) {
    double the size of the backing storage
    realloc the buffer (which will probably copy all elements)
}

El motivo para doblar en lugar de ser más conservador es que desea que la operación queue.push_pack tenga O (1) tiempo promedio. Dado que la reasignación puede copiar los elementos existentes, una versión que solo creció la matriz según sea necesario (1 elemento a la vez) sería O (n ^ 2) cuando inicialmente inserte todos sus valores en la cola. Lo dejaré como un ejercicio para el lector de cómo la versión de duplicación da tiempo promedio constante.

Dado que está citando el tamaño de todo el proceso, su estimación de aproximadamente 2x de sobrecarga cuando empuja un poco más que una potencia de 2 (2 ^ 26 <100MM <2 ^ 27) valor de elementos parece razonable. Intente detenerse en 2 ^ (n-1), midiendo, luego empujando algunos elementos y midiendo nuevamente.