Ir para o conteúdo

Cachelines e False Sharing

5 min. de leitura

Avatar de Thiago Borba

Thiago Borba Autoria do conteúdo


False sharing é um problema que ocorre quando threads físicas paralelas acessam uma mesma cacheline que possui dados pequenos e que sofrem alterações constantes. False sharing é um problema universal em processadores onde as linhas de cache são compartilhadas com mais de uma thread.

Navegue pelo conteúdo com os links abaixo!

1. CPU Cache

1.1 Cacheline

1.2 Cache coherence protocol

1.3 Otimização de compiladores

2. False sharing

2.1 Cenário A – False sharing

2.2 Cenário B – Otimização de código

2.3 Benchmark Cenários A e B

3. Conclusão

CPU Cache

Os processadores possuem estratégias de caching para manter as próximas instruções a serem executadas e blocos de dados a serem manipulados o mais próximo de uma thread, economizando ciclos para buscar dados na memória RAM; busca que no contexto de CPU é extremamente lenta. O cache de CPU é distribuído em níveis, onde L1 é um cache muito pequeno, exclusivo para um core e compartilhado com as suas threads, e o L2 é um cache um pouco maior, compartilhado por um grupo de core.

Cacheline

O processador busca dados na memória em blocos e não ‘byte’ a ‘byte’. Esses blocos de dados são chamados de cacheline. Quando o processador lê um determinado ponto da memória, ele busca, a partir desse ponto, a quantidade de dados equivalentes ao tamanho da cacheline. Em média, uma linha de cache possui 64 ‘bytes’, variando de acordo com a arquitetura do processador. Quanto maior o tamanho do cache, maior é quantidade de linhas — ou seja, menor é a quantidade de leituras na memória RAM.

ProcessadorCache L1Cache L2Cache L3LançamentoPreço
i7-9750H32K256K12M2019~USD 395
Xeon E5-2620384K1,5M15M2012~USD 410
Tamanho do cache e cacheline

Para verificar o tamanho do cache e cacheline em uma máquina com Windows, utilize o aplicativo Coreinfo da Sysinternal.

Tela do aplicativo Coreinfo,
Execução do Coreinfo

Cache coherence protocol

As CPUs modernas, na sua maioria, possuem mais de uma thread por core, utilizando técnicas de programação paralela. Uma das estratégias é utilizar as micropausas de uma thread física (ex.: buscar dados na memória RAM) para que outra thread execute alguma operação.


Tecnologia proprietária

Cada fornecedor define a sua tecnologia para maximizar o desempenho de um processador.


As threads físicas compartilham o cache L1 exclusivo do seu core, assim como o cache L2, que é compartilhado por um grupo de core e outros níveis de cache que possam existir. Por fim, acima dessa estrutura de cache, existe a memória RAM.

Gif que apresenta fluxo entre "P1", "cache" e "memory", assim como "P2", "cache" e "memory".
Uso de cache sem coerência/integridade | Fonte: Wikipédia

Dado o cenário de paralelismo, a CPU deve implementar estratégias de sincronização desses dados para evitar o problema demonstrado na imagem acima. Essa estratégia é chamada de cache coherence protocol. Esse protocolo é responsável por manter a coerência e integridade no cache.

Gif que apresenta fluxo entre "P1", "cache" e "memory", assim como "P2", "cache" e "memory".
Estratégia de coerência | Fonte: Wikipédia

Otimização de compiladores

Os compiladores modernos, além de gerarem códigos que utilizam os recursos fornecidos pelas CPUs, também implementam estratégias e técnicas de otimização, com o objetivo de extrair o máximo do hardware. Porém, nem sempre os compiladores conseguem gerar o código mais performático, por uma série de motivos que, sozinhos, serão tema de um futuro post. Dificilmente esses problemas são detectados nos processos de desenvolvimento e/ou qualidade. Não é incomum que eles ocorram somente em produção de forma não determinística.

False sharing

Em algumas situações, o código de um programador não consegue ser otimizado pelo compilador, o que introduz problemas de desempenho ou até mesmo falhas. Uma dessas situações é o false sharing. O false sharing ocorre quando o cache coherence protocol entende ser necessário atualizar uma determinada linha de cache, fazendo com que ocorra uma nova leitura do dado na memória RAM. Lembrando que leitura de memória RAM num contexto de CPU é uma operação lenta!

Essa situação ocorrerá quando threads físicas fizerem leituras e gravações frequentes de um dado muito pequeno que está alinhado na memória RAM num cenário de paralelismo.

Nos exemplos abaixo, temos um código cujo objetivo é, para cada posição de um array de inteiros, incrementar o valor da referência num ‘looping for’ 1.000.000 de vezes.


Foi utilizado um laptop com um processador i7-9750H para os testes.


Cenário A – False sharing

17,435 segundos para finalizar o processamento.

private readonly int[] sharedArray = new int[4];

public void CenarioA()
{
    var task1 = Task.Run(() => Inc(0));
    var task2 = Task.Run(() => Inc(1));
    var task3 = Task.Run(() => Inc(2));
    var task4 = Task.Run(() => Inc(3));

    Task.WaitAll(task1, task2, task3, task4);
}

private void Inc(int position)
{
    for (var i = 0; i < 1_000_000; i++)
        sharedArray[position]++;
}

Cenário B – Otimização de código

5,72 segundos para finalizar o processamento.

private readonly int[] sharedArray = new int[64];

public void CenarioB()
{
    var task1 = Task.Run(() => Inc(0));
    var task2 = Task.Run(() => Inc(16));
    var task3 = Task.Run(() => Inc(32));
    var task4 = Task.Run(() => Inc(48));

    Task.WaitAll(task1, task2, task3, task4);
}

private void Inc(int position)
{
    for (var i = 0; i < 1_000_000; i++)
        sharedArray[position]++;
}

Benchmark Cenários A e B

No benchmark, observamos que o Cenário B executou aproximadamente 3x mais rápido que o Cenário A.

Tabela comparativa Cenário A x B. Mean: 17.435 ms x 5.722 ms. Error: 0.3354 ms x 0.2482 ms. StdDev: 0.4362 ms x 0.7317 ms. Ratio: 1.00 x 0.29.
Benchmark A x B

No Cenário A, todas as threads compartilham a mesma cacheline para leitura e gravação. Isso faz o cache coherence protocol invalidar diversas vezes a cacheline e, consequentemente, a CPU deve buscar na memória RAM o valor atualizado. Já no Cenário B, utilizamos uma estratégia onde cada thread utiliza uma cacheline diferente! Para fazer isso, são utilizados saltos de 16 posições no array de inteiro, ou seja:

Quantidade de Int32Tamanho Int32Tamanho ocupado
164 bytes16 x 4 bytes = 64 bytes

Considerando que o processador onde o benchmark é executado possui uma cacheline de 64 ‘bytes’, cada thread utilizará uma cacheline diferente.

Conclusão

Apesar dos compiladores ocultarem parte da complexidade da programação paralela, há cenários que precisam da intervenção do programador. Entender como funciona a alocação de memória na sua stack de desenvolvimento, assim como conhecer o funcionamento de componentes de hardware, são ferramentas essenciais para a escrita de códigos de alto desempenho e otimizados.


? Dica ☠️

Otimização prematura do código traz complexidade sem agregar valor! Evite. 🙂



? Informação

False sharing é um problema universal em processadores multithreading que compartilham cache. O exemplo acima funciona em qualquer linguagem. 🙂


Gostou?