Arreglo de estructuras frente a estructura de arreglos

Una tabla de ticks puede estar en memoria de dos maneras, y la correcta depende de cómo la lea. Recorrer una columna de una tabla guardada fila a fila carga cinco veces la memoria que usa; leer filas enteras de columnas separadas desperdicia lo mismo al revés. Esta lección cuenta los fallos de ambas disposiciones y deja que los recuentos elijan.

La memoria es una larga fila de bytes, así que una tabla bidimensional hay que aplanarla. Hay dos maneras naturales. En un arreglo de estructuras los cinco valores de un día (apertura, máximo, mínimo, cierre, volumen) se guardan juntos, luego los cinco del día siguiente, y así. En una estructura de arreglos primero van todas las aperturas, luego todos los máximos, y así. Los valores y el programa son los mismos, pero las direcciones cambian.

La dirección de un valor se deduce de su fila y su columna. En AoS el número del valor es fila por el número de columnas más la columna. En SoA es columna por el número de filas más la fila. Se multiplica por 8 bytes para un float64. El código siguiente muestra las direcciones de los cierres de los cuatro primeros días en una tabla de 100 días y 5 columnas.

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. 1En AoS la fila siguiente está n_cols valores más allá, así que dos cierres consecutivos están separados 5 valores (40 bytes).

En AoS los cierres de días consecutivos están separados 40 bytes. En SoA están a 8 bytes, uno justo tras otro, que es exactamente la lectura en orden del primer tema de esta habilidad.

Promediar los cierres lee una columna de la tabla. Convertimos esa lectura en una lista de direcciones, la pasamos por la caché construida en los temas anteriores y contamos los fallos para 1000 días. El último número que mostramos es la 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

El recorrido SoA falla 125 veces para 1000 valores, un fallo por cada ocho valores y nada desperdiciado. El recorrido AoS falla 625 veces, cinco veces más, y solo el 20 % de los bytes cargados son cierres. El otro 80 % son aperturas, máximos, mínimos y volúmenes que el promedio nunca mira, y expulsan líneas útiles de la caché.

Muchos programas de ticks hacen otra pregunta: para este tick, deme el precio, el tamaño y el lado juntos. Eso lee todos los valores de una fila. En AoS la fila entera es un bloque de 40 bytes, que está en una o dos líneas. En SoA los cinco valores están en cinco arreglos distintos, así que cada fila abre cinco líneas. El código lee una fila de cada siete y cuenta los fallos.

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

Ahora AoS gana por un factor de tres: 214 fallos contra 625. La disposición que era cinco veces peor para el recorrido de columna es tres veces mejor para la lectura de filas. Ninguna disposición es la mejor: cada una lo es para una forma de leer.

Un programa real hace los dos tipos de lectura, así que la elección depende de la mezcla. Para cada disposición sume los fallos de la carga: recorridos de columna por fallos de columna más lecturas de filas por fallos de filas. Gana la disposición con el total menor, y un empate va a AoS. El código siguiente prueba cuatro mezclas en la misma tabla.

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

El laboratorio sigue la lección: las dos disposiciones, los dos tipos de lectura, la comparación, la elección para una carga, la parte útil y el estudio sobre la tabla real de SPY.

• Función · preguntaSe apoya en
• address(layout, row, col, n_rows, n_cols)¿Dónde vive este valor?Aritmética simple
• scan_column(layout, col, n_rows, n_cols)¿Qué direcciones lee un recorrido de columna?address
• scan_rows(layout, rows, n_rows, n_cols)¿Qué direcciones toca una lectura de filas?address
• compare(n_rows, n_cols, col, rows)¿Cuántos fallos cuesta cada lectura en cada disposición?scan_columnscan_rows
• best_layout(...)¿Qué disposición conviene a esta carga?compare
• useful_fraction(layout, col, n_rows, n_cols)¿Cuánto de lo cargado se usa?scan_column
• study(bars)¿Qué disposición conviene a la tabla de SPY?comparebest_layout

Siguiente tema: la disposición decidió el paso de una tabla. En Orden de recorrido y mosaico de bucles la tabla es una matriz y usted elige el orden de los bucles y luego los corta en teselas para que un bloque de la matriz siga en la caché mientras se usa.