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

46

Considere o seguinte trecho:

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

Obviamente, ele travaria na maioria das plataformas, porque o tamanho da pilha padrão geralmente é inferior a 20 MB.

Agora considere o seguinte código:

#include <array>
#include <vector>

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

Surpreendentemente, ele também trava! O traceback (com uma das versões recentes do libstdc ++) leva ao include/bits/stl_uninitialized.harquivo, onde podemos ver as seguintes linhas:

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

O vectorconstrutor de redimensionamento deve inicializar os elementos por padrão, e é assim que ele é implementado. Obviamente, _ValueType()falhas temporárias na pilha.

A questão é se é uma implementação em conformidade. Se sim, na verdade significa que o uso de um vetor de grandes tipos é bastante limitado, não é?

Igor R.
fonte
Não se deve armazenar objetos enormes em um tipo de matriz. Fazer isso potencialmente requer uma região muito grande de memória contigiosa que pode não estar presente. Em vez disso, tenha um vetor de ponteiros (normalmente std :: unique_ptr) para não colocar uma demanda tão alta em sua memória.
NathanOliver 6/01
2
Apenas memória. Existem implementações de C ++ em execução que não usam memória virtual.
NathanOliver 6/01
3
Qual compilador, btw? Não consigo reproduzir com o VS 2019 (16.4.2)
ChrisMM
3
Observando o código libstdc ++, essa implementação será usada apenas se o tipo de elemento for trivial e atribuível à cópia e se o padrão std::allocatorfor usado.
noz
11
@ Damon Como mencionei acima, parece ser usado apenas para tipos triviais com o alocador padrão, portanto, não deve haver nenhuma diferença observável.
noz

Respostas:

19

Não há limite para a quantidade de armazenamento automático que qualquer API padrão usa.

Todos eles podem exigir 12 terabytes de espaço na pilha.

No entanto, essa API requer apenas Cpp17DefaultInsertablee sua implementação cria uma instância extra sobre o que é exigido pelo construtor. A menos que esteja atrasado para detectar que o objeto é trivialmente copiável e copiável, essa implementação parece ilegal.

Yakk - Adam Nevraumont
fonte
8
Observando o código libstdc ++, essa implementação será usada apenas se o tipo de elemento for trivial e atribuível à cópia e se o padrão std::allocatorfor usado. Não sei ao certo por que esse caso especial é apresentado em primeiro lugar.
noz
3
@walnut O que significa que o compilador é livre para criar, se não realmente, esse objeto temporário; Eu estou supondo que há uma chance decente em uma compilação otimizada que não seja criada?
Yakk - Adam Nevraumont
4
Sim, acho que sim, mas para elementos grandes o GCC não parece. Clang com libstdc ++ otimiza o temporário, mas parece que apenas se o tamanho do vetor passado para o construtor for uma constante em tempo de compilação, consulte godbolt.org/z/-2ZDMm .
noz
11
@walnut o caso especial existe para enviarmos std::fillpara tipos triviais, que depois usam memcpyos bytes em locais, o que é potencialmente muito mais rápido do que construir muitos objetos individuais em um loop. Acredito que a implementação libstdc ++ esteja em conformidade, mas causar um estouro de pilha para objetos grandes é um erro de Qualidade de Implementação (QoI). Eu relatei como gcc.gnu.org/PR94540 e o corrigirei.
Jonathan Wakely
@JonathanWakely Sim, isso faz sentido. Não me lembro por que não pensei nisso quando escrevi meu comentário. Eu acho que eu teria pensado que o primeiro elemento construído por padrão seria construído diretamente no local e, em seguida, poderia-se copiar disso, para que nenhum objeto adicional do tipo de elemento jamais fosse construído. Mas é claro que realmente não pensei sobre isso em detalhes e não conheço as vantagens e desvantagens da implementação da biblioteca padrão. (Percebi tarde demais que essa também é sua sugestão no relatório de erros.)
walnut
9
huge_type t;

Obviamente, ele falharia na maioria das plataformas ...

Eu discuto a suposição de "a maioria". Como a memória do objeto enorme nunca é usada, o compilador pode ignorá-lo completamente e nunca alocar a memória; nesse caso, não haveria falha.

A questão é se é uma implementação em conformidade.

O padrão C ++ não limita o uso da pilha, nem reconhece a existência de uma pilha. Então, sim, está em conformidade com o padrão. Mas pode-se considerar que este é um problema de qualidade de implementação.

na verdade, significa que o uso de um vetor de tipos enormes é bastante limitado, não é?

Esse parece ser o caso do libstdc ++. A falha não foi reproduzida com libc ++ (usando clang), portanto, parece que isso não é uma limitação na linguagem, mas apenas nessa implementação específica.

eerorika
fonte
6
"não travará necessariamente apesar do transbordamento da pilha, porque a memória alocada nunca é acessada pelo programa" - se a pilha for usada de qualquer forma após isso (por exemplo, para chamar uma função), isso travará mesmo nas plataformas com comprometimento excessivo .
Ruslan
Qualquer plataforma na qual isso não trava (supondo que o objeto não seja alocado com sucesso) é vulnerável ao Stack Clash.
user253751 7/01
@ user253751 Seria otimista supor que a maioria das plataformas / programas não é vulnerável.
eerorika
Eu acho que o overcommit se aplica apenas ao heap, não à pilha. A pilha possui um limite superior fixo em seu tamanho.
Jonathan Wakely 21/01
@JonathanWakely Você está certo. Parece que o motivo pelo qual ele não falha é porque o compilador nunca aloca o objeto que não é usado.
eerorika 21/01
5

Não sou advogado de idiomas nem especialista em C ++, mas o cppreference.com diz:

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

Constrói o contêiner com contagem de instâncias inseridas por padrão de T. Nenhuma cópia é feita.

Talvez eu esteja entendendo mal "inserção padrão", mas eu esperaria:

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

ser equivalente a

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

A última versão não deve criar uma cópia de pilha, mas construir um tipo enorme diretamente na memória dinâmica do vetor.

Não posso dizer com autoridade que o que você está vendo não é compatível, mas certamente não é o que eu esperaria de uma implementação de qualidade.

Adrian McCarthy
fonte
4
Como mencionei em um comentário sobre a questão, o libstdc ++ somente usa essa implementação para tipos triviais com atribuição de cópias e std::allocator, portanto, não deve haver diferença observável entre inserir diretamente na memória de vetores e criar uma cópia intermediária.
noz
@walnut: Certo, mas a enorme alocação de pilha e o impacto no desempenho do init e da cópia ainda são coisas que eu não esperaria de uma implementação de alta qualidade.
Adrian McCarthy
2
Sim eu concordo. Eu acho que isso foi uma supervisão na implementação. Meu argumento foi apenas que isso não importa em termos de conformidade padrão.
noz
Você também precisa copiar ou mover a IIRC, emplace_backmas não apenas para criar um vetor. O que significa que você pode ter, vector<mutex> v(1)mas não. vector<mutex> v; v.emplace_back();Para algo como huge_typevocê ainda pode ter uma alocação e mover a operação mais com a segunda versão. Nem deve criar objetos temporários.
dyp
11
@IgorR. vector::vector(size_type, Allocator const&)requer (Cpp17) DefaultInsertable
dyp