Projeto final: reorganizar uma tabela de ticks e provar a redução de faltas

Tudo o que esta habilidade ensinou se junta numa tabela de ticks. Oito colunas, três tarefas que a leem de jeitos diferentes e três disposições na memória. Você modela o endereço de cada valor, conta as faltas de cada tarefa com o cache que construiu, as precifica com o modelo de latência e prova qual disposição vence. Nenhuma vence todas as tarefas; a híbrida vence a mistura, com 1,5 vezes menos faltas que o array de structs.

Uma tabela de ticks tem 8 colunas de 8 bytes: um timestamp, os preços e tamanhos de bid e ask, o preço do negócio, seu tamanho e alguns flags. Uma linha tem exatamente 64 bytes, o tamanho de uma linha de cache. Três tarefas leem essa tabela. Uma varredura lê a coluna de preço de cada linha, para uma média móvel. Uma tarefa de cotação lê o bid, o ask e o tamanho do bid de cada linha, para montar um livro. Uma consulta lê o tick completo de 1000 linhas escolhidas pela tabela, como faz um depurador ou um replay. A memória do primeiro tópico tem uma hierarquia, a do segundo uma linha de 64 bytes e a do quinto duas disposições de uma tabela: o array de structs (os valores de uma linha juntos) e o struct de arrays (cada coluna separada). Agora há um terceiro caminho, o híbrido, que mantém juntas as colunas quentes de cotação e juntas as colunas frias.

As três disposições são uma só ideia. Uma disposição é uma lista de grupos de colunas. Os valores de um grupo são guardados linha após linha e os grupos se seguem. Um grupo com todas as colunas é o array de structs; um grupo por coluna é o struct de arrays; dois grupos de quatro colunas são o nosso híbrido. Assim uma função dá o endereço de qualquer valor em qualquer disposição: pular os grupos antes do que contém a coluna e avançar row * len(group) + position valores dentro dele.

def address(groups, row, col, n_rows, elem_bytes=ELEM_BYTES):    base = 0    for group in groups:        if col in group:            return base + (row * len(group) + group.index(col)) * elem_bytes        base += n_rows * len(group) * elem_bytes1    raise ValueError("column %d is in no group" % col)print(address([[0, 1, 2]], 2, 1, 10))print(address([[0], [1], [2]], 2, 1, 10))print(address([[1, 2], [0]], 3, 0, 10))

56
96
184

1. 1Um grupo ocupa n_rows * len(group) * elem_bytes bytes: o grupo seguinte começa logo depois.

Confira os três resultados à mão. Com um grupo de três colunas, a linha 2 coluna 1 é o valor número 2 × 3 + 1 = 7, no byte 56. Com um grupo por coluna, a coluna 1 começa depois dos 10 valores da coluna 0, no byte 80, e a linha 2 fica 16 bytes adiante: 96. No híbrido [[1, 2], [0]] o grupo da coluna 0 vem em segundo, depois de 10 linhas de 2 valores (160 bytes), e a linha 3 fica 24 bytes adiante: 184.

Uma tarefa é a lista de colunas que ela lê em cada linha que visita. Seu trace é, para cada linha em ordem, os endereços dessas colunas; o cache transforma o trace em faltas; e o modelo de latência do primeiro tópico transforma faltas em tempo, com 1 ns por acerto e 80 ns por falta. A comparação é então um laço sobre as disposições e a prova é o menor número. Rode as três tarefas da aula em 4000 ticks e você vê que a melhor disposição depende da tarefa.

def workload_trace(groups, n_rows, reads, rows):    return [address(groups, row, col, n_rows) for row in rows for col in reads]def layout_misses(groups, n_rows, reads, rows=None):    rows = range(n_rows) if rows is None else rows    return count_misses(workload_trace(groups, n_rows, reads, rows))def compare_layouts(layouts, n_rows, reads, rows=None):    return {name: layout_misses(groups, n_rows, reads, rows) for name, groups in layouts.items()}def best_layout(misses):    return min(misses, key=misses.get)def time_ns(accesses, misses, hit_ns=HIT_NS, miss_ns=MISS_NS):    return (accesses - misses) * hit_ns + misses * miss_nsprint(workload_trace([[0, 1]], 4, [1, 0], [2]))for job, reads in WORKLOADS.items():    rows = sampled_rows(4000) if job == "lookup" else None    result = compare_layouts(LAYOUTS, 4000, reads, rows)    print(job, result, "->", best_layout(result))

[40, 32]
scan {'aos': 4000, 'soa': 500, 'hybrid': 2000} -> soa
quote {'aos': 4000, 'soa': 1500, 'hybrid': 2000} -> soa
lookup {'aos': 1000, 'soa': 8000, 'hybrid': 2000} -> aos

A varredura quer uma só coluna: o struct de arrays empacota oito preços por linha (500 faltas) e o array de structs desperdiça sete oitavos de cada linha que carrega (4000 faltas). A consulta pontual quer os oito valores de uma linha: o array de structs usa uma linha (1000 faltas) e o struct de arrays oito (8000). A cotação lê três das quatro colunas do grupo quente, então o híbrido é bom mas não o melhor. Qual disposição escolher depende da frequência de cada tarefa, e é isso que a mistura mede.

def study(bars):    n_rows = min(int(bars.shape[0]), 4000)    misses = {}    accesses = 0    for job, reads in WORKLOADS.items():        rows = sampled_rows(n_rows) if job == "lookup" else None        misses[job] = compare_layouts(LAYOUTS, n_rows, reads, rows)        accesses += len(reads) * (len(rows) if rows is not None else n_rows)    mixed = {name: sum(misses[job][name] for job in WORKLOADS) for name in LAYOUTS}    best = best_layout(mixed)    return {"mixed": mixed, "mixed_best": best, "reduction": mixed["aos"] / mixed[best],            "ns": {name: time_ns(accesses, mixed[name]) for name in LAYOUTS}}out = study(load_bars())print(out["mixed"], "->", out["mixed_best"])print(round(out["reduction"], 2), "times fewer misses than the array of structs")print({name: round(ns / 1000) for name, ns in out["ns"].items()}, "microseconds")

{'aos': 9000, 'soa': 10000, 'hybrid': 6000} -> hybrid
1.5 times fewer misses than the array of structs
{'aos': 735, 'soa': 814, 'hybrid': 498} microseconds

Somando, o array de structs falta 9000 vezes, o struct de arrays 10 000 e o híbrido 6000. O híbrido não vence nenhuma tarefa de forma clara e não perde nenhuma feio: as varreduras e as cotações custam o dobro do que paga o struct de arrays, as consultas o dobro do que paga o array de structs, e a mistura favorece a disposição que nunca é péssima. No modelo de latência são 498 µs contra 735 µs do array de structs: 1,5 vez menos faltas e um terço a menos de tempo. Essa é a prova que o projeto final pede, e vale só para esta mistura de tarefas.

O laboratório segue a aula: o endereço de um valor em qualquer disposição, o trace de uma tarefa, as faltas de uma tarefa em uma disposição e em todas, a melhor disposição, o tempo de uma tarefa e o estudo da tabela de ticks com a prova da mistura.

• Função · perguntaBaseia-se em
• address(groups, row, col, n_rows)Onde está este valor na memória?Aritmética simples
• workload_trace(groups, n_rows, reads, rows)Quais endereços a tarefa toca?address
• layout_misses(groups, n_rows, reads, rows)Quantas faltas nesta disposição?workload_tracecount_misses
• compare_layouts(layouts, n_rows, reads, rows)E em cada disposição?layout_misses
• best_layout(misses)Qual vence?Aritmética simples
• time_ns(accesses, misses)Quanto custa em tempo?Aritmética simples
• study(bars)Qual disposição vence a mistura de tarefas?compare_layoutsbest_layouttime_ns

Próxima habilidade: o lado de memória do desempenho está feito. As próximas habilidades da trilha de otimização passam para o processador: executar a mesma operação em muitos valores de uma vez em registradores vetoriais e compartilhar dados entre núcleos sem travas.