Por que é tão lento iteração sobre um grande std :: lista?

Question

Como o título sugere, eu tive problemas com um programa de mina onde eu usei um std :: list como uma pilha e também para iterar sobre todos os elementos da lista. O programa foi tomando um caminho muito longo quando as listas tornou-se muito grande.

Alguém tem uma boa explicação para isso? É algum comportamento pilha / cache?

(Resolvido o problema alterando as listas para std :: vector e std :: deque (uma estrutura surpreendente de dados por sinal) e tudo de repente ficou muito mais rápido)

EDIT: Eu não sou um tolo e eu faço elementos não acesso no meio das listas. A única coisa que eu fiz com as listas era remover / adicionar elementos no final / início e para percorrer todas elementos da lista. E eu sempre usado iterators para iterar sobre a lista.

Answer 1

As listas têm terrível (inexistente) cache localidade. Cada nó é uma nova alocação de memória, e pode ser qualquer . Então, todas vez que você siga um ponteiro de um nó para o próximo, você saltar para um novo, não relacionado, lugar na memória. E sim, isso prejudica o desempenho um pouco. Um erro de cache pode ser duas ordens de magnitude mais lento do que um acerto de cache. Em um vector ou deque, praticamente todos os acesso será um sucesso cache. Um vetor é um bloco contíguo único de memória, de modo a iteração sobre isso é tão rápido quanto você está indo para obter. Um deque é vários blocos menores de memória, por isso introduz o cache miss ocasional, mas que ainda vai ser raro, e iteração ainda será muito mais rápido que você está recebendo em sua maioria acessos ao cache.

A lista será quase todos os erros de cache. E o desempenho vai sugar.

Na prática, uma lista ligada quase nunca é a escolha certa de um ponto de vista do desempenho.

Editar : Como um comentário apontou, outro problema com listas é dependências de dados. A CPU moderna gosta de operações de sobreposição. Mas não pode fazer isso se a próxima instrução depende do resultado de um presente.

Se você é iteração sobre um vetor, isso não é problema. Você pode calcular o próximo endereço para ler na mosca, sem ter que verificar na memória. Se você está lendo no x endereço agora, então o próximo elemento será localizado na x + sizeof(T) endereço onde T é o tipo de elemento. Portanto, não há dependências ali, e a CPU pode começar a carregar o próximo elemento, ou aquele depois, imediatamente, enquanto ainda está processando um elemento anteriormente. Dessa forma, os dados estarão prontos para nós quando precisamos dela, e isso ajuda ainda mascarar o custo de acesso a dados na memória RAM.

Em uma lista, precisamos seguir um ponteiro do nó i ao nó i+1, e até i+1 foi carregado, nós nem sequer sabem onde procurar i+2. Temos uma dependência de dados, de modo que a CPU é forçado a ler os nós um de cada vez, e não pode começar a ler os nós futuros antes do tempo, porque ele ainda não sabe onde eles estão.

Se a lista não tinha sido todos os erros de cache, isso não teria sido um grande problema, mas já que estamos recebendo um monte de erros de cache, esses atrasos são caros.

Answer 2

É devido à grande quantidade de erros de cache que você começa ao usar uma lista. Com um vector os elementos circundantes são armazenados no cache do processador.

Answer 3

Tenha um olhar no seguinte stackoverflow fio .

Answer 4

Não é uma questão de cache: todos os dados no vetor são armazenados em um pedaço contíguo, e cada elemento da lista é alocada separadamente e pode acontecer de ser armazenado em um lugar muito aleatório de memória, o que leva a mais erros de cache. No entanto, eu aposto que você encontra um dos problemas descritos em outras respostas.

Answer 5

A resposta simples é porque iteração sobre um vetor não está interagindo em tudo, ele está apenas começando na base de uma matriz e lendo os elementos um após o outro.

Eu vejo isso é marcada C ++, não C, mas uma vez que eles fazem a mesma coisa debaixo das cobertas É importante ressaltar que você pode adicionar elementos para o início eo fim de uma matriz alocando-lo arbitrariamente grande, e realloc () ing e memmove () ing entre 2 matrizes de companhia, se e quando você correr para fora da sala. Muito rápido.

O truque para a adição de elementos para o início de uma matriz é a polarização do início lógico da matriz com o avanço do ponteiro para a matriz, no início, e, em seguida, apoiando-se quando a adição de elementos na parte da frente. (Também a forma de uma pilha é implementada)

Em exatamente da mesma maneira, C pode ser feito para subscritos apoio negativas.

C ++ faz tudo isso para você com a classe STL vector, mas ainda vale a pena lembrar o que está acontecendo nos bastidores.

Answer 6

[Edit: eu estou corrigido. std :: lista não tem operador []. Desculpe.]

É difícil dizer a partir de sua descrição, mas eu suspeito que você estava tentando acessar os itens aleatoriamente (ou seja, pelo índice):

for(int i = 0; i < mylist.size(); ++i) { ... mylist[i] ... }

Em vez de usar os iteradores:

for(list::iterator i = mylist.begin(); i != mylist.end(); ++i) { ... (*i) ... }

Tanto o "vector" & "deque" são bons em acesso aleatório, por isso ou irá desempenhar adequadamente para esses tipos --- O (1) em ambos os casos. Mas "a lista" não é bom em acesso aleatório. Aceder a lista pelo índice levaria O (n ^ 2) o tempo, contra o (1) quando se utiliza iterators.