Desempenho do código orientado ao ADT de atribuição única em CPUs modernas

32

Trabalhar em dados imutáveis ​​com atribuições únicas tem o efeito óbvio de exigir mais memória, presume-se, porque você está constantemente criando novos valores (embora os compiladores ocultos façam truques de ponteiro para tornar isso menos um problema).

Mas ouvi algumas vezes agora que as perdas no desempenho são superadas pelos ganhos na maneira como a CPU (seu controlador de memória especificamente) pode tirar proveito do fato de que a memória não é mutada (tanto).

Eu esperava que alguém pudesse lançar alguma luz sobre como isso é verdade (ou se não é?).

Em um comentário em outro post , foi mencionado que os Abstract Data Types (ADTs) têm a ver com isso, o que me deixou ainda mais curioso, como os ADTs afetam especificamente a maneira como a CPU lida com a memória? No entanto, isso é um aparte, principalmente, estou interessado apenas em como a pureza da linguagem afeta necessariamente o desempenho da CPU e seus caches, etc.

Jimmy Hoffa
fonte
2
isto é principalmente útil em multithreading, onde um leitor pode atomicamente agarrar um instantâneo e ser seguro no conhecimento de que ele não vai sofrer mutação, enquanto ele está lendo isso
aberração catraca
@ratchetfreak Eu entendo isso do ponto de vista da programação, que o seu código tem mais garantias de segurança, mas minha curiosidade é sobre o controlador de memória na CPU e como esse comportamento é importante para ele (ou se não), como ouvi alegações sobre uma mão cheia de vezes que disse que era mais eficiente para o controlador de memória, e eu não conheço os detalhes de baixo nível o suficiente para dizer se ou como isso pode ser verdade.
Jimmy Hoffa
Mesmo se fosse verdade, eu não pensaria que menos modificações de memória são o melhor ponto de venda para imutabilidade. Afinal, a memória está para ser modificada, e as CPUs e os gerenciadores de memória ficaram muito bons nisso ao longo dos anos.
precisa saber é o seguinte
1
Eu também gostaria de salientar que a eficiência da memória não precisa necessariamente depender das otimizações do compilador ao usar estruturas imutáveis. Neste exemplo let a = [1,2,3] in let b = 0:a in (a, b, (-1):c)partilha reduz os requisitos de memória, mas depende da definição de (:)e []e não o compilador. Eu acho que? Não tenho certeza sobre este.

Respostas:

28

A CPU (seu controlador de memória especificamente) pode tirar proveito do fato de que a memória não está mutada

A vantagem é que esse fato evita que o compilador use as instruções do membar quando os dados são acessados.

Uma barreira de memória, também conhecida como membar, cerca de memória ou instrução de cerca, é um tipo de instrução de barreira que faz com que uma unidade central de processamento (CPU) ou compilador imponha uma restrição de ordem nas operações de memória emitidas antes e depois da instrução de barreira. Isso normalmente significa que certas operações são garantidas para serem realizadas antes da barreira e outras depois.

Barreiras de memória são necessárias porque a maioria das CPUs modernas emprega otimizações de desempenho que podem resultar em execução fora de ordem. Essa reordenação das operações de memória (cargas e armazenamentos) normalmente passa despercebida em um único encadeamento de execução, mas pode causar comportamento imprevisível em programas simultâneos e drivers de dispositivo, a menos que seja cuidadosamente controlado ...


Veja, quando os dados são acessados ​​a partir de diferentes threads, na CPU com vários núcleos, é o seguinte: threads diferentes são executados em núcleos diferentes, cada um usando seu próprio cache (local ao núcleo) - uma cópia de algum cache global.

Se os dados são mutáveis ​​e o programador precisa que ele seja consistente entre diferentes threads, é necessário tomar medidas para garantir a consistência. Para programador, isso significa usar construções de sincronização quando eles acessam (por exemplo, ler) dados em um encadeamento específico.

Para o compilador, a construção de sincronização no código significa que ele precisa inserir uma instrução membar para garantir que as alterações feitas na cópia dos dados em um dos núcleos sejam propagadas adequadamente ("publicadas"), para garantir que os caches em outros núcleos tenha a mesma cópia (atualizada).

Um pouco simplificador, veja a nota abaixo , eis o que acontece no processador multi-core para membar:

  1. Todos os núcleos param o processamento - para evitar a gravação acidental no cache.
  2. Todas as atualizações feitas nos caches locais são gravadas novamente no global - para garantir que o cache global contenha os dados mais recentes. Isso leva algum tempo.
  3. Os dados atualizados são gravados de volta do cache global para os locais - para garantir que os caches locais contenham os dados mais recentes. Isso leva algum tempo.
  4. Todos os núcleos retomam a execução.

Veja bem, todos os núcleos não estão fazendo nada enquanto os dados estão sendo copiados entre os caches globais e locais . Isso é necessário para garantir que os dados mutáveis ​​sejam sincronizados corretamente (thread-safe). Se houver 4 núcleos, todos os 4 param e esperam enquanto os caches estão sendo sincronizados. Se houver 8, todos os 8 param. Se houver 16 ... bem, você tem 15 núcleos que não fazem exatamente nada enquanto esperam pelo que é necessário fazer em um deles.

Agora, vamos ver o que acontece quando os dados são imutáveis? Não importa qual thread acessa, é garantido o mesmo. Para programador, isso significa que não há necessidade de inserir construções de sincronização quando eles acessam dados (lidos) em um encadeamento específico.

Para o compilador, isso significa que não há necessidade de inserir uma instrução membar .

Como resultado, o acesso aos dados não precisa parar núcleos e aguardar enquanto os dados estão sendo gravados entre caches globais e locais. Essa é uma vantagem do fato de a memória não estar mutada .


Observe que a explicação um pouco simplificadora acima elimina alguns efeitos negativos mais complicados de os dados serem mutáveis, por exemplo, no pipelining . Para garantir a solicitação necessária, a CPU precisa invalidar as linhas de controle afetadas pelas alterações de dados - isso é mais uma penalidade no desempenho. Se isso for implementado através da invalidação direta (e, portanto, confiável) de todos os pipelines, o efeito negativo será amplificado.

mosquito
fonte