std :: vector (ab) usa almacenamiento automático

46

Considere el siguiente fragmento:

#include <array>
int main() {
  using huge_type = std::array<char, 20*1024*1024>;
  huge_type t;
}

Obviamente, se bloqueará en la mayoría de las plataformas, porque el tamaño predeterminado de la pila suele ser inferior a 20 MB.

Ahora considere el siguiente código:

#include <array>
#include <vector>

int main() {
  using huge_type = std::array<char, 20*1024*1024>;
  std::vector<huge_type> v(1);
}

¡Sorprendentemente también se bloquea! El rastreo (con una de las versiones recientes de libstdc ++) conduce al include/bits/stl_uninitialized.harchivo, donde podemos ver las siguientes líneas:

typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
std::fill(__first, __last, _ValueType());

El cambio de tamaño vector constructor de debe inicializar por defecto los elementos, y así es como se implementa. Obviamente, _ValueType()temporal bloquea la pila.

La pregunta es si se trata de una implementación conforme. En caso afirmativo, en realidad significa que el uso de un vector de tipos enormes es bastante limitado, ¿no es así?

Igor R.
fuente
Uno no debe almacenar objetos enormes en un tipo de matriz. Hacerlo potencialmente requiere una región muy grande de memoria contigua que puede no estar presente. En su lugar, tenga un vector de punteros (std :: unique_ptr típicamente) para que no ponga tanta demanda en su memoria.
NathanOliver
2
Solo recuerdo. Hay implementaciones de C ++ en ejecución que no usan memoria virtual.
NathanOliver
3
¿Qué compilador, por cierto? No puedo reproducir con VS 2019 (16.4.2)
ChrisMM
3
Al observar el código libstdc ++, esta implementación solo se usa si el tipo de elemento es trivial y se puede asignar copia y si std::allocatorse usa el predeterminado .
nogal
1
@Damon Como mencioné anteriormente, parece que solo se usa para tipos triviales con el asignador predeterminado, por lo que no debería haber ninguna diferencia observable.
nogal

Respuestas:

19

No hay límite en cuanto al almacenamiento automático que utiliza cualquier API estándar.

Todos podrían requerir 12 terabytes de espacio de pila.

Sin embargo, esa API solo requiere Cpp17DefaultInsertable, y su implementación crea una instancia adicional sobre lo que requiere el constructor. A menos que esté cerrado detrás de detectar que el objeto es trivialmente copiable y copiable, esa implementación parece ilegal.

Yakk - Adam Nevraumont
fuente
8
Al observar el código libstdc ++, esta implementación solo se usa si el tipo de elemento es trivial y se puede asignar copia y si std::allocatorse usa el predeterminado . No estoy seguro de por qué este caso especial se hace en primer lugar.
nogal
3
@walnut Lo que significa que el compilador es libre de crear un objeto temporal; Supongo que hay una posibilidad decente en una compilación optimizada que no se crea.
Yakk - Adam Nevraumont
44
Sí, supongo que podría, pero para elementos grandes, GCC no parece. Clang con libstdc ++ optimiza lo temporal, pero parece que solo si el tamaño del vector pasado al constructor es una constante de tiempo de compilación, vea godbolt.org/z/-2ZDMm .
nogal
1
@walnut, el caso especial está ahí para que enviemos a los std::filltipos triviales, que luego se utilizan memcpypara disparar los bytes en lugares, lo que es potencialmente mucho más rápido que construir muchos objetos individuales en un bucle. Creo que la implementación de libstdc ++ se está conformando, pero causar un desbordamiento de la pila para objetos grandes es un error de calidad de implementación (QoI). Lo informé como gcc.gnu.org/PR94540 y lo solucionaré.
Jonathan Wakely
@ JonathanWakely Sí, eso tiene sentido. No recuerdo por qué no pensé en eso cuando escribí mi comentario. Supongo que habría pensado que el primer elemento construido por defecto se construiría directamente en el lugar y luego se podría copiar a partir de eso, para que nunca se construyan objetos adicionales del tipo de elemento. Pero, por supuesto, no he pensado esto en detalle y no conozco los entresijos de la implementación de la biblioteca estándar. (Me di cuenta demasiado tarde que esta también es su sugerencia en el informe de error).
nogal
9
huge_type t;

Obviamente se estrellaría en la mayoría de las plataformas ...

Disputo la suposición de "la mayoría". Dado que la memoria del gran objeto nunca se usa, el compilador puede ignorarlo por completo y nunca asignar la memoria, en cuyo caso no habría bloqueo.

La pregunta es si se trata de una implementación conforme.

El estándar C ++ no limita el uso de la pila, ni siquiera reconoce la existencia de una pila. Entonces, sí, se ajusta al estándar. Pero se podría considerar que se trata de un problema de calidad de implementación.

en realidad significa que el uso de un vector de tipos enormes es bastante limitado, ¿no es así?

Ese parece ser el caso con libstdc ++. El bloqueo no se reprodujo con libc ++ (usando clang), por lo que parece que esto no es una limitación en el lenguaje, sino solo en esa implementación particular.

eerorika
fuente
66
"no necesariamente se bloqueará a pesar del desbordamiento de la pila porque el programa nunca accede a la memoria asignada" - si la pila se usa de alguna manera después de esto (por ejemplo, para llamar a una función), se bloqueará incluso en las plataformas que se comprometen demasiado .
Ruslan
Cualquier plataforma en la que esto no se bloquee (suponiendo que el objeto no se haya asignado correctamente) es vulnerable a Stack Clash.
user253751
@ user253751 Sería optimista suponer que la mayoría de las plataformas / programas no son vulnerables.
Eerorika
Creo que el exceso de compromiso solo se aplica al montón, no a la pila. La pila tiene un límite superior fijo en su tamaño.
Jonathan Wakely
@ JonathanWakely Tienes razón. Parece que la razón por la que no se bloquea es porque el compilador nunca asigna el objeto que no se utiliza.
Eerorika
5

No soy un abogado de idiomas ni un experto en estándares de C ++, pero cppreference.com dice:

explicit vector( size_type count, const Allocator& alloc = Allocator() );

Construye el contenedor con el recuento de instancias de T. insertadas por defecto. No se realizan copias.

Quizás estoy malinterpretando "insertado por defecto", pero esperaría:

std::vector<huge_type> v(1);

ser equivalente a

std::vector<huge_type> v;
v.emplace_back();

La última versión no debería crear una copia de la pila, sino construir un enorme_tipo directamente en la memoria dinámica del vector.

No puedo decir con autoridad que lo que está viendo no cumple, pero ciertamente no es lo que esperaría de una implementación de calidad.

Adrian McCarthy
fuente
44
Como mencioné en un comentario sobre la pregunta, libstdc ++ solo usa esta implementación para tipos triviales con asignación de copias y std::allocator, por lo tanto, no debería haber una diferencia observable entre insertar directamente en la memoria de vectores y crear una copia intermedia.
nogal
@walnut: Correcto, pero la enorme asignación de pila y el impacto en el rendimiento de init y copy siguen siendo cosas que no esperaría de una implementación de alta calidad.
Adrian McCarthy
2
Sí estoy de acuerdo. Creo que esto fue un descuido en la implementación. Mi punto era solo que no importa en términos de cumplimiento estándar.
nogal
IIRC también necesita copiabilidad o movilidad, emplace_backpero no solo para crear un vector. Lo que significa que puede tener, vector<mutex> v(1)pero no vector<mutex> v; v.emplace_back();para algo como huge_typetodavía podría tener una asignación y mover la operación más con la segunda versión. Ninguno de los dos debería crear objetos temporales.
Dyp
1
@IgorR. vector::vector(size_type, Allocator const&)requiere (Cpp17) DefaultInsertable
dyp