Array de structs contra struct de arrays

Uma tabela de ticks pode estar na memória de duas maneiras, e a certa depende de como você a lê. Varrer uma coluna de uma tabela guardada linha a linha carrega cinco vezes a memória que você usa; ler linhas inteiras de colunas separadas desperdiça o mesmo ao contrário. Esta aula conta as faltas das duas disposições e deixa as contagens escolherem.

A memória é uma longa fila de bytes, então uma tabela bidimensional precisa ser achatada. Há duas maneiras naturais. Num array de structs os cinco valores de um dia (abertura, máxima, mínima, fechamento, volume) são guardados juntos, depois os cinco do dia seguinte, e assim por diante. Num struct de arrays vêm primeiro todas as aberturas, depois todas as máximas, e assim por diante. Os valores e o programa são os mesmos, mas os endereços mudam.

O endereço de um valor decorre de sua linha e coluna. No AoS o número do valor é linha vezes o número de colunas mais a coluna. No SoA é coluna vezes o número de linhas mais a linha. Multiplique por 8 bytes para um float64. O código abaixo mostra os endereços dos fechamentos dos quatro primeiros dias numa tabela de 100 dias e 5 colunas.

def address(layout, row, col, n_rows, n_cols, elem_bytes=8):    if layout == "aos":        return (row * n_cols + col) * elem_bytes1    return (col * n_rows + row) * elem_bytesclose = 3print("aos:", [address("aos", row, close, 100, 5) for row in range(4)])print("soa:", [address("soa", row, close, 100, 5) for row in range(4)])

aos: [24, 64, 104, 144]
soa: [2400, 2408, 2416, 2424]

1. 1No AoS a linha seguinte está n_cols valores adiante, então dois fechamentos consecutivos ficam a 5 valores (40 bytes) um do outro.

No AoS os fechamentos de dias consecutivos ficam a 40 bytes uns dos outros. No SoA ficam a 8 bytes, um logo após o outro, que é exatamente a leitura em ordem do primeiro tópico desta habilidade.

Tirar a média dos fechamentos lê uma coluna da tabela. Transformamos essa leitura numa lista de endereços, passamos pelo cache construído nos tópicos anteriores e contamos as faltas para 1000 dias. O último número que mostramos é a parte útil.

def scan_column(layout, col, n_rows, n_cols):    return [address(layout, row, col, n_rows, n_cols) for row in range(n_rows)]for layout in ("aos", "soa"):    misses = count_misses(scan_column(layout, 3, 1000, 5))    print(layout, "misses:", misses, "- useful share:", round(1000 * 8 / (misses * 64), 3))

aos misses: 625 - useful share: 0.2
soa misses: 125 - useful share: 1.0

A varredura SoA falha 125 vezes para 1000 valores, uma falta a cada oito valores e nada desperdiçado. A varredura AoS falha 625 vezes, cinco vezes mais, e só 20% dos bytes carregados são fechamentos. Os outros 80% são aberturas, máximas, mínimas e volumes que a média nunca olha, e eles expulsam linhas úteis do cache.

Muitos programas de ticks fazem outra pergunta: para este tick, me dê o preço, o tamanho e o lado juntos. Isso lê todos os valores de uma linha. No AoS a linha inteira é um bloco de 40 bytes, que fica em uma ou duas linhas de cache. No SoA os cinco valores estão em cinco arrays diferentes, então cada linha abre cinco linhas de cache. O código lê uma linha a cada sete e conta as faltas.

def scan_rows(layout, rows, n_rows, n_cols):    return [address(layout, row, col, n_rows, n_cols) for row in rows for col in range(n_cols)]rows = list(range(0, 1000, 7))for layout in ("aos", "soa"):    print(layout, "misses:", count_misses(scan_rows(layout, rows, 1000, 5)))

aos misses: 214
soa misses: 625

Agora o AoS ganha por um fator de três: 214 faltas contra 625. A disposição que era cinco vezes pior para a varredura de coluna é três vezes melhor para a leitura de linhas. Nenhuma disposição é a melhor: cada uma é a melhor para uma forma de ler.

Um programa real faz os dois tipos de leitura, então a escolha depende da mistura. Para cada disposição some as faltas da carga: varreduras de coluna vezes faltas de coluna mais leituras de linhas vezes faltas de linhas. Vence a disposição de menor total, e um empate vai para o AoS. O código abaixo testa quatro misturas na mesma tabela.

def compare(n_rows, n_cols, col, rows):    out = {}    for layout in ("aos", "soa"):        out[layout] = {            "column": count_misses(scan_column(layout, col, n_rows, n_cols)),            "rows": count_misses(scan_rows(layout, rows, n_rows, n_cols)),        }    return outdef best_layout(n_column_scans, n_row_reads, n_rows, n_cols, col, rows):    counts = compare(n_rows, n_cols, col, rows)    totals = {layout: n_column_scans * counts[layout]["column"] + n_row_reads * counts[layout]["rows"] for layout in counts}    return "soa" if totals["soa"] < totals["aos"] else "aos"rows = list(range(0, 1000, 7))for scans, reads in ((1, 4), (1, 2), (1, 1), (4, 1)):    print(scans, "column scans per", reads, "row reads:", best_layout(scans, reads, 1000, 5, 3, rows))

1 column scans per 4 row reads: aos
1 column scans per 2 row reads: aos
1 column scans per 1 row reads: soa
4 column scans per 1 row reads: soa

O laboratório segue a aula: as duas disposições, os dois tipos de leitura, a comparação, a escolha para uma carga, a parte útil e o estudo sobre a tabela real do SPY.

• Função · perguntaBaseia-se em
• address(layout, row, col, n_rows, n_cols)Onde vive este valor?Aritmética simples
• scan_column(layout, col, n_rows, n_cols)Quais endereços uma varredura de coluna lê?address
• scan_rows(layout, rows, n_rows, n_cols)Quais endereços uma leitura de linhas toca?address
• compare(n_rows, n_cols, col, rows)Quantas faltas cada leitura custa em cada disposição?scan_columnscan_rows
• best_layout(...)Qual disposição serve a esta carga?compare
• useful_fraction(layout, col, n_rows, n_cols)Quanto do que é carregado é usado?scan_column
• study(bars)Qual disposição serve à tabela do SPY?comparebest_layout

Próximo tópico: a disposição decidiu o passo de uma tabela. Em Ordem de percurso e ladrilhamento de laços a tabela é uma matriz e você escolhe a ordem dos laços e depois os corta em ladrilhos para que um bloco da matriz fique no cache enquanto é usado.