Predicción de saltos

Un procesador no espera a saber hacia dónde va un if: adivina y empieza a trabajar. Una buena apuesta es gratis y una mala tira el trabajo, unos 15 ciclos perdidos. Con qué frecuencia acierta depende de los datos: el mismo bucle sobre los mismos rendimientos de SPY cuesta 8,3 veces menos ciclos una vez ordenados los rendimientos.

Un procesador funciona como una cadena de montaje: mientras se ejecuta una instrucción, las siguientes ya se están leyendo y decodificando. Un if rompe la cadena, porque la siguiente instrucción depende de su respuesta, que aún no está lista. Así que el procesador hace una predicción de salto y avanza con ella. Si acierta no se pierde nada. Si falla, el trabajo hecho por el camino equivocado se tira y la cadena reinicia, lo que cuesta unos 15 ciclos en un núcleo moderno, tanto como una visita a la caché L2. Escribimos el resultado de un salto como True cuando se toma. En un bucle de trading un salto es, por ejemplo, if daily_return > 0, y el flujo de sus resultados es simplemente un True o False por día.

def taken_sequence(values, threshold):    return [bool(value > threshold) for value in values]def always_taken_mispredicts(outcomes):    return sum(1 for outcome in outcomes if not outcome)returns = [0.004, -0.012, 0.007, 0.001, -0.003, 0.009]outcomes = taken_sequence(returns, 0)print(outcomes)print(always_taken_mispredicts(outcomes), "misses out of", len(outcomes))

[True, False, True, True, False, True]
2 misses out of 6

De seis días, cuatro tuvieron un rendimiento positivo: el salto se toma cuatro veces y no se toma dos. El predictor más simple, siempre tomado, falla exactamente en los dos resultados False. Acierta tantas veces como se toma el salto e ignora el historial.

Los procesadores reales usan el historial. El predictor de 1 bit recuerda lo que hizo el salto la última vez y adivina lo mismo. Es bueno cuando los resultados vienen en rachas, pero paga dos veces cada resultado suelto: una cuando llega y otra cuando la racha se reanuda. El predictor de 2 bits lo arregla con un contador de 0 a 3 que se detiene en ambos extremos. Adivina «tomado» en 2 y 3, avanza un paso hacia cada resultado y por eso necesita dos resultados seguidos en contra para cambiar de opinión. Empezamos la apuesta de 1 bit en «no tomado» y el contador en 1.

def one_bit_mispredicts(outcomes):    guess = False    wrong = 0    for outcome in outcomes:        if guess != outcome:            wrong += 1        guess = outcome    return wrongdef two_bit_mispredicts(outcomes):    counter = 1    wrong = 0    for outcome in outcomes:        if (counter >= 2) != outcome:            wrong += 1        counter = min(3, counter + 1) if outcome else max(0, counter - 1)1    return wrongruns = [True] * 4 + [False] * 4 + [True] * 4stray = [True] * 6 + [False] + [True] * 6for name, stream in (("runs", runs), ("one stray", stray)):    print(name, "| 1-bit", one_bit_mispredicts(stream), "| 2-bit", two_bit_mispredicts(stream))

runs | 1-bit 3 | 2-bit 5
one stray | 1-bit 3 | 2-bit 2

1. 1El contador avanza un paso hacia el resultado y se detiene en 0 y 3: eso lo hace saturante.

En las rachas de cuatro, ambos predictores fallan tres veces (la primera apuesta y los dos giros). Con un solo False suelto entre resultados tomados, el de 1 bit falla tres veces y el de 2 bits solo una, porque el contador baja de 3 a 2 y aún adivina «tomado». Por eso los procesadores reales prefieren contadores. Tenga presente el otro lado: cuando los resultados no tienen patrón, ningún predictor puede hacerlo mejor que adivinar la respuesta más frecuente.

Para convertir los fallos en tiempo los sumamos: cada salto cuesta un ciclo base y cada fallo añade una penalización de 15. Ahora el experimento que da nombre a esta lección: tomemos los primeros 4000 rendimientos diarios de SPY y ejecutemos el salto return > 0 dos veces, sobre los rendimientos en orden de fechas y sobre los mismos rendimientos ordenados. Ordenar no cambia nada de los números, solo su orden, pero convierte los resultados de un cara o cruz en dos rachas largas: todos los False primero y todos los True después.

def cycles(n_branches, mispredicts, penalty=PENALTY, base=BASE_CYCLES):    return base * n_branches + penalty * mispredictsdef sorted_stream(values, threshold):    return taken_sequence(sorted(values), threshold)returns = [float(r) for r in load_bars()["close"].pct_change().dropna()][:4000]for name, stream in (("unsorted", taken_sequence(returns, 0)), ("sorted", sorted_stream(returns, 0))):    wrong = two_bit_mispredicts(stream)    print(name, "| always", always_taken_mispredicts(stream), "| 1-bit", one_bit_mispredicts(stream), "| 2-bit", wrong, "|", cycles(len(stream), wrong), "cycles")

unsorted | always 1800 | 1-bit 2035 | 2-bit 1950 | 33250 cycles
sorted | always 1800 | 1-bit 1 | 2-bit 2 | 4030 cycles

En orden de fechas, 2200 de los 4000 rendimientos son positivos: el salto se toma el 55 % de las veces y pasa de una respuesta a otra casi sin patrón. Siempre tomado falla 1800 veces, el de 1 bit 2035 y el de 2 bits 1950. Los predictores con memoria son incluso peores que la apuesta simple, porque siguen cada cambio. Ordenados, los resultados son 1800 False seguidos de 2200 True, y el de 2 bits falla solo 2 veces. El coste baja de 33 250 a 4030 ciclos, 8,3 veces menos, con exactamente los mismos datos y el mismo bucle.

El laboratorio sigue la lección: los resultados de un salto, los tres predictores, el coste en ciclos, el flujo ordenado y un estudio de los rendimientos de SPY en orden de fechas y ordenados.

• Función · preguntaSe apoya en
• taken_sequence(values, threshold)¿Qué hace el salto con cada valor?Aritmética simple
• always_taken_mispredicts(outcomes)¿Cuántas veces falla «siempre tomado»?Aritmética simple
• one_bit_mispredicts(outcomes)¿Y un predictor que recuerda el último resultado?Aritmética simple
• two_bit_mispredicts(outcomes)¿Y un contador saturante?Aritmética simple
• cycles(n_branches, mispredicts)¿Cuánto cuesta todo?Aritmética simple
• sorted_stream(values, threshold)¿Y si los valores se ordenaran antes?taken_sequence
• study(bars)¿Cuánto ahorra ordenar en SPY?sorted_streamtwo_bit_mispredictscycles

Siguiente tema: el proyecto final reúne toda la habilidad. Se le da una tabla de ticks y una carga que la lee; la reorganiza en filas, columnas o bloques, cuenta los fallos de caché de cada disposición con la caché que construyó, los valora con el modelo de latencia del primer tema y demuestra qué disposición gana.