Como a localidade do cache afeta o desempenho do ArrayList em comparação ao LinkedList em Java?
Ouvi dizer que ArrayList tem uma vantagem em termos de localidade de cache, mas não entendo completamente o porquê. Como Java armazena objetos na memória como referências, acessar elementos em qualquer uma das listas não exigiria saltar para locais aleatórios na memória?
Espere, vamos primeiro ilustrar como o Java funciona, porque sem esse conhecimento você não consegue entender essas afirmações conflitantes sobre "tudo é um link".
Em Java, cada variável tem tamanho fixo e é muito pequena. Isso é muito conveniente, pois permite fazer declarações tão grandes e abrangentes como "sempre que você chama um método, todos os parâmetros são copiados para o método que você está chamando; esse método pode fazer o que quiser com essas cópias, e as cópias desaparecem assim que o método termina a execução". Afinal, se você fizer essa declaração e uma variável tiver 2 GB de tamanho, passá-la adiante causará erros de falta de memória muito rapidamente.
Mas como isso funciona? Certamente
List<String> list = enumerateEveryWordInTheCollectedWorksOfShakespeare();não é "tamanho fixo e pequeno".É aí que a segunda parte entra: em Java, você tem primitivos, que é esta lista codificada de tipos:
int,long,short,byte,double,float,char,boolean. (Essa é a lista desde sempre, ela nunca mudará, você não pode criar seus próprios primitivos ^1) - cada um deles é 'fixo, tamanho pequeno' (especificamente, todos eles têm 64 bits ou menos). E todo o resto é uma referência . Um ponteiro.Quando você escreve:
Então é incorreto dizer "x é olá". Não é. x é uma referência a ele.
É como se "Olá" fosse uma casa (pense nisso: strings podem ter comprimentos arbitrários. Podem ser todas as obras de Shakespeare. Não são "fixas, de tamanho pequeno"), e x é apenas uma página em um catálogo de endereços. É uma instrução que lhe diz como chegar à casa. Dada essa página, se você quiser saber se a casa é vermelha, você pode fazer isso - apenas... vá até lá e olhe. Tudo o que você precisa é da página. Mas você precisa investir tempo, por assim dizer.
ArrayListArrayList é "uma lista de links" nesse sentido exato: por definição, você não pode ter uma lista de arraylist de valores primitivos (você pode ter um
List<Integer>;Integerque é a versão em caixa, ou seja, "referência" deint.List<int>não é válido em Java), portanto, deve ser uma lista de referências. Isso significa que umArrayListé um catálogo de endereços . É uma lista de endereços.A lista é "contígua" — ou seja, a agenda está inteira e na ordem que você espera. Se você está na página 5 da agenda e está curioso sobre o endereço na página 6, posso garantir que a página 6 está bem próxima. Simplesmente... vire a página e lá está. Garantido .
Uma desvantagem das arraylists é que, assim como as agendas de endereços reais, elas têm um tamanho fixo. Então, o que acontece quando você enche sua agenda de endereços? Bem, a implementação de ArrayList fará uma mágica secreta para fazer parecer que a lista não tem um problema de "ops, está cheia": ela compra uma agenda de endereços nova e maior, copia manualmente todos os endereços da antiga, substitui rapidamente sua agenda de endereços por esta nova e joga a antiga no lixo, tudo como parte de suas operações normais. Chamar métodos não é tanto "fazer" algo a um objeto, é pedir ao objeto para fazer isso por você. ArrayList é uma agenda de endereços capaz de entender como sair, comprar uma nova e maior, copiar a si mesma na nova, transferir sua consciência para a nova e então jogar sua antiga versão no lixo.
LinkedListO LinkedList é como uma agenda da qual você arranca cada página e as espalha pela sala. Você sabe onde está a página 1 da agenda. Mas isso é tudo o que você sabe. Felizmente, cada página lista o local onde você escondeu a próxima página, bem como a página anterior. Então, se você quiser, digamos, ir até a casa listada na sua agenda na página 5, porque quer saber de que cor ela é pintada, você encontra a página 1, que diz "Você empurrou a página 2 para trás do sofá", você encontra a página 2, que diz "a página 3 está em cima da geladeira", você encontra a página 3, que diz "a página 4 está na mesa", e a página 4 diz "a página 5 também está na mesa", e então finalmente você pode ir até aquela casa.
Este é um processo absurdamente demorado. Ele tem uma única vantagem: você nunca mais precisa comprar uma nova agenda e copiar a antiga completa para ela . Afinal, com esse sistema de páginas espalhadas, se você ficar sem páginas, basta espalhar mais algumas páginas em branco pela sala e continuar. Isso não é uma grande vantagem, mas já é alguma coisa, eu acho.
Agora, se você criar uma lista encadeada e preencher imediatamente as primeiras 500 páginas, é provável que todas as 500 páginas ainda estejam empilhadas na sua mesa, mais ou menos ordenadas exatamente. Mas, como não é possível ter certeza, mesmo que seja o caso, se você quiser ir à casa listada na página 250, ainda precisará ler cada página, enquanto com o catálogo de endereços da lista de arrays você pode ir direto para a página 250 de uma só vez.
Mas o LinkedList não exige que você o preencha cuidadosamente à medida que o cria. Se você o preencher ao longo do tempo, terá o cenário de "páginas espalhadas por todo lado".
... piora!
Cada "página" do nosso catálogo de endereços linkedlist, na verdade, armazena 3 coisas. Nenhuma delas. Ela armazena a localização da página anterior, a localização da próxima página e, claro, o endereço da casa. Cada uma dessas coisas é uma "pequena coisa fixa" (uma referência). Mas essas 3 juntas — não é assim que Java funciona, é demais.
Então, na verdade, uma LinkedList é mais como 'cada página do catálogo de endereços é, na verdade, um pequeno catálogo de endereços com 3 páginas, uma explicando onde está o post-it anterior, uma onde está o próximo post-it e uma com o endereço da casa', e esses mini catálogos de endereços estão por todo lugar, assim como um monte de post-its que explicam onde encontrar os mini catálogos de endereços.
e agora voltando a como funciona em termos Java
Uma LinkedList consiste em uma referência ao primeiro e ao último nó. Um nó é um pequeno objeto que consiste em uma referência ao próximo nó, ao nó anterior e ao objeto que esta entrada na lista representa. Para, por exemplo, iterar pelos primeiros 10 itens de uma lista encadeada e, por exemplo, imprimi-los todos, a JVM precisa resolver a referência à lista encadeada, a partir daí resolver a referência ao primeiro nó, a partir daí resolver a referência ao objeto e imprimi-la, então resolver a referência ao próximo nó, resolver a referência ao objeto e imprimi-la, resolver a referência ao próximo nó e assim por diante.
Cada pequeno objeto nó é criado conforme você adiciona um objeto e, a menos que você faça isso de uma só vez, esses objetos nó ficam espalhados por todo o heap. E, claro, os objetos que a lista contém podem ou não estar espalhados por todo o heap, dependendo de quando foram criados.
Em contraste, com um
ArrayList, você simplesmente tem uma série consecutiva garantida de referências aos objetos reais contidos na lista. Esses objetos podem não ser consecutivos , mas pelo menos as referências a eles são.Então o que isso significa?
Tudo se resume a apenas duas palavras, que são tudo o que você precisa saber como um programador Java sobre listas vinculadas.
LinkedList RUIM.
É isso. É só isso. O número de casos em que uma LL é a resposta correta é extremamente pequeno. ArrayList costuma ser melhor, mas certamente nem sempre; no entanto, alguma outra variante de coleção será melhor que LL em praticamente todos os casos de uso imagináveis.
Várias abordagens agnósticas de linguagem sobre LL fazem afirmações que podem se aplicar a uma LinkedList, mas não se aplicam à abordagem de Java . Por exemplo, "a vantagem de uma lista encadeada é que, dado um objeto na lista, é muito rápido inserir um objeto logo depois dele". Isso é falso - dado um item em uma lista encadeada, você não pode "voltar" ao nó da lista encadeada em Java . Em essência, a única maneira de começar a aproveitar os benefícios de LLs em Java é usar o
.listIterator()método raramente usado, que de fato pode fazer uma inserção rápida de um valor de uma forma com a qual ArrayList não pode competir. Sem listIterator, a única coisa que LL pode fazer que AL não pode fazer é "adicionar/remover rapidamente do início e do fim".Mas se é isso que você quer, use
ArrayDeque- muito mais eficiente na função de 'uma coisa de lista que permite adicionar/remover rapidamente de qualquer extremidade'.[1] Vários aspectos do Valhalla e do Panamá significam que essas declarações precisarão de muitas ressalvas em breve. A partir do JDK24, isso é preciso. Se você sabe o que são o Projeto Valhalla e o Panamá, sim, a mudança está no horizonte.
Sim, ArrayList armazena referências em um array contíguo, tornando o acesso sequencial mais rápido para o cache da CPU. Os nós de LinkedList estão espalhados na memória, causando mais falhas de cache.
Vou responder de duas maneiras: com uma resposta técnica e com um exemplo interessante e fácil de seguir. Precisei pesquisar um pouco antes de responder, e simplificar as coisas sempre me ajuda, então vamos primeiro apresentar a terminologia do cache:
Cache: um cache é como uma mesa de leitura especial onde são colocados os livros mais usados. Em vez de correr para as prateleiras toda vez, o computador pode pegar o livro específico da mesa.
Agora, como isso se relaciona com sua pergunta?
O ArrayList armazena dados em uma fileira na mesa de leitura. Assim, quando o computador lê um livro, já tem o próximo por perto, tornando a leitura super rápida e eficiente. Consequentemente, o acesso sequencial é mais rápido.
A LinkedList é como um conjunto de livros dispersos onde você precisa seguir as notas que levam ao próximo livro. Toda vez que o computador precisa de um novo livro, ele precisa passar por outra prateleira.
Agora você pode querer uma resposta mais "técnica", então aqui está:
Em ArrayList:
Como todos os elementos estão em um único bloco, acessar um elemento carrega automaticamente os elementos próximos no cache. Isso obviamente torna a iteração muito mais rápida, pois a CPU recupera mais elementos de uma só vez.
Em LinkedList:
Como os nós estão espalhados pela memória, acessar um nó não garante que o próximo esteja próximo. Cada acesso a um nó envolve uma desreferência de ponteiro, resultando em mais perdas de cache.
Para resumir: ao iterar em uma LinkedList, tanto a referência ao objeto quanto a referência ao próximo nó precisam ser resolvidas, muitas vezes causando mais perdas de cache do que em uma ArrayList, onde o próximo elemento é simplesmente a próxima posição na memória.
Aqui está um artigo que me ajudou: Por que a localidade do cache é importante para o desempenho de arrays? Esta discussão no Stack Overflow é semelhante. Ela se aprofunda nas vantagens da localidade do cache em arrays em comparação com linkedLists.