Localidade temporal e conjuntos de trabalho

Um cache só ajuda com dados que você lê de novo, e o que importa é quão cedo. Esta aula mede isso com um único número, a distância de reutilização, e o usa para prever de uma vez a taxa de acertos de todos os tamanhos de cache, incluindo o precipício em que um laço é só um pouco grande demais para caber.

Os dois últimos tópicos trataram de para onde vão as linhas. Este trata de quando elas voltam. Um programa que lê um preço, trabalha um pouco e lê o mesmo preço de novo um instante depois mostra localidade temporal. Quanto menor a lacuna, maior a chance de a linha ainda estar no cache. Pense nos livros da sua mesa: o que você usou há um minuto ainda está lá, o do mês passado voltou para a estante.

Ler a linha 5 duas vezes seguidas dá distância 0. Na sequência 1, 2, 3, 1 a última leitura tem distância 2, porque as linhas 2 e 3 vieram no meio. Ler dez vezes a linha 2 entre duas leituras da linha 1 ainda conta como uma só linha. O código guarda uma lista das linhas na ordem do último uso, a mais recente por último. Quando uma linha volta, as linhas depois dela na lista são exatamente as usadas desde então.

def reuse_distances(lines):    stack = []    out = []    for line in lines:        if line in stack:            position = stack.index(line)            out.append(len(stack) - 1 - position)1            stack.pop(position)        else:            out.append(None)        stack.append(line)    return outprint(reuse_distances([1, 2, 3, 1, 2, 1, 1]))

[None, None, None, 2, 2, 1, 0]

1. 1As linhas depois desta na lista são exatamente as usadas desde a sua última leitura: o número delas é a distância.

Eis o fato útil. Pegue um cache que guarda C linhas e remove a menos recentemente usada, sejam quais forem os números das linhas. A cada momento ele guarda as C linhas diferentes usadas mais recentemente. Uma leitura acerta exatamente quando sua linha está entre elas, isto é, quando menos de C linhas diferentes foram lidas desde o último uso. Em outras palavras, a leitura acerta quando sua distância de reutilização é menor que C.

O código abaixo verifica a afirmação. Ele simula um cache LRU para capacidades de 1 a 4 e também calcula a taxa de acertos só a partir das distâncias, sem cache algum. As duas colunas concordam. As distâncias são calculadas uma vez e depois dão a taxa de acertos de cada tamanho de cache.

def lru_hit_rate(lines, capacity):    cache = []    hits = 0    for line in lines:        if line in cache:            hits += 1            cache.remove(line)        elif len(cache) >= capacity:            cache.pop(0)        cache.append(line)    return hits / len(lines)def hit_rate_from_distances(distances, capacity):    hits = sum(1 for d in distances if d is not None and d < capacity)    return hits / len(distances)lines = [1, 2, 3, 1, 2, 3, 4, 1, 2, 3]d = reuse_distances(lines)for capacity in (1, 2, 3, 4):    print(capacity, "lines:", round(lru_hit_rate(lines, capacity), 3), round(hit_rate_from_distances(d, capacity), 3))1

1 lines: 0.0 0.0
2 lines: 0.0 0.0
3 lines: 0.3 0.3
4 lines: 0.6 0.6

1. 1Os mesmos números nas duas colunas: as distâncias sozinhas preveem a taxa de acertos de cada tamanho de cache.

O conjunto de trabalho de um trecho de leituras é o conjunto de linhas diferentes que elas tocam. Se cabe no cache, o programa roda quase todo a partir do cache. Se é só um pouco maior, o LRU pode falhar por completo. Pegue um laço que lê 48 linhas em ordem, três vezes. Cada linha é lida de novo depois de outras 47, então toda distância de reutilização é 47. Um cache de 47 linhas ou menos nunca acerta, e um de 48 acerta em toda leitura depois da primeira passada.

def sweep_lines(n_lines, passes):    return list(range(n_lines)) * passeslines = sweep_lines(48, 3)for capacity in (16, 32, 47, 48):    print(capacity, "lines:", round(lru_hit_rate(lines, capacity), 3))

16 lines: 0.0
32 lines: 0.0
47 lines: 0.0
48 lines: 0.667

Uma média móvel calculada do jeito lento lê os últimos 20 valores todo dia: ela relê 19 dos 20 valores lidos no dia anterior. É um programa com muita localidade temporal. O código monta os endereços lidos para os primeiros 600 fechamentos, transforma-os em linhas e mede as distâncias, a taxa de acertos para quatro tamanhos de cache e o conjunto de trabalho de 20 leituras consecutivas.

def rolling_mean_trace(n, window, elem_bytes):    trace = []    for end in range(window - 1, n):        for position in range(end - window + 1, end + 1):            trace.append(position * elem_bytes)    return tracedef working_set(lines, window):    return max(len(set(lines[i:i + window])) for i in range(len(lines) - window + 1))lines = [address // 64 for address in rolling_mean_trace(600, 20, 8)]d = reuse_distances(lines)print(len(lines), "reads from", len(set(lines)), "lines")for capacity in (1, 2, 4, 8):    print(capacity, "lines:", round(hit_rate_from_distances(d, capacity), 3))print("working set of 20 reads:", working_set(lines, 20), "lines")

11620 reads from 75 lines
1 lines: 0.831
2 lines: 0.831
4 lines: 0.994
8 lines: 0.994
working set of 20 reads: 4 lines

Uma linha basta para 83% das leituras, porque o próximo valor do array está na linha que acabou de ser lida. Quatro linhas chegam a 99,4%. As 75 linhas do conjunto de dados nunca precisam caber: o conjunto de trabalho de 20 leituras é só de 4 linhas, então um cache minúsculo basta. Essa é a diferença entre o tamanho dos dados e o tamanho do conjunto de trabalho.

O laboratório pede as peças acima, mais o auxiliar que acha o menor cache para uma taxa de acertos, e termina com o estudo sobre os fechamentos reais do SPY.

• Função · perguntaBaseia-se em
• reuse_distances(lines)Quão cedo cada linha é lida de novo?Uma lista em ordem do último uso
• lru_hit_rate(lines, capacity)Quanto acerta um cache LRU simulado?Linhas em ordem LRU
• hit_rate_from_distances(distances, capacity)A mesma taxa de acertos, sem cache?reuse_distances
• working_set(lines, window)Quantas linhas um trecho de leituras toca?Uma janela deslizante
• capacity_for(lines, target)Quão pequeno o cache pode ser?reuse_distanceshit_rate_from_distances
• rolling_mean_trace(n, window, elem_bytes)Quais endereços uma média móvel lenta lê?Aritmética simples
• study(bars)Quão local é uma média móvel sobre os fechamentos do SPY?rolling_mean_tracecapacity_for

Próximo tópico: agora você sabe como uma disposição vira um rastro e um rastro vira acertos e faltas. Em Array de structs contra struct de arrays você usa isso para escolher como dispor uma tabela de ticks, comparando leituras de colunas e de linhas inteiras nas duas disposições.