Previsão de desvios

Um processador não espera saber para onde vai um if: ele palpita e começa a trabalhar. Um palpite certo é de graça e um errado joga o trabalho fora, cerca de 15 ciclos perdidos. A frequência de acertos depende dos dados: o mesmo laço sobre os mesmos retornos do SPY custa 8,3 vezes menos ciclos depois de ordenar os retornos.

Um processador funciona como uma linha de montagem: enquanto uma instrução executa, as seguintes já estão sendo lidas e decodificadas. Um if quebra a linha, porque a próxima instrução depende da resposta dele, que ainda não está pronta. Então o processador faz uma previsão de desvio e avança nela. Se o palpite estiver certo, nada se perde. Se estiver errado, o trabalho feito no caminho errado é jogado fora e a linha recomeça, o que custa cerca de 15 ciclos num núcleo moderno, tanto quanto uma visita ao cache L2. Escrevemos o resultado de um desvio como True quando ele é tomado. Num laço de trading um desvio é, por exemplo, if daily_return > 0, e o fluxo de seus resultados é simplesmente um True ou False por dia.

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 dias, quatro tiveram retorno positivo: o desvio é tomado quatro vezes e não tomado duas. O preditor mais simples, sempre tomado, erra exatamente nos dois resultados False. Ele acerta tantas vezes quanto o desvio é tomado e ignora o histórico.

Os processadores reais usam o histórico. O preditor de 1 bit lembra o que o desvio fez da última vez e palpita o mesmo. É bom quando os resultados vêm em sequências, mas paga duas vezes cada resultado isolado: uma quando ele chega e outra quando a sequência retoma. O preditor de 2 bits resolve isso com um contador de 0 a 3 que para nas duas pontas. Ele palpita «tomado» em 2 e 3, anda um passo em direção a cada resultado, e por isso precisa de dois resultados seguidos contra o palpite para mudar de ideia. Começamos o palpite de 1 bit em «não tomado» e o contador em 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. 1O contador anda um passo em direção ao resultado e para em 0 e 3: é isso que o torna saturante.

Nas sequências de quatro, os dois preditores erram três vezes (o primeiro palpite e as duas viradas). Com um único False isolado entre resultados tomados, o de 1 bit erra três vezes e o de 2 bits só uma, porque o contador cai de 3 para 2 e ainda palpita «tomado». Por isso os processadores reais preferem contadores. Lembre do outro lado: quando os resultados não têm padrão, nenhum preditor consegue fazer melhor do que palpitar a resposta mais frequente.

Para transformar erros em tempo, somamos: cada desvio custa um ciclo base e cada erro soma uma penalidade de 15. Agora o experimento que dá nome a esta aula: pegue os primeiros 4000 retornos diários do SPY e execute o desvio return > 0 duas vezes, sobre os retornos em ordem de data e sobre os mesmos retornos ordenados. Ordenar não muda nada nos números, só a ordem deles, mas transforma os resultados de um cara ou coroa em duas sequências longas: todos os False primeiro e todos os True depois.

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

Em ordem de data, 2200 dos 4000 retornos são positivos: o desvio é tomado 55% das vezes e pula de uma resposta para a outra quase sem padrão. Sempre tomado erra 1800 vezes, o de 1 bit 2035 e o de 2 bits 1950. Os preditores com memória são até piores que o palpite simples, porque seguem cada virada. Ordenados, os resultados são 1800 False seguidos de 2200 True, e o de 2 bits erra só 2 vezes. O custo cai de 33 250 para 4030 ciclos, 8,3 vezes menos, com exatamente os mesmos dados e o mesmo laço.

O laboratório segue a aula: os resultados de um desvio, os três preditores, o custo em ciclos, o fluxo ordenado e um estudo dos retornos do SPY em ordem de data e ordenados.

• Função · perguntaBaseia-se em
• taken_sequence(values, threshold)O que o desvio faz com cada valor?Aritmética simples
• always_taken_mispredicts(outcomes)Quantas vezes «sempre tomado» erra?Aritmética simples
• one_bit_mispredicts(outcomes)E um preditor que lembra o último resultado?Aritmética simples
• two_bit_mispredicts(outcomes)E um contador saturante?Aritmética simples
• cycles(n_branches, mispredicts)Quanto custa tudo isso?Aritmética simples
• sorted_stream(values, threshold)E se os valores fossem ordenados antes?taken_sequence
• study(bars)Quanto ordenar economiza no SPY?sorted_streamtwo_bit_mispredictscycles

Próximo tópico: o projeto final reúne toda a habilidade. Você recebe uma tabela de ticks e uma carga que a lê; reorganiza em linhas, colunas ou blocos, conta as faltas de cache de cada disposição com o cache que construiu, as precifica com o modelo de latência do primeiro tópico e prova qual disposição vence.