c++ - standard - vector class



Bjarne Stroustrup diz que devemos evitar listas vinculadas (1)

Vi este vídeo no YouTube: https://www.youtube.com/watch?v=YQs6IC-vgmo no qual Bjarne diz que é melhor usar vetores, em vez de listas vinculadas. Eu sou incapaz de entender a coisa toda, então alguém poderia explicar o que ele está dizendo em termos leigos?

PS: Eu sou um estudante do ensino médio e posso lidar facilmente com listas vinculadas, mas estou lutando para aprender vetores por conta própria. Você poderia sugerir alguma fonte para aprender vetores?


Vantagens do vetor vs. lista vinculada

A principal vantagem do vetor versus as listas vinculadas é a localização da memória.

Geralmente, cada elemento é alocado separadamente em uma lista vinculada. Como conseqüência, esses elementos provavelmente não estão próximos um do outro na memória. (Lacunas entre os elementos na memória.)

Um vetor é garantido para armazenar todos os elementos contidos contiguamente. (Itens próximos um do outro, sem lacunas;)

Nota: Podem ocorrer simplificações excessivas ...;)

Imo, os principais pontos simplificados sobre o desempenho superior de um padrão de armazenamento de dados contíguo armazenado versus armazenamento não contíguo são

1. falta de cache

As CPUs modernas não buscam bytes únicos da memória, mas pedaços um pouco maiores. Portanto, se o tamanho dos objetos de dados for menor que o tamanho desses pedaços e se o armazenamento for contíguo, você poderá obter mais de um elemento por vez, pois vários elementos podem estar em um único pedaço.

Exemplo:

Um bloco de 64 bytes (tamanho normal da linha de cache) cabe dezesseis inteiros de 32 bits por vez. Portanto, uma falta de cache (dados que ainda não estão no cache -> é necessário carregar da memória principal) ocorre após o processamento de 16 elementos a partir do momento em que o primeiro foi trazido para o cache. Se uma lista vinculada for usada, o primeiro elemento poderá ser o único dentro de um bloco de 64 bytes. Em teoria, pode acontecer que ocorra uma falta de cache para cada elemento da lista.

Exemplo concreto:

std::vector<std::uint32_t> v;
// somehow fill 64 values into v
std::uint32_t s{};
for(std::size_t i{0}; i<v.size(); ++i)
{
  s += v[i];
}

Imagine o conteúdo de v não sendo armazenado em cache.

O que acontece durante o processamento dos dados no loop for?

1) Verifique se o elemento v [0] está no cache. -> Não

2) Busque 64 bytes começando no endereço de v [0] da memória principal em uma linha de cache

3) Carregue v [0] do cache e processe adicionando seu valor a s

4) O elemento v 1 no cache? -> Sim carregado com a busca anterior porque vizinho v [0]

5) Carregue v 1 do cache e processe adicionando seu valor a s

6) O elemento v [2] está no cache? -> Sim ...

7) Carregue v [2] do cache e processe adicionando seu valor a s

... etc ...

34) O elemento v [16] está no cache? -> Não

35) Busque 64 bytes começando no endereço de v [16] da memória principal em uma linha de cache

36) Carregue v [16] do cache e processe adicionando seu valor a s

37) O elemento v [17] está no cache? -> Sim carregado com a busca anterior porque vizinho v [16]

etc ...

Buscar dados da memória principal no cache leva muito mais tempo do que carregar dados do cache nos registros do processador e executar operações simples. Portanto, o fato de vários valores residirem em uma única linha de cache pode aumentar significativamente o desempenho.

As listas vinculadas não fornecem uma garantia de armazenamento contígua e você não pode esperar obter esse aumento de desempenho. Esse também é o motivo pelo qual a iteração aleatória (acessando elementos aleatoriamente) tem desempenho pior que a iteração direta (acessando elementos em ordem) para contêineres contíguos.

2. pré-busca

O efeito acima é amplificado por um recurso da CPU chamado "pré-buscador".

Se um pedaço foi carregado da memória principal, o pré-buscador prepara o carregamento do próximo pedaço / já o coloca no cache, reduzindo significativamente a penalidade de carregar coisas dessa parte da memória principal.

É claro que isso é eficaz se, e somente se, de fato, você precisar de dados do próximo bloco preparado.

Como os vetores geralmente funcionam (internamente)?

Veja: 1





linked-list