Proyecto final: reorganizar una tabla de ticks y demostrar la reducción de fallos

Todo lo que enseñó esta habilidad se junta en una tabla de ticks. Ocho columnas, tres trabajos que la leen de formas distintas y tres disposiciones en memoria. Modela la dirección de cada valor, cuenta los fallos de cada trabajo con la caché que construyó, los valora con el modelo de latencia y demuestra qué disposición gana. Ninguna gana todos los trabajos; la híbrida gana la mezcla, con 1,5 veces menos fallos que el arreglo de estructuras.

Una tabla de ticks tiene 8 columnas de 8 bytes: una marca de tiempo, los precios y tamaños de bid y ask, el precio de la operación, su tamaño y algunas banderas. Una fila mide exactamente 64 bytes, el tamaño de una línea de caché. Tres trabajos leen esta tabla. Un barrido lee la columna de precios de cada fila, para una media móvil. Un trabajo de cotización lee el bid, el ask y el tamaño del bid de cada fila, para construir un libro. Una búsqueda lee el tick completo de 1000 filas elegidas por la tabla, como hace un depurador o una repetición. La memoria del primer tema tiene una jerarquía, la del segundo una línea de 64 bytes y la del quinto dos disposiciones de una tabla: el arreglo de estructuras (los valores de una fila juntos) y la estructura de arreglos (cada columna por separado). Ahora hay una tercera vía, la híbrida, que mantiene juntas las columnas calientes de cotización y juntas las columnas frías.

Las tres disposiciones son una sola idea. Una disposición es una lista de grupos de columnas. Los valores de un grupo se guardan fila tras fila y los grupos se siguen. Un grupo con todas las columnas es el arreglo de estructuras; un grupo por columna es la estructura de arreglos; dos grupos de cuatro columnas son nuestro híbrido. Así una función da la dirección de cualquier valor en cualquier disposición: saltar los grupos anteriores al que contiene la columna y avanzar row * len(group) + position valores dentro de él.

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. 1Un grupo ocupa n_rows * len(group) * elem_bytes bytes: el siguiente grupo empieza justo después.

Compruebe los tres resultados a mano. Con un grupo de tres columnas, la fila 2 columna 1 es el valor número 2 × 3 + 1 = 7, en el byte 56. Con un grupo por columna, la columna 1 empieza tras los 10 valores de la columna 0, en el byte 80, y la fila 2 está 16 bytes más allá: 96. En el híbrido [[1, 2], [0]] el grupo de la columna 0 va segundo, tras 10 filas de 2 valores (160 bytes), y la fila 3 está 24 bytes más allá: 184.

Un trabajo es la lista de columnas que lee por cada fila que visita. Su traza es, para cada fila en orden, las direcciones de esas columnas; la caché convierte la traza en fallos; y el modelo de latencia del primer tema convierte los fallos en tiempo, con 1 ns por acierto y 80 ns por fallo. La comparación es entonces un bucle sobre las disposiciones y la prueba es el número más pequeño. Ejecute los tres trabajos de la lección con 4000 ticks y verá que la mejor disposición depende del trabajo.

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

El barrido quiere una sola columna: la estructura de arreglos empaqueta ocho precios por línea (500 fallos) y el arreglo de estructuras desperdicia siete octavos de cada línea que carga (4000 fallos). La búsqueda puntual quiere los ocho valores de una fila: el arreglo de estructuras toma una línea (1000 fallos) y la estructura de arreglos ocho (8000). La cotización lee tres de las cuatro columnas del grupo caliente, así que el híbrido es bueno pero no el mejor. Qué disposición elegir depende de con qué frecuencia se ejecuta cada trabajo, y eso es lo que mide la mezcla.

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

Sumados, el arreglo de estructuras falla 9000 veces, la estructura de arreglos 10 000 y el híbrido 6000. El híbrido no gana ningún trabajo por completo ni pierde ninguno gravemente: los barridos y las cotizaciones cuestan el doble de lo que paga la estructura de arreglos, las búsquedas el doble de lo que paga el arreglo de estructuras, y la mezcla favorece a la disposición que nunca es terrible. En el modelo de latencia son 498 µs contra 735 µs del arreglo de estructuras: 1,5 veces menos fallos y un tercio menos de tiempo. Esa es la prueba que pide el proyecto final, y solo vale para esta mezcla de trabajos.

El laboratorio sigue la lección: la dirección de un valor en cualquier disposición, la traza de un trabajo, los fallos de un trabajo en una disposición y en todas, la mejor disposición, el tiempo de un trabajo y el estudio de la tabla de ticks con la prueba de la mezcla.

• Función · preguntaSe apoya en
• address(groups, row, col, n_rows)¿Dónde está este valor en memoria?Aritmética simple
• workload_trace(groups, n_rows, reads, rows)¿Qué direcciones toca el trabajo?address
• layout_misses(groups, n_rows, reads, rows)¿Cuántos fallos en esta disposición?workload_tracecount_misses
• compare_layouts(layouts, n_rows, reads, rows)¿Y en cada disposición?layout_misses
• best_layout(misses)¿Cuál gana?Aritmética simple
• time_ns(accesses, misses)¿Cuánto cuesta en tiempo?Aritmética simple
• study(bars)¿Qué disposición gana la mezcla de trabajos?compare_layoutsbest_layouttime_ns

Siguiente habilidad: el lado de memoria del rendimiento está hecho. Las siguientes habilidades de la vía de optimización pasan al procesador: ejecutar la misma operación sobre muchos valores a la vez en registros vectoriales y compartir datos entre núcleos sin cerrojos.