Início / coding / Perguntas / 78689825
Accepted
i like bananas
Asked: 2024-07-01 05:17:25 +0800 CST

Como armazenar itens na pilha LIFO de maneira amigável ao cache?

  • 772

EDITAR / AVISO LEGAL:

Parece que meu entendimento das linhas de cache estava errado, o que torna esta questão irrelevante e enganosa. Pensei que sempre que a CPU tenta buscar uma memória em um índice específico, ela também captura índices logo após o primeiro, o que NÃO é verdade. Consulte Como funcionam as linhas de cache? para referência.

Eu estava prestes a escrever um contêiner de dados para armazenar um bloco de memória contínuo e redimensionável, no qual os itens só seriam possíveis de acessar de um lado, pressionando ou popping - basicamente uma pilha LIFO. Tenho lido muito sobre cache da CPU e padrões de acesso à memória e queria que esse contêiner fosse o mais amigável possível ao cache.

Então, dei uma olhada nas implementações comuns de pilhas LIFO na Internet. A maioria deles sugere usar um array dinâmico como base e acessar os dados anexando ou removendo itens do final do array. Neste caso, a lacuna de capacidade vazia é armazenada após os dados da seguinte maneira:

 stack bottom            stack top
 array begin             V  array end
 V                       V  V
|V          data         V |V     gap     |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|8 |7 |6 |5 |4 |3 |2 |1 |0 |  |  |  |  |  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                        |       cache line       |

No entanto, isso não me parece muito amigável ao cache. Sempre que alguém procura o item no topo da pilha, a CPU busca a memória do espaço que contém lixo, ou pelo menos é assim que eu entendo.

A abordagem onde a lacuna aparece como o início do bloco de memória e os dados no final teria melhor desempenho? Neste caso os índices dos itens seriam invertidos, assim como inferior e superior. Neste caso a linha de cache poderia atingir mais itens como este:

                stack top               stack bottom
                V                       V
|      gap     |V          data         V |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |  |  |  |  |0 |1 |2 |3 |4 |5 |6 |7 |8 |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
               |       cache line      |

Meu entendimento está correto aqui? Qual abordagem tem melhor desempenho e é mais amigável ao cache?

Posso estar totalmente errado com minhas suposições. Como eu disse, a maioria das implementações que vi usam a primeira abordagem, então deve haver algo nisso.

Saúde!

algorithm

1 respostas

  1. Best Answer

    As pilhas LIFO que usam uma matriz são igualmente compatíveis com o cache para qualquer direção de crescimento, a menos que você tenha um padrão específico de tamanhos que favoreça uma alocação de tamanho ímpar e um crescimento decrescente.

    APIs para realocação eficiente (sem copiar os dados), como Linux mremapou C, reallocsão projetadas para adicionar novo espaço no final de uma alocação, não no início, então esse é um ponto a favor da maneira normal se sua pilha puder crescer além da alocação inicial . Pelo menos se você estiver usando uma API de alocação que suporte isso, não como o C++ prejudicado new/ deleteque essencialmente força std::vectora ser uma merda.

    Fora isso, eles são iguais, a menos que seu limite máximo seja geralmente 1 ou 2 elementos a mais que um múltiplo de 64 bytes, como você mostrou aqui para fazer sua outra versão parecer boa. Nessa versão, o primeiro elemento enviado está sozinho em uma linha de cache, mas o topo da pilha ainda não cruzou para uma nova linha de cache.

    Se você inserir mais um elemento em seu segundo diagrama, ele será o único elemento em uso em sua linha de cache. Parece bom apenas porque você escolheu um número de elementos para o estado atual da pilha que funciona bem com o desalinhamento (em relação aos limites da linha de cache) escolhido para o primeiro elemento (a "parte inferior" da pilha, no ponto mais alto endereço para sua pilha crescente).

    Com seu design de lacuna na frente crescente, potencialmente o primeiro elemento enviado (endereço mais alto) está na mesma linha de cache que alguns outros dados úteis, de modo que a linha de cache permanecendo quente pode ser útil (se sua pilha frequentemente fica vazio para que você realmente acesse esse elemento).
    Os alocadores de memória geralmente arredondam as alocações para múltiplos de tamanho maior, como 16 bytes, mas ainda pode haver outras alocações em uma linha de cache.
    Ainda assim, a menos que você saiba algo especial sobre os tamanhos de pilha esperados e/ou o que vem a seguir, normalmente você desejaria alocar um pedaço de memória que seja um múltiplo do tamanho da linha de cache.

    Curiosidade: a pilha de chamadas asm diminui nos ISAs convencionais (e nas convenções de chamada para ISAs como MIPS, que não favorecem uma direção de crescimento da pilha). por exemplo, x86 pushe calldiminuir o registro de ponteiro de pilha (RSP). As razões para isso não são a eficiência do cache, mas sim históricas , que remontam a antes das CPUs terem caches. No entanto, não apresenta problemas específicos para caches de CPU.

    As pilhas de CPU/asm são alocadas de forma que a linha de cache de endereço mais alto seja totalmente usada, ao contrário da sua, onde o fim da alocação não é o fim de uma linha de cache. (Normalmente, "a pilha" é um múltiplo do tamanho da página, portanto, de qualquer maneira, não haverá outras coisas próximas a ela na mesma linha.)

    • 1

relate perguntas