A hierarquia de memória e os números de latência

Um processador soma dois números em uma fração de nanossegundo, mas buscar um número que não está em nenhum cache pode levar 80 ns. Esta aula transforma esses números de latência em uma só cifra, o custo médio de um acesso à memória, e mostra qual nível de memória consome o seu tempo.

Um programa de trading passa a maior parte da vida esperando dados: um preço, uma ordem, uma linha de tabela. A aritmética sobre esses dados é quase de graça, mas os dados precisam antes viajar da memória até o processador, e quanto mais longe estão, mais demora. Pense numa mesa, uma estante, o andar de uma biblioteca e um armazém do outro lado da cidade. Os poucos papéis da mesa são instantâneos, a estante leva segundos, a biblioteca um minuto e o armazém uma tarde. Os computadores copiam os dados mais usados para memórias pequenas e rápidas junto ao processador, chamadas caches, para que a maioria dos pedidos seja atendida na mesa.

Um núcleo de servidor típico tem três caches na frente da memória principal. Chamamos de L1, L2 e L3, e a memória principal de RAM. Um pedido atendido por um cache é um acerto; um pedido que precisa seguir para o próximo nível é uma falta. A tabela abaixo põe as quatro latências lado a lado.

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}for level, ns in LATENCY_NS.items():    print(level, ns, "ns", ns / LATENCY_NS["L1"], "x L1")

L1 1.0 ns 1.0 x L1
L2 4.0 ns 4.0 x L1
L3 15.0 ns 15.0 x L1
RAM 80.0 ns 80.0 x L1

Cada nível é várias vezes mais lento que o de cima, e a RAM é 80 vezes mais lenta que a L1. Toda esta habilidade trata de garantir que a maioria dos acessos seja atendida perto do topo.

Um acesso começa na L1. Se o valor está lá, o acesso custa a latência da L1 e acaba. Se não, o processador pergunta à L2, depois à L3 e depois à RAM, que sempre tem o valor. Cada nível consultado custa tempo, acerte ou não, então um acesso encontrado na L3 pagou L1, L2 e L3.

1. 1
   Perguntar à L1Pague 1 ns. Um acerto termina o acesso.
2. 2
   Em caso de falta, perguntar à L2Pague mais 4 ns. Um acerto termina o acesso.
3. 3
   Em caso de falta, perguntar à L3Pague mais 15 ns. Um acerto termina o acesso.
4. 4
   Em caso de falta, ir à RAMPague mais 80 ns. A RAM sempre tem o valor.

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}cost_found_in_l3 = LATENCY_NS["L1"] + LATENCY_NS["L2"] + LATENCY_NS["L3"]print(cost_found_in_l3, "ns")

20.0 ns

Um acesso atendido pela L3 custa 20 ns, não 15: o 1 ns e os 4 ns gastos nas duas faltas anteriores fazem parte da conta.

Nenhum acesso é típico, então pedimos a média de muitos acessos. Pondere o custo de cada caminho por sua frequência. Todo acesso paga a latência da L1; só a parte que falha na L1 paga a L2; só a que falha nas duas paga a L3; e assim por diante. Escrito como uma expressão, com parênteses que se aninham como os níveis:

Este é o tempo médio de acesso à memória. Leia os parênteses de dentro para fora: o mais interno é o que custa uma falta na L3, o seguinte soma a visita à L3, e assim por diante até a visita à L1 que todo acesso paga.

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}h1, h2, h3 = 0.9, 0.8, 0.7t = LATENCY_NSamat = t["L1"] + (1 - h1) * (t["L2"] + (1 - h2) * (t["L3"] + (1 - h3) * t["RAM"]))1print(round(amat, 2), "ns")

2.18 ns

1. 11 - h é a parte dos acessos que falham, então cada parêntese é multiplicado pela parte que chega até ali.

Com 90% dos acessos acertando na L1, a média ainda é 2,18 ns, mais que o dobro da latência da L1. Os poucos acessos que vão fundo são tão caros que puxam a média. Por isso uma taxa de acerto que parece excelente ainda pode esconder um programa lento.

Duas perguntas parecem iguais mas têm respostas diferentes. Qual nível atende os acessos? E qual nível leva o tempo? A primeira conta acessos, a segunda conta espera. Um nível é alcançado por uma parte dos acessos e cada visita custa a sua latência, então um nível raramente alcançado mas lento ainda pode dominar a espera.

h1, h2, h3 = 0.9, 0.8, 0.7served = [h1, (1 - h1) * h2, (1 - h1) * (1 - h2) * h3, (1 - h1) * (1 - h2) * (1 - h3)]reach = [1.0, 1 - h1, (1 - h1) * (1 - h2), (1 - h1) * (1 - h2) * (1 - h3)]1cost = [r * ns for r, ns in zip(reach, [1.0, 4.0, 15.0, 80.0])]2print([round(x, 3) for x in served])print([round(c / sum(cost), 3) for c in cost])

[0.9, 0.08, 0.014, 0.006]
[0.459, 0.183, 0.138, 0.22]

1. 1reach é a parte dos acessos que visitam cada nível: todos visitam a L1.
2. 2sum(cost) é o tempo médio de acesso: os mesmos 2,18 ns de antes.

A RAM atende só 0,6% dos acessos mas responde por 22% do tempo de espera, enquanto a L1 atende 90% deles e leva 46% do tempo. Este é o fato central por trás de toda otimização desta habilidade: não conte acessos, conte para onde vai o tempo.

Quanto isso importa numa tabela real? A tabela de barras diárias do SPY do laboratório tem 5.405 linhas e cinco colunas (abertura, máxima, mínima, fechamento, volume), ou seja, 27.025 valores. Leia cada valor uma vez em três condições: caches quentes onde quase tudo acerta, caches mornos e caches frios onde metade dos acessos falha em cada nível.

O laboratório transforma esta aula em seis funções pequenas, cada uma construída sobre as anteriores, e termina precificando a leitura da tabela real do SPY. Aqui estão elas com a pergunta que cada uma responde.

• Função · perguntaBaseia-se em
• average_access_time(hit_rates)Quanto custa um acesso em média?A tabela de latências
• slowdown(hit_rates)Quantas vezes mais lento que acertar sempre na L1?average_access_time
• levels_served(hit_rates)Qual nível atende os acessos?Taxas de acerto locais
• time_shares(hit_rates)Qual nível leva o tempo?average_access_time
• scan_time_us(n_accesses, hit_rates)Quanto tempo levam n acessos?average_access_time
• study(bars)Quanto custa ler toda a tabela do SPY?scan_time_ustime_shares

Próximo tópico: esta aula tomou as taxas de acerto como dadas. Em Linhas de cache e localidade espacial você constrói o cache que as produz e descobre por que ler um valor ao lado de outro recém-lido é quase de graça.