smart - std:: uso de memoria deque-Visual C++, y comparación con otros

programar contratos inteligentes

Question

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

Visual C ++ administra los bloques de deque acuerdo con el tipo de elemento contenedor utilizando esto:

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

Esto resulta en una huella de memoria muy grande para elementos pequeños. Al cambiar el 16 en la primera línea a 128, pude reducir drásticamente la huella requerida para un gran deque<char> . Los bytes privados del Explorador de procesos se redujeron de 181 MB -> 113 MB después de las push_back(const char& mychar) 100 m).

• ¿Alguien puede justificar los valores en esa #define ?
• ¿Cómo manejan otros compiladores el tamaño de bloques de desque?
• ¿Cuál sería su huella (operación de 32 bits) para la prueba simple de llamadas de 100 m push_back a deque<char> ?
• ¿Permite STL anular este tamaño de bloque en tiempo de compilación, sin modificar el código <deque> ?

Answer 1

STLPort

... seems use :

::: <stl/_alloc.h>
...
enum { _MAX_BYTES = 32 * sizeof(void*) };
...
::: <deque>
...
static size_t _S_buffer_size()
{
  const size_t blocksize = _MAX_BYTES;
  return (sizeof(_Tp) < blocksize ? (blocksize / sizeof(_Tp)) : 1);
}

Eso significaría un tamaño de bloque de 32 x 4 = 128 bytes en 32 bits y un tamaño de bloque de 32 x 8 = 256 bytes en 64 bits.

Mi idea: a partir de un POV de sobrecarga de tamaño, creo que tendría sentido que cualquier implementación operara con bloques de longitud variable, pero creo que sería extremadamente difícil acertar con el requisito de acceso aleatorio de tiempo constante de deque .

En cuanto a la pregunta

¿Permite STL anular este tamaño de bloque en tiempo de compilación, sin modificar el código?

Tampoco es posible aquí.

Apache

(parece ser la versión Rogue Wave STL) aparentemente usa:

static size_type _C_bufsize () {
    // deque only uses __rw_new_capacity to retrieve the minimum
    // allocation amount; this may be specialized to provide a
    // customized minimum amount
    typedef deque<_TypeT, _Allocator> _RWDeque;
    return _RWSTD_NEW_CAPACITY (_RWDeque, (const _RWDeque*)0, 0);
}

por lo que parece haber algún mecanismo para anular el tamaño del bloque a través de la especialización y la definición de ... se ve así:

// returns a suggested new capacity for a container needing more space
template <class _Container>
inline _RWSTD_CONTAINER_SIZE_TYPE
__rw_new_capacity (_RWSTD_CONTAINER_SIZE_TYPE __size, const _Container*)
{
    typedef _RWSTD_CONTAINER_SIZE_TYPE _RWSizeT;

    const _RWSizeT __ratio = _RWSizeT (  (_RWSTD_NEW_CAPACITY_RATIO << 10)
                                       / _RWSTD_RATIO_DIVIDER);

    const _RWSizeT __cap =   (__size >> 10) * __ratio
                           + (((__size & 0x3ff) * __ratio) >> 10);

    return (__size += _RWSTD_MINIMUM_NEW_CAPACITY) > __cap ? __size : __cap;
}

Así que diría que es, aehm, complicado.

(Si alguien tiene ganas de averiguar más sobre esto, siéntase libre de editar mi respuesta directamente o simplemente deje un comentario).

Answer 2

La implementación de Dinkumware (MS) quiere aumentar el deque en 16 bytes a la vez. ¿Podría ser que esta es solo una implementación extremadamente antigua (como la primera?) Que se ajustó para plataformas con muy poca memoria (para los estándares actuales) para evitar la memoria general y agotadora (como haría un std::vector )?

Tuve que implementar mi propia cola en una aplicación en la que estoy trabajando porque la huella de memoria 2.5X de std::queue (que usa std::deque ) era inaceptable.

Parece que hay muy poca evidencia en las interwebs de que la gente se haya topado con esta ineficiencia, lo que me sorprende. Pensaría que una estructura de datos tan fundamental como una cola (biblioteca estándar, no menos) sería bastante omnipresente en la naturaleza, y estaría en aplicaciones críticas para el rendimiento / tiempo / espacio. Pero aquí estamos.

Para responder a la última pregunta, el estándar de C ++ no define una interfaz para modificar el tamaño del bloque. Estoy bastante seguro de que no exige ninguna implementación, solo requisitos de complejidad para inserciones / eliminaciones en ambos extremos.

Answer 3

gcc tiene

return __size < 512 ? size_t(512 / __size) : size_t(1);

con un comentario

/*  The ''512'' is
 *  tunable (and no other code needs to change), but no investigation has
 *  been done since inheriting the SGI code.
 */