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

Question

Estoy trabajando en un algoritmo de clasificación externo que usa std::queue y debo restringir cuidadosamente su uso de memoria. Me he dado cuenta de que durante la fase de fusión (que usa varios std::queue s de longitud fija), mi uso de memoria aumenta a aproximadamente 2,5 veces lo que esperaba. Como std::queue usa por defecto std::deque como su contenedor subyacente, ejecuté 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 char a un std::deque, el uso de la memoria crece 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 la memoria crecer 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 "trozos". 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 mis contenedores subyacentes std::queue a std::vector ya que no hay sobrecarga (dado que el tamaño apropiado es reserve ed). 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 menor, dado que el total el uso de la memoria es mucho menor. ¿Es solo una mala implementación de std::deque de Microsoft?

Answer 1

mirar el código de _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 hace más pequeño si el elemento es mayor. 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 2

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

Puede verificar la atribución de esto usando umdh a una 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)); 
} 

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

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

    __int64 a; 
    __int64 b; 
}; 

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

Mi conclusión es que la sobrecarga restante que viste se debe a las estructuras de administració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) */ 

Moral - si realmente desea optimizar esto para su propósito especial, estar preparado 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 de los tamaños de cola, 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 3

Sin mirar a la aplicación real de std :: cola que está usando, mi conjetura es que su asignación de memoria es como la siguiente:

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

La razón 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 2 veces cuando empuja un poco más de una potencia de 2 (2^26 < 100MM < 2^27), el valor de los elementos parece razonable. Intente detenerse en 2^(n-1), midiendo, luego empujando algunos elementos y midiendo nuevamente.